一、樹的概念及結(jié)構(gòu)

1.樹的概念

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做樹是因?yàn)樗雌饋硐褚豢玫箳斓臉?#xff0c;也就是說它是根朝上，而葉朝下的。

樹有一個(gè)特殊的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，根節(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，除根節(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成(M>0)個(gè)互不相交的集合T1、T2、……、Tm，其中每一個(gè)集合Ti(1<= i <= m)又是一棵結(jié)構(gòu)與樹類似的子樹。每棵子樹的根結(jié)點(diǎn)有且只有一個(gè)前驅(qū)，可以有0個(gè)或多個(gè)后繼節(jié)點(diǎn)

因此，樹是遞歸定義的。

【注意】：樹形結(jié)構(gòu)中，子樹之間不能有交集，否則就不是樹形結(jié)構(gòu)

在上面前三個(gè)圖中，節(jié)點(diǎn)直接形成了回路，所以不能稱為數(shù)，應(yīng)該稱為圖。

2.樹的相關(guān)概念名詞

節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度； 如上圖：A的為6

葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)； 如上圖：B、C、H、I…等節(jié)點(diǎn)為葉節(jié)點(diǎn)

非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)； 如上圖：D、E、F、G…等節(jié)點(diǎn)為分支節(jié)點(diǎn)

雙親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)； 如上圖：A是B的父節(jié)點(diǎn)

孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)； 如上圖：B是A的孩子節(jié)點(diǎn)

兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)； 如上圖：B、C是兄弟節(jié)點(diǎn)

樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度； 如上圖：樹的度為6

節(jié)點(diǎn)的層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推

樹的高度或深度：樹中節(jié)點(diǎn)的最大層次； 如上圖：樹的高度為4

堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互為堂兄弟；如上圖：H、I互為兄弟節(jié)點(diǎn)

節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；如上圖：A是所有節(jié)點(diǎn)的祖先

子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。如上圖：所有節(jié)點(diǎn)都是A的子孫

森林：由m（m>0）棵互不相交的樹的集合稱為森林；

3.樹的表示

樹結(jié)構(gòu)相對線性表就比較復(fù)雜了，要存儲(chǔ)表示起來就比較麻煩了，既然保存值域，也要保存結(jié)點(diǎn)和結(jié)點(diǎn)之系，實(shí)際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等。我們這里就簡單的了解其中最常用的孩子兄弟表示法。

typedef int DataType;
struct Node
{struct Node* _firstChild1; // 第一個(gè)孩子結(jié)點(diǎn)struct Node* _pNextBrother; // 指向其下一個(gè)兄弟結(jié)點(diǎn)DataType _data; // 結(jié)點(diǎn)中的數(shù)據(jù)域
}

4.樹在實(shí)際中的運(yùn)用

樹在我們實(shí)際生活中的應(yīng)用之一就是用于表示文件系統(tǒng)的目錄：

二、二叉樹概念及結(jié)構(gòu)

1.二叉樹的概念

一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合:

1.或者為空

2.由一個(gè)根節(jié)點(diǎn)加上兩棵別稱為左子樹和右子樹的二叉樹組成

從上圖可以看出：

1.二叉樹不存在度大于2的結(jié)點(diǎn)

2.二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹

【注意】對于任意的二叉樹都是由以下幾種情況復(fù)合而成的：

現(xiàn)實(shí)中的二叉樹：

2.特殊的二叉樹

1.滿二叉樹：一個(gè)二叉樹，如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹就是滿二叉樹。也就是說，如果一個(gè)二叉樹的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是 2^k-1，則它就是滿二叉樹。

2.完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對應(yīng)時(shí)稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。

3.二叉樹的性質(zhì)

1.若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有 2^(i-1)個(gè)結(jié)點(diǎn)

2.若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點(diǎn)數(shù)是 2^h-1

3.對任何一棵二叉樹, 如果度為0其葉結(jié)點(diǎn)個(gè)數(shù)為 n0,度為2的分支結(jié)點(diǎn)個(gè)數(shù)為n2 ,則有n0 ＝ n2＋1

