判断一颗二叉树是不是另一棵二叉树的子结构

1、题目描述：

如何判断一个二叉树是否是另一个的子结构？ 比如：

6

有个子结构是 9 / 2 3

有关二叉树的算法问题，一般都可以通过递归来解决。那么写成一个正确的递归程序，首先一定要分析正确递归结束的条件。

拿这道题来讲，什么时候递归结束。

<1>第二个二叉树root2为空时，说明root2是第一棵二叉树的root1的子结构，返回true。

<2>当root1为空时，此时root2还没为空，说明root2不是root1的子结构，返回false。

<3>递归下面有两种思路：

方法一：现在root1中找结点值与root2的值相等的结点，如果找到就判断root2是不是这个结点开头的子结构。所以，首先IsSubTree()判断。

方法二：就是直接判断，相同就递归判断root2左右子树是不是也是相应的子结构。如果值不相同，就分别递归到root1的左右子树寻找。尤其要注意最后两句递归的逻辑判断。

3、代码：

方法一：

//判断root2是不是root1开头的子结构

boolIsSubTree(BiTreeNode *root1,BiTreeNode *root2)

{

//先判断root2

if(root2==NULL)

return true;

if(root1==NULL)

return false;

if(root1->data!=root2->data)

return false;

returnIsSubTree(root1->LC,root2->LC) &&IsSubTree(root1->RC,root2->RC);

}

//递归查找以root1为节点的树中，是否有和root2相同的值，如果有，则调用IsSubTree(root1, root2);

boolCheckIfSubTree(BiTreeNode *root1,BiTreeNode *root2)

{

if(root1==NULL)

return false;

bool result=false;

if(root1->data==root2->data)

result=IsSubTree(root1,root2);

if(result==false)

result=CheckIfSubTree(root1->LC,root2);

if(result==false)

result=CheckIfSubTree(root1->RC,root2);

return result;

}

方法二：

//一次递归完成

boolCheckIfSubTree2(BiTreeNode *root1,BiTreeNode *root2)

{

if(root2==NULL)

return true;

if(root1==NULL)

return false;

if(root1->data==root2->data)

returnCheckIfSubTree2(root1->LC,root2->LC) &&CheckIfSubTree2(root1->RC,root2->RC);

else

returnCheckIfSubTree2(root1->LC,root2) || CheckIfSubTree2(root1->RC,root2);

}

4、附先序生成二叉树的代码

struct BiTreeNode { struct BiTreeNode* LC; struct BiTreeNode* RC; int data; }; void CreateBiTree(BiTreeNode* &root) { int ch; cin>>ch; if(ch==0) { root=NULL; } else { root=(BiTreeNode*)malloc(sizeof(BiTreeNode)); if(root==NULL) exit(1); root->data=ch; //cout<<"--"<<root->data<<endl; CreateBiTree(root->LC); CreateBiTree(root->RC); } }

5、小结

一定要好好的体会递归，尤其是递归结束的情况。这是解大多数递归问题的关键。