為什么我們要學那么多的數據結構？這是因為沒有一種數據結構能夠去應對所有場景。我們在不同的場景需要選擇不同的數據結構，所以數據結構沒有好壞之分，而評估數據結構的好壞要針對場景，就如我們已經學習的結構而言，如果在一種場景下我們需要頻繁地對頭部進行插入刪除操作，那么這個時候我們用鏈表；但是如果對尾部進行插入刪除操作比較頻繁，那我們用順序表比較好。 因此，不同的場景我們選擇不同的數據結構

---

一、樹

1.樹的基本概念

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

??? ???有一個特殊的結點，稱為根結點，根結點沒有前驅結點，如下圖中A是根節點，前驅節點指的就是c的前面的節點A(前驅)。在樹中有且僅有一個根節點

圖1:

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

??? ??? 解釋： 整棵樹可以看成一個大集合，A就是根節點，而大集合可以分成一個個獨立的小集合稱為子樹，如以B為根節點的小集合，C和D也可以看成集合，但要注意的是每個集合互不相交，如下圖子樹均相交則不是樹而是圖，在后續的博客會有介紹

圖3：

??? ???注意：因為是有限結點組成一個具有層次關系的集合，所以樹在邏輯結構上就不是線性的。我們在生活中經常看到樹是向上生長的，而在數據結構中的樹是生活中的樹抽象過來——根朝上，葉子朝下，如下圖

圖2：

結論： 1.子樹是不相交
??? ?????? ?2.除了根節點外，每個節點有且僅有一個父節點
??? ?????? ?3.一棵N個節點的樹有N-1條邊（如圖1中一共有12個節點，有11條邊）

2.樹相關術語

1 .葉結點或終端結： 度為0的結點稱為葉結點； 如上圖：B、C、H、I…等結點為葉結點

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

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

4 .孩子結點或子結點： 一個結點含有的子樹的根結點稱為該結點的子結點； 如上圖：B是A的孩子結點

5 .兄弟結點： 具有相同父結點的結點互稱為兄弟結點； 如上圖：B、C是兄弟結點

6 .結點的度： 一個結點含有的子樹的個數稱為該結點的度； 如上圖：A的為6（B C D E F G）

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

8 . 結點的層次： 從根開始定義起，根為第1層，根的子結點為第2層，以此類推；

9 .樹的高度或深度： 樹中結點的最大層次； 如上圖：樹的高度為4

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

11 .路徑： 一條從樹中任意節點出發，沿父節點-子節點連接，達到任意節點的序列，比如A到Q的路徑A-E-J-Q；H到Q的路徑H-D-A-E-J-Q

11 .結點的祖先： 從根到該結點所經分支上的所有結點；如上圖：A是所有結點的祖先

12 .子孫： 以某結點為根的子樹中任一結點都稱為該結點的子孫。如上圖：所有結點都是A的子孫

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

3.樹的表示

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

