服务器之家

服务器之家 > 正文

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

时间:2021-03-06 14:13     来源/作者:zinss26914

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:非递归无非就是用个栈存储结点而已,没什么技术含量)

  

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
  * 第一步判断,遍历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, bhead, numb);
  
     if (! flag && ahead[numa].rchild != -1)
       flag = judgeChildTree(ahead, ahead[numa].rchild, bhead, numb);
   }
  
   return flag;
 }

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 第二步判断,判断A树是否有B树的子结构
 */
int doesTree1HasTree2(struct btree *ahead, int numa, struct btree *bhead, int numb)
{
  if (numb == -1) 
    return 1;
  if (numa == -1)
    return 0;
 
  if (ahead[numa].value != bhead[numb].value)
    return 0;
 
  return (doesTree1HasTree2(ahead, ahead[numa].lchild, bhead, bhead[numb].lchild) &&
    doesTree1HasTree2(ahead, ahead[numa].rchild, bhead, bhead[numb].rchild));
}


完整代码

   

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#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, int numa, struct btree *bhead, int numb)
 {
   if (numb == -1) 
     return 1;
   if (numa == -1)
     return 0;
  
   if (ahead[numa].value != bhead[numb].value)
     return 0;
  
   return (doesTree1HasTree2(ahead, ahead[numa].lchild, bhead, bhead[numb].lchild) &&
     doesTree1HasTree2(ahead, ahead[numa].rchild, bhead, bhead[numb].rchild));
 }
  
 /**
  * 第一步判断,遍历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, bhead, numb);
  
     if (! flag && ahead[numa].rchild != -1)
       flag = judgeChildTree(ahead, ahead[numa].rchild, bhead, 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", &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);
   }
  
   return 0;
 }

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部