1. 樹的相關概念

1.1 簡述：樹

樹是一種非線性的數據結構，其有n個有限的節點構成，樹結構具有層次性。它的形狀頗像一顆顛倒的樹，因此而被稱為樹。

補充：

1. 樹的結構中有一個特殊的結點，其沒有前驅結點，被稱為根結點。
2. 樹的結構中，其子樹間不能存在交集，若存在交集，那么，此結構就不能被稱為樹結構。

1.2 樹的概念補充

1. 節點的度：一個節點含有的子樹的個數稱為該節點的度；（A結點的度為3）
2. 葉子節點：度為0的結點；（E, F, G, D, H結點）
3. 非葉子節點：度不為0的結點（B，C, G結點）
4. 父親節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點
5. 子節點：一個節點含有的子樹的根節點稱為該節點的子節點；
6. 兄弟節點：具有相同父節點的節點互稱為兄弟節點；
7. 樹的度：一棵樹中，最大的節點的度稱為樹的度；
8. 節點的層 ：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；
9. 樹的深度 ：樹中節點的最大層次；
10. 堂兄弟結點 ：雙親在同一層的節點互為堂兄弟；
11. 祖先結點：從根到該節點所經分支上的所有節點；
12. 子孫結點 ：以某節點為根的子樹中任一節點都稱為該節點的子孫；
13. 森林： 多棵互不相交的樹的集合

2. 二叉樹

2.1 二叉樹的概念

對于樹結構的初次學習，我們來重點學習二叉樹這一結構。

由上圖可知，二叉樹具有兩個特點：

1. 二叉樹是一個結點的集合，可能為空或者由根節點，左子樹，右子樹構成。
2. 二叉樹由左右子樹之分，所以，二叉樹為一個有序樹，其順序不能顛倒。
3. 二叉樹的沒有擁有超過兩個孩子結點的結點，即二叉樹的度為2。
4. 補充：特殊的二叉樹
   <1> 滿二叉樹：除葉子結點外，所有結點都有左右孩子結點，若k二叉樹的層數，那么滿二叉樹的結點就有$k^2$ - 1個結點。
   <2> 完全二叉樹：除最后一層外，所有結點都有左右孩子結點，最后一層葉子結點連續。

2.2 二叉樹的性質

1. 若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有2^(i - 1) 個結點.
2. 若規定根節點的層數為1，則深度為h的二叉樹的最大結點數是 $2^h$ - 1.（等比數列求和）
3. 對任何一棵二叉樹, 如果度為0其葉結點個數為n, 則其度為0的結點一定比度為2的結點多一個.
4. 若規定根節點的層數為1，具有n個結點的滿二叉樹的深度，h = $lo{g}_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.3 二叉樹的存儲結構與堆

2.3.1 存儲結構

1. 順序存儲：
   其采用的方式為使用數組進行數據的存儲，其各個結點的關系通過下標之間的數學關系來實現，在物理結構上其仍為數組，此結構只適合存儲完全二叉樹。
2. 鏈式存儲：
   使用鏈表的方式來存儲數據，其存在三個域，數據域，左孩子指針域，右孩子指針域。在邏輯上，呈現鏈式的邏輯結構。

2.3.2 堆的概念

1. 堆是一棵完全二叉樹。
2. 堆分為大堆與小堆，當所有結點的值都大于孩子結點時即為大堆，當所有結點的值都小于其孩子結點時即為小堆。

2.3.3 堆的實現

1. 因為堆都是完全二叉樹，這里我們使用順序存儲的方式來進行堆的實現。
2. 在數組中若父親節點的下標為pos，其左孩子的下標為pos × 2 + 1，右孩子結點的下標為pos × 2 + 2，下標為0的元素為根結點。(順序存儲方式，使用數組來實現堆結構的方式)

我們已經知曉了如何判斷一個數組是否為堆，可我們對下面兩個問題還是沒有辦法去解決：

1. 當一個數組是堆時，我們如何保證在不斷向數組中插入數據而堆的結構不被打亂。
2. 如何將一個不是堆的數組調整為堆。
3. 如何去創建一個是堆的數組。

我們接下來進行這幾個問題的學習。

2.3.3.1 堆的向上調整法

void HeapAdjustUp(int* arr, int child)
{int parent = (child - 1) / 2;while (child > 0){if (arr[parent] < arr[child]){swap(&arr[parent], &arr[child]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

向上調整建堆：

1. 將數組中的元素從首元素開始一個一個視作插入已有的堆中在進行向上調整，初始堆為空。

那么，我們就可以進行如下操作：

for(int i = 0; i < n; i++)
{HeapAdjustUp(arr, i);
}

2.3.3.2 堆的向下調整算法

void HeapAdjustDown(int* arr, int n, int parent)
{//n為元素個數int child = parent * 2 + 1;while (child < n){if (child + 1 < n && arr[child] < arr[child + 1]){child++;}if (arr[parent] < arr[child]){swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}

向下調整法建堆：
2. 我們從最后一個非葉子結點開始，向下調整，調整過后的子樹都為堆，一直循環到根結點。

操作如下：

過程演示：

for (int j = (n - 1 - 1) / 2; j >= 0; j--)
{HeapAdjustDown(arr, n, j);
}

2.3.3.3 堆的實現

堆的結構：

typedef struct Heap
{int* data;int size;int capacity;
}Heap;

堆的初始化與銷毀：

void HeapInit(Heap* heap)
{heap->data = NULL;heap->capacity = heap->size = 0;
}void HeapDestroy(Heap* heap)
{while (heap->size){HeapPop(heap);}free(heap->data);heap->data = NULL;heap->capacity = heap->size = 0;
}

堆的元素增加與頭刪：

void CheckCapacity(Heap* heap)
{if (heap->size == heap->capacity){int newcapacity = heap->capacity == 0 ? 4 : heap->capacity * 2;int* tmp = (int*)realloc(heap->data, newcapacity * sizeof(int));if (tmp == NULL){perror("malloc failed");exit(-1);}heap->data = tmp;heap->capacity = newcapacity;}
}void HeapPush(Heap* heap, int val)
{CheckCapacity(heap);heap->data[heap->size] = val;heap->size++;HeapAdjustUp(heap->data, heap->size - 1);
}//逆置首尾元素，size--，再向下調整
//向下調整后堆仍為堆的前置條件為，左右子樹都為堆
void HeapPop(Heap* heap)
{assert(!HeapEmpty(heap));swap(&heap->data[0], &heap->data[heap->size - 1]);heap->size--;//左右子樹都為堆HeapAdjustDown(heap->data, heap->size, 0);
}

返回堆頂元素與判空：

bool HeapEmpty(Heap* heap)
{return heap->size == 0;
}int HeapTop(Heap* heap)
{assert(!HeapEmpty(heap));return heap->data[0];
}