僅不到三萬字輕松了解二叉樹和堆

前言

這里并不可能把所有樹的結構都在此篇文章進行詳細介紹，我會通過步步延伸的方式去了解樹

樹 ? 二叉樹 ? 搜索二叉樹 ? 平衡搜索二叉樹 (AVL樹和紅黑樹) ? M叉多叉平衡搜索樹 (B樹和B+樹)

一、樹概念及結構

💦 樹的概念

樹是一種非線性的資料結構，它是由 n (n>=0) 個有限結點組成一個具有層次關系的集合，
把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下，

1?? 有一個特殊的結點，稱為根結點，根節點沒有前驅結點

2?? 除根節點外，其余結點被分為 M (M>0) 個互不相交的集合 T1、T2 … 、Tm，其中每一個集合 Ti (1<=i<=m) 又是一棵結構與樹類似的子樹，每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼

3?? 因此，樹是遞回定義的

? 注意：樹形結構中，子樹之間不能有交集，否則就不是樹形結構

? 子樹是不相交的

? 除了根節點外，每個節點有且僅有一個父節點

? 一棵 N 個節點的樹有 N-1 條連

💦 樹的相關概念

1?? 節點的度：一個節點含有的子樹的個數稱為該節點的度； 如上圖：A 的為6

2?? 葉節點或終端節點：度為0的節點稱為葉節點； 如上圖：B、C、H、I…等節點為葉節點

3?? 非終端節點或分支節點：度不為0的節點； 如上圖：D、E、F、G…等節點為分支節點

4?? 雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點； 如上圖：A 是 B 的父節點

5?? 孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點； 如上圖：B 是 A 的孩子節點

6?? 兄弟節點：具有相同父節點的節點互稱為兄弟節點 (這里指的是親兄弟，而非表堂兄弟)； 如上圖：B、C 是兄弟節點

7?? 樹的度：一棵樹中，最大的節點的度稱為樹的度； 如上圖：樹的度為 6

8?? 節點的層次：從根開始定義起，根為第 1 層，根的子節點為第 2 層， 以此類推；如上圖：樹的層次為 4

9?? 樹的高度或深度：樹中節點的最大層次 (這里有 2 種說法：其一，根算 0，其二，根算 1)； 如上圖：樹的高度為 4
? 這里推薦理解其二，因為：
? 當要算空樹的高度是多少時，按其一的理解，高度是 -1；按其二的理解，高度是 0
? 當要算只有一個根節點的樹的高度是多少時，按其一的理解，高度是 0；按其二的理解，高度是 1

🔟 堂兄弟節點：雙親在同一層的節點互為堂兄弟；如上圖：H、I 互為兄弟節點

1??1?? 節點的祖先：從根到該節點所經分支上的所有節點；如上圖：A 是所有節點的祖先

1??2?? 子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫，如上圖：所有節點都是 A 的子孫

1??3?? 森林：由 m(m>0) 棵互不相交的樹的集合稱為森林，并查集就是一個森林

💦 樹的表示

樹結構相對線性表就比較復雜了，要存盤表示起來比較麻煩，既要保存值域，也要保存結點和結點之間的關系，
實際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等，我們這里就簡單的了解其中最常用的孩子兄弟表示法，

? 對于樹的定義其實并不好定義，因為其中有許多未知的因素

1、除非明確說明樹的度是多少，比如樹的度是 6

struct TreeNode
{
	int data;
	//這種結構其實是很浪費的，因為最大的度是6,但往下可能并沒有那么多
	struct TreeNode* subs[6];//指標陣列
}

2、如果沒有說明樹的度是多少，可以使用順序表存盤

struct TreeNode
{
	int data;
	SeqList subs;//順序表中存盤的是節點的指標
	//vector<struct TreeNode*>subs;//在C++學了模板后可以這樣定義
}

3、雙親表示法

struct TreeNode
{
	int data;
	struct TreeNode* parent;
}

4、左孩子右兄弟表示法 (比較實用)

typedef int DataTpye;
struct Node
{
	struct Node* _firstChild1;//第一個孩子節點(如有多個孩子，那么只指向最左邊的)
	struct Node* _pNextBrother;//指向下一個兄弟節點
	DataType _data;//節點中的資料域
}

💦 樹在實際中的運用 (表示檔案系統的目錄樹結構)

????? 以下為 Linux 下的目錄樹 ?

二、二叉樹概念及結構

💦 二叉樹的概念

一棵二叉樹是節點的一個有限集合，該集合：
1、或者為空
2、由一個根節點加上兩棵別稱為左子樹和右子樹的二叉樹組成

1?? 二叉樹不存在度大于 2 的結點

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

? 注意：對于任意的二叉樹都是由以下幾種情況復合而成的：

? 現實中的存在這種二叉樹嗎 ?

???在人為的干涉的情況下一定是存在的，因為沒有什么是一電鋸解決不了的事

當然也不乏有大自然的鬼斧神工，注意區分普通的樹

💦 特殊的二叉樹

1?? 滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，也就是說，如果一個二叉樹的層數為 K，且結點總數是 2^k - 1，則它就是滿二叉樹，

2?? 完全二叉樹：完全二叉樹的前 k - 1 層都滿的，第 k 層不一定滿 (這就意味著滿二叉樹是完全二叉樹，但完全二叉樹不一定是滿二叉樹)，但是從最后一層從左到右必須是連續的，也就是說完全二叉樹中度為 1 的節點最少 0 個，最多 1 個，完全二叉樹是效率很高的資料結構，完全二叉樹是由滿二叉樹而引出來的，對于深度為 K 的，有 n 個結點的二叉樹，且每個結點都與深度為 K 的滿二叉樹中編號從 1 至 n 的結點 一一 對應稱之為完全二叉樹，要注意的是滿二叉樹是一種特殊的完全二叉樹，

