问题描述

如何判断一个树是不是另外一个二叉树的子树呢？

请教大神们一个数据结构的问题，才学，琢磨很久没想出来

解决方案

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

boolIsSubTree(BiTreeNode *root1BiTreeNode *root2)

{

   //先判断root2   if(root2==NULL)          return true;   if(root1==NULL)          return false;       if(root1->data!=root2->data)          return false;   returnIsSubTree(root1->LCroot2->LC) &&IsSubTree(root1->RCroot2->RC);

}

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

boolCheckIfSubTree(BiTreeNode *root1BiTreeNode *root2)

{

   if(root1==NULL)          return false;   bool result=false;   if(root1->data==root2->data)          result=IsSubTree(root1root2);   if(result==false)          result=CheckIfSubTree(root1->LCroot2);   if(result==false)          result=CheckIfSubTree(root1->RCroot2);   return result;

}

解决方案二：
首先在二叉树p中遍历寻找c的根节点，如果找到了，从这个节点开始遍历二叉树p，并且判定如果所有p对应的子节点都在c中出现，并且c不存在的p也不存在。就符合条件。

解决方案三：
树的子结构——判断B树是不是A树的一颗子树
判断一个树是否为另一棵树的子树
判断一个二叉树是否是另一个的子树