數據結構（7）—— 二叉樹（1）

前言

本文介紹二叉樹以及堆的認識，以及對于堆的介紹和代碼編寫。

一、樹概念及結構

1.1樹的概念

樹是一種非線性的數據結構，由節點（Node）和邊（Edge）組成，是由n（n>=0）個有限結點組成一個具有層次關系的集合。樹結構具有層次性，通常用于表示具有父子關系的數據。

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

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

要注意：

樹中子樹不能相交，就如之前說的子樹的根節點有且只有一個前驅一樣，除了根節點以外，每一個子節點有且只有一個根結點，子樹不能有交集，否則就不是樹形結構，一棵樹N個節點那么它有N-1條邊。

1.2樹的相關概念

一顆樹中每一個部分都有自己的名字，針對上面的一個數對樹的相關概念進行解釋：

節點的度：一個節點包含所有子樹的個數成為這個節點的度；例如上面的A節點的度就是6。

葉節點或終端節點：度為0的節點；例如上面的LMJK就是葉節點。

雙親節點或父節點：若一個節點含有子節點，那么這個節點就是其子節點的父節點；例如A就是B的父節點。

孩子節點或父節點：一個節點含有的子樹的根節點稱為該節點的子節點；上面B就是A的孩子節點。

兄弟節點：具有相同父節點的節點稱為兄弟節點；B、C就是兄弟節點，它們的共同父節點就是A。

樹的度：一棵樹中，最大的節點的度稱為數的度；上面就是6。

節點的吃層次：從跟開始定義，跟為第1層，跟的子節點為第2層，以此類推；

樹的高度或深度：樹中節點的最大層次；上面就是4層。

堂兄弟節點：雙親在同一層的節點互為堂兄弟；如上面的E和F就是互為堂兄弟。

節點的祖先：從跟到該節點所經分支上的所有節點；A就是所有節點的祖先。

子孫：以某節點為跟的子樹中任一節點都稱為該節點的子孫。如上圖：所有節點都是A的子孫。

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

1.3數的表示

樹的表示有很多種，這里介紹幾種樹的表示方法：

1.二叉樹表示

二叉樹是最基礎的樹的結構，每一個節點有兩個子節點（左子樹和右子樹），當然還包括一個data用來存儲數據。

// 定義二叉樹節點結構
struct TreeNode {int data;struct TreeNode* left;struct TreeNode* right;
};

2.孩子兄弟表示法

孩子兄弟表示法是構建普通數的常用方式。

// 多叉樹節點結構（孩子兄弟表示法）
struct TreeNode {int data;struct TreeNode* firstChild; // 第一個孩子節點struct TreeNode* nextSibling; // 兄弟節點
};

3.動態數組存儲

當然，使用動態數組也可以實現多叉樹節點的結構：

// 多叉樹節點結構（動態數組）
struct TreeNode {int data;int childCount;struct TreeNode* children[MAX_CHILDREN];
};

1.4樹的實際應用

文件系統管理
文件系統的目錄結構通常采用樹形組織，根目錄為頂層節點，子目錄和文件作為子節點。這種結構便于用戶導航和管理文件。

數據庫索引
B樹和B+樹是數據庫索引的核心數據結構，能夠高效支持數據的插入、刪除和查詢操作，保持對數級的時間復雜度。

網絡路由
路由器使用前綴樹（Trie）存儲IP路由表，快速匹配最長前綴路由規則，優化數據包轉發效率。

人工智能決策
決策樹通過樹形分支模擬人類決策過程，每個節點代表一個判斷條件，廣泛應用于分類和回歸任務。

組織結構管理
企業組織架構常表現為樹形，CEO為根節點，各部門經理為子節點，清晰反映匯報關系和職責劃分。

XML/HTML解析
DOM樹將文檔表示為節點樹，每個標簽作為節點，父子關系反映標簽嵌套層級，便于程序分析和操作。

游戲開發
場景圖使用樹結構管理游戲對象，父子節點關系實現坐標系的層級變換，優化渲染效率。

編譯器設計
抽象語法樹（AST）表示源代碼的語法結構，每個節點對應語言構造，支撐語義分析和代碼生成。

二、二叉樹概念及結構

2.1概念

一顆二叉樹，顧名思義，只能有兩個度，所以二叉樹是一個有限集合，該集合要么為空，要么每一個根節點加上左右子樹組成，同時二叉樹有左右之分，次序不能顛倒，因此二叉樹是有序樹。

2.2特殊的二叉樹

1.滿二叉樹

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

2. 完全二叉樹

完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹。要注意的是滿二叉樹是一種特殊的完全二叉樹。

2.3二叉樹的性質

