用C語言判斷一個二叉樹是否為另一個的子結(jié)構(gòu)
1、問題描述：
如何判斷一個二叉樹是否是另一個的子結(jié)構(gòu)？
比如：
2
/ \
9 8
/ \ /
2 3 5
/
6
有個子結(jié)構(gòu)是
9
/ \
2 3
2、分析問題：
有關(guān)二叉樹的算法問題，一般都可以通過遞歸來解決。那么寫成一個正確的遞歸程序，首先一定要分析正確遞歸結(jié)束的條件。
拿這道題來講，什么時候遞歸結(jié)束。
<1>第二個二叉樹root2為空時，說明root2是第一棵二叉樹的root1的子結(jié)構(gòu)，返回true。
<2>當(dāng)root1為空時，此時root2還沒為空，說明root2不是root1的子結(jié)構(gòu)，返回false。
<3>遞歸下面有兩種思路：
方法一：現(xiàn)在root1中找結(jié)點(diǎn)值與root2的值相等的結(jié)點(diǎn)，如果找到就判斷root2是不是這個結(jié)點(diǎn)開頭的子結(jié)構(gòu)。所以，首先IsSubTree()判斷。
方法二：就是直接判斷，相同就遞歸判斷root2左右子樹是不是也是相應(yīng)的子結(jié)構(gòu)。如果值不相同，就分別遞歸到root1的左右子樹尋找。尤其要注意最后兩句遞歸的邏輯判斷。
3、習(xí)題實(shí)例
題目描述：
輸入兩顆二叉樹A，B，判斷B是不是A的子結(jié)構(gòu)。
輸入：
輸入可能包含多個測試樣例，輸入以EOF結(jié)束。
對于每個測試案例，輸入的第一行一個整數(shù)n,m(1<=n<=1000,1<=m<=1000)：n代表將要輸入的二叉樹A的節(jié)點(diǎn)個數(shù)（節(jié)點(diǎn)從1開始計數(shù)），m代表將要輸入的二叉樹B的節(jié)點(diǎn)個數(shù)（節(jié)點(diǎn)從1開始計數(shù)）。接下來一行有n個數(shù)，每個數(shù)代表A樹中第i個元素的數(shù)值，接下來有n行，第一個數(shù)Ki代表第i個節(jié)點(diǎn)的子孩子個數(shù)，接下來有Ki個樹，代表節(jié)點(diǎn)i子孩子節(jié)點(diǎn)標(biāo)號。接下來m+1行，與樹A描述相同。
輸出：
對應(yīng)每個測試案例，
若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
實(shí)現(xiàn)
第一步，在A樹中查找和B樹根節(jié)點(diǎn)一樣的值，其實(shí)就是樹的前序遍歷，建議遞歸，方便（ps：非遞歸無非就是用個棧存儲結(jié)點(diǎn)而已，沒什么技術(shù)含量）
/**
* 第一步判斷，遍歷A樹查找是否有等于B樹根結(jié)點(diǎn)的子樹
*/
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;
}
第二步，進(jìn)一步判斷A中以R為根節(jié)點(diǎn)的子樹是不是與B樹具有相同的結(jié)點(diǎn)
/**
* 第二步判斷，判斷A樹是否有B樹的子結(jié)構(gòu)
*/
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>
// 二叉樹結(jié)點(diǎn)定義
struct btree
{
int value;
int lchild, rchild;
};
// A樹和B樹的最多結(jié)點(diǎn)數(shù)
int n, m;
/**
* 第二步判斷，判斷A樹是否有B樹的子結(jié)構(gòu)
*/
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樹根結(jié)點(diǎn)的子樹
*/
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樹的節(jié)點(diǎn)值
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樹的節(jié)點(diǎn)值
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;
}
上一篇：詳解C語言中的常量指針和指針常量
欄 目：C語言
本文標(biāo)題：用C語言判斷一個二叉樹是否為另一個的子結(jié)構(gòu)
本文地址：http://mengdiqiu.com.cn/a1/Cyuyan/2882.html
您可能感興趣的文章
- 04-02c語言函數(shù)調(diào)用后清空內(nèi)存 c語言調(diào)用函數(shù)刪除字符
- 04-02c語言的正則匹配函數(shù) c語言正則表達(dá)式函數(shù)庫
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言中對數(shù)函數(shù)的表達(dá)式 c語言中對數(shù)怎么表達(dá)
- 04-02c語言用函數(shù)寫分段 用c語言表示分段函數(shù)
- 04-02c語言編寫函數(shù)冒泡排序 c語言冒泡排序法函數(shù)
- 04-02c語言沒有round函數(shù) round c語言
- 04-02c語言分段函數(shù)怎么求 用c語言求分段函數(shù)
- 04-02C語言中怎么打出三角函數(shù) c語言中怎么打出三角函數(shù)的值
- 04-02c語言調(diào)用函數(shù)求fibo C語言調(diào)用函數(shù)求階乘
閱讀排行
本欄相關(guān)
- 04-02c語言函數(shù)調(diào)用后清空內(nèi)存 c語言調(diào)用
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言的正則匹配函數(shù) c語言正則表達(dá)
- 04-02c語言用函數(shù)寫分段 用c語言表示分段
- 04-02c語言中對數(shù)函數(shù)的表達(dá)式 c語言中對
- 04-02c語言編寫函數(shù)冒泡排序 c語言冒泡排
- 04-02c語言沒有round函數(shù) round c語言
- 04-02c語言分段函數(shù)怎么求 用c語言求分段
- 04-02C語言中怎么打出三角函數(shù) c語言中怎
- 04-02c語言調(diào)用函數(shù)求fibo C語言調(diào)用函數(shù)求
隨機(jī)閱讀
- 08-05DEDE織夢data目錄下的sessions文件夾有什
- 01-10C#中split用法實(shí)例總結(jié)
- 01-11Mac OSX 打開原生自帶讀寫NTFS功能(圖文
- 04-02jquery與jsp,用jquery
- 01-10delphi制作wav文件的方法
- 01-10SublimeText編譯C開發(fā)環(huán)境設(shè)置
- 01-11ajax實(shí)現(xiàn)頁面的局部加載
- 08-05織夢dedecms什么時候用欄目交叉功能？
- 08-05dedecms(織夢)副欄目數(shù)量限制代碼修改
- 01-10使用C語言求解撲克牌的順子及n個骰子