一、樹

1.樹的概念

樹是一種非線性的數據結構，由n(n≥0)個有限結點組成的一個有層次關系的集合。形狀類似一棵倒掛的樹，根朝上，分支向下。

根結點沒有前驅結點，可以有n(n≥0)個后繼結點。

其余結點被分為M個互不相交的集合，每一個集合都是一棵子樹，每棵子樹的根節點均有1個前驅結點，n(n≥0)個后繼結點。因此樹是遞歸定義的。

注：除根外的結點被分為互不相交的集合，如果相交，就不是樹，而是圖了。

子樹之間存在交集，不屬于樹形結構，某結點存在多個父結點即它的前驅結點>1，也不屬于樹形結構。

2.與樹有關的概念

節點的度：一個節點含有的子樹的個數稱為該節點的度；?
葉節點(終端節點)：度為0的節點稱為葉節點；(重要)
分支節點(非終端節點)：度不為0的節點；
父節點(雙親結點)：若一個節點含有子節點，則這個節點稱為其子節點的父節點；(重要)
子節點(孩子節點)：一個節點含有的子樹的根節點稱為該節點的子節點；(重要)
兄弟節點：具有相同父節點的節點互稱為兄弟節點；
樹的度：一棵樹中，最大的節點的度稱為樹的度；
節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；(重要)
樹的高度或深度：樹中節點的最大層次；(重要)
堂兄弟節點：雙親在同一層的節點互為堂兄弟；
節點的祖先：從根到該節點所經分支上的所有節點；(重要)
子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 森林：由m（m>0）棵互不相交的樹的集合稱為森林；

注：關于樹的層次，一般而言是從1開始，即根所在層次為1，如果題目給定從0開始，那就從0開始，否則默認從1開始層次，因為對于無結點樹而言，層次剛好是0，從0開始那么無結點樹層次就為-1。

3.樹的表示

如果我們使用數組來表示樹，那么我們一般采用數組ArrayChild來存儲孩子結點

#define N 6 //假設已知樹的度為6
struct TreeNode
{TreeNodeTypeData val;struct TreeNode* ArrayChild[N];
};

但是，如果這樣來表示樹，那么相當于每一個分支結點，都有N個數組空間(N是樹的度的值)，但是樹的分支結點不一定都有N個子結點，這樣的表示就太過于浪費空間了。

如果用順序表來表示樹型結構，

struct TreeNode
{TreeNodeTypeData val;SeqList Childlist;
};

那么每個孩子結點都是一個順序表，但是需要我們去構建一個順序表，在C語言階段也是非常費心費力的。

左孩子右兄弟表示法

樹形結構的最優表示方法是左孩子右兄弟表示法。

樹形結構中創建兩個指針，左孩子指針LeftChild與右兄弟指針RightBrother

struct TreeNode
{TreeNodeTypeData val;struct TreeNode* LeftChild;struct TreeNode* RightBrother;
};

我們通過每一次的根節點訪問左孩子，就可以通過左孩子結點訪問右兄弟指針找到該層次的其他結點；如果想訪問下一層次，那么現在的左孩子結點訪問它的左孩子結點，通過它的左孩子結點訪問右兄弟指針能夠找到其他所有結點。

上圖中左孩子右兄弟表示形式里，未標識出來的左孩子LeftChild指針都應該指向NULL。

由此我們只需要訪問上一層次某一棵子樹的根節點的左孩子結點就可以遍歷該層次屬于該子樹的所有結點。

如A的左孩子為B，A結點訪問成員LeftChild得到B結點，B結點訪問成員RightBrother就能夠訪問到同層次屬于A孩子的C與D結點。如B的左孩子是E，那么通過B訪問到E結點就可以遍歷E、F結點。

4.樹的實際運用

Linux樹狀目錄結構。

Windows文件目錄多盤形式---森林。

二、二叉樹

1.概念

二叉樹的結點的度均≤2(即每個結點的子結點不超過2個)，同時二叉樹區分左右子樹(即區分左右結點)，是有序樹。

二叉樹是特殊的樹。

2.特殊的二叉樹

①滿二叉樹

二叉樹的所有結點的度都是2，那么就是滿二叉樹。對于滿二叉樹而言，每一層的結點數都達到了最大值。

假設滿二叉樹的深度為h，結點數為N，那么存在關系：2^h - 1 = N <==>?h?=?log(N+1) (以2為底)