解析：如圖所示：

當(dāng)二叉樹只有一個(gè)節(jié)點(diǎn)的時(shí)候，葉子節(jié)點(diǎn)數(shù)為1，度為2的分支節(jié)點(diǎn)數(shù)為0，此時(shí)葉子節(jié)點(diǎn)數(shù)比度為2的節(jié)點(diǎn)數(shù)多1

當(dāng)我們增加一個(gè)度為1的分支節(jié)點(diǎn)的時(shí)候，會(huì)消耗一個(gè)葉子節(jié)點(diǎn)，但同時(shí)又會(huì)產(chǎn)生一個(gè)新的葉子節(jié)點(diǎn)，所以增加度為1的分支節(jié)點(diǎn)時(shí)葉子節(jié)點(diǎn)的數(shù)量不變

當(dāng)我們增加一個(gè)度為2的節(jié)點(diǎn)的時(shí)候，我們會(huì)同時(shí)產(chǎn)生一個(gè)葉子節(jié)點(diǎn)，所以葉子節(jié)點(diǎn)數(shù)始終比度為2的分支節(jié)點(diǎn)多1

4.若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個(gè)結(jié)點(diǎn)的滿二叉樹的深度,h=log(n+1). (是log以2為底，n+1為對數(shù))

高度為h的完全二叉樹：2^(h-1) <= N <= 2^h-1

? logN+1 <= h <=log(N+1)

5… 對于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點(diǎn)從0開始編號(hào)，則對于序號(hào)為i的結(jié)點(diǎn)有：

1.若i>0，i位置節(jié)點(diǎn)的雙親序號(hào)：(i-1)/2；i=0，i為根節(jié)點(diǎn)編號(hào)，無雙親節(jié)點(diǎn)

2.若2i+1<n，左孩子序號(hào)：2i+1，2i+1>=n否則無左孩子

3.若2i+2<n，右孩子序號(hào)：2i+2，2i+2>=n否則無右孩子

概念和性質(zhì)相關(guān)選擇題

1.某二叉樹共有 399 個(gè)結(jié)點(diǎn)，其中有 199 個(gè)度為 2 的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)為（ ）

A 不存在這樣的二叉樹

B 200

C 198

D 199

【解析】B 根據(jù)結(jié)論：度為0的節(jié)點(diǎn)數(shù)比度為2的節(jié)點(diǎn)數(shù)多1可得n0=200

2.在具有 2n 個(gè)結(jié)點(diǎn)的完全二叉樹中，葉子結(jié)點(diǎn)個(gè)數(shù)為（ ）

A n

B n+1

C n-1

D n/2

【解析】A 通過完全二叉樹的概念我們知道，完全二叉樹只存在三種節(jié)點(diǎn)，分別為度為0，度為1和度為2的節(jié)點(diǎn)，其中度為1的節(jié)點(diǎn)要么不存在要么只有一個(gè)；又根據(jù)度為0的節(jié)點(diǎn)數(shù)比度為2的節(jié)點(diǎn)數(shù)多1這個(gè)結(jié)論，我們可得n0+n1+n0-1=2n,我們知道n0*,n1都為整數(shù)，又2n為偶數(shù)，我們可知*n1=1;n0=n;

3.一棵完全二叉樹的節(jié)點(diǎn)數(shù)位為531個(gè)，那么這棵樹的高度為（ ）

A 11

B 10

C 8

D 12

【解析】B 我們知道 2^(h-1) <= N <= 2^h-1 ,所以h為10

4.二叉樹的存儲(chǔ)結(jié)構(gòu)

二叉樹一般可以使用兩種結(jié)構(gòu)存儲(chǔ)，一種順序結(jié)構(gòu)，一種鏈?zhǔn)浇Y(jié)構(gòu)。

1.順序存儲(chǔ)

順序結(jié)構(gòu)存儲(chǔ)就是使用數(shù)組來存儲(chǔ)，一般使用數(shù)組只適合表示完全二叉樹，因?yàn)椴皇峭耆鏄鋾?huì)有空間的浪費(fèi)。而現(xiàn)實(shí)中使用中只有堆才會(huì)使用數(shù)組來存儲(chǔ)，二叉樹順序存儲(chǔ)在物理上是一個(gè)數(shù)組，在邏輯上是一顆二叉樹。

