用C语言判断一个二叉树是否为另一个的子结构

概述1、问题描述：    如何判断一个二叉树是否是另一个的子结构？

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”（不包含引号）。 
    样例输入： 
    7 3 
    8 8 7 9 2 4 7 
    2 2 3 
    2 4 5 
    0 
    0 
    2 6 7 
    0 
    0 
    8 9 2 
    2 2 3 
    0 
    0 

    实现
    第一步，在A树中查找和B树根节点一样的值，其实就是树的前序遍历，建议递归，方便（ps：非递归无非就是用个栈存储结点而已，没什么技术含量）

  

 /**    * 第一步判断，遍历A树查找是否有等于B树根结点的子树    */   int judgeChildTree(struct btree *ahead,int numa,struct btree *bhead,int numb)   {     int flag = 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,numb);          if (! flag && ahead[numa].rchild != -1)         flag = judgeChildTree(ahead,ahead[numa].rchild,numb);     }        return flag;   } 

    第二步，进一步判断A中以R为根节点的子树是不是与B树具有相同的结点

  /**    * 第二步判断，判断A树是否有B树的子结构    */   int doesTree1HasTree2(struct btree *ahead,int numb)   {     if (numb == -1)        return 1;     if (numa == -1)       return 0;        if (ahead[numa].value != bhead[numb].value)       return 0;        return (doesTree1HasTree2(ahead,bhead[numb].lchild) &&       doesTree1HasTree2(ahead,bhead[numb].rchild));   } 

完整代码

   

 #include <stdio.h>   #include <stdlib.h>      // 二叉树结点定义   struct btree   {     int value;     int lchild,rchild;   };      // A树和B树的最多结点数   int n,m;      /**    * 第二步判断，判断A树是否有B树的子结构    */   int doesTree1HasTree2(struct btree *ahead,bhead[numb].rchild));   }      /**    * 第一步判断，遍历A树查找是否有等于B树根结点的子树    */   int judgeChildTree(struct btree *ahead,numb);     }        return flag;   }      int main(voID)   {     int i,data,count,left,right,flag;     struct btree *ahead,*bhead;        while (scanf("%d %d",&n,&m) != EOF) {       // 获取A树的节点值       ahead = (struct btree *)malloc(sizeof(struct btree) * 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 = (struct btree *)malloc(sizeof(struct btree) * 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",&left);             bhead[i].lchild = left - 1;           } else {             scanf("%d %d",&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);       if (flag)         printf("YES\n");       else         printf("NO\n");          free(ahead);       free(bhead);     }        return 0;   } 

总结

以上是内存溢出为你收集整理的用C语言判断一个二叉树是否为另一个的子结构全部内容，希望文章能够帮你解决用C语言判断一个二叉树是否为另一个的子结构所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。