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; } 新聞熱點
疑難解答
圖片精選