2.鏈?zhǔn)酱鎯?chǔ)

二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。 通常的方法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址 。鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈，當(dāng)前我們學(xué)習(xí)中一般都是二叉鏈，紅黑樹等會(huì)用到三叉鏈。

typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{struct BinTreeNode* _pLeft; // 指向當(dāng)前節(jié)點(diǎn)左孩子struct BinTreeNode* _pRight; // 指向當(dāng)前節(jié)點(diǎn)右孩子BTDataType _data; // 當(dāng)前節(jié)點(diǎn)值域
}
// 三叉鏈
struct BinaryTreeNode
{struct BinTreeNode* _pParent; // 指向當(dāng)前節(jié)點(diǎn)的雙親struct BinTreeNode* _pLeft; // 指向當(dāng)前節(jié)點(diǎn)左孩子struct BinTreeNode* _pRight; // 指向當(dāng)前節(jié)點(diǎn)右孩子BTDataType _data; // 當(dāng)前節(jié)點(diǎn)值域
}

三、二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)

1.結(jié)構(gòu)的定義

// 符號(hào)和結(jié)構(gòu)的定義
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

2.構(gòu)建二叉樹

由于二叉樹不能進(jìn)行增加和刪除操作，所以一般都是給定一個(gè)字符串或者一個(gè)數(shù)組，該字符串或者數(shù)組有我們創(chuàng)建二叉樹所需要的所有節(jié)點(diǎn)，我們根據(jù)字符串或者數(shù)組的內(nèi)容來構(gòu)建二叉樹

【注意】字符串或者數(shù)組中 # 表示空節(jié)點(diǎn)，即上一個(gè)節(jié)點(diǎn)沒有左孩子或者右孩子

// 通過前序遍歷的數(shù)組 1 2 3 # # 4 5 # # 6 ##構(gòu)建二叉樹
BTNode* BinaryTreeCreat(BTDataType* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}// 創(chuàng)建根節(jié)點(diǎn)BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc fail");exit(-1);}root->data = a[*pi];(*pi)++;// 創(chuàng)建左右子樹root->left = BinaryTreeCreat(a, pi);root->right = BinaryTreeCreat(a, pi);return root;
}

3.二叉樹前序遍歷

所謂二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對二叉樹中的節(jié)點(diǎn)進(jìn)行相應(yīng)的操作，并且每個(gè)節(jié)點(diǎn)只操作一次。訪問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問題。 遍歷是二叉樹上最重要的運(yùn)算之一，也是二叉樹上進(jìn)行其它運(yùn)算的基礎(chǔ)

按照規(guī)則，二叉樹的遍歷有：前序/中序/后序的遞歸結(jié)構(gòu)遍歷：

前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前

中序遍歷(Inorder Traversal)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之中（間）

后序遍歷(Postorder Traversal)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后

由于被訪問的結(jié)點(diǎn)必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。

前序遍歷遞歸圖解：

//二叉樹先序遍歷
void PreOrder(BTNode* root)
{//如果是空樹則返回NULLif (root == NULL){printf("NULL ");return;}printf("%d ", root->data);   //訪問根節(jié)點(diǎn)PreOrder(root->left);        //先序遍歷左子樹PreOrder(root->right);       //先序遍歷右子樹
}

4.二叉樹中序遍歷

//二叉樹中序遍歷
void InOrder(BTNode* root)
{//如果是空樹則返回NULLif (root == NULL){//printf("NULL ");return;}InOrder(root->left);              //中序遍歷左子樹printf("%d ", root->data);        //訪問根節(jié)點(diǎn)//printf("%c ", root->data);InOrder(root->right);             //中序遍歷右子樹
}

5.二叉樹后序遍歷