? 滿二叉樹的節點個數就是等比求和

2⁰ + 2¹ + 2² + … 2^(k-1)

利用公式所以滿二叉樹的節點個數就是 2^k - 1

? 完全二叉樹的節點個數

最多：2^k - 1 ?這是滿二叉樹

最少：2^(k-1) - 1 + 1 ?->? 2^(k-1)

???2^(k-1) - 1 這是前 k-1 層節點的個數，+1 則是第 k 層至少一個

💦 二叉樹的性質

1?? 若規定根節點的層數為 1，則一棵非空二叉樹的第 i 層上最多有 2^(i-1) 個結點

2?? 若規定根節點的層數為 1，則深度為 h 的二叉樹的最大結點數是 2^h - 1

3?? 對任何一棵二叉樹, 如果度為 0 其葉結點個數為 n?, 度為 2 的分支結點個數為 n?,則有 n?＝ n?＋1

4?? 若規定根節點的層數為 1，具有 n 個結點的滿二叉樹的深度為 h = log?(n+1) ?ps：log?(n+1)是 log 以 2 為底， n+1 的對數

5?? 對于具有 n 個結點的完全二叉樹，如果按照從上至下從左至右的陣列順序對所有節點從 0 開始編號，則對于序號為 i 的結點有：

??? 若 i>0，i 位置節點的雙親序號：(i-1)/2；i=0，i 為根節點編號，無雙親節點

??? 若 2i+1<n，左孩子序號：2i+1，2i+1>=n 否則無左孩子

??? 若 2i+2<n，右孩子序號：2i+2，2i+2>=n 否則無右孩子

💦 二叉樹的概念選擇題

1、某二叉樹共有 399 個結點，其中有 199 個度為 2 的節點，則該二叉樹中的葉子節點數為（ ）

A. 不存在這樣的二叉樹

B. 200

C. 198

D. 199

📝 分析：這里的葉子節點就是度為 0 的節點，已知二叉樹中度為 2 的節點為 199 個，則度為 0 的節點等于度為 2 的節點 +1，所以選擇 B 選項

---

2、下列資料結構中，不適合采用順序存盤結構的是（ ）注意此題可以先了解下面的二叉樹的存盤結構在來做

A. 非完全二叉樹

B. 堆

C. 佇列

D. 堆疊

---

3、在具有 2n 個節點的完全二叉樹中，葉子節點個數為（ ）

A. n

B. n+1

C. n-1

D. n/2

📝 分析：

假設度為 0 的個數是 x0，度為 2 的個數是 x2，度為 1 的個數是 x1，那么：

? x0 + x1 + x2 = 2n

? x0 = x2 + 1

由 x0 = x2 + 1 得到 x2 = x0 - 1

所以 x0 + x1 + x2 = 2n 同 x0 + x1 + x0 - 1 = 2n 同 2x0 + x1 - 1 = 2n

這時再回過頭想想完全二叉樹中度為 1 的節點最少 0 個，最多就只有 1 個，

所以 x1 = 0 or 1

所以 2x0 + x1 - 1 = 2n 就有 2 種情況：

? 2x0 + 0 - 1 = 2n

? 2x0 + 1 - 1 = 2n

所以結果一目了然，當 x1 = 0 時，x0為小數，顯然不可能；當 x1 = 1 時滿足，所以選擇 A 選項

---

4、一棵完全二叉樹的節點數為 531 個，那么這棵樹的高度為（ ）

A. 11

B. 10

C. 8

D. 12

📝 分析：

假設完全二叉樹的高度是 h，那么：最多有 2^h-1 個節點；最少有 2^(h-1) 個節點

? h = 11 時：最多 2047；最少 2014，所以不合理

? h = 10 時：最多 1023；最少 512，所以合情合理

? h = 8 時：最多 255；最少 128，所以不合理

? h = 12 時：最多 4095；最少 2048，所以不合理

所以選擇 B 選項

---

5、一個具有 767 個節點的完全二叉樹，其葉子節點個數為 ( )

A. 383

B. 384

C. 385

D. 386

📝 分析：此題類似于第 3 題

假設度為 0 的個數是 x0，度為 2 的個數是 x2，度為 1 的個數是 x1，那么：

? x0 + x1 + x2 = 767

? x0 = x2 + 1

由 x0 = x2 + 1 得到 x2 = x0 - 1

所以 x0 + x1 + x2 = 767 同 x0 + x1 + x0 - 1 = 767 同 2x0 + x1 - 1 = 767

這時再回過頭想想完全二叉樹中度為 1 的節點最少 0 個，最多就只有 1 個，

所以 x1 = 0 or 1

所以 2x0 + x1 - 1 = 767 就有 2 種情況：

? 2x0 + 0 - 1 = 767

? 2x0 + 1 - 1 = 767

所以結果一目了然，當 x1 = 0 時，滿足條件；當 x1 = 1 時，不滿足條件，所以選擇 B 選項

💦 二叉樹的存盤結構

二叉樹一般可以使用兩種結構存盤，一種順序結構，一種鏈式結構：，

??1?? 順序存盤：順序結構存盤就是使用陣列來存盤，它只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費，而現實使用中只有堆才會使用陣列來存盤，二叉樹順序存盤在物理上是一個陣列，在邏輯上是一顆二叉樹，如下圖所見，陣列只適合存盤完全二叉樹或者滿二叉樹，

??? 怎么表示下標和樹的關系 ?

?????下標表示樹中父子關系的公式：

