1.樹

1.1.樹的概念

樹是一種非線性的數據結構，是由n(n>=0)個有限結點組成的具有層次關系的集合

• 樹的結構類似于一棵倒掛的樹(根在上，枝葉在下)
• 根節點是一個特殊的結點，它沒有前驅結點
• 除去根結點，其余結點又被分成了m(m>=0)個集合，這些集合被稱為根結點的子樹
• 每個子樹又是一個與樹相似的結構，都只有一個前驅，有0或多個后繼，因此樹是遞歸定義的

1.2.樹的結構

在樹形結構中，子樹之間不能有交集，否則就是非樹形結構
非樹形結構：

1.3.樹的相關術語

父結點/雙親結點：若一個結點含有前驅結點，則這個前驅結點就是該結點的父結點，如圖：A是B、C、D的父結點，B是E、F的父結點···
子結點/孩子結點：若一個結點有后繼節點，那么這個后繼結點就是該結點的子結點，如圖：B是A的子結點，G是D的子結點···
結點的度：一個結點含有的子結點個數就是該結點的度，如圖：A的度為3，C的度為0···
樹的度：一棵樹中，我們把所有結點中最大的度，稱為樹的度，如圖：度為3(A和D的度最大)
葉?結點/終端結點：度為0的結點，如圖：J、K、L、M···
分?結點/?終端結點：度不為 0 的結點，如圖：B、C、D、E、F···
兄弟結點：具有相同?結點的結點互稱為兄弟結點(親兄弟)，如圖：B、C 是兄弟結點
結點的層次：從根開始定義起，根為第 1 層，根的?結點為第 2 層，以此類推
樹的?度或深度：樹中結點的最?層次，如圖：高度為4
結點的祖先：從根到該結點所經分?上的所有結點，如圖： A是所有結點的祖先
路徑：?條從樹中任意節點出發，沿?結點-?結點連接，達到任意節點的序列，?如A到O的路徑為：
A-D-I-O
?孫：以某結點為根的?樹中任?結點都稱為該結點的?孫，如圖：所有結點都是A的?孫
森林：由 m（m>0） 棵互不相交的樹的集合稱為森林

2.二叉樹

2.1.二叉樹的概念

二叉樹是最常見的樹形結構結構，通常由一個根節和兩課子樹構成

1. 二叉樹中，每個結點的度都不大于2
2. 二叉樹是有序樹，左右子樹有次序之分，不能顛倒

2.2.特殊的二叉樹

2.2.1.滿二叉樹

若一個二叉樹中，每一層結點數都達到了最大值，那么這棵樹就是滿二叉樹，假設層數為k，那么總結點個數為$2^k?1$

2.2.2.完全二叉樹

完全二叉樹是由滿二叉樹得來的，最后一層的結點個數不一定達到最大，其他層結點個數都到達最大值，且結點從左到右排列

2.3.二叉樹的特性

規定根結點的層數為1:

1. 二叉樹第i層上最多有$2^{i?1}$個結點
2. 深度為k的二叉樹，最多有$2^k$個結點
3. 結點個數為n的滿二叉樹，它的深度為$lo{g}_2(n+1)$

2.4.二叉樹的存儲結構

一般分為順序存儲和鏈式存儲兩種

2.4.1.順序結構

即用數組(順序表)按順序存儲每一個節點

2.4.2.鏈式結構

用鏈表來表示二叉樹，每一個節點都包含兩個指針，分別指向自己的左孩子結點和右孩子結點，若該節點沒有對應的孩子結點，則對應的指針為空

3.堆

3.1.堆的概念

大根堆/大堆/最大堆：把數據按照順序存儲的方式存儲到一個完全二叉樹中，其中根結點最大，每個結點的左右結點都不大于它本身，這樣的存儲結構就叫大根堆
小根堆/小堆/最小堆：把數據按照順序存儲的方式存儲到一個完全二叉樹中，其中根結點最小，每個結點的左右結點都不小于它本身，這樣的存儲結構就叫小根堆

假設根節點序號為0，節點總數為n(n>0)，取任意結點序號為i,則
左孩子序號=2i+1(<n)，若結果大于等于n，則該結點沒有左孩子
右孩子序號=2i+2(<n)，若結果大于等于n，則該結點沒有右孩子

3.2.堆的實現

3.2.1.堆結構的定義

由于堆是按照順序存儲方式存儲的，所以結構體中的成員要包含一個數組(指針)、有效數據個數、數組的空間大小

//堆的結構
typedef int HPDataType;
struct Heap{HPDataType* arr;int size;//有效數據個數int capacity;//空間大小
}HP;

3.2.2.堆的初始化

把所有成員置為空即可

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

3.2.3.堆的銷毀

釋放數組，把成員都置為空即可

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

3.2.4.插入數據

3.2.4.1.向上(下)調整算法

由于插入數據后，會破壞堆的平衡，因此我們要創建一個函數，用來調整堆中的數據位置，使堆再次保持平衡

向上調整算法：以創建小堆為例，從當前節點開始，與它的父節點比較，如果它小于父節點，那么與父節點交換位置，繼續從他的父節點重復該操作，直到遇到根節點或當前節點不小于父節點為止
交換數據函數：