/ 二叉樹后序遍歷
void PostOrder(BTNode* root)
{//如果是空樹則返回NULLif (root == NULL){printf("NULL ");return;}PostOrder(root->left);        //后序遍歷左子樹PostOrder(root->right);       //后序遍歷右子樹printf("%d ", root->data);    //訪問根節(jié)點(diǎn)
}

6.二叉樹層次遍歷

層序遍歷：除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進(jìn)行層序遍歷。設(shè)二叉樹的根節(jié)點(diǎn)所在層數(shù)為1，層序遍歷就是從所在二叉樹的根節(jié)點(diǎn)出發(fā)，首先訪問第一層的樹根節(jié)點(diǎn)，然后從左到右訪問第2層上的節(jié)點(diǎn)，接著是第三層的節(jié)點(diǎn)，以此類推，自上而下，自左至右逐層訪問樹的結(jié)點(diǎn)的過程就是層序遍歷

相比于其他三種遍歷方式，層序遍歷采用的是非遞歸的方式，其具體思路是：

利用一個(gè)隊(duì)列來存儲(chǔ)二叉樹節(jié)點(diǎn)的地址，先讓父節(jié)點(diǎn)入隊(duì)列，然后父節(jié)點(diǎn)出隊(duì)列，同時(shí)父節(jié)點(diǎn)的左右孩子會(huì)入隊(duì)列，如果沒有就不入，直到隊(duì)列為空時(shí)結(jié)束，這樣使得當(dāng)一層節(jié)點(diǎn)全部出隊(duì)列的時(shí)候，下一層的節(jié)點(diǎn)剛好全部入隊(duì)列，當(dāng)隊(duì)列為空時(shí)，二叉樹的節(jié)點(diǎn)就全部訪問完畢了；

【注意】我們用隊(duì)列來存儲(chǔ)二叉樹節(jié)點(diǎn)的地址，所以我們需要自己實(shí)現(xiàn)一個(gè)隊(duì)列，也可以把我們之前實(shí)現(xiàn)寫的隊(duì)列Queue.h和Queue.c加入到當(dāng)前工程中；此外，我們應(yīng)該將二叉樹節(jié)點(diǎn)的結(jié)構(gòu)體需要定義在隊(duì)列結(jié)構(gòu)體的前面。

// 二叉樹層序遍歷
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){// 取出隊(duì)頭元素BTNode* front = QueueFront(&q);QueuePop(root);printf("%c ", front->data);// 將隊(duì)頭元素的左右子節(jié)點(diǎn)入隊(duì)列if (front->left)QueuePop(&q, front->left);if (front->right)QueuePop(&q, front->right);}QueueDestroy(&q);
}

7.二叉樹節(jié)點(diǎn)個(gè)數(shù)

我們采用子問題思路來解決，我們要計(jì)算二叉樹節(jié)點(diǎn)的個(gè)數(shù)，那么分為左子樹的節(jié)點(diǎn)個(gè)數(shù)和右節(jié)點(diǎn)的個(gè)數(shù)再加上根節(jié)點(diǎn) 二叉樹節(jié)點(diǎn)數(shù) = 左子樹節(jié)點(diǎn)個(gè)數(shù)+右節(jié)點(diǎn)個(gè)數(shù)+根節(jié)點(diǎn)

/計(jì)算二叉樹節(jié)點(diǎn)個(gè)數(shù)
int TreeSize(BTNode* root)
{if (root == NULL)return 0;// 左子樹節(jié)點(diǎn)個(gè)數(shù)+右節(jié)點(diǎn)個(gè)數(shù)+根節(jié)點(diǎn)return TreeSize(root->left) + TreeSize(root->right) + 1;
}

8.二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)

和計(jì)算二叉樹節(jié)點(diǎn)個(gè)數(shù)方法一樣，但是葉子節(jié)點(diǎn)要求左孩子為空并且右孩子為空，所以葉子節(jié)點(diǎn)數(shù)等與左右葉子數(shù)之和