?????左孩子和右孩子

???????leftchild = parent * 2 + 1

???????rightchild = parent * 2 + 2

?????父親 (這里無論是左孩子還是右孩子都適用于以下公式)

???????parent = (child - 1) / 2

??2?? 鏈式存盤：二叉樹的鏈式存盤結構是指用鏈表來表示一棵二叉樹，即用鏈表來指示元素的邏輯關系，通常的方法是鏈表中每個結點由三個域組成，資料域和左右指標域，左右指標分別用來給出該結點左孩子和右孩子所在的鏈的存盤地址，鏈式結構又分為二叉鏈和三叉鏈，現階段本篇文章我們只了解二叉鏈，在以后的文章內寫到高階資料結構時，如紅黑樹等才會用到三叉鏈，

??? 如何定義二叉鏈和三叉鏈 ?

????二叉鏈只能通過父親找孩子，類似于單向鏈表；而三叉鏈不僅能通過父親找孩子，還能通過孩子找父親，類似于雙向鏈表，

typedef int BTDataType;
//二叉鏈
struct BinaryTreeNode
{
	struct BinaryTreeNode* _pLeft; //指向當前節點的左孩子
	struct BinaryTreeNode* _pRight; //指向當前節點的右孩子	
	BTDataType _data; //當前節點的值域 
}

//三叉鏈
struct BinaryTreeNode
{
	struct BinaryTreeNode* _pParent; //指向當前節點的父親
	struct BinaryTreeNode* _pLeft; //指向當前節點的左孩子
	struct BinaryTreeNode* _pRight; //指向當前節點的右孩子
	BTDataType _data; //當前節點的值域
}

三、二叉樹順序結構及實作

💦 二叉樹的順序結構

普通的二叉樹是不適合用陣列來存盤的，因為可能會存在大量的空間浪費，
而完全二叉樹更適合使用順序結構存盤，現實中我們通常把堆 (一種二叉樹) 使用順序結構的陣列來存盤，
需要注意的是這里的堆和作業系統虛擬行程地址空間中的堆是兩回事，一個是資料結構，一個是作業系統中管理記憶體的一塊區域分段，

??? 作業系統和資料結構這兩門學科中都有堆疊和堆的概念，如何區分 ?

💦 堆的概念及結構

如果有一個關鍵碼的集合K = {k?, k?, k?,…，k_n-1}，把它的所有元素按完全二叉樹的順序存盤方式存盤，在一個一維陣列中，并滿足：K_i <= K_2*i+1 且 K_i <= K_2*i+2 (K_i >= K_2*i+1 且 K_i >= K_2*i+2) i = 0，1，2…，則稱為小堆 (或大堆)，將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆，

????? 堆的性質 ?

??????? 堆中某個節點的值總是不大于或不小于其父節點的值；

??????? 堆總是一棵完全二叉樹；

????---------------------------------------Cut-----------------------------------------

????? 大(根)堆和小(根)堆 ?

??????? 大(根)堆，樹中所有父親都小于或者等于孩子，且大堆的根是最小值；

??????? 小(根)堆，樹中所有父親都大于或者等于孩子，且小堆的根是最大值；

💦 堆的概念選擇題

1、下列關鍵字序列為堆的是（ ）

A. 100, 60, 70, 50, 32, 65

B. 60, 70, 65, 50, 32, 100

C. 65, 100, 70, 32, 50, 60

D. 70, 65, 100, 32, 50, 60

E. 32, 50, 100, 70, 65, 60

F. 50, 100, 70, 65, 60, 32

📝 分析：根據堆的概念分析，A 選項為大根堆；

---

2、注，請理解下面堆應用的知識再做，已知小根堆為 8, 15, 10, 21, 34, 16, 12，洗掉關鍵字 8 之后需重建堆，在此程序中，關鍵字之間的比較次數是（ ）

A. 1

B. 2

C. 3

D. 4

📝 分析：

此題考查的是建堆的程序

所以選擇 C 選項

---

3、注，請理解下面堆應用的知識再做，一組記錄排序碼為 (5 11 7 2 3 17)，則利用堆排序方法建立的初始堆為（ ）

A. (11 5 7 2 3 17)

B. (11 5 7 2 17 3)

C. (17 11 7 2 3 5)

D. (17 11 7 5 3 2)

E. (17 7 11 3 5 2)

F. (17 7 11 3 2 5)

📝 分析：

此題考查的是堆排序建堆的程序

根據下面堆排序的程序分析，選擇 C 選項

---

4、、注，請理解下面堆應用的知識再做，最小堆 [0, 3, 2, 5, 7, 4, 6, 8]，在洗掉堆頂元素0之后，其結果是（ ）

A. [3，2，5，7，4，6，8]

B. [2，3，5，7，4，6，8]

C. [2，3，4，5，7，8，6]

D. [2，3，4，5，6，7，8]

📝 分析：

此題考查的是 Pop 堆頂后，重新建堆的變化

所以選擇 C 選項

---

💦 堆的實作

1、堆向下調整演算法

現在我們給出一個陣列，邏輯上看做一顆完全二叉樹，我們通過從根節點開始的向下調整演算法可以把它調整成一個小堆，
向下調整演算法有一個前提：左右子樹必須是一個堆 (包括大堆和小堆)，才能調整，

????? 建堆 ?
????????有一個隨機值的陣列，把它理解成完全二叉樹，并模擬成堆 (大堆/小堆)

????-------------------------------------------------------Cut---------------------------------------------------------

int array[] = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37} 

????? 觀察上面這組資料 ?
????????根下面的左右子樹都是小根堆，其實堆向下調整演算法就是針對這種特殊資料結構

