讓花成花，讓樹成樹
上一次我們學習了樹的分類，并初步了解了二叉樹。
今天我們深入了解二叉樹并寫出C語言代碼

1.二叉樹的存儲結構

在學習C語言時，我們就知道了數據有兩種存儲結構，一種是順序結構，一種是鏈式結構。
對于用數組來實現的二叉樹，完全二叉樹要優于非完全二叉樹。


我們從圖中可以看到，非完全二叉樹會有空間浪費。
現實中我們通常把堆（?種?叉樹）使?順序結構的數組來存儲，需要注意的是這?的堆和操作系統虛擬進程地址空間中的堆是兩回事，?個是數據結構，?個是操作系統中管理內存的?塊區域分段。

2.實現順序結構二叉樹

堆是?種特殊的?叉樹，具有?叉樹的特性的同時，還具備其他的特性。

2.1何為堆

堆是一種樹形數據結構，每個父節點都大于或等于（最大堆）或者小于或等于（最小堆）其子節點，根節點的值是堆中所有元素的最大值或最小值。

2.2堆的性質

• 堆中某個結點的值總是不?于或不?于其?結點的值；
• 堆總是?棵完全?叉樹

在用代碼實現前，我們還需要知道一些二叉樹的性質：

2.3堆的定義

typedef int HpDataType;
typedef struct Heap {HpDataType* arr;int size;int capacity;
}Hp;

size表示有效個數
capacity表示可用容量

2.3堆的初始化與銷毀

//初始化
void HpInit(Hp* php) {assert(php);php->arr = NULL;php->size = php->capacity = 0;
}
//銷毀
void HpDestroy(Hp* php) {assert(php);if (php->arr)free(php->arr);php->size = php->capacity = 0;
}

3.1向上調整算法

當我們往堆中添加數據時，怎么能使數據自動校正自己的位置，使得其插入后任然滿足是一個堆。
對于大堆：

//向上調整
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;}}
}

每一次和父節點比較，如果比父節點大則交換并使父節點變子節點，再找新的父節點比較。否則退出循環。

3.2向下調整算法

對于大堆：

//向下調整
void AdjustDown(HpDataType* arr, int parent, int n) {int child = 2 * parent + 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 = 2 * parent + 1;}else {break;}}
}

4.入堆

//入堆
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, newcapacity * sizeof(HpDataType));if (tmp == NULL) {perror("realloc fail");exit(1);}php->arr = tmp;php->capacity = newcapacity;}php->arr[php->size++] = x;//向上調整AdjustUp(php->arr, php->size - 1);
}

5.出堆

出堆指的是堆頂元素出去。

//出堆
void HpPop(Hp* php) {assert(!HpEmpty(php));Swap(&php->arr[0], &php->arr[php->size - 1]);php->size--;//重新向上調整AdjustUp(php->arr, php->size - 1);//如果使用向下調整，換成	AdjustDown(php->arr, 0, php->size);
}

完
如果發現錯誤，歡迎打在評論區。
主頁還有更多優質內容OvO