//計(jì)算二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)
int TreeLeafSize(BTNode* root)
{//空樹返回0if (root == NULL){return 0;}//左子樹和右子樹均為空則為葉子節(jié)點(diǎn)if (root->left == NULL && root->right == NULL){return 1;}//葉子節(jié)點(diǎn)數(shù)等與左右葉子數(shù)之和return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

9.二叉樹第k層節(jié)點(diǎn)個(gè)數(shù)

求第k層節(jié)點(diǎn)的個(gè)數(shù)轉(zhuǎn)換成求左右子樹的k-1層的節(jié)點(diǎn)個(gè)數(shù)，當(dāng)k為1 的時(shí)候，節(jié)點(diǎn)數(shù)為1

//第K層節(jié)點(diǎn)個(gè)數(shù)
int TreeKLevel(BTNode* root, int k)
{assert(k > 0);  //層數(shù)大于0//空樹返回0if (root == NULL){return 0;}if (k == 1){return 1;}//相對于根是第k層，則相對于根是子樹的k-1層！！！//換成求子樹第k-1層return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);}c

10.二叉樹的高度

樹的高度等于左子樹的高度和右子樹的高度的最大值+1

//計(jì)算二叉樹深度
int TreeHeight(BTNode* root)
{//如果是空樹返回0if (root == NULL){return 0;}int lret = TreeHeight(root->left);  //遞歸計(jì)算左子樹的深度記為lretint rret = TreeHeight(root->right); //遞歸計(jì)算右子樹的深度記為rret/*if (lret > rret){return lret + 1;}else{return rret + 1;}*///二叉樹的深度為lret和rret的較大者+1return lret > rret ? lret + 1 : rret + 1;
}

11.在二叉樹中查找值為x的節(jié)點(diǎn)

我們先在左子樹找沒有找到再到右子樹找，都沒有找到則返回NULL；注意的是，上一個(gè)節(jié)點(diǎn)的返回值將作為下一個(gè)節(jié)點(diǎn)是否繼續(xù)找的依據(jù)，所以我們要用一個(gè)指針保存左右子樹查找的返回值，再進(jìn)行判斷。

// 在二叉樹中查找值為x的節(jié)點(diǎn)
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->data == x)return root;// 先去左樹找BTNode* lret = TreeFind(root->left, x);if (lret)return lret;// 左樹沒有找到，再到右樹找BTNode* rret = TreeFind(root->right, x);if (rret)return rret;//return TreeFind(root->right, x);// 都找不到則返回空retun NULL;
}

12.判斷二叉樹是否是完全二叉樹

我們知道，高度為h的完全二叉樹，前h-1層都是滿二叉樹，最后一層不一定是滿二叉樹，但是最后一層的節(jié)點(diǎn)必須是連續(xù)的，也就是說，當(dāng)完全二叉樹遇到空節(jié)點(diǎn)的時(shí)候，后面就不會(huì)在出現(xiàn)非空的節(jié)點(diǎn)，否則就不是完全二叉樹

根據(jù)上面完全二叉樹的性質(zhì)，我們可以利用二叉樹的層序遍歷來判斷二叉樹是否是完全二叉樹，基本思路為對二叉樹進(jìn)行層序遍歷，不管節(jié)點(diǎn)是否為空都入隊(duì)列，當(dāng)隊(duì)頭的元素為空的時(shí)候，我們檢查隊(duì)列中的剩余數(shù)據(jù)是否都是空節(jié)點(diǎn)，如果含有非空節(jié)點(diǎn)則該樹就不是完全二叉樹。

// 判斷二叉樹是否是完全二叉樹
int BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);if (front == NULL)break;QueuePop(&q);QueuePush(&q, root->left);QueuePush(&q, root->right);}// 遇到空以后，后面全是空，則是完全二叉樹// 遇到空以后，后面存在非空，則不是完全二叉樹while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);if (front != NULL){QueueDestroy(&q);return false;}QueuePop(&q);}return true;
}

13.銷毀二叉樹

我們不能直接刪除根節(jié)點(diǎn)，需要采用后續(xù)遍歷的方式進(jìn)行依次刪除

// 銷毀二叉樹
void BinaryTreeDestroy(BTNode* root)
{if (root == NULL)return;// 通過后續(xù)遍歷來銷毀節(jié)點(diǎn)BinaryTreeDestroy(root->left);BinaryTreeDestroy(root->right);// 此處置空不會(huì)影響外面，需要在外面進(jìn)行置空free(root);
}