typedef int DataType;struct Node{      struct Node* child;    // 左邊開始的第一個孩子節點struct Node* brother;   // 指向其右邊的下一個兄弟節點  DataType data;          // 結點中的數據域};

4.樹形結構實際運用場景

??????文件系統是計算機存儲和管理文件的一種方式，它利用樹形結構來組織和管理文件和文件夾。在文件系統中，樹結構被廣泛應用，它通過父節點和子節點之間的關系來表示不同層級的文件和文件夾之間的關聯

二、二叉樹

1. 概念與結構

??????在樹形結構中，我們最常用的就是二叉樹，一棵二叉樹是節點的一個有限集合，該節點是由一個根節點加上兩棵別稱為左子樹和右子樹的二叉樹組成或者為空

???從上圖可以看出二叉樹具備以下特點：

?????1 .二叉樹不存在度大于2的節點（孩子不超過2個，可以是0個孩子，一個孩子，兩個孩子）

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

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

現實中的二叉樹

特殊的二叉樹

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

???2 . 完全二叉樹：完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。（最后一層節點的個數不一定達到最大）

???證明：第一層節點有2 ^0 個節點，第二層是 2 ^1個節點，第三層是2 ^2個，以此內推，第n層是 2 ^(n-1)個節點，這符合高中等比數列求和公式，相加得到最終總結點事2 ^n-1個。

二叉樹的性質

根據二叉樹的特點可知;

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

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

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

4）對任何一棵二叉樹, 如果度為0其葉結點個數為n0 , 度為2的分支結點個數為n2 ,則有 n0＝n2 ＋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否則無右孩子

這里對性質4進行證明：

• 假設二叉樹有N個結點

• 從總結點數角度考慮：N = n0 + n1 + n2 ①

• 從邊的角度考慮，N個結點的任意二叉樹，總共有N-1條邊

• 因為二叉樹中每個結點都有雙親，根結點沒有雙親，每個節點向上與其雙親之間存在一條邊

• 因此N個結點的二叉樹總共有N-1條邊

• 因為度為0的結點沒有孩子，故度為0的結點不產生邊; 度為1的結點只有一個孩子，故每個度為1的結
  點* 產生一條邊; 度為2的結點有2個孩子，故每個度為2的結點產生兩條邊，所以總邊數為：
  n1+2*n2

• 故從邊的角度考慮：N-1 = n1 + 2*n2 ②

• 結合① 和 ②得：n0 + n1 + n2 = n1 + 2*n2 - 1

• 即：n0 = n2 + 1

二叉樹存儲結構

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

1. 順序結構： 就是使用數組存儲，一般使用數組只適合完全二叉樹，因為不是完全二叉樹會有空間的浪費，而在現實中使用中只有堆才會使用數組存儲，需要注意的是這個里的堆和操作系統虛擬進程空間中的堆事兩碼事，一個是數據結構，一個是操作系統中管理內存的一塊區域分段。

???二叉樹順序存儲在物理上是一個數組，在邏輯上是一棵二叉樹

???這里大家可能疑惑，為啥在非完全二叉樹中必須空出位置來代表該節點為空，因為二叉樹是有序的，否則會導致父親變孩子，左孩子變右孩子

2. 鏈式結構： 二叉樹的鏈式存儲結構是指用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。 通常的方法是鏈表中每個結點由三個域組成，數據域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所在的鏈結點的存儲地址 。鏈式結構又分為二叉鏈和三叉鏈，當前我們學習中一般都是二叉鏈，后面學到高階數據結構如紅黑樹等會用到三叉鏈。

二叉鏈有兩個指針指向左右孩子，不可以向上找父親節點，但是三叉鏈多了個指針指向父親節點。

三、手動模擬實現順序二叉樹——堆

???堆是一種特殊的二叉樹，具有二叉樹的特性的同時，還具備其他特性，下面是其的概念和結構解釋

定義：如果有一個關鍵碼的集合K = { ， ， ，…， }，把它的所有元素按完全二叉樹的順序存儲方式存儲在一個一維數組中，并滿足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，則稱為小堆(或大堆)。將根結點最大的堆叫做最大堆或大根堆，根結點最小的堆叫做最小堆或小根堆（在左右子樹中根節點也是對應的最小 / 最大）

小根堆：堆頂是堆中最小的節點 ，大根堆：堆頂是堆中最大的節點

注意：這里大家可能疑惑堆和二叉樹具體是什么關系，可以認為堆除了具有二叉樹的性質還具有堆頂是最大節點/最小節點的特性

1.堆的結構

這里堆的定義和順序表的定義是類似的

typedef int HPDataType;//堆的結構
typedef struct Heap
{HPDataType* arr; int size;         //有效數據個數 int capacity;     //容量
}HP; 

2.初始化

和順序表類似

void HPInit(HP* php)
{assert(php);php->arr = NULL;php->capacity = php->size = 0;
}

3.銷毀

void HPDestroy(HP* php)
{assert(php);if (php->arr)free(php->arr);php->arr = NULL;php->capacity = php->size = 0;}

4.向上調整算法

是為了下一個插入數據方法做出鋪墊，將插入的數據默認為孩子節點，根據二叉樹的性質可知parent=(child-1)/2，如果我們要實現的是小堆，那么

1. 比較child和parent誰小，誰小誰往上放（交換）
2. 然后繼續讓child往上走（child=parent即可），結束條件是child>0,因為child走到根節點后沒有其父節點

//交換
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}//向上調整算法   前提;往有效的堆中調整
void AdjustUp(HPDataType *arr,int child)
{int parent = (child - 1) / 2;while (child>0){//  >:大堆//  <:小堆if (arr[child] <arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}

5.插入數據

1. 初始情況下需要動態增容（這里和順序表類似）
2. 插入數據：php->arr[php->size] = x
3. 判斷插入的數據是否符合大堆/小堆，不符合則調用向上調整算法（這里是使用大堆）
4. 最后讓size++

如下圖：先插入一個10到數組的尾上，再進行向上調整算法，直到滿足堆

//插入數據
void HPPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;//空間滿了，需要增容HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail!\n");exit(1);}php->arr = tmp;php->capacity = newcapacity;}php->arr[php->size] = x;//向上調整AdjustUp(php->arr, php->size);++php->size;
}

6.判空

這里和順序表一樣

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

7.求size

返回堆中有效的數據個數

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

8.向下調整算法

我們已知父親節點來找孩子節點，假設我們要實現的是小堆，那么就需要讓父親節點和孩子節點比較，這里需要注意，我們需要讓左右節點均要和父親節點比，誰小誰和parent交換，然后讓parent走到child位置，循環進行該操作直至child走到n結束

void AdjustDown(HPDataType* arr, int parent,int n)
{int child = parent * 2 + 1;while (child<n){//先找最大的孩子，這里排序是<//如果是文件的是創建大堆，所以是>if (child+1<n &&  arr[child] >arr[child + 1]){child++;}//先找最大的孩子，這里排序是>//如果是文件的是創建大堆，所以是<if (arr[child] <arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}

9.刪除堆頂數據

1.首先保證堆不為空，調用堆判空接口

2.刪除堆頂元素

如果直接刪除堆頂元素，讓孩子節點均往前移動會導致原來的孩子節點變成父親節點，左右孩子順序不對等情況，如下圖中原本25是15的左孩子，現在變成56的兄弟節點，那么我們就需要重新一個個調整，代價太大了，那么有沒有方法可以解決？

我們交換堆頂元素和最后一個數據，然后讓size- -，走到a[5]位置，a[5]可以存儲數據，但是不是有效的（即10不是堆中有序的數據），我們發現70變成了堆頂，但是15 56 25 等數據之間的關系并沒有發生變化，因此我們只需要讓堆頂70向下調整，直接調用向下調整方法即可

具體步驟如下：

1.將堆頂元素與堆中最后一個元素進行交換

2.刪除堆中最后一個元素

3.將堆頂元素向下調整到滿足堆特性為止

10.獲取堆頂數據

判空后直接返回a[0]位置的數據即可

HPDataType HPTOP(HP* php)
{assert(!HPEmpty(php));return php->arr[0];
}

注意：上述所說的向上調整算法和向下調整算法均有個前提是往有效的堆中調整

四、最全源碼

1.堆中接口源碼

五、堆排序

1.思考

這里我們需要思考：排升序和排降序時需要建大堆還是小堆。這里第一反應是通過循環取堆頂元素發現排升序是建立小堆，降序建立大堆。那么是對還是錯？？？

具體操作：
1 .創建數組
2. 我們調用堆中的push接口將數組中的數據建堆
3 .通過頻繁取堆頂元素放入到數組中（條件為堆不為空），并且要不斷刪除堆頂

注意：大家這里可能疑惑為什么不直接打印堆頂元素，而是將堆頂元素取出來放入數組中，首先我們明確需要的條件是將數組排序，打印堆頂元素并沒有直接改變數組中原本的數據

//排升序----建大堆，因為調用AdjustDown函數，將大的放到最后一個子節點，依次這樣進行，會使得最小的在根節點處，就變成升序
//排降序----建小堆，因為調用AdjustDown函數，將小的放到最后一個子節點，依次這樣進行，會使得最大的在根節點處，就變成降序
//借助數據結果---堆
void test01()
{int arr[] = { 17,20,10,13,19,15 };int n = sizeof(arr) / sizeof(arr[0]);HP hp;HPInit(&hp);//調用push將數組中的數據建堆for (int i = 0; i < n; i++){HPPush(&hp, arr[i]);}int i = 0;while (!HPEmpty(&hp)){arr[i++]=HPTOP(&hp);HPPop(&hp);}for (int j = 0; j< n; j++){printf("%d ", arr[j]);}HPDestroy(&hp);}

我們這里來看下我們之前學習過的冒泡排序的代碼是如何的，經過比較發現冒泡排序是通過思想來實現排序，而上述的堆排序是通過使用數據結構——堆來輔助實現的，因此要實現堆排序需要借助堆的排序思想

2.冒泡排序：

//冒泡排序，時間復雜度O（n^2）
void BubbleSort(int* arr, int n)
{for (int i= 0; i < n; i++){int exchange = 0;for (int j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1]){exchange = 1;Swap(&arr[j], &arr[j + 1]);}}if (exchange = 0){break;}}}

3.建堆——算法復雜度的優與劣

??? ???這里我們根據數組中存儲的最后一個數據的有效下標（孩子節點）根據parent=（child-1)/2可得，依次遞減parent直至根節點，結束循環

??? ???大家可能疑惑在向下調整算法中可不可以從a[0]位置開始調整？答案是不可以，因為向上調整算法和向下調整算法成立的前提是該堆已經是有效的堆，從a[0]開始調整就相當于從有效的大/小堆中來調整大/小堆，所以不行，我們應該依次調整左右子樹的大/小堆最后整體形成大/小堆

??? ???注意：大家可能會把堆排序中的向上尋找parent節點認為是向上調整算法，但是如何確定是向上/向下調整算法的實質是調整方向，父親節點——>子節點是向下調整，是通過比較兩個孩子之間誰和父親節點大/小來實現，可以保證堆的已有順序不會被修改
代碼如下：

void HeapSort(int*arr,int n)
{//根據給定的arr來進行建堆//child:n-1   parent;(n-1-1)/2for(int i=(n-1-1)/2;i>=0;i--){AdjustDown(arr,i,n);}
}

時間復雜度： 我們發現如果要建的堆事滿二叉樹則一共有2^h-1個節點，最壞情況下就是從根節點到最后一個節點一次次往下移動（一層層移動），則h=log2(n+1),向下調整為logn，那么總時間復雜度為nlongn

那么可以使用向下調整算法建堆也是可以使用向上調整算法的，那么哪個時間復雜度更優捏？初次思考我們發現兩個算法均是nlongn，那么是不是如此呢？

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

需要移動節點總的移動步數為：每層節點個數x向上調整次數


從第一層到最后一層節點個數逐漸增多，向下調整次數逐漸減少

向上調整算法時間復雜度證明：

這里和向下調整算法證明類似，最后可以得出F(n)=(n+1)(log2(n+1)-2)+2，則時間復雜度為O(n*logn)

結論：因此向下調整算法是堆排序中主流用法！

4.排序

假設我們需要排降序，

1.我們通過交換根節點a[0]和最后一個節點的數據

2.讓end–

3.使用向下調整算法不斷將小的數據放到根節點處

結論：根據上述步驟我們得到:

排升序----建大堆，因為不斷交換堆頂數據和最后一個位置數據交換，將大的放到最后一個子節點，依次這樣進行，會使得最小的在根節點處，就變成升序

排降序----建小堆，因為不斷交換堆頂數據和最后一個位置數據交換，將小的放到最后一個子節點，依次這樣進行，會使得最大的在根節點處，就變成降序

六、TOP-K問題

TOP-K問題:即求數據結合中前k個最大的元素或者最小的元素，一般情況下數據量都比較大。
比如：專業前10名，世界500強，富豪榜，游戲中前100的活躍玩家等。
對于TOP-K問題，能想到的最簡單直接的方法就是排序，但是：如果數據量非常大，排序就不太可取了（可能數據都不能一下子全部加載到內存中），最佳的方法就是使用堆來解決，基本思路如下：

1.用數據集合中前k個元素來建堆
前k個最大的元素，則建小堆
前k個最小的元素，則建大堆

2.用剩余的N-k個元素依次與堆頂元素進行比較，不滿足則替換堆頂元素
將剩余N-K個元素依次與堆頂元素比較完之后，堆中剩余的k個元素就是所求的前k個最小或者最大的元素

例子：假設·我們有N個數據， N是10億個整數，需要申請多大的內存？

換算：
int = 4 byte
1G=1024MB=10241024KB=10241024*1024 byte

根據上述換算可得：1G約等于10億個字節，因此存儲10億數據需要申請4G內存。

如果面試官問我們，如果我們只有1G內存——我們該如何解決？
這里我們可以分多次來存儲，建立4個堆，每份都求取該堆中最大的幾個數據，最后四個堆中數據個數相加為k即可

那么假設只有1KB內存該如何呢？
先取前k個數據進行建堆，遍歷剩下的 N-K個數據跟堆頂數據進行比較

找最大的前K個數據，建小堆，因為堆頂是該堆中最小的數據，當我們每遍歷一個數據就和堆頂比誰大，誰大誰入堆（小就出堆）

創造數據：

void CreateNDate()
{// 造數據int n = 100000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = (rand() + i) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}

生成了data.txt文件，里面存放了十萬個整型數據，如下

遍歷剩余的N-K個數據，和堆頂比大小，符合條件則調用向下調整算法

void TopK()
{int k = 0;printf("請輸入K：");scanf("%d", &k);//讀取文件中前k個數據建堆const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");exit(1);}//找最大的前K個數，建小堆int* minHeap = (int*)malloc(sizeof(int) * k);if (minHeap == NULL){perror("malloc fail!");exit(2);}//讀取文件中前K個數據建堆for (int i = 0; i < k; i++){fscanf(fout, "%d", &minHeap[i]);}//建堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(minHeap, i, k);}//遍歷剩下的n-k個數據，跟堆頂比較，誰大誰入堆//調整堆int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > minHeap[0]){minHeap[0] = x;AdjustDown(minHeap, 0, k);}}for (int i = 0; i < k; i++){printf("%d ", minHeap[i]);}fclose(fout);
}

打印結果：

結論：找最大的前K個數據，建小堆，找最小的前K個數據，建大堆

總結

本文以“長幼有序”為核心思想，系統解析了樹形結構及其衍生數據結構的層次化特性與應用：

1.樹結構：作為非線性數據結構的基石，通過根節點與子樹的層次關系，構建了自然的層級模型，體現了數據間的“長幼”邏輯。

2.二叉樹：以簡潔的左右子樹劃分，強化了順序的重要性，滿二叉樹與完全二叉樹的特性為高效算法（如堆）奠定了基礎。

3.堆結構：作為二叉樹的特殊形態，通過向上/向下調整算法，將層次化結構轉化為排序利器，小根堆與大根堆的區分直接服務于TOP-K等實際問題。

4.TOP-K問題：利用堆的層次調整能力，在大數據場景下高效求解極值問題，體現了“長幼有序”思想在資源優化中的關鍵作用

全文貫穿“層次決定順序，結構決定效率”的理念，展示了數據結構從理論到實踐的完整鏈路