1.題目
輸入兩棵二叉樹 A 和 B拗秘，判斷 B 是不是 A 的子結(jié)構(gòu)。
2.示例
樹 A
3
/ \
4 5
/ \
1 2
樹B
4
/ \
1 2
上面 B 是 A 的子結(jié)構(gòu)蜗细，故返回 true。
3.解題思路
1.在樹 A 中找到和樹 B 的根結(jié)點的值一樣的結(jié)點 Root蹭劈。
2.接著判斷樹 A 中以 Root 為根結(jié)點的子樹是否包含和樹 B 一樣的結(jié)構(gòu)。
3.若第 2 步有相同的結(jié)構(gòu)則返回ture线召，若沒有铺韧，則繼續(xù)重復第 1、2步缓淹，直到遍歷完樹 A 還沒有找到哈打，就返回false。
4.代碼實現(xiàn)
#include <stdio.h>
#include <stdbool.h>
// 二叉樹的二叉鏈表存儲結(jié)構(gòu)
typedef struct BiTNode {
double data; // 結(jié)點數(shù)據(jù)域
struct BiTNode* lchild; // 左孩子結(jié)點
struct BiTNode* rchild; // 右孩子結(jié)點
}BiTNode;
// 函數(shù)聲明
// 不想寫聲明的話讯壶，下面這兩個函數(shù)的定義需要放到 HasSubTree函數(shù)的前面
bool DoesRootAHaveRootB(BiTNode* RootA, BiTNode* RootB);
bool Equal(double num1, double num2);
// 判斷樹 B 是不是樹 A 的子結(jié)構(gòu)
// 主要是通過遞歸的方式前序遍歷樹 A料仗，找到一個與樹 B 的根結(jié)點相等的結(jié)點
bool HasSubTree(BiTNode* RootA, BiTNode* RootB)
{
bool result = false;
if (RootA != NULL && RootB != NULL) {
// 若樹 A 的某一結(jié)點的值和樹 B 的頭結(jié)點的值相同
if (Equal(RootA->data, RootB->data)) {
result = DoesRootAHaveRootB(RootA, RootB);
}
if (!result) {
result = HasSubTree(RootA->lchild, RootB);
}
if (!result) {
result = HasSubTree(RootA->rchild, RootB)
}
}
return result;
}
// 判斷樹 A 中以 Root 為根結(jié)點的子樹是否和樹 B 具有相同的結(jié)構(gòu)
bool DoesRootAHaveRootB(BiTNode* RootA, BiTNode* RootB)
{
if (RootB == NULL) {
return true;
}
if (RootA == NULL) {
return false;
}
if (!Equal(RootA->data, RootB->data)) {
return false;
}
// 在根結(jié)點相同的情況下，若樹 A 與 樹 B 對應的子結(jié)點也都相同伏蚊，則返回 true
return DoesRootAHaveRootB(RootA->lchild, RootB->lchild) &&
DoesRootAHaveRootB(RootA->rchild, RootB->rchild);
}
// 判斷兩個結(jié)點的值是否相等
// 注意判斷兩個小數(shù)是否相等立轧，不能直接用 ==，因為計算機內(nèi)表示小數(shù)時其實都是有誤差的
// 因此躏吊，一般來說它們之差的絕對值若在一個很小的范圍內(nèi)氛改，就認為它們相等
bool Equal(double num1, double num2)
{
if ((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001)) {
return true;
} else {
return false;
}
}
個人主頁：