四、完整代碼

1.BTree.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//創(chuàng)建二叉樹
BTNode* CreateTree();
//二叉樹先序遍歷
void PreOrder(BTNode* root);
//二叉樹中序遍歷
void InOrder(BTNode* root);
//二叉樹后序遍歷
void PostOrder(BTNode* root);
// 二叉樹層序遍歷
void BinaryTreeLevelOrder(BTNode* root);
//計(jì)算二叉樹節(jié)點(diǎn)個(gè)數(shù)
int TreeSize(BTNode* root);
//計(jì)算二叉樹深度
int TreeHeight(BTNode* root);
//第K層節(jié)點(diǎn)個(gè)數(shù)
int TreeKLevel(BTNode* root, int k);
//計(jì)算二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)
int TreeLeafSize(BTNode* root);
//返回x所在的節(jié)點(diǎn)
BTNode* TreeFind(BTNode* root, BTDataType x);
//創(chuàng)建二叉樹
BTNode* BTreeCreate(char* a, int* pi);
// 判斷二叉樹是否是完全二叉樹
int BinaryTreeComplete(BTNode* root);
// 銷毀二叉樹
void BinaryTreeDestroy(BTNode* root);

2.BTree.c

#include "BTree.h"//創(chuàng)建二叉樹
BTNode* CreateTree()
{//創(chuàng)建節(jié)點(diǎn)BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));assert(n1);BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));assert(n2);BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));assert(n3);BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));assert(n4);BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));assert(n5);BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));assert(n6);BTNode* n7 = (BTNode*)malloc(sizeof(BTNode));assert(n7);//鏈接關(guān)系n1->data = 1;n2->data = 2;n3->data = 3;n4->data = 4;n5->data = 5;n6->data = 6;n7->data = 7;n1->left = n2;n1->right = n4;n2->left = n3;n2->right = NULL;n4->left = n5;n4->right = n6;n3->left = NULL;n3->right = NULL;n5->left = NULL;n5->right = NULL;n6->left = NULL;n6->right = NULL;n3->right = n7;n7->left = NULL;n7->right = NULL;return n1;
}//二叉樹先序遍歷
void PreOrder(BTNode* root)
{//如果是空樹則返回NULLif (root == NULL){printf("NULL ");return;}printf("%d ", root->data);   //訪問根節(jié)點(diǎn)PreOrder(root->left);        //先序遍歷左子樹PreOrder(root->right);       //先序遍歷右子樹
}//二叉樹中序遍歷
void InOrder(BTNode* root)
{//如果是空樹則返回NULLif (root == NULL){//printf("NULL ");return;}InOrder(root->left);              //中序遍歷左子樹printf("%d ", root->data);        //訪問根節(jié)點(diǎn)//printf("%c ", root->data);InOrder(root->right);             //中序遍歷右子樹
}// 二叉樹后序遍歷
void PostOrder(BTNode* root)
{//如果是空樹則返回NULLif (root == NULL){printf("NULL ");return;}PostOrder(root->left);        //后序遍歷左子樹PostOrder(root->right);       //后序遍歷右子樹printf("%d ", root->data);    //訪問根節(jié)點(diǎn)
}// 二叉樹層序遍歷
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){// 取出隊(duì)頭元素BTNode* front = QueueFront(&q);QueuePop(root);printf("%c ", front->data);// 將隊(duì)頭元素的左右子節(jié)點(diǎn)入隊(duì)列if (front->left)QueuePop(&q, front->left);if (front->right)QueuePop(&q, front->right);}QueueDestroy(&q);
}//int count = 0;//定義全局變量，導(dǎo)致兩次調(diào)用返回值不一樣//計(jì)算二叉樹節(jié)點(diǎn)個(gè)數(shù)
int TreeSize(BTNode* root)
{//知易行難（不行）遍歷計(jì)數(shù)//static int count = 0;//static修飾count成為全局變量，導(dǎo)致兩次返回值不一樣！！！// 第一次打印7，則第二次打印14！！！//if (root == NULL)//	return count;//	//++count;//TreeSize(root->left);//TreeSize(root->right);//	//	return count;/*if (root == NULL){return 0;}int lret = TreeSize(root->left);int rret = TreeSize(root->right);return TreeSize(root->left) + TreeSize(root->right) + 1;*//*if (root == NULL){return 0;}return TreeSize(root->left) + TreeSize(root->right) + 1;*///二叉樹的節(jié)點(diǎn)個(gè)數(shù)等于左子樹的個(gè)數(shù)+右子樹的深度+1return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}//計(jì)算二叉樹深度
int TreeHeight(BTNode* root)
{//如果是空樹返回0if (root == NULL){return 0;}int lret = TreeHeight(root->left);  //遞歸計(jì)算左子樹的深度記為lretint rret = TreeHeight(root->right); //遞歸計(jì)算右子樹的深度記為rret/*if (lret > rret){return lret + 1;}else{return rret + 1;}*///二叉樹的深度為lret和rret的較大者+1return lret > rret ? lret + 1 : rret + 1;
}//第K層節(jié)點(diǎn)個(gè)數(shù)
int TreeKLevel(BTNode* root, int k)
{assert(k > 0);  //層數(shù)大于0//空樹返回0if (root == NULL){return 0;}if (k == 1){return 1;}//相對于根是第k層，則相對于根是子樹的k-1層！！！//換成求子樹第k-1層return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);}//計(jì)算二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)
int TreeLeafSize(BTNode* root)
{//空樹返回0if (root == NULL){return 0;}//左子樹和右子樹均為空則為葉子節(jié)點(diǎn)if (root->left == NULL && root->right == NULL){return 1;}//葉子節(jié)點(diǎn)數(shù)等與左右葉子數(shù)之和return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}//返回x所在的節(jié)點(diǎn)
BTNode* TreeFind(BTNode* root, BTDataType x)
{//空樹返回NULLif (root == NULL){return NULL;}//根節(jié)點(diǎn)返回root的地址 if (root->data == x){return root;}//先在左子樹找BTNode* lret = TreeFind(root->left, x);if (lret){return lret;}//左子樹沒找到，去右子樹找BTNode* rret = TreeFind(root->right, x);if (rret){return rret;}//不推薦，可讀性不強(qiáng)，不容易理解//return TreeFind(root->right, x);return NULL;
}BTNode* BTreeCreate(char* a, int* pi)
{//輸入字符為‘#’returnif (a[*pi] == '#'){(*pi)++;return NULL;}//創(chuàng)建新節(jié)點(diǎn)BTNode* root = (BTNode*)malloc(sizeof(BTNode));//空間未開辟成功，退出程序if (root == NULL){perror("malloc fail");exit(-1);}//數(shù)組的字符賦給根節(jié)點(diǎn)root->data = a[*pi];(*pi)++;root->left = BTreeCreate(a, pi);    //遞歸創(chuàng)建左子樹root->right = BTreeCreate(a, pi);  //遞歸創(chuàng)建右子樹return root;
}
// 判斷二叉樹是否是完全二叉樹
int BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);if (front == NULL)break;QueuePop(&q);QueuePush(&q, root->left);QueuePush(&q, root->right);}// 遇到空以后，后面全是空，則是完全二叉樹// 遇到空以后，后面存在非空，則不是完全二叉樹while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);if (front != NULL){QueueDestroy(&q);return false;}QueuePop(&q);}return true;
}// 銷毀二叉樹
void BinaryTreeDestroy(BTNode* root)
{if (root == NULL)return;// 通過后續(xù)遍歷來銷毀節(jié)點(diǎn)BinaryTreeDestroy(root->left);BinaryTreeDestroy(root->right);// 此處置空不會(huì)影響外面，需要在外面進(jìn)行置空free(root);
}

