用C說話斷定一個二叉樹能否為另外一個的子構造。本站提示廣大學習愛好者：（用C說話斷定一個二叉樹能否為另外一個的子構造）文章只能為提供參考，不一定能成為您想要的結果。以下是用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”（不包括引號）。
樣例輸出：
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, bhead, numb);
if (! flag && ahead[numa].rchild != -1)
flag = judgeChildTree(ahead, ahead[numa].rchild, bhead, numb);
}
return flag;
}
第二步，進一步斷定A中以R為根節點的子樹是否是與B樹具有雷同的結點
/**
* 第二步斷定，斷定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));
}
完全代碼
#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;
}