1. 若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有 $2^{i-1}$ 個結點.
2. 若規定根節點的層數為1，則深度為h的二叉樹的最大結點數是 $2^{h-1}$ .
3. 對任何一棵二叉樹, 如果度為0其葉結點個數為 , 度為2的分支結點個數為 ,則有 n0＝ n2＋1
4. 若規定根節點的層數為1，具有n個結點的滿二叉樹的深度，h= $\log (n+1)$ . (ps：是log以2為底，n+1為對數)。
5. 對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的數組順序對所有節點從0開始編號，則對于序號為i的結點有：
1. 若i>0，i位置節點的雙親序號：(i-1)/2；i=0，i為根節點編號，無雙親節點

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

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

2.4二叉樹的存儲結構

二叉樹一般有兩種存儲結構，一種是順序結構，一種是鏈式結構。

1.順序存儲

數序存儲就是使用數組來存儲，一般使用數組只適合表示完全二叉樹，因為不是完全二叉樹的話，中間有空擋，本身數組就是一段連續的存儲地址，那么就會有浪費的空間，而現實中只有堆才會使用數組來存儲，二叉樹順序存儲本身就是物理上的一個數組，在邏輯上就是一顆二叉樹。

2.鏈式存儲

用鏈表來表示一顆二叉樹，用鏈來指示元素的邏輯關系，通常的方法就是鏈表中每個節點由三個域組成，數據域和左右指針域，左右指針分別用來給出該節點左孩子和右孩子所在的鏈節點的存儲地址，一般都是二叉鏈，其中紅黑樹是用到的三叉鏈。

三、二叉樹的順序結構實現

3.1二叉樹的順序結構

普通的二叉樹是不適合使用數組來進行存儲的，因為可能會出現大量的空間浪費，只有完全二叉樹才更適合順序結構存儲，現實中我們把堆用順序結構來存儲。

3.2堆的概念及其結構

堆是一種特殊的完全二叉樹，分為最大堆和最小堆。最大堆中每個節點的值都大于或等于其子節點的值，最小堆中每個節點的值都小于或等于其子節點的值。堆常用于實現優先隊列和堆排序算法，將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。

堆的性質：

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

2.堆總是一顆完全二叉樹；

3.3堆的實現

我們通過實現這些：

void HeapInit(HP* php);//初始化
void HeapPush(HP* php, HPDataType x);//尾插
void HeapPop(HP* php);//刪除頭
void AdjustDown(HPDataType* a, int n, int parent);//向下調整
void AdjustUp(HPDataType* a, int child);//向上調整
HPDataType HeapTop(HP* php);//堆頂元素
bool HeapEmpty(HP* php);//檢查空
int HeapSize(HP* php);//堆數據的個數

3.3.1結構體定義

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

3.3.2初始化

void HeapInit(HP* php)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType)*4);//分配4空間if (php->a == NULL){perror("malloc fail");return;}php->size = 0;//當前數據個數php->capacity = 4;//空間大小
}

3.3.3向上調整（大堆）

//前提是除了child這個位置，前面的數據都構成堆
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//while(parent>=0)//雖然可以運行，但是不建議，因為有問題，，但還是可以跑while (child>0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

函數通過計算父節點索引?parent = (child - 1) / 2?定位當前節點的父節點。循環條件?child > 0?確保不會越界，避免了使用?parent >= 0?可能導致的潛在問題。當子節點值大于父節點值時，調用?Swap?交換兩者位置，并更新子節點和父節點的索引。如果子節點值不大于父節點值，循環終止，堆性質已滿足。

3.3.4向下調整（大堆）

//前提左右子樹都是大堆或者小堆
//向下調整，取大換小
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){//選出左右孩子中的大的那一個if (child+1<n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}
}

函數接收三個參數：堆數組a、堆的大小n、需要調整的父節點索引parent。初始化時計算左孩子索引：child = parent * 2 + 1。循環條件為當前孩子節點在堆范圍內（child < n）。在循環體內，先比較左右孩子節點的大小（確保右孩子存在的情況下），選擇較大的孩子節點。如果較大的孩子節點大于父節點，則交換兩者位置，并繼續向下調整。如果父節點已經大于或等于兩個孩子節點，則調整完成，退出循環。

3.3.5插入

void HeapPush(HP* php,HPDataType x)
{assert(php);if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * php->capacity*2);if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity *= 2;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

3.3.6刪除頭

//刪除堆頂才有意義，也就是刪除根,不斷的篩選大根堆小跟堆的根節點，從而實現排序，挑出最大最小的
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);
}

3.3.7獲取堆頂元素

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

3.3.8檢查空

bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

3.3.9獲取個數

int HeapSize(HP* php)
{assert(php);return php->size;
}

測試

void HeapSort(int* a, int n)
{//建堆//1.向上調整建堆for (int i = 1; i < n; ++i){AdjustUp(a, i);//模擬插入建堆,降序}
}
//排升序不能建小堆，得建大堆
// 排降序應該建小堆
//排升序第一個數排好了，但是剩下的數關系全亂了int main()
{int a[10] = { 2,1,5,7,6,8,0,9,4,3 };//對數組排序HeapSort(a, 10);return 0;
}