3.test.c

#include "BTree.h"int main()
{//創(chuàng)建二叉樹BTNode* root = CreateTree();//先序遍歷二叉樹PreOrder(root);printf("\n");//計(jì)算二叉樹節(jié)點(diǎn)個(gè)數(shù)printf("Tree size:%d\n", TreeSize(root));printf("Tree size:%d\n", TreeSize(root));//計(jì)算二叉樹高度printf("Tree Height:%d\n", TreeHeight(root));//計(jì)算第k層節(jié)點(diǎn)個(gè)數(shù)printf("Tree KLevel:%d\n", TreeKLevel(root, 1));printf("Tree KLevel:%d\n", TreeKLevel(root, 2));printf("Tree KLevel:%d\n", TreeKLevel(root, 3));printf("Tree KLevel:%d\n", TreeKLevel(root, 4));//查找x所在的節(jié)點(diǎn)BTNode* ret = TreeFind(root, 7);printf("ret=%p\n", ret);printf("retbefore:%d\n", ret->data);//修改x所在的節(jié)點(diǎn)的值ret->data *= 10;printf("retafter:%d\n", ret->data);//計(jì)算二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)printf("Tree LeafSize:%d\n", TreeLeafSize(root));//測試創(chuàng)建二叉樹//char str[100];       //創(chuàng)建數(shù)組//scanf("%s", str);    //輸入字符//int i = 0;           //記錄數(shù)組的下標(biāo)遞歸i的值不會(huì)改變，所以傳i的地址！！！//BTNode* root = BTreeCreate(str, &i);//InOrder(root);return 0;
}