反過來說，如果一個二叉樹的層數為K，它的結點數為2^K-1，那么這個二叉樹就是滿二叉樹。

②完全二叉樹

完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。

對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹。滿二叉樹是一種特殊的完全二叉樹。

通俗來講，除去最后一層的其它層結點數達到最大值，最后一層結點數不確定但是從左到右一定有序的二叉樹就是完全二叉樹。

對于完全二叉樹來說，由于最后一層的結點有序，但是不確定最后一層結點個數，因此總的結點數N是一個范圍，最小的時候最后一層只有1個結點，最大的時候是滿二叉樹。

那么N的范圍為：[2^(h-1)-1+1 , 2^(h) -1]? 化簡--->[2^(h-1) , 2^(h) -1]

注意，對于完全二叉樹來說，最后一層的結點一定是有序的！結點一定是從左至右增加的。

3.二叉樹的性質

4.二叉樹的存儲結構

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

①順序存儲

順序結構存儲就是使用數組來存儲，一般使用數組只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費。而現實中使用中只有堆才會使用數組來存儲，二叉樹順序存儲在物理上是一個數組，在邏輯上是一顆二叉樹。

順序存儲--->使用數組存儲，只適用于完全二叉樹。如果用數組存儲的方式對任意二叉樹，那么由于每個結點的度不同，會有許多數組空間的浪費，因此數組存儲只適用于完全二叉樹。

將完全二叉樹的結點一層一層的存入數組中，

我們會發現，父子結點的下標是存在聯系的。

②鏈式存儲

對于不是完全二叉樹和滿二叉樹的樹形結構，我們采取鏈式結構來進行數據存儲。

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

5.堆

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

堆的性質：①堆中某個節點的值總是不大于或不小于其父節點的值；②堆總是一棵完全二叉樹。

簡單的說，如果一個數組的內容滿足堆的性質，那么堆就把這個數組數據看做一棵完全二叉樹。

堆只分為小(根)堆和大(根)堆，小堆表示所有的父結點的數據都小于等于其子結點；大堆表示所有的父結點的數據都大于等于其子結點。除此之外都不是堆。

有序數組是不是堆？是，但是堆不一定是有序數組。

跟之前數據結構講的棧不同于內存中的棧類似，

數據結構的堆是一種管理數據的結構，是完全二叉樹；

而操作系統中的堆，指的是一個內存區域，這個區域中的空間可以通過malloc、calloc開辟、realloc擴容使用，最后free釋放。

堆的物理結構是數組；邏輯結構是完全二叉樹。

堆的意義：

1.堆排序---時間復雜度O(N*logN)

2.top?k問題

對于堆的實現，我們想象自己操縱的是完全二叉樹，但是我們實際上操縱的是數組。

數組實現堆

結構如下，我們來實現一下大(根)堆：

//堆是由讀取規定的---與棧和隊列一樣，堆頂開始讀取然后刪除
//大堆---父節點始終大于等于子節點
#define HeapDataType int
typedef struct Heap
{HeapDataType* a;int size;int capacity;
}Heap;

接口函數

①初始化HeapInit

void HeapInit(Heap* php);

//初始化
void HeapInit(Heap* php)
{assert(php);php->a = NULL;php->capacity = 0;php->size = 0;
}

②銷毀HeapDestroy

void HeapDestroy(Heap* php);

//銷毀
void HeapDestroy(Heap* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = 0;php->size = 0;
}

③插入HeapPush---O(logN)

void HeapPush(Heap* php, HeapDataType x);

在一個堆中插入一個新的數據x，那么我們就必須得將該數據移動到合適的位置，確保插入后新的數組仍然是一個大堆。

首先先寫出擴容判斷的代碼以及插入的代碼：

	//檢測容量---不用單獨開接口，因為只有一個插入if (php->size == php->capacity){int NewCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HeapDataType* tmp = (HeapDataType*)realloc(php->a, sizeof(HeapDataType) * NewCapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = NewCapacity;}//插入數據php->a[php->size] = x;php->size++;

那么就差最后一步，判斷是否需要更換位置：

我們知道，對于大堆而言，父節點的數據始終大于等于子節點的數據，對于目前插入在最后一層的新結點而言，我們需要將其與它的父輩、祖輩，與它的祖先進行比較，如果新結點的數據大于父節點，那么就需要將新結點與父節點交換，然后接著向上比較：