????-------------------------------------------------------Cut---------------------------------------------------------

????? 針對于這種型別的資料應該怎么調堆 ?
?????? 思路：從根開始與左右孩子比較，如果孩子比父親小，則兩兩交換位置，再繼續往下調，直到左右孩子都比父親大或者調到葉子
???? 具體見下圖：

????-------------------------------------------------------Cut---------------------------------------------------------

????? 如果不滿足左右子樹是堆，怎么調整 ?

int array[] = {27, 37, 28, 18, 19, 34, 65, 25, 49, 15} 

????根的左右子樹 37、28 都不滿足：這里的想法就是先讓左右子樹先滿足；而對于左右子樹 37、28 來說又需要讓 37 先滿足；這樣依此類推直至滿足堆的條件，那干脆就從倒數的第一棵樹，也就是倒數的第一個非葉子節點開始調整

2、堆的創建

????? 這里從倒數的第一個非葉子節點開始調整 ?

#include<stdio.h>

//實作父子交換的函式
void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
//實作調整
void AdjustDown(int* arr, int sz, int parent)
{
	//確定左孩子的下標
	int child = parent * 2 + 1;
	//孩子的下標超出陣列的范圍就停止
	while (child < sz)
	{
		//確定左右孩子中較小/大的那個
			//左孩子大于右孩子，所以讓child記錄較小孩子的下標 || (arr[child]<arr[child+1]記錄較大孩子的下標)
		if (arr[child] > arr[child + 1] && child + 1 < sz)
		{
			child++; //(當只有一個左孩子時，會越界，且后面使用時會發生非法訪問)
		}
		//判斷父親和小孩子
			//小孩子小于父親，則交換，且繼續調整 || (arr[child]>arr[parent]大孩子大于父親，則交換，且繼續調整)
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			//迭代
			parent = child;
			//重新確定左孩子的下標(當最后的葉子節點是parent時，這時去確定child會以讀的方式越界，但可以不關心)
			child = parent * 2 + 1;
		}
		//小孩子大于父親，則停止調整
		else
		{
			break;
		}
	}
}
//堆排序 -> 效率更高
void HeapSort(int* arr, int sz)
{
	//建堆
	int i = 0;
	//從最后一棵樹開始調整，也就是最后一個節點的父親
	for (i = (sz - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, sz, i);
	}
}
int main()
{
	//左右子樹都為堆
	int arr1[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
	//左右子樹都為非堆
	int arr2[] = { 27, 37, 28, 18, 19, 34, 65, 25, 49, 15 };

	HeapSort(arr1, sizeof(arr1) / sizeof(arr1[0]));
	int i = 0;
	for (i = 0; i < sizeof(arr1) / sizeof(arr1[0]); i++)
	{
		printf("%d ", arr1[i]);
	}

	printf("\n");

	HeapSort(arr2, sizeof(arr2) / sizeof(arr2[0]));
	for (i = 0; i < sizeof(arr2) / sizeof(arr2[0]); i++)
	{
		printf("%d ", arr2[i]);
	}
	return 0;
}

????💨 輸出結果：

??????小堆

??????大堆

3、堆的時間復雜度

??????? 證明建堆的時間復雜度是O(N) ?

因為堆是完全二叉樹，而滿二叉樹也是完全二叉樹，此處為了簡化使用滿二叉樹來證明
(時間復雜度本來看的就是近似值，多幾個節點不影響最終結果)

建堆的呼叫次數用 T(N) 表示：(從最后一個非葉子節點 <也就是倒數第二層> 開始，最壞的情況下：倒數第二層每個節點最多能向下調 1 次；倒數第三層每個節點最多能向下調 2 次；倒數第四層每個節點最多能向下調 3 次；)

每層節點個數 × \times × 最壞情況向下調整次數：

T(N) = 2^h-2 × \times × 1 + 2^h-3 × \times × 2 + … … + 2⁰ × \times × (h-1)

這里我們從上至下開始

T(N) = 2⁰ × \times × (h - 1) + 2¹ × \times × (h - 2) + 2² × \times × (h - 3) + 2³ × \times × (h - 4) + … … + 2^h-3 × \times × 2 + 2^h-2 × \times × 1

????? 錯位相減法 ?

??????等號左右兩邊乘個 2 得到一個新公式，再用新公式減去舊的公式，具體見下圖

4、堆的插入

先插入一個10到陣列的尾上，再進行向上調整演算法，直到滿足堆，

5、堆的洗掉

洗掉堆是洗掉堆頂的資料，將堆頂的資料和最后一個資料交換換，然后洗掉陣列最后一個資料，再進行向下調整演算法，

6、堆的代碼實作

? 注意 ?

????? 堆的初始化一般是使用陣列進行初始化的

????? 堆的插入資料不分頭插、尾插，將資料插入后，原來堆的屬性不變

??????先放在陣列的最后一個位置，再向上調整

????? 堆的洗掉資料洗掉的是堆頂的資料，將資料洗掉后，原來堆的屬性不變

??????為了效率，將第一個和最后一個元素交換，再減容，然后再調整

? 這里需要三個檔案 ?

????1?? Heap.h，用于函式的宣告

#pragma once

//頭
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>

typedef int HPDataType;

//C++ -> priority_queue 在C++里用的是優先級佇列，其底層就是一個堆
//大堆
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
//函式的宣告
//交換
void Swap(int* px, int* py);
//向下調整
void AdjustDown(int* arr, int n, int parent);
//向上調整
void AdjustUp(int* a, int child);
//使用陣列進行初始化
void HeapInit(HP* php, HPDataType* a, int n);
//回收空間
void HeapDestroy(HP* php);
//插入x，保持它繼續是堆
void HeapPush(HP* php, HPDataType x); 
//洗掉堆頂的資料，保持它繼續是堆
void HeapPop(HP* php);
//獲取堆頂的資料，也就是最值
HPDataType HeapTop(HP* php);
//判空
bool HeapEmpty(HP* php);
//堆的資料個數
int HeapSize(HP* php);
//輸出
void HeapPrint(HP* php);

????2?? Heap.c，用于函式的定義

#include"Heap.h"


void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void AdjustDown(int* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (arr[child] < arr[child + 1] && child + 1 < n)
		{
			child++;
		}
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void HeapPrint(HP* php)
{
	assert(php);

	int i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
//1、對于HeapCreate函式，結構體不是外面傳進來的，而是在函式內部自己malloc空間，再創建的
/* 
HP* HeapCreate(HPDataType* a, int n)
{}
*/
//2、對于HeapInit函式，在外面定義一個結構體，把結構體的地址傳進來
void HeapInit(HP* php, HPDataType* a, int n)
{
	assert(php); 
	//malloc空間(當前陣列大小一樣的空間)
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//使用陣列初始化
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = n;
	php->capacity = n;
	//建堆 
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, n, i);
	}
}
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
void HeapPush(HP* php, HPDataType x)
{
	assert(php);

	//空間不夠，增容
	if (php->size == php->capacity)
	{
		HPDataType* temp = (HPDataType*)realloc(php->a, php->capacity * 2 * sizeof(HPDataType));
		if (temp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			php->a = temp;	
		}
		php->capacity *= 2;
	}
	//將x放在最后
	php->a[php->size] = x;
	php->size++;
	//向上調整
	AdjustUp(php->a, php->size - 1);
}
void HeapPop(HP* php)
{
	assert(php);
	//沒有資料洗掉就報錯
	assert(!HeapEmpty(php));
	//交換首尾
	Swap(&php->a[0], &php->a[php->size-1]);
	php->size--;
	//向下調整
	AdjustDown(php->a, php->size, 0);
}
HPDataType HeapTop(HP* php)
{
	assert(php);
	//沒有資料獲取就報錯
	assert(!HeapEmpty(php));
	
	return php->a[0];
}
int HeapSize(HP* php)
{
	assert(php);

	return php->size;
}

????3?? Test.c，用于測驗函式

#include"Heap.h"

void TestHeap()
{
	int arr[] = { 27, 37, 28, 18, 19, 34, 65, 25, 49, 15 };
	HP hp;
	HeapInit(&hp, arr, sizeof(arr)/sizeof(arr[0]));
	HeapPrint(&hp);
	HeapPush(&hp, 18);
	HeapPrint(&hp);
	HeapPush(&hp, 98);
	HeapPrint(&hp);
	printf("\n\n");
	//將堆這資料結構實作好后，我們就可以利用這些介面實作排序
	while(!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));	
		HeapPop(&hp);
	}
	printf("\n");
	
}
int main()
{
	TestHeap();
	return 0;
}

