题目描述：

题目：二叉树的结点定义如下：

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>usingnamespacestd;structBinaryTreeNode{intdata;BinaryTreeNode*left;BinaryTreeNode*right;BinaryTreeNode(intx):data(x),left(NULL),right(NULL){}};classBinaryTree{protected:BinaryTreeNode*_root;BinaryTreeNode*_CreateBinaryTree(int*arr,int&index,intsize){BinaryTreeNode*root=NULL;if(index<size&&arr[index]!='#'){root=newBinaryTreeNode(arr[index]);root->left=_CreateBinaryTree(arr,++index,size);root->right=_CreateBinaryTree(arr,++index,size);}returnroot;}boolCommonRoot(BinaryTreeNode*father,BinaryTreeNode*child){boolret=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);returnret;}boolHaveSub(BinaryTreeNode*father,BinaryTreeNode*child){if(child==NULL)//子树为空returntrue;if(father==NULL)//子树为空，父树不为空returnfalse;if(father->data!=child->data)returnfalse;//如果他们的值相同，则递归地判断他们的各自的左右结点的值是不是相同。//递归的终止条件是我们到达了父树或者子树的叶结点returnHaveSub(father->left,child->left)&&HaveSub(father->right,child->right);}public:BinaryTree():_root(NULL){}BinaryTree(int*arr,intsize){intindex=0;_root=_CreateBinaryTree(arr,index,size);}voidPreOrder_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;}voidInOrder_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;}voidPostOrder_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;}boolIsSub(BinaryTree&bt){if((_root==NULL&&bt._root!=NULL)||(_root!=NULL&&bt._root==NULL))returnfalse;if(_root==NULL&&bt._root==NULL)returntrue;returnCommonRoot(_root,bt._root);}};voidTest1(){/*intarr1[]={1,8,9,'#','#',2,4,'#','#',7,'#','#',7};intarr2[]={8,9,'#','#',2};BinaryTreeb1(arr1,sizeof(arr1)/sizeof(arr1[0]));BinaryTreeb2(arr2,sizeof(arr2)/sizeof(arr2[0]));b1.InOrder_Non();b2.InOrder_Non();//1cout<<b1.IsSub(b2)<<endl;*/intarr1[]={1,8,9,'#','#',8,4,'#','#',7,'#','#',7};intarr2[]={8,4,'#','#',7};BinaryTreeb1(arr1,sizeof(arr1)/sizeof(arr1[0]));BinaryTreeb2(arr2,sizeof(arr2)/sizeof(arr2[0]));b1.InOrder_Non();b2.InOrder_Non();//0cout<<b1.IsSub(b2)<<endl;//当子树不相等时，可继续向下重新寻找相同的根节点intarr3[]={2,3,'#','#',6};BinaryTreeb3(arr3,sizeof(arr3)/sizeof(arr3[0]));//0cout<<b1.IsSub(b3)<<endl;}#include"Tree.h"intmain(){Test1();system("pause");return0;}

注：我们一定要注意边界条件的检查，即检查空指针。当父树或子树为空的时候，定义相应的输出。如果没有检查并做相应的处理，程序非常容易崩溃。