void swap(HPDataType* a, HPDataType* b)
{HPDataType tmp = *a;*a = *b;*b = tmp;
}

向上調整算法：

//logn
void AjustUp(HPDataType* arr, int child)
{//一直向上比較并調整 直到遇到根節點while(child > 0){//計算父節點int parent = (child - 1)/2;//比較//建小堆 <//建大堆 >if(arr[child] < arr[parent]){swap(&arr[child], &arr[parent]);child = parent;}else{break;}}
}

向下調整算法：以創建小堆為例，從根節點開始，與左右孩子中最小的比較，若根節點大于它，則跟它交換位置，并從該孩子節點繼續重復以上操作，直到當前節點下標超出節點總數或左右孩子結點都不小于它為止

//logn
void AJustDown(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;}}
}

3.2.4.2.插入數據

在數組末尾插入數據，再用向上調整算法使堆平衡即可

void HPPush(HP* php, HPDataType x)
{assert(php);//空間不夠 擴容if(php->capacity == php->size){int newCapacity = php->capacity==0 ? 4 : 2*php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType)*newCapacity);//擴容失敗if(tmp == NULL){perror("Realoc Failed!");exit(1);}php->arr = tmp;php->capacity = newCapacity;}php->arr[php->size++] = x;//向上調整AjustUp(php->arr, php->size-1);
}

3.2.5.堆的判空

判斷size是否等于0即可

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

3.2.6.刪除(堆頂)數據

先判斷堆是否為空，若不為空，交換堆頂數據與數組末尾數據的位置，size–，再用向下調整算法使堆平衡即可

void HPPop(HP* php)
{assert(!HPEmpty(php));swap(&php->arr[0], &php->arr[php->size-1]);--php->size;AJustDown(php->arr, 0, php->size);
}

3.2.7.取堆頂數據

若堆不為空，返回數組第一個元素即可

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

3.2.8.堆的數據個數

返回size值即可

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

3.3.完整代碼

Heap.h

//
//  Heap.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>//堆的結構
typedef int HPDataType;
typedef struct Heap{HPDataType* arr;int size;//有效數據個數int capacity;//空間大小
}HP;//初始化
void HPInit(HP* php);
//銷毀
void HPDestroy(HP* php);//交換
void swap(HPDataType* a, HPDataType* b);
//向上調整算法
void AjustUp(HPDataType* arr, int child);
//向上調整算法
void AJustDown(HPDataType* arr, int child, int n);//插入數據
void HPPush(HP* php, HPDataType x);//判空
bool HPEmpty(HP* php);//刪除數據
void HPPop(HP* php);//取堆頂元素
HPDataType HPTop(HP* php);//數據個數
int HPSize(HP* php);//打印堆
void HPPrint(HP* php);

Heap.c

//
//  Heap.c
#include "Heap.h"void HPInit(HP* php)
{assert(php);php->arr = NULL;php->size = php->capacity = 0;
}
void HPDestroy(HP* php)
{assert(php);free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}void swap(HPDataType* a, HPDataType* b)
{HPDataType tmp = *a;*a = *b;*b = tmp;
}
//logn
void AjustUp(HPDataType* arr, int child)
{//一直向上比較并調整 直到遇到根節點while(child > 0){//計算父節點int parent = (child - 1)/2;//比較//建小堆 <//建大堆 >if(arr[child] < arr[parent]){swap(&arr[child], &arr[parent]);child = parent;}else{break;}}
}
//logn
void AJustDown(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;}}
}void HPPush(HP* php, HPDataType x)
{assert(php);//空間不夠 擴容if(php->capacity == php->size){int newCapacity = php->capacity==0 ? 4 : 2*php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType)*newCapacity);//擴容失敗if(tmp == NULL){perror("Realoc Failed!");exit(1);}php->arr = tmp;php->capacity = newCapacity;}php->arr[php->size++] = x;//向上調整AjustUp(php->arr, php->size-1);
}bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}void HPPop(HP* php)
{assert(!HPEmpty(php));swap(&php->arr[0], &php->arr[php->size-1]);--php->size;AJustDown(php->arr, 0, php->size);
}HPDataType HPTop(HP* php)
{assert(!HPEmpty(php));return php->arr[0];
}
int HPSize(HP* php)
{return php->size;
}void HPPrint(HP* php)
{for(int i = 0; i < php->size; i++)printf("%d ", php->arr[i]);printf("\n");
}

main.c

//
//  main.c
#include "Heap.h"
void test(void)
{//建小堆HP hp;HPInit(&hp);HPPush(&hp, 29);HPPush(&hp, 17);HPPush(&hp, 14);HPPush(&hp, 31);HPPush(&hp, 22);HPPush(&hp, 12);HPPrint(&hp);printf("size: %d, top: %d\n", HPSize(&hp), HPTop(&hp));int k = 5;while(k--){HPPop(&hp);HPPrint(&hp);printf("size: %d, top: %d\n", HPSize(&hp), HPTop(&hp));}HPDestroy(&hp);HPPrint(&hp);
}
int main(void)
{test();return 0;
}

3.4.運行結果