题目描述：
题目：二叉树的结点定义如下：
struct TreeNode
{
int m_nValue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
输入两棵二叉树A和B，判断树B是不是A的子结构。
例如，下图中的两棵树A和B，由于A中有一部分子树的结构和B是一样的，因此B就是A的子结构。
1 8
/ \ / \
8 7 9 2
/ \
9 2
/ \
4 7
要查找树A中是否存在和树B结构一样的子树，我们可以分为两步：第一步在树A中找到和B的根结点的值一样的结点N，第二步再判断树A中以N为根结点的子树是不是包括和树B一样的结构。
第一步在树A中查找与根结点的值一样的结点。这实际上就是树的遍历。
第二步判断以树A中以N为根结点的子树是不是和树B具有相同的结构。同样，我们也可以用递归的思路来考虑：如果结点N的值和树B的根结点不相同，则以N为根结点的子树和树B肯定不具有相同的结点；如果他们的值相同，则递归地判断他们的各自的左右结点的值是不是相同。递归的终止条件是我们到达了树A或者树B的叶结点。
#include<iostream>
#include<stack>
using namespace std;
struct BinaryTreeNode
{
int data;
BinaryTreeNode* left;
BinaryTreeNode* right;
BinaryTreeNode(int x)
:data(x)
, left(NULL)
, right(NULL)
{}
};
class BinaryTree
{
protected:
BinaryTreeNode* _root;
BinaryTreeNode* _CreateBinaryTree(int* arr, int& index, int size)
{
BinaryTreeNode* root = NULL;
if (index<size&&arr[index] != '#')
{
root = new BinaryTreeNode(arr[index]);
root->left = _CreateBinaryTree(arr, ++index, size);
root->right = _CreateBinaryTree(arr, ++index, size);
}
return root;
}
bool CommonRoot(BinaryTreeNode* father, BinaryTreeNode* child)
{
bool ret = false;
if (father->data == child->data)
{
ret=HaveSub(father, child);
}
if (!ret&&father->left != NULL)
ret=CommonRoot(father->left, child);
if (!ret&&father->right != NULL)
ret=CommonRoot(father->right, child);
return ret;
}
bool HaveSub(BinaryTreeNode* father, BinaryTreeNode* child)
{
if (child == NULL)//子树为空
return true;
if (father == NULL)//子树为空，父树不为空
return false;
if (father->data != child->data)
return false;
//如果他们的值相同，则递归地判断他们的各自的左右结点的值是不是相同。
//递归的终止条件是我们到达了父树或者子树的叶结点
return HaveSub(father->left, child->left) && HaveSub(father->right, child->right);
}
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree(int *arr, int size)
{
int index = 0;
_root = _CreateBinaryTree(arr, index, size);
}
void PreOrder_Non()
{
if (_root == NULL)
return;
BinaryTreeNode* cur = _root;
stack<BinaryTreeNode*> s;
s.push(_root);
while (!s.empty())
{
cur = s.top();
printf("%d ", cur->data);
s.pop();
if (cur->right)
s.push(cur->right);
if (cur->left)
s.push(cur->left);
}
cout << endl;
}
void InOrder_Non()
{
if (_root == NULL)
return;
stack<BinaryTreeNode*> s;
BinaryTreeNode* cur = _root;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->left;
}
if (!s.empty())
{
cout << s.top()->data << " ";
cur = s.top()->right;
s.pop();
}
}
cout << endl;
}
void PostOrder_Non()
{
if (_root == NULL)
return;
stack<BinaryTreeNode*> s;
BinaryTreeNode* cur = _root;
BinaryTreeNode* prev = NULL;
BinaryTreeNode* top = NULL;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->left;
}
top = s.top();
if (top->right == NULL || top->right == prev)
{
cout << top->data << " ";
s.pop();
prev = top;
}
else
{
cur = top->right;
}
}
cout << endl;
}
bool IsSub(BinaryTree& bt)
{
if ((_root == NULL&&bt._root != NULL) || (_root != NULL&&bt._root == NULL))
return false;
if (_root == NULL&&bt._root == NULL)
return true;
return CommonRoot(_root, bt._root);
}
};
void Test1()
{
/*int arr1[] = { 1, 8, 9, '#', '#', 2, 4, '#', '#', 7, '#', '#', 7 };
int arr2[] = { 8, 9, '#', '#', 2 };
BinaryTree b1(arr1, sizeof(arr1) / sizeof(arr1[0]));
BinaryTree b2(arr2, sizeof(arr2) / sizeof(arr2[0]));
b1.InOrder_Non();
b2.InOrder_Non();
//1
cout << b1.IsSub(b2) << endl;*/
int arr1[] = { 1, 8, 9, '#', '#', 8, 4, '#', '#', 7, '#', '#', 7 };
int arr2[] = { 8, 4, '#', '#', 7 };
BinaryTree b1(arr1, sizeof(arr1) / sizeof(arr1[0]));
BinaryTree b2(arr2, sizeof(arr2) / sizeof(arr2[0]));
b1.InOrder_Non();
b2.InOrder_Non();
//0
cout << b1.IsSub(b2) << endl;//当子树不相等时，可继续向下重新寻找相同的根节点
int arr3[] = { 2, 3, '#', '#', 6 };
BinaryTree b3(arr3, sizeof(arr3) / sizeof(arr3[0]));
//0
cout << b1.IsSub(b3) << endl;
}
#include"Tree.h"
int main()
{
Test1();
system("pause");
return 0;
}注：我们一定要注意边界条件的检查，即检查空指针。当父树或子树为空的时候，定义相应的输出。如果没有检查并做相应的处理，程序非常容易崩溃。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
