面试题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;
}

补充：软件开发 , C++ ,

上一个：面试题17：二叉树的镜像
下一个：面试题15：合并两个排序的链表