💦 堆的應用

1、堆排序

????? 堆創建后，如何進行排序 (升序、降序) ?
????????升序建大堆；降序建小堆，不是說升序建小堆；降序建大堆不行，而是因為不好：
????????如果排升序建小堆：
??????????1、選出最小的數，最小的數就放在第一個位置
??????????2、接著就要選次小的數，再選次小的數 … … ，不斷的選下去，如何選 ？
??????????? 只能對剩下的 sz-1、sz-2、sz-3 … 個數繼續建堆，可想這樣的代價是很高的 —— 建堆的時間
??????????? 復雜度是 O(N)，整個時間復雜度就是 O(N²)，堆的價值沒有體現，還不如直接回圈遍歷
????????如果排升序建大堆：
??????????1、選出最大的數，與最后一個數交換位置
??????????2、怎么選出次大、次次大 ？
??????????? 堆的結構沒有被破壞，且最后一個數不看做堆，左右子樹依舊是大堆，向下調整即可
??????????? 最多調整 log₂N 次，整體的時間復雜度是 O(N*log₂N）
????????對比效率：

	1000	1000000
O(N2)	1000000	1000000000000
O(N*log2N)	10000	20000000

????? 動圖畫解思路 ?

????????升序建大堆

????????降序建小堆

#include<stdio.h>

void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void AdjustDown(int* arr, int sz, int parent)
{
	int child = parent * 2 + 1;
	while (child < sz)
	{
		if (arr[child] > arr[child + 1] && child + 1 < sz)
		{
			child++; 
		}
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* arr, int sz)
{
	int i = 0;
	for (i = (sz - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, sz, i);
	}
	//排升序 > 建大堆
	//排降序 > 建小堆
	int end = sz - 1;
	//每次回圈都將最小或最大的值與最后一個值交換，且最后一個值不看作堆的內容
	while (end > 0)
	{
		//與最后一個值交換
		Swap(&arr[0], &arr[end]);
		//調整
		AdjustDown(arr, end, 0);
		end--;
	}

}
int main()
{
	//左右子樹都為堆
	int arr1[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
	//左右子樹都為非堆
	int arr2[] = { 27, 37, 28, 18, 19, 34, 65, 25, 49, 15 };

	HeapSort(arr1, sizeof(arr1) / sizeof(arr1[0]));
	int i = 0;
	for (i = 0; i < sizeof(arr1) / sizeof(arr1[0]); i++)
	{
		printf("%d ", arr1[i]);
	}

	printf("\n");

	HeapSort(arr2, sizeof(arr2) / sizeof(arr2[0]));
	for (i = 0; i < sizeof(arr2) / sizeof(arr2[0]); i++)
	{
		printf("%d ", arr2[i]);
	}
	return 0;
}

????💨 輸出結果：

??????升序

??????降序

3、TOP - K問題

TOP-K問題：即求資料結合中前K個最大的元素或者最小的元素，一般情況下資料量都比較大，
比如：CSDN總榜前10、世界500強、富豪榜等，

? 如何求 ?

🔑 方法 1：

????排序，時間復雜度 O(N*logN)

🔑 方法 2：

????建一個 N 個數的堆(優先級佇列)，不斷選數，選出前 K 個，時間復雜度 O(N+K*log(N))

????? 假設 N 是十億，顯然前兩個方法都不適用 ?

🔑 方法 3：

????對于 Top-K 問題，能想到的最簡單直接的方式就是排序，但是：如果資料量非常大，排序就不太可取了(可能資料都不能一下子全部加載到記憶體中)，最佳的方式就是用堆 (優化方法 2) 來解決，基本思路如下：

????1?? 用資料集合中前 K 個元素來建堆

??????? 前k個最大的元素，則建小堆

??????? 前k個最小的元素，則建大堆

????2?? 用剩余的N-K個元素依次與堆頂元素來比較，不滿足則替換堆頂元素

??????? 將剩余 N-K 個元素依次與堆頂元素比完之后，堆中剩余的 K 個元素就是所求的前 K 個最小或者最大的元素

? 模擬 ?

????創建亂數種子，生成亂數

? 怎么知道前十個數就是 TOP - 10 ?

????默認隨機生成的數都是小于 1000000 的，然后給隨機位置的 10 個數都是比 1000000 要大的，把這 10 個數選出來就說明演算法是對的

---

? 這里需要三個檔案 ?

????1?? TOP-K.h，用于函式的宣告

#pragma once

//頭
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<time.h>

typedef int HPDataType;

//C++ -> priority_queue 在C++里用的是優先級佇列，其底層就是一個堆
//大堆
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
//函式的宣告
//交換
void Swap(int* px, int* py);
//向下調整
void AdjustDown(int* arr, int n, int parent);
//向上調整
void AdjustUp(int* a, int child);
//使用陣列進行初始化
void HeapInit(HP* php, HPDataType* a, int n);
//回收空間
void HeapDestroy(HP* php);
//插入x，保持它繼續是堆
void HeapPush(HP* php, HPDataType x);
//洗掉堆頂的資料，保持它繼續是堆
void HeapPop(HP* php);
//獲取堆頂的資料，也就是最值
HPDataType HeapTop(HP* php);
//判空
bool HeapEmpty(HP* php);
//堆的資料個數
int HeapSize(HP* php);
//輸出
void HeapPrint(HP* php);

????2?? TOP-K.c，用于函式的定義

#include"TOP-K.h"

void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void AdjustDown(int* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (arr[child] > arr[child + 1] && child + 1 < n)
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void HeapPrint(HP* php)
{
	assert(php);

	int i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
//1、對于HeapCreate函式，結構體不是外面傳進來的，而是在函式內部自己malloc空間，再創建的
/*
HP* HeapCreate(HPDataType* a, int n)
{}
*/
//2、對于HeapInit函式，在外面定義一個結構體，把結構體的地址傳進來
void HeapInit(HP* php, HPDataType* a, int n)
{
	assert(php);
	//malloc空間(當前陣列大小一樣的空間)
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//使用陣列初始化
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = n;
	php->capacity = n;
	//建堆 
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, n, i);
	}
}
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
void HeapPush(HP* php, HPDataType x)
{
	assert(php);

	//空間不夠，增容
	if (php->size == php->capacity)
	{
		HPDataType* temp = (HPDataType*)realloc(php->a, php->capacity * 2 * sizeof(HPDataType));
		if (temp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			php->a = temp;
		}
		php->capacity *= 2;
	}
	//將x放在最后
	php->a[php->size] = x;
	php->size++;
	//向上調整
	AdjustUp(php->a, php->size - 1);
}
void HeapPop(HP* php)
{
	assert(php);
	//沒有資料洗掉就報錯
	assert(!HeapEmpty(php));
	//交換首尾
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	//向下調整
	AdjustDown(php->a, php->size, 0);
}
HPDataType HeapTop(HP* php)
{
	assert(php);
	//沒有資料獲取就報錯
	assert(!HeapEmpty(php));

	return php->a[0];
}
int HeapSize(HP* php)
{
	assert(php);

	return php->size;
}

????3?? Test.c，用于函式的測驗

#include"TOP-K.h"

void PrintTopK(int* a, int n, int k)
{
	HP hp;
	HeapInit(&hp, a, k);

	int i = 0;
	for (i = k; i < n; i++)
	{
		//比較堆頂的資料
		if (a[i] > HeapTop(&hp))
		{
			HeapPop(&hp);
			HeapPush(&hp, a[i]);
		}
	}

	HeapPrint(&hp);
	HeapDestroy(&hp);
}
void TestTopk()
{
	int n = 100000;
	int* a = (int*)malloc(sizeof(int)*n);
	//創建亂數種子
	srand((unsigned int)time(0));
	//生成亂數
	for (size_t i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	//如果找出這10個數，說明TOP-K演算法是正確的
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2335] = 1000000 + 6;
	a[9999] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;

	PrintTopK(a, n, 10);
}

int main()
{
	TestTopk();
	return 0;
}

四、二叉樹鏈式結構及實作

💦 前置說明

普通二叉樹的增刪查改復雜且沒有意義，所以我們并不打算學習它的增刪查改，主要是學習它的結構
在學習二叉樹的基本操作前，需先要創建一棵二叉樹，然后才能學習其相關的基本操作，
由于現在對二叉樹結構掌味訓不夠深入，為了降低學習成本，此處手動快速創建一棵簡單的二叉樹，以此快速進入二叉樹操作學習，等二叉樹結構了解的差不多時，我們反過頭再來研究二叉樹真正的創建方式，

? 以下代碼并不是創建二叉樹的方式，真正創建二叉樹方式后序詳解重點講解

? 回顧二叉樹 ?

??1?? 空樹

??2?? 非空：根節點，根節點的左子樹、根節點的右子樹組成

💨 從概念中可以看出，二叉樹定義是遞回式的，因此后序基本操作中基本都是按照該概念實作的，

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right; 
}BTNode; 

BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode('A');
	BTNode* node2 = BuyNode('B');
	BTNode* node3 = BuyNode('C');
	BTNode* node4 = BuyNode('D');
	BTNode* node5 = BuyNode('E');
	BTNode* node6 = BuyNode('F');

	node1->_left = node2;
	node1->_right = node3;
	node2->_left = node4;
	node3->_left = node5;
	node3->_right = node6;
	
	return node1; 
 }
 

💦 二叉樹的遍歷

學習二叉樹結構，最簡單的方式就是遍歷，所謂二叉樹遍歷 (Traversal) 是按照某種特定的規則，依次對二叉樹中的節點進行相應的操作，并且每個節點只操作一次，
訪問結點所做的操作依賴于具體的應用問題， 遍歷是二叉樹上最重要的運算之一，也是二叉樹上進行其它運算的基礎，

其實這種就是遞回的思想，且在現實生活中也經常使用到 —— 比如 1 位校長要統計學校的人數，他不可能親自去挨個數，一般是通過院長、系主任、輔導員、班長、舍長的層層反饋才得到結果的

1?? 前序遍厲：?根 ??左子樹??右子樹

2?? 中序遍厲：?左子樹 ??根??右子樹

3?? 后序遍厲：?左子樹??右子樹??根

4?? 層序遍厲：?一層一層的遍

1、前序、中序以及后序遍歷

1?? 前序遍歷(Preorder Traversal 亦稱先序遍歷) —— 訪問根結點的操作發生在遍歷其左右子樹之前，

2?? 中序遍歷(Inorder Traversal) —— 訪問根結點的操作發生在遍歷其左右子樹之中（間），

3?? 后序遍歷(Postorder Traversal) —— 訪問根結點的操作發生在遍歷其左右子樹之后，

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

// 二叉樹前序遍歷
void PreOrder(BTNode* root);
// 二叉樹中序遍歷
void InOrder(BTNode* root);
// 二叉樹后序遍歷
void PostOrder(BTNode* root);

---

? 實作 ?

#include<stdio.h>
#include<stdlib.h>

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right; 
}BTNode; 

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = malloc(sizeof(BTNode));
	node->_data = x;
	node->_left = NULL;
	node->_right = NULL;
	
	return node;
}

BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode('A');
	BTNode* node2 = BuyNode('B');
	BTNode* node3 = BuyNode('C');
	BTNode* node4 = BuyNode('D');
	BTNode* node5 = BuyNode('E');
	BTNode* node6 = BuyNode('F');

	node1->_left = node2;
	node1->_right = node3;
	node2->_left = node4;
	node3->_left = node5;
	node3->_right = node6;
	
	return node1; 
 }
//二叉樹前序遍歷
void PreOrder(BTNode* root)
{
	if(root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->_data);
	PreOrder(root->_left);
	PreOrder(root->_right);
}
//二叉樹中序遍歷
void InOrder(BTNode* root)
{
	if(root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->_left);
	printf("%c ", root->_data);
	InOrder(root->_right);
}
//二叉樹后序遍歷
void PostOrder(BTNode* root)
{
	if(root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->_left);
	PostOrder(root->_right);
	printf("%c ", root->_data);
}
//構建二叉樹
void TestTree()
{
	BTNode* root = CreatBinaryTree();
	PreOrder(root);
}

int main()
{
	TestTree();
	return 0;
}

📝 分析：

以上真正的核心代碼是 PreOrder、InOrder、PostOrder 函式的遞回呼叫短短幾行代碼卻執行了如此復雜的計算，這里豌豆太懶了就只畫一個展開圖：