需要交換數據，那么我們封裝為一個Swap函數用來交換數據：

//交換函數
void Swap(HeapDataType* p1, HeapDataType* p2)
{HeapDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}

所以對于插入的值的比較，我們需要通過該結點找到其父結點，根據前面學到的堆的父子結點關系，我們知道，子節點下標child，(child-1)/2就能夠得到父節點下標parent。

最后的比較要到什么時候終止呢？如果最慢的情況，插入的數據比原根節點都要大，那么就要換到A結點處--->因此循環的終止條件應為child == 0 。那么我們將判斷和移動數據的過程封裝成一個函數UpAdjust(向上調整)。

向上調整算法UpAdjust

void UpAdjust(Heap* php, int child)；

    //向上調整算法UpAdjust(php, php->size - 1);

傳入的child是插入結點的下標，由于前面插入后size自增1了，所以這個地方傳進來的應該是size-1。

//向上調整算法---最壞情況調整深度h次，而完全二叉樹的h與logN相關---因此時間復雜度logN
void UpAdjust(Heap* php, int child)
{assert(php);int parent = (child - 1) / 2;//父節點下標為子節點-1再除2while (child > 0){if (php->a[parent] < php->a[child]){Swap(&php->a[parent], &php->a[child]);child = parent;parent = (parent - 1) / 2;}elsebreak;}
}

④刪除HeapPop---O(logN)

void HeapPop(Heap* php);

在堆的實現中的刪除操作，刪除的是堆頂元素---即根結點元素。

但是我們又不能夠直接進行覆蓋操作，如果直接進行覆蓋，一會導致原來的這個父子下標關系改變，摧毀了這個堆；二是數組的頭刪挪位覆蓋時間復雜度為O(N)。

所以就有一種方法：我們先交換堆頂元素與最后一個元素，然后進行尾刪--->就刪除了堆頂元素。

對于數組結構而言，尾刪是非常方便的，size自減1即可。然后這個時候，除了堆頂元素改變，其他位置上的元素均沒有變化，其實類似于向上調整---我們實現一個向下調整算法DownAdjust。

//刪除堆頂結點---時間復雜度O(logN)
void HeapPop(Heap* php)
{assert(php);Swap(&php->a[0], &php->a[php->size - 1]);//交換--->尾刪原堆頂php->size--;//尾刪原堆頂//向下調整算法---O(logN)，要將交換上去的結點向下調整DownAdjust(php->a, php->size, 0);
}

在DownAdjust向下調整算法內，我們將堆頂元素與它的子節點元素中較大的進行判斷，如果堆頂元素大，那么符合大堆，不用進行交換元素，反之，堆頂元素小于較大的子結點元素，那么交換二者，將交換后的處于子節點處的該元素繼續與這個位置上它的子結點的較大元素進行比較。

向下調整算法DownAdjust

?void DownAdjust(HeapDataType* a, int size, int parent)；

//向下調整---時間復雜度O(logN)
void DownAdjust(HeapDataType* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){if ( child+1 < size && a[child] < a[child + 1])//小心越界{child++;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = 2 * child + 1;}elsebreak;}
}

為了防止if else判斷兩個子節點誰大的代碼冗長，我們選擇使用了假設判斷法，先將其中的左節點下標給child，然后再if判斷如果左節點數據小于右孩子結點，那么將右節點下標給child，實際上就與child自增1沒有區別。?極端情況下，當我們判斷兩者大小時，可能出現child+1的越界訪問的問題。 因此需要在if的條件中多加上一條child+1<size。

找到更大的孩子節點、然后進行比較，這個整體是一個循環過程，因為交換到堆頂的數據最多需要進行深度h次交換，如果該數據足夠小的話。循環進行條件就是chiild<size，即下標不能越界。在發現了該節點處的數據大于等于較大子節點的數據時，就滿足了大堆性質，直接跳出循環即可。

⑤獲取堆頂元素HeapTop

HeapDataType HeapTop(Heap* php);

//獲取堆頂元素
HeapDataType HeapTop(Heap* php)
{assert(php);assert(php->size);return php->a[0];
}

有關于獲取堆頂元素的接口，我們一般與刪除堆頂元素聯合起來使用，大堆的堆頂元素讀取然后刪除，執行k次，就能夠找到這個堆中前k大的數據。

