面試題16：樹的子結構

#include "stdafx.h"   
#include <iostream>   
using namespace std;  
  
struct BinaryTreeNode  
{  
    int m_nValue;  
    BinaryTreeNode *m_pLeft;  
    BinaryTreeNode *m_pRight;  
};  
  
bool DoesTree1haveTree2(BinaryTreeNode *pRoot1, BinaryTreeNode *pRoot2)  
{  
    if (pRoot2 == NULL)  
    {  
        return true;  
    }  
  
    if (pRoot1 == NULL)  
    {  
        return false;  
    }  
  
    if (pRoot1->m_nValue != pRoot2->m_nValue)  
    {  
        return false;  
    }  
  
    return DoesTree1haveTree2(pRoot1->m_pLeft, pRoot2->m_pLeft)  
        && DoesTree1haveTree2(pRoot1->m_pRight, pRoot2->m_pRight);  
}  
  
//判斷B是否為A的子結構   
bool IsSubStruct(BinaryTreeNode *pRootOfTreeA, BinaryTreeNode *pRootOfTreeB)  
{  
   bool result = false;  
   if (pRootOfTreeA != NULL && pRootOfTreeB != NULL)  
   {  
       if (pRootOfTreeA->m_nValue == pRootOfTreeB->m_nValue)  
       {  
           result = DoesTree1haveTree2(pRootOfTreeA, pRootOfTreeB);  
       }  
  
       if (!result)  
       {  
           result = IsSubStruct(pRootOfTreeA->m_pLeft, pRootOfTreeB);  
       }  
  
       if (!result)  
       {  
           result = IsSubStruct(pRootOfTreeA->m_pRight, pRootOfTreeB);  
       }  
   }   
  
   return result;  
}  
  
//以先序的方式構建二叉樹，輸入-1表示結點為空   
void CreateBinaryTree(BinaryTreeNode *&pRoot)  
{  
    int nNodeValue = 0;  
    cin >> nNodeValue;      
    if (-1 == nNodeValue)  
    {  
       return;   
    }  
    else  
    {  
        pRoot = new BinaryTreeNode();  
        pRoot->m_nValue = nNodeValue;  
        CreateBinaryTree(pRoot->m_pLeft);  
        CreateBinaryTree(pRoot->m_pRight);  
    }  
}  
  
void PrintInOrder(BinaryTreeNode *&pRoot)  
{  
    if (pRoot != NULL)  
    {  
        PrintInOrder(pRoot->m_pLeft);  
        cout << pRoot->m_nValue << " ";  
        PrintInOrder(pRoot->m_pRight);  
    }  
}  
  
int _tmain(int argc, _TCHAR* argv[])  
{  
    BinaryTreeNode *pRoot1 = NULL;  
    CreateBinaryTree(pRoot1);  
    PrintInOrder(pRoot1);  
    cout << endl;  
  
    BinaryTreeNode *pRoot2 = NULL;  
    CreateBinaryTree(pRoot2);  
    PrintInOrder(pRoot2);  
    cout << endl;  
  
    cout << "Root2是否為Root1的子結構，是返回1，否則返回0.結果是： " << IsSubStruct(pRoot1, pRoot2) << endl;  
  
    system("pause");  
    return 0;  
}  
#include "stdafx.h"
#include <iostream>
using namespace std;

struct BinaryTreeNode
{
	int m_nValue;
	BinaryTreeNode *m_pLeft;
	BinaryTreeNode *m_pRight;
};

bool DoesTree1haveTree2(BinaryTreeNode *pRoot1, BinaryTreeNode *pRoot2)
{
	if (pRoot2 == NULL)
	{
		return true;
	}

	if (pRoot1 == NULL)
	{
		return false;
	}

	if (pRoot1->m_nValue != pRoot2->m_nValue)
	{
		return false;
	}

	return DoesTree1haveTree2(pRoot1->m_pLeft, pRoot2->m_pLeft)
		&& DoesTree1haveTree2(pRoot1->m_pRight, pRoot2->m_pRight);
}

//判斷B是否為A的子結構
bool IsSubStruct(BinaryTreeNode *pRootOfTreeA, BinaryTreeNode *pRootOfTreeB)
{
   bool result = false;
   if (pRootOfTreeA != NULL && pRootOfTreeB != NULL)
   {
	   if (pRootOfTreeA->m_nValue == pRootOfTreeB->m_nValue)
	   {
		   result = DoesTree1haveTree2(pRootOfTreeA, pRootOfTreeB);
	   }

	   if (!result)
	   {
		   result = IsSubStruct(pRootOfTreeA->m_pLeft, pRootOfTreeB);
	   }

	   if (!result)
	   {
		   result = IsSubStruct(pRootOfTreeA->m_pRight, pRootOfTreeB);
	   }
   } 

   return result;
}

//以先序的方式構建二叉樹，輸入-1表示結點為空
void CreateBinaryTree(BinaryTreeNode *&pRoot)
{
	int nNodeValue = 0;
	cin >> nNodeValue;	
	if (-1 == nNodeValue)
	{
       return; 
	}
	else
	{
		pRoot = new BinaryTreeNode();
		pRoot->m_nValue = nNodeValue;
		CreateBinaryTree(pRoot->m_pLeft);
		CreateBinaryTree(pRoot->m_pRight);
	}
}

void PrintInOrder(BinaryTreeNode *&pRoot)
{
	if (pRoot != NULL)
	{
		PrintInOrder(pRoot->m_pLeft);
		cout << pRoot->m_nValue << " ";
		PrintInOrder(pRoot->m_pRight);
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	BinaryTreeNode *pRoot1 = NULL;
	CreateBinaryTree(pRoot1);
	PrintInOrder(pRoot1);
	cout << endl;

	BinaryTreeNode *pRoot2 = NULL;
	CreateBinaryTree(pRoot2);
	PrintInOrder(pRoot2);
	cout << endl;

	cout << "Root2是否為Root1的子結構，是返回1，否則返回0.結果是： " << IsSubStruct(pRoot1, pRoot2) << endl;

	system("pause");
	return 0;
}