? PreOrder ?

2、層序遍歷

除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進行層序遍歷，
設二叉樹的根節點所在層數為1，層序遍歷就是從所在二叉樹的根節點出發，首先訪問第一層的樹根節點，然后從左到右訪問第2層上的節點，接著是第三層的節點，
以此類推，自上而下，自左至右逐層訪問樹的結點的程序就是層序遍歷，

// 層序遍歷
void LevelOrder(BTNode* root);

💦 節點個數以及高度等

? 實作以下介面 ?

// 二叉樹節點個數
int BinaryTreeSize(BTNode* root);
// 二叉樹葉子節點個數
int BinaryTreeLeafSize(BTNode* root);
// 二叉樹第k層節點個數
int BinaryTreeLevelKSize(BTNode* root, int k);
//二叉樹深度/高度
int BinaryTreeDepth(BTNode* root)
// 二叉樹查找值為x的節點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

? 實作代碼 ?

??? BinaryTreeSize ?

????🔑 核心思想1 ：使用前序 || 中序 || 后序遍歷，全域變數記錄

????? 但是以下代碼有 Bug ：如果采用前序重復遍歷 2 次

????? 經查，問題出在全域變數上，這里只需要在第 2 次遍歷時置 0 即可

????? 在以后的知識面更大后，其實你會發現這種操作還有執行緒安全的問題

