面试题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++ ,