同時如果我們也可以這樣獲取降序的全部數據--->大堆就能夠獲取降序，小堆能夠獲取升序數據。

⑥獲取堆有效元素個數HeapSize

int HeapSize(Heap* php);

//獲取堆有效元素個數
int HeapSize(Heap* php)
{assert(php);return php->size;
}

⑦判斷堆是否為空HeapEmpty

bool HeapEmpty(Heap* php);

//判斷堆是否為空
bool HeapEmpty(Heap* php)
{assert(php);return php->size == 0;
}

堆的應用

1.堆排序問題

時間復雜度O(N*logN)。

上面通過數組實現了堆，那么給定一個數組，我們當然可以將數組的數據插入的堆結構中，進行向上調整，然后通過獲取堆頂數據，刪除堆頂向下調整的小套餐來打印排序后的數據，但是這樣的操作有兩個缺點：①需要一個完整的堆結構②原數組其實沒有改變

那么實際上不需要如上操作進行排序，堆排序可以對該數組重新排序。

升序--->①建立大堆②進行排序

大堆父結點大于子節點，為什么會升序？===>這就涉及到偽刪除，我們利用到堆接口函數刪除堆頂元素的實現，本質是將尾部數據與堆頂數據互換再刪除堆頂數據，那么其實此時堆頂數據在末尾，只要我們不刪除，就能夠實現每一次的偽刪除會將最大的數據移動到數組尾部。每一次互換之后我們需要進行向下調整，當然調整不會包括互換后的尾結點數據。

降序--->①建立小堆②進行排序

降序為什么建立小堆同上。

下面演示升序：

①升序演示---建立大堆

建堆有兩種方式：我們可以通過將每個數組數據從起始開始進行向上調整；也可以從尾結點的父結點開始進行向下調整。目的都是為了將數組數據排放成堆的形式。

從起始開始向上調整：時間復雜度O(N*logN)

	//數組建堆---//方法一:第一個數據成堆，其他數據依次入堆然后向上調整 O(N*logN)for (int i=1; i < n; i++){UpAdjust(a, i);//數據依次向上調整成大堆}

從尾結點的父結點開始向下調整：時間復雜度O(N)

	//方法二:從最后一個結點的父結點開始，倒著對所有非葉子結點進行向下調整 O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--){DownAdjust(a, n, i);}

起始我們也能看出來時間復雜度差在哪里，對于方式二而言，最后一層結點數最多，但是對于方式二卻不用對它們進行任何次數的調整，因此時間復雜度比方式一要小。

②升序演示---偽刪除/選數

將堆頂與尾部數據交換，然后傳入DownAdjust向下調整的end每次遍歷減1。第一次交換后傳入的size應該是減1之后的===>即下面代碼的end = n-1。

	//偽刪除---堆頂數據與尾部交換，size--，向下調整===>那么數組尾部就是最大數據 O(NlogN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);DownAdjust(a, end, 0);//依次向下調整end--;}

一個數據在向下調整最多層數h次，N個數據===>N*logN。

選數操作的時間復雜度O(N*logN)。?

推排序升序數組：

//堆排序
//堆排序是將給出的數組數據先排序成堆，然后再進行排序
//而不是將數據依次插入實現好的堆中
void HeapSort()//測試---堆排序
{int a[] = { 1,5,3,6,8,2,1,5,8 };int n = sizeof(a) / sizeof(a[0]);//數組建堆---//方法一:第一個數據成堆，其他數據依次入堆然后向上調整 O(N*logN)for (int i=1; i < n; i++){UpAdjust(a, i);//數據依次向上調整成大堆}//方法二:從最后一個結點的父結點開始，倒著對所有非葉子結點進行向下調整 O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--){DownAdjust(a, n, i);}//偽刪除---堆頂數據與尾部交換，size--，向下調整===>那么數組尾部就是最大數據 O(NlogN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);DownAdjust(a, end, 0);//依次向下調整end--;}for (int i = 0; i < n; i++){printf("%d ", a[i]);}
}

2.top k問題

思路一

前面接口函數中提到了top k問題的解決方法，我們可以通過將這些數據以大堆的形式全部插入到堆中，那么再循環k次來刪除k次堆頂數據并獲取前k個最大的數據。但是如果數據基數N非常大，那么我們需要為這個大堆開辟的空間是非常非常大的，舉個例子，N=100億--->100億個整型--->約為400億字節--->約為40G的內存大小，現如今普通人家的電腦內存大小，16-32G，無法完成，而且就算能夠完成，也不適用。

