用C語(yǔ)言判斷一個(gè)二叉樹(shù)是否為另一個(gè)的子結(jié)構(gòu)
1、問(wèn)題描述：
如何判斷一個(gè)二叉樹(shù)是否是另一個(gè)的子結(jié)構(gòu)？
比如：
2
/ \
9 8
/ \ /
2 3 5
/
6
有個(gè)子結(jié)構(gòu)是
9
/ \
2 3
2、分析問(wèn)題：
有關(guān)二叉樹(shù)的算法問(wèn)題，一般都可以通過(guò)遞歸來(lái)解決。那么寫(xiě)成一個(gè)正確的遞歸程序，首先一定要分析正確遞歸結(jié)束的條件。
拿這道題來(lái)講，什么時(shí)候遞歸結(jié)束。
<1>第二個(gè)二叉樹(shù)root2為空時(shí)，說(shuō)明root2是第一棵二叉樹(shù)的root1的子結(jié)構(gòu)，返回true。
<2>當(dāng)root1為空時(shí)，此時(shí)root2還沒(méi)為空，說(shuō)明root2不是root1的子結(jié)構(gòu)，返回false。
<3>遞歸下面有兩種思路：
方法一：現(xiàn)在root1中找結(jié)點(diǎn)值與root2的值相等的結(jié)點(diǎn)，如果找到就判斷root2是不是這個(gè)結(jié)點(diǎn)開(kāi)頭的子結(jié)構(gòu)。所以，首先IsSubTree()判斷。
方法二：就是直接判斷，相同就遞歸判斷root2左右子樹(shù)是不是也是相應(yīng)的子結(jié)構(gòu)。如果值不相同，就分別遞歸到root1的左右子樹(shù)尋找。尤其要注意最后兩句遞歸的邏輯判斷。
3、習(xí)題實(shí)例
題目描述：
輸入兩顆二叉樹(shù)A，B，判斷B是不是A的子結(jié)構(gòu)。
輸入：
輸入可能包含多個(gè)測(cè)試樣例，輸入以EOF結(jié)束。
對(duì)于每個(gè)測(cè)試案例，輸入的第一行一個(gè)整數(shù)n,m(1<=n<=1000,1<=m<=1000)：n代表將要輸入的二叉樹(shù)A的節(jié)點(diǎn)個(gè)數(shù)（節(jié)點(diǎn)從1開(kāi)始計(jì)數(shù)），m代表將要輸入的二叉樹(shù)B的節(jié)點(diǎn)個(gè)數(shù)（節(jié)點(diǎn)從1開(kāi)始計(jì)數(shù)）。接下來(lái)一行有n個(gè)數(shù)，每個(gè)數(shù)代表A樹(shù)中第i個(gè)元素的數(shù)值，接下來(lái)有n行，第一個(gè)數(shù)Ki代表第i個(gè)節(jié)點(diǎn)的子孩子個(gè)數(shù)，接下來(lái)有Ki個(gè)樹(shù)，代表節(jié)點(diǎn)i子孩子節(jié)點(diǎn)標(biāo)號(hào)。接下來(lái)m+1行，與樹(shù)A描述相同。
輸出：
對(duì)應(yīng)每個(gè)測(cè)試案例，
若B是A的子樹(shù)輸出”YES”(不包含引號(hào))。否則，輸出“NO”（不包含引號(hào)）。
樣例輸入：
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樹(shù)中查找和B樹(shù)根節(jié)點(diǎn)一樣的值，其實(shí)就是樹(shù)的前序遍歷，建議遞歸，方便（ps：非遞歸無(wú)非就是用個(gè)棧存儲(chǔ)結(jié)點(diǎn)而已，沒(méi)什么技術(shù)含量）
/**
* 第一步判斷，遍歷A樹(shù)查找是否有等于B樹(shù)根結(jié)點(diǎn)的子樹(shù)
*/
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)的子樹(shù)是不是與B樹(shù)具有相同的結(jié)點(diǎn)
/**
* 第二步判斷，判斷A樹(shù)是否有B樹(shù)的子結(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>
// 二叉樹(shù)結(jié)點(diǎn)定義
struct btree
{
int value;
int lchild, rchild;
};
// A樹(shù)和B樹(shù)的最多結(jié)點(diǎn)數(shù)
int n, m;
/**
* 第二步判斷，判斷A樹(shù)是否有B樹(shù)的子結(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樹(shù)查找是否有等于B樹(shù)根結(jié)點(diǎn)的子樹(shù)
*/
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樹(shù)的節(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樹(shù)的節(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樹(shù)是否為A的子樹(shù)
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語(yǔ)言版本二叉樹(shù)基本操作示例(先序 遞歸 非遞歸)
- 使用C語(yǔ)言構(gòu)建基本的二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)
- C語(yǔ)言實(shí)現(xiàn)二叉樹(shù)遍歷的迭代算法
- C語(yǔ)言中計(jì)算二叉樹(shù)的寬度的兩種方式
- C語(yǔ)言 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)實(shí)例
- C語(yǔ)言二叉樹(shù)的非遞歸遍歷實(shí)例分析
- 使用C語(yǔ)言求二叉樹(shù)結(jié)點(diǎn)的最低公共祖先的方法
- C語(yǔ)言實(shí)現(xiàn)線索二叉樹(shù)的定義與遍歷示例
- C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之線索二叉樹(shù)及其遍歷
- C語(yǔ)言實(shí)現(xiàn)二叉樹(shù)的搜索及相關(guān)算法示例
- C語(yǔ)言二叉樹(shù)常見(jiàn)操作詳解【前序,中序,后序,層次遍歷及非遞歸查找,統(tǒng)計(jì)個(gè)數(shù),比較,求深度】
相關(guān)文章
本篇文章是對(duì)C++中輸出指針自增(++)運(yùn)算的示例進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了c++中，vector是一個(gè)十分有用的容器，下面對(duì)這個(gè)容器做一下總結(jié)2013-12-12
這篇文章主要介紹了C/C++預(yù)處理器的一些工作,有助于理解編譯器底層的工作流程,需要的朋友可以參考下2015-07-07
Visual Studio C++指針靠前靠后的問(wèn)題全面解析
這篇文章主要介紹了Visual Studio C++指針靠前靠后的問(wèn)題全面解析,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-04-04
C++將二叉樹(shù)轉(zhuǎn)為雙向鏈表及判斷兩個(gè)鏈表是否相交
這篇文章主要介紹了C++將二叉樹(shù)轉(zhuǎn)為雙向鏈表及判斷兩個(gè)鏈表是否相交的方法,文中還給出了求兩個(gè)鏈表相交的第一個(gè)節(jié)點(diǎn)列的實(shí)現(xiàn)方法,需要的朋友可以參考下2016-02-02
這篇文章主要介紹了C/C++ 監(jiān)控磁盤(pán)與目錄操作的示例，幫助大家更好的理解和學(xué)習(xí)C/C++編程，感興趣的朋友可以了解下2020-10-10
C++實(shí)現(xiàn)LeetCode(68.文本左右對(duì)齊)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(68.文本左右對(duì)齊),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C語(yǔ)言中實(shí)現(xiàn)協(xié)程案例
這篇文章主要介紹了C語(yǔ)言中實(shí)現(xiàn)協(xié)程案例,本文通過(guò)將協(xié)程與線程和異步回調(diào)進(jìn)行對(duì)比,以及具體實(shí)現(xiàn)案例,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
本文主要介紹了C/C++字節(jié)序的深入理解，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-02-02
這篇文章主要給大家介紹了關(guān)于C++中const的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11