判断一棵树为另一颗树的子树

题目：

    有两颗二叉树，判断其中一颗A是否是另一颗B的子树。

解决思想：

    按先序遍历树B的每个结点，判断结点是否和树A的根结点相同。若相同，再判断以该结点为根结点的树是否有和树A相同的子树。

代码：

#include <iostream>
using namespace std;

struct BTree
{
int m_val;
BTree *m_lchild;
BTree *m_rchild;
};

bool DoesTree1HaveTree2(BTree *root1, BTree *root2);


//相当于以前序遍历判断每个结点是否和子树的根结点相同
bool HasSubTree(BTree *root1, BTree *root2)
{
if (root1 == NULL || root2 == NULL)
return false;

bool result = false;
if (root1->m_val == root2->m_val)    //找到一个结点与目标子树根结点相同
result = DoesTree1HaveTree2(root1, root2);    //判断以该结点为根结点是否有棵子树与目标子树相同
if (!result)    //上个结点与子树根结点不同
result = HasSubTree(root1->m_lchild, root2);    //判断左子结点
if (!result)    //左子结点也与子树根结点不同
result = HasSubTree(root1->m_rchild, root2);    //判断右子结点

return result;
}

bool DoesTree1HaveTree2(BTree *root1, BTree *root2)
{
if (root2 == NULL)    //能走到这步，说明该结点前面的结点都相同
return true;
if (root1 == NULL)    //即root2!=NULL，root1=NULL
return false;
if (root1->m_val != root2->m_val)
return false;

return DoesTree1HaveTree2(root1->m_lchild, root2->m_lchild) && DoesTree1HaveTree2(root1->m_rchild, root2->m_rchild);
}

/* 构造一颗二叉树 */
void CreateBTree(BTree **T)
{
int val;
cin >> val;
if (val == 0)    //输入0表示结尾
*T = NULL;
else
{
*T = new BTree;
if (*T == NULL)
return ;
(*T)->m_val = val;
CreateBTree(&(*T)->m_lchild);
CreateBTree(&(*T)->m_rchild);
}
}

int main()
{
printf("输入树1的结点：\n");
BTree *T1;
CreateBTree(&T1);
printf("输入树2的结点：\n");
BTree *T2;
CreateBTree(&T2);
cout << "树2是1的子树?(1：是；0：否)：" << HasSubTree(T1, T2) << endl;
return 0;
}

测试：

1.T1：123000246000500 T2:2400500 结果：1

2.T1：123000246000500 T2:2300500 结果：0