用C语言判断一个二叉树是否为另一个的子结构
1、问题描述：
如何判断一个二叉树是否是另一个的子结构？
比如：
2
/ \
9 8
/\ /
2 3 5
/
6
有个子结构是
9
/\
2 3
2、分析问题：
有关二叉树的算法问题，一般都可以通过递归来解决。那么写成一个正确的递归程序，首先一定要分析正确递归结束的条件。
拿这道题来讲，什么时候递归结束。
<1>第二个二叉树root2为空时，说明root2是第一棵二叉树的root1的子结构，返回true。
<2>当root1为空时，此时root2还没为空，说明root2不是root1的子结构，返回false。
<3>递归下面有两种思路：
方法一：现在root1中找结点值与root2的值相等的结点，如果找到就判断root2是不是这个结点开头的子结构。所以，首先IsSubTree()判断。
方法二：就是直接判断，相同就递归判断root2左右子树是不是也是相应的子结构。如果值不相同，就分别递归到root1的左右子树寻找。尤其要注意最后两句递归的逻辑判断。
3、习题实例
题目描述：
输入两颗二叉树A，B，判断B是不是A的子结构。
输入：
输入可能包含多个测试样例，输入以EOF结束。
对于每个测试案例，输入的第一行一个整数n,m(1<=n<=1000,1<=m<=1000)：n代表将要输入的二叉树A的节点个数（节点从1开始计数），m代表将要输入的二叉树B的节点个数（节点从1开始计数）。接下来一行有n个数，每个数代表A树中第i个元素的数值，接下来有n行，第一个数Ki代表第i个节点的子孩子个数，接下来有Ki个树，代表节点i子孩子节点标号。接下来m+1行，与树A描述相同。
输出：
对应每个测试案例，
若B是A的子树输出”YES”(不包含引号)。否则，输出“NO”（不包含引号）。
样例输入：
73
8879247
223
245
0
0
267
0
0
892
223
0
0
实现
第一步，在A树中查找和B树根节点一样的值，其实就是树的前序遍历，建议递归，方便（ps：非递归无非就是用个栈存储结点而已，没什么技术含量）
/**
*第一步判断，遍历A树查找是否有等于B树根结点的子树
*/
intjudgeChildTree(structbtree*ahead,intnuma,structbtree*bhead,intnumb)
{
intflag=0;
if(numa!=-1&&numb!=-1){
if(ahead[numa].value==bhead[numb].value)
flag=doesTree1HasTree2(ahead,numa,bhead,numb);
if(!flag&&ahead[numa].lchild!=-1)
flag=judgeChildTree(ahead,ahead[numa].lchild,bhead,numb);
if(!flag&&ahead[numa].rchild!=-1)
flag=judgeChildTree(ahead,ahead[numa].rchild,bhead,numb);
}
returnflag;
}
第二步，进一步判断A中以R为根节点的子树是不是与B树具有相同的结点
/**
*第二步判断，判断A树是否有B树的子结构
*/
intdoesTree1HasTree2(structbtree*ahead,intnuma,structbtree*bhead,intnumb)
{
if(numb==-1)
return1;
if(numa==-1)
return0;
if(ahead[numa].value!=bhead[numb].value)
return0;
return(doesTree1HasTree2(ahead,ahead[numa].lchild,bhead,bhead[numb].lchild)&&
doesTree1HasTree2(ahead,ahead[numa].rchild,bhead,bhead[numb].rchild));
}
完整代码
#include<stdio.h>
#include<stdlib.h>
//二叉树结点定义
structbtree
{
intvalue;
intlchild,rchild;
};
//A树和B树的最多结点数
intn,m;
/**
*第二步判断，判断A树是否有B树的子结构
*/
intdoesTree1HasTree2(structbtree*ahead,intnuma,structbtree*bhead,intnumb)
{
if(numb==-1)
return1;
if(numa==-1)
return0;
if(ahead[numa].value!=bhead[numb].value)
return0;
return(doesTree1HasTree2(ahead,ahead[numa].lchild,bhead,bhead[numb].lchild)&&
doesTree1HasTree2(ahead,ahead[numa].rchild,bhead,bhead[numb].rchild));
}
/**
*第一步判断，遍历A树查找是否有等于B树根结点的子树
*/
intjudgeChildTree(structbtree*ahead,intnuma,structbtree*bhead,intnumb)
{
intflag=0;
if(numa!=-1&&numb!=-1){
if(ahead[numa].value==bhead[numb].value)
flag=doesTree1HasTree2(ahead,numa,bhead,numb);
if(!flag&&ahead[numa].lchild!=-1)
flag=judgeChildTree(ahead,ahead[numa].lchild,bhead,numb);
if(!flag&&ahead[numa].rchild!=-1)
flag=judgeChildTree(ahead,ahead[numa].rchild,bhead,numb);
}
returnflag;
}
intmain(void)
{
inti,data,count,left,right,flag;
structbtree*ahead,*bhead;
while(scanf("%d%d",&n,&m)!=EOF){
//获取A树的节点值
ahead=(structbtree*)malloc(sizeof(structbtree)*n);
for(i=0;i<n;i++){
scanf("%d",&data);
ahead[i].value=data;
ahead[i].lchild=ahead[i].rchild=-1;
}
for(i=0;i<n;i++){
scanf("%d",&count);
if(count==0){
continue;
}else{
if(count==1){
scanf("%d",&left);
ahead[i].lchild=left-1;
}else{
scanf("%d%d",&left,&right);
ahead[i].lchild=left-1;
ahead[i].rchild=right-1;
}
}
}
//获取B树的节点值
bhead=(structbtree*)malloc(sizeof(structbtree)*m);
for(i=0;i<m;i++){
scanf("%d",&data);
bhead[i].value=data;
bhead[i].lchild=bhead[i].rchild=-1;
}
for(i=0;i<m;i++){
scanf("%d",&count);
if(count==0){
continue;
}else{
if(count==1){
scanf("%d",&left);
bhead[i].lchild=left-1;
}else{
scanf("%d%d",&left,&right);
bhead[i].lchild=left-1;
bhead[i].rchild=right-1;
}
}
}
//判断B树是否为A的子树
if(n==0||m==0){
printf("NO\n");
continue;
}
flag=judgeChildTree(ahead,0,bhead,0);
if(flag)
printf("YES\n");
else
printf("NO\n");
free(ahead);
free(bhead);
}
return0;
}