????🔑 核心思想 2：函式使用帶回傳值的方式，其內部的遞回本質上是一個后序遍厲

??? BinaryTreeLeafSize ?

????🔑 核心思想 ：以 left 和 right 為標志，如果都為 NULL，則累加

??? BinaryTreeLevelKSize ?

????🔑 核心思想 ：求當前樹的第 k 層 = 左子樹的第 k - 1 層 +　右子樹的第 k - 1 層 (當 k = 1 時，說明此層就是目標層)

??? BinaryTreeDepth ?

????🔑 核心思想 ：當前樹的深度 = max (左子樹的深度，右子樹的深度) + 1

??? BinaryTreeFind ?

????🔑 核心思想 ：

??????1、先判斷是不是當前節點，是就回傳；

??????2、先去左樹找，找到就回傳

??????3、左樹沒找到，再找右樹

#include<stdio.h>
#include<stdlib.h>

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = malloc(sizeof(BTNode));
	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}
// 二叉樹節點個數
	//1、前序遞回遍歷
int sz1 = 0;
void BinaryTreeSize1(BTNode* root)
{
	if (root == NULL)
		return;
	else
		sz1++;
	BinaryTreeSize1(root->left);
	BinaryTreeSize1(root->right);
}
//2、中序遞回遍歷
int sz2 = 0;
void BinaryTreeSize2(BTNode* root)
{
	if (root == NULL)
		return;
	BinaryTreeSize2(root->left);
	if (root != NULL)
		sz2++;
	BinaryTreeSize2(root->right);
}
//3、后序遞回遍歷
int sz3 = 0;
void BinaryTreeSize3(BTNode* root)
{
	if (root == NULL)
		return;
	BinaryTreeSize3(root->left);
	BinaryTreeSize3(root->right);
	if (root != NULL)
		sz3++;
}
// 二叉樹節點個數
int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
//二叉樹葉子節點個數
int BinaryTreeLeaSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	else
	{
		return BinaryTreeLeaSize(root->left) + BinaryTreeLeaSize(root->right);
	}
}
//二叉樹第k層節點個數
int BinaryTreeLeveLKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}

	return BinaryTreeLeveLKSize(root->left, k - 1) + BinaryTreeLeveLKSize(root->right, k - 1);
}
//二叉樹的深度/高度 
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDepth = BinaryTreeDepth(root->left);
	int rightDepth = BinaryTreeDepth(root->right);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
// 二叉樹查找值為x的節點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* retleft = BinaryTreeFind(root->left, x);
	if (retleft)
	{
		return retleft;
	}
	BTNode* retright = BinaryTreeFind(root->right, x);
	if (retright)
	{
		return retright;
	}
	return NULL;
}
BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode('A');
	BTNode* node2 = BuyNode('B');
	BTNode* node3 = BuyNode('C');
	BTNode* node4 = BuyNode('D');
	BTNode* node5 = BuyNode('E');
	BTNode* node6 = BuyNode('F');

	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node3->left = node5;
	node3->right = node6;

	return node1;
}

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}
int main()
{
	BTNode* root = CreatBinaryTree();
	//遍厲前中后序輸出二叉樹節點的個數
	BinaryTreeSize1(root);
	BinaryTreeSize2(root);
	BinaryTreeSize3(root);
	printf("BinaryTreeSize:%d\n", sz1);
	printf("BinaryTreeSize:%d\n", sz2);
	printf("BinaryTreeSize:%d\n", sz3);
	printf("-----------------cur-----------------\n");
	//優化二叉樹節點的個數
	printf("BinaryTreeSize:%d\n", BinaryTreeSize(root));
	printf("-----------------cur-----------------\n");
	//二叉樹葉子節點個數
	printf("BinaryTreeLeaSize:%d\n", BinaryTreeLeaSize(root));
	printf("-----------------cur-----------------\n");
	//二叉樹第k層節點個數
	printf("BinaryTreeLeveLKSize:%d\n", BinaryTreeLeveLKSize(root, 3));
	printf("-----------------cur-----------------\n");
	//二叉樹的深度/高度 
	printf("BinaryTreeDepth:%d\n", BinaryTreeDepth(root));
	printf("-----------------cur-----------------\n");
	// 二叉樹查找值為x的節點
	BTNode* ret = BinaryTreeFind(root, 'D');
	if(ret)
	{
		printf("找到了\n");
	}
	else
	{
		printf("沒找到\n");
	}

	PreOrder(root);
	return 0;
}

💦 二叉樹基礎oj練習

注：豌豆在這里也貼心的留了幾道 OJ 題，點擊鏈接即可做題，后續會補全(其實是還沒趕出來😂)

1、單值二叉樹＜難度系數?＞

leetcode原題

2、檢查兩顆樹是否相同＜難度系數?＞

leetcode原題

3、對稱二叉樹＜難度系數?＞

leetcode原題

4、二叉樹的前序遍歷＜難度系數?＞

leetcode原題

5、二叉樹中序遍歷＜難度系數?＞

leetcode原題

6、二叉樹的后序遍歷＜難度系數?＞

leetcode原題

7、另一顆樹的子樹＜難度系數?＞

leetcode原題

8、二叉樹的構建及遍歷＜難度系數?＞

leetcode原題

💦 二叉樹的創建和銷毀

// 通過前序遍歷的陣列"ABD##E#H##CF##G##"構建二叉樹
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉樹銷毀
void BinaryTreeDestory(BTNode** root);
// 判斷二叉樹是否是完全二叉樹
int BinaryTreeComplete(BTNode* root);