思路二---最優解

在top k問題中，如果要在一個非常非常大的N個數據中，找出k個最大的數據，那么我們可以通過這樣的辦法實現：

創建一個k個數據的小堆，先將最開始的k個數據存入小堆中，然后在剩余的數據依次與小堆堆頂元素比較，如果大于堆頂元素，那么覆蓋堆頂元素并向下調整，使其依然滿足小堆。那么到最后，小堆中就是最大的k個數據了。這種方法是非常便捷的，時間復雜度為O(N*logk)即O(N)，但是空間復雜度只有O(1)，而思路一的空間復雜度達到了O(N)，而且基本上難以實現。

時間復雜度O(N*logk)==O(N)。

那么通過最優解，就可以從N個數據中找k個最大的數據，假設我們在文件中保存1000000個隨機值，然后通過堆來找出k個最大的值：

首先我們在文件中寫入N=1000000個隨機值：

//TopK問題---在N個數據中找到K個最大的數據
void CreatNData()//在文件中創建1000000個數據
{FILE* fin = fopen("data.txt", "w");if (fin == NULL){perror("fopen fail");return;}int n = 10000000;srand(time(0));while (n--){int x = (rand() + n) % 1000000;//數據都是小于1000000的fprintf(fin, "%d\n", x);}fclose(fin);
}

這里寫入的數據模了1000000方便我們后續測試是否成功取出k個最大數據。

我們執行一次CreatNdatra函數，那么就能夠創建這個data.txt文件并在其中寫入1000000個數據。

由于我們需要取較大數據，那么就需要用小堆===>即原來適用于大堆的向上調整與向下調整算法需要進行細微的修改。

下面是小堆的向上向下調整算法(其實只需調整幾個大于小于號)

//小堆的向上向下調整算法
//向上調整算法---最壞情況調整深度h次，而h大概率等于logN相關---因此時間復雜度logN
void UpAdjust_lowheap(HeapDataType* a, int child)
{int parent = (child - 1) / 2;//父節點下標為子節點-1再除2while (child > 0){if (a[parent] > a[child]){Swap(&a[parent], &a[child]);child = parent;parent = (parent - 1) / 2;}elsebreak;}
}
//向下調整---時間復雜度O(logN)---小堆
void DownAdjust_lowheap(HeapDataType* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){if (child + 1 < size && a[child] > a[child + 1])//小心越界{child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = 2 * child + 1;}elsebreak;}
}

寫一個函數PrintTopK，解決topk問題：

void PrintTopK(FILE* file, int k);

創建一個minheap數組存儲k個數據，VS不支持變長數組，那么我們使用malloc開辟k個數據大小的空間給minheap。

int* minheap = (int*)malloc(sizeof(int) * k);

第一步將該文件中的前k個數據存入小堆進行向上調整；

	//讀前k個數據建小堆for (int i = 0; i < k; i++){fscanf(fout, "%d", &minheap[i]);UpAdjust_lowheap(minheap, i);}

第二步將文件中剩余的N-k個數據依次遍歷與堆頂數據比較，大于等于堆頂數據則替換堆頂數據然后進行向下調整使之依然成小堆。

	//剩下N-K個數據依次遍歷與堆頂數據比較，大于等于堆頂數據進入堆int x = 0;while (fscanf(fout, "%d", &x) != EOF)//先讀到x中，若x大于等于堆頂，放入堆頂并向下調整{if (x >= minheap[0]){minheap[0] = x;DownAdjust_lowheap(minheap, k, 0);}}

fscanf讀取結束返回EOF，那么循環條件可以直接寫作如上圖所示，將每次遍歷的文件中的數據存入x中，x與堆頂數據進行判斷，若大于等于堆頂數據，替換堆頂數據并向下調整。

注：scanf函數以及fscanf等函數，默認遇到空格或者換行\n終止。?

最后我們可以打印minheap來觀察數據，記得最后需要釋放堆中開辟的空間以及關閉文件。

	for(int i=0;i<k;i++){printf("%d ",minheap[i]);}free(minheap);minheap = NULL;fclose(fout);

前面手動添加了取模1000000，我們可以通過手動修改data.txt中的5個數據使其大于1000000，再次執行程序來觀察最大值的變化，從而判斷程序是否正確無誤。