4.Queue.h

#pragma once   //防止頭文件被重復(fù)包含//包含頭文件
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef char BTDataType;
typedef struct BinaryTree
{BTDataType data;struct BinaryTree* left;struct BinaryTree* right;
}BTNode;//結(jié)構(gòu)和符號(hào)的定義
typedef int QDataType;  //數(shù)據(jù)類型重定義//定義隊(duì)列的一個(gè)節(jié)點(diǎn)
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;   //記錄隊(duì)列的頭QNode* tail;   //記錄隊(duì)列的尾int size;      //記錄隊(duì)列的長度
}Queue;//函數(shù)的聲明
//初始化隊(duì)列
void QueueInit(Queue* pq);
//銷毀隊(duì)列
void QueueDestroy(Queue* pq);
//隊(duì)尾入隊(duì)列
void QueuePush(Queue* pq, QDataType x);
//對頭出隊(duì)列
void QueuePop(Queue* pq);
//獲取對頭元素
QDataType QueueFront(Queue* pq);
//獲取隊(duì)尾元素
QDataType QueueBack(Queue* pq);
//判斷隊(duì)列是否為空
bool QueueEmpty(Queue* pq);
//返回隊(duì)列元素個(gè)數(shù)
int QueueSize(Queue* pq);

5.Queue.c

#include "Queue.h"//初始化隊(duì)列
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}//銷毀隊(duì)列
void QueueDestroy(Queue* pq)
{assert(pq);//遍歷刪除QNode* cur = pq->head;while (cur){QNode* del = cur;cur = cur->next;free(del);}pq->head = pq->tail = NULL;
}//隊(duì)尾入隊(duì)列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//開辟新節(jié)點(diǎn)QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}else{//節(jié)點(diǎn)的數(shù)據(jù)復(fù)制為x，指針置為空newnode->data = x;newnode->next = NULL;}//空隊(duì)列在隊(duì)列頭部if (pq->head == NULL){pq->head = pq->tail = newnode;}else{//尾指針后移pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}//對頭出隊(duì)列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));  //隊(duì)列為空時(shí)不能出隊(duì)列//只有一個(gè)元素的時(shí)候，出隊(duì)列之后，頭尾指針都置為空if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* del = pq->head;pq->head = pq->head->next;free(del);del = NULL;}pq->size--;
}//獲取對頭元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}//獲取隊(duì)尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}//判斷隊(duì)列是否為空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL && pq->tail == NULL;
}//返回隊(duì)列元素個(gè)數(shù)
int QueueSize(Queue* pq)
{assert(pq);/*int count = 0;QNode* cur = pq->head;while (cur){cur = cur->next;count++;}return count;*/return pq->size;
}