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; } |
