文章中其實有很多圖來幫助了解，但是因為外鍊的原因，我電腦上的圖不能直接拉過來，要完整版的可以評論我直接發PDF版本。個人筆記，僅供參考。
樹與二叉樹
-
- 樹
-
- 常考考點
- 二叉樹
- 二叉樹的順序存儲
- 二叉樹的鍊式存儲
- 二叉樹的周遊
-
-
- 二叉樹的層次周遊
- 線索二叉樹
-
- 找中序前驅
- 中序線索化
- 先序線索化
- 後序線索化
- 中序線索二叉樹找中序後繼
- 中序線索二叉樹找中序前驅
- 先序線索二叉樹找先序後繼
- 先序線索二叉樹找先序前驅
-
- 樹的存儲結構
-
- 雙親表示法（順序存儲）
- 孩子表示法（順序+鍊式存儲）
- 孩子兄弟表示法（鍊式存儲） C
- 樹的層次周遊（廣度優先周遊）
- 樹的先根、後根周遊（深度優先周遊）
- 二叉排序樹（BST Binary Search Tree）
-
- 二叉排序樹的查找
-
- 循環結構實作
- 遞歸結構實作
- 二叉排序樹的插入
-
- 循環結構實作
- 遞歸結構實作
- 二叉排序樹的構造
- 二叉排序樹的删除
- 查找效率分析
- 平衡二叉樹
-
- 定義
- 調整最小不平衡子樹
-
- 調整1（LL）
- 調整2（RR）
- 調整3（LR）
- 調整4（RL）
- 查找效率分析
- 哈夫曼樹
-
- 帶權路徑長度
- 哈夫曼樹的定義（Huffman Tree）
- 哈夫曼樹的構造
樹
·結點之間的路徑隻能從上往下
·結點的度：結點的分支數
·樹的度：樹中各節點的度的最大值
常考考點
- 結點數 = 總度數 + 1（根結點的頭上沒有分支）；
- 度為m的樹、m叉樹的差別；<img
- 度為m的樹第i層至多有 m i − 1 m^{i-1} mi−1個結點（i >= 1），m叉樹第i層至多有 m i − 1 m^{i-1} mi−1個結點（i >= 1）；
- 高度為h的m叉樹至多有 m h − 1 m − 1 \frac{m^h-1}{m-1} m−1mh−1個結點（等比數列求和）；
- 高度為h的m叉樹至少有h個結點，高度為h、度為m的樹至少有h+m-1個結點；
- 具有n個結點的m叉樹的最小高度為 ⌈ log m ( n ( m − 1 ) + 1 ) ⌉ \lceil\log_m(n(m-1)+1)\rceil ⌈logm(n(m−1)+1)⌉
二叉樹
1.滿二叉樹 2.完全二叉樹 3.二叉排序樹 4.平衡二叉樹
常考考點：
- 設非空二叉樹中度為0、1和2度結點個數分别為 n 0 、 n 1 n_0、n_1 n0、n1和 n 2 n_2 n2，則 n 0 = n 2 + 1 n_0 = n_2 + 1 n0=n2+1
- 二叉樹第i層至多有 2 i − 1 2^{i-1} 2i−1個結點（i >= 1）
- 高度為h的二叉樹至多有 2 h − 1 2^h - 1 2h−1個結點
-
具有n個（n>0）結點的完全二叉樹的高度h為 ⌈ log 2 ( n + 1 ) ⌉ \lceil\log_2(n+1)\rceil ⌈log2(n+1)⌉或 ⌊ log 2 n ⌋ + 1 \lfloor\log_2n\rfloor+1 ⌊log2n⌋+1
5 對于完全二叉樹，可以由結點數n推出度為0、1和2的結點個數 n 0 、 n 1 n_0、n_1 n0、n1和 n 2 n_2 n2
二叉樹的順序存儲
#define MaxSize 100
struct TreeNode{
ElemType value; //結點中的資料元素
bool isEmpty; //結點是否為空
};
TreeNode t[MaxSize];
//初始化
for (int i=0; i<MaxSize; i++){
t[i].isEmpty = true;
}
對于完全二叉樹：[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-9xzA6fog-1585843866454)(/Users/zyairelu/Library/Application%20Support/typora-user-images/Screen%20Shot%202020-04-01%20at%207.00.09%20PM.png)]
二叉樹的鍊式存儲
struct ElemType{
int value;
};
typedef struct BiTNode{
ElemType data; //資料域
struct BiTNode *lchild, *rchild; //左、右孩子指針
struct BiTNode *parent; //父結點指針
}BiTNode, *BiTree;
//定義一棵空樹
BiTree root = NULL;
//插入根結點
root = (BiTree)malloc(sizeof(BiTNode));
root -> data = {1};
root -> lchild = NULL;
root -> rchild = NULL;
//插入新結點
BiTNode * p = (BiTNode *)malloc(sizeof(BiTNode));
p -> data = {2};
p -> lchild = NULL;
p -> rchild = NULL;
root -> lchild = p; //作為根結點的左孩子
· n個結點的二叉連結清單共有n+1個空鍊域
二叉樹的周遊
- 先序周遊：根左右（NLR）
- 中序周遊：左根右（LNR）
- 後序周遊：左右根（LRN）
二叉樹的層次周遊
算法思想：
· 初始化一個輔助隊列；
·根結點入隊；
·若隊列非空，則隊頭結點出隊，通路該結點，并将其左、右孩子插入隊尾（如果有的話）
·重複第三步直至隊列為空
線索二叉樹
找中序前驅
//中序周遊
void FindPre(BiTree T){
if (T != NULL){
FindPre(T -> lchild); //遞歸周遊左子樹
visit(T); //通路根結點
FindPre(T -> rchild); //遞歸周遊右子樹
}
}
//通路結點q
void visit(BiTNode *q){
if (q == p) //目前通路結點剛好是結點p
final = pre; //找到p的前驅
else
pre = q; //pre指向點錢通路的結點
}
//輔助全局變量，用于查找結點p的前驅
BiTNode *p; //p指向目标結點
BiTNode *pre = NULL; //指向目前通路結點的前驅
BiTNode *final = NULL; //用于記錄最終結果
中序線索化
//全局變量pre，指向目前通路結點的前驅
ThreadNode *pre = NULL;
//中序線索化二叉樹
void CreateInThread(ThreadTree T){
pre = NULL; //pre初始為NULL
if (T != NULL){ //非空二叉樹才能線索化
InThread(T); //中序線索化二叉樹
if (pre -> rchild == NULL)
pre -> rtag = 1; //處理周遊的最後一個結點
}
}
//線索二叉樹結點
typedef struct ThreadNode{
ElemType data; //資料域
struct BiTNode *lchild, *rchild; //左、右孩子指針
int ltag, rtag; //左、右線索标志
}ThreadNode, *ThreadTree;
//中序周遊二叉樹，一邊周遊一邊線索化
void InThread(ThreadTree T){
if (T != NULL){
InThread(T -> lchild);
visit(T);
InThread(T -> rchild);
}
}
void visit(ThreadNode *q){
if (q -> lchild == NULL){
q -> lchild = pre;
q -> ltag = 1;
}
if (pre != NULL && pre -> rchild == NULL){
pre -> rchild = q;
pre -> rtag = 1;
}
pre = q;
}
先序線索化
//全局變量pre，指向目前通路結點的前驅
ThreadNode *pre = NULL;
//中序線索化二叉樹
void CreateInThread(ThreadTree T){
pre = NULL; //pre初始為NULL
if (T != NULL){ //非空二叉樹才能線索化
InThread(T); //中序線索化二叉樹
if (pre -> rchild == NULL)
pre -> rtag = 1; //處理周遊的最後一個結點
}
}
//線索二叉樹結點
typedef struct ThreadNode{
ElemType data; //資料域
struct BiTNode *lchild, *rchild; //左、右孩子指針
int ltag, rtag; //左、右線索标志
}ThreadNode, *ThreadTree;
//先序周遊二叉樹，一邊周遊一邊線索化
void InThread(ThreadTree T){
if (T != NULL){
visit(T);
if (T -> ltag == 0) //important! 判斷lchild不是前驅線索
InThread(T -> lchild);
InThread(T -> rchild);
}
}
void visit(ThreadNode *q){
if (q -> lchild == NULL){
q -> lchild = pre;
q -> ltag = 1;
}
if (pre != NULL && pre -> rchild == NULL){
pre -> rchild = q;
pre -> rtag = 1;
}
pre = q;
}
後序線索化
同上理
中序線索二叉樹找中序後繼
//找到以p為根的子樹中，第一個被中序周遊的結點
ThreadNode *Firstnode(ThreadNode *p){
//循環找到最左下結點（不一定是葉結點）
while(p->ltag == 0) p = p->lchild;
return p;
}
//在中序線索二叉樹中找到結點p的後繼結點
ThreadNode *Nextnode(ThreadNode *p){
//右子樹中最左下結點
if (p->rtag == 0) return Firstnode(p->rchild);
else return p->rchild; //rtag == 1直接傳回後繼線索，即是中序後繼
}
//對中序線索二叉樹進行中序周遊 （利用線索實作的非遞歸算法 空間複雜度O(1)）
void Inorder(ThreadNode *T){
for(ThreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p))
visit(p);
}
中序線索二叉樹找中序前驅
//找到以p為根的子樹中，最後一個被中序周遊的結點
ThreadNode *Lastnode(ThreadNode *p){
//循環找到最左下結點（不一定是葉結點）
while(p->rtag == 0) p = p->rchild;
return p;
}
//在中序線索二叉樹中找到結點p的前驅結點
ThreadNode *Prenode(ThreadNode *p){
//左子樹中最右下結點
if (p->ltag == 0) return Lastnode(p->lchild);
else return p->lchild; //rtag == 1直接傳回前驅線索，即是中序前驅
}
//對中序線索二叉樹進行逆向中序周遊 （利用線索實作的非遞歸算法 空間複雜度O(1)）
void Inorder(ThreadNode *T){
for(ThreadNode *p = Lastnode(T); p != NULL; p = Prenode(p))
visit(p);
}
先序線索二叉樹找先序後繼
//在先序線索二叉樹中找到結點p的後繼結點
ThreadNode *Nextnode(ThreadNode *p){
//若p有左孩子，則先序後繼為左孩子，否則為右孩子
//若均無，則為它自己，表明為最後一個結點
if (p->lchild != 0) return p->lchild;
else if (p->rchild != 0) return p->rchild;
else return p;
}
//對先序線索二叉樹進行中序周遊，根結點為起始
void Inorder(ThreadNode *T){
for(ThreadNode *p = root; p != NULL; p = Nextnode(p))
visit(p);
}
先序線索二叉樹找先序前驅
隻有知道p的父結點，才可以找到先序前驅。
後序線索二叉樹與先序線索二叉樹找前驅後繼相似。
樹的存儲結構
雙親表示法（順序存儲）
#define MAX_TREE_SIZE 100 //樹中最多結點
typedef struct{ //樹的結點定義
ElemType data; //資料元素
int parent; //雙親位置域
}PTNode;
typedef struct{ //樹的類型定義
PTNode nodes[MAX_TREE_SIZE]; //雙親表示
int n; //結點數
}PTree;
孩子表示法（順序+鍊式存儲）
struct CTnode{
int child; //孩子結點在數組中的位置
struct CTNode *next; //下一個孩子
};
typedef struct{
CTBox nodes[MAX_TREE_SIZE];
int n, r; //結點數和根的位置
}CTree;
孩子兄弟表示法（鍊式存儲） C
typedef struct CSNode{
ElemType data; //資料域
struct CSNode *firstchild, *nextsibling; //第一個孩子和右兄弟指針
}CSNode, *CSTree;
樹的層次周遊（廣度優先周遊）
用隊列實作：
- 若樹非空，則根結點入隊；
- 若隊列非空，隊頭元素出隊并通路，同時将該元素的孩子依次入隊；
- 重複2直到隊列為空
樹的先根、後根周遊（深度優先周遊）
樹的後根周遊序列與這棵樹相應的二叉樹的中序序列相同。
二叉排序樹（BST Binary Search Tree）
左子樹結點值 < 根結點值 < 右子樹結點值
=> 用中序周遊後，可以得到一個遞增的有序序列
二叉排序樹的查找
循環結構實作
//二叉排序樹結點
typeof struct BSTNode{
int key;
struct BSTNode *lchild, *rchild;
}BSTNode, BSTree;
//在二叉排序樹中查找值為key的結點
BSTNode *BST_Search(BSTree T, int key){
while(T != NULL && key != T->key){ //若樹空或等于key的值，則結束
if (key < T->key) T = T->lchild; //小于，則在左子樹上查找
else T = T->rchild; //大于，則在右子樹上查找
}
return T;
}
遞歸結構實作
BSTNode *BSTSearch(BSTree T, int key){
if (T == NULL)
return NULL; //查找失敗
if (key == T->key)
return T; //查找成功，傳回結點T
else if (key < T->key)
return BSTSearch(T->lchild. key); //在左子樹中查找
else
return BSTSearch(T->rchild, key); //在右子樹中查找
}
二叉排序樹的插入
循環結構實作
BSTNode *BST_Insert(BSTree &T, int key){
while(T->key != NULL){
if (T->key == key) //已經存在了該值，則插入失敗
return 0;
else if (T->key < key) //左子樹
T = T->lchild;
else
T = T->rchild;
}
T->key = key;
return 1; //插入成功
}
遞歸結構實作
遞歸實作，最壞空間複雜度為O(h)，h為深度。
int BST_Insert(BSTree &T, int k){
if (T == NULL){ //原樹為空，新插入的結點即為根結點
T = (BSTree)malloc(sizeof(BSTNode));
T->key = k;
T->lchild = NULL;
T->rchild = NULL;
return 1; //傳回1，則插入成功
}
else if (k == T->key) //原樹中已經存在了相應的值，則插入失敗
return 0;
else if (k < T->key) //插入到左子樹
return BST_Insert(T->lchild, k);
else //插入到右子樹
return BST_Insert(T->rchild, k);
}
二叉排序樹的構造
//按照 str[]中關鍵字序列建立二叉排序樹
void Creat_BST(BSTree &T, int str[], int n){
T = NULL; //初始時T為空樹
int i = 0;
while (i < n){
BST_Insert(T, str[i]);
i++;
}
}
//舉個例子
void main(){
str = [13, 15, 8, 5, 9, 12];
int n = sizeof(str);
BSTree T;
Creat_BST(&T, str, n); //over
}
值得注意的是，具有相同元素的str，因素順序的不同排列可能會産生相同或不相同的二叉排序樹。
二叉排序樹的删除
- 若被删除結點z是葉結點，則直接删除；
- 若結點z隻有一棵左子樹或一棵右子樹，則讓z的子樹成為z父結點的子樹，替代z的位置；
- 若結點z有左、右兩棵子樹，則令z的直接後繼（或直接前驅）替代z，然後從二叉排序樹中删去這個替代本體[左子樹的最大值或者右子樹的最小值]，然後再按照1，2步的方法繼續。
查找效率分析
查找成功的平均查找長度 ASL（Average Search Length)
A S L = 每 個 結 點 查 找 長 度 之 和 結 點 總 數 ASL = \frac{每個結點查找長度之和}{結點總數} ASL=結點總數每個結點查找長度之和
查找失敗的平均查找長度 ASL（Average Search Length)
A S L = 每 個 空 葉 結 點 查 找 長 度 之 和 空 葉 結 點 總 數 ASL = \frac{每個空葉結點查找長度之和}{空葉結點總數} ASL=空葉結點總數每個空葉結點查找長度之和
平衡二叉樹
定義
平衡二叉樹（Balanced Binary Tree），簡稱平衡樹（AVL樹）——樹上任一結點的左子樹和右子樹的高度之差不超過1。
結點的平衡因子 = 左子樹高 - 右子樹高
故可以定義平衡二叉樹結點：
//平衡二叉樹結點
typedef struct AVLNode{
int key; //資料域
int balance; //平衡因子
struct AVLNode *lchild, *rchild;
}AVLNode, *AVLTree;
調整最小不平衡子樹
調整1（LL）
調整2（RR）
調整3（LR）
調整4（RL）
總結來看，就是調整最小不平衡子樹，則其他的子樹包括總的樹都會平衡。
查找效率分析
平衡二叉樹——樹上任一結點的左子樹和右子樹的高度之差不超過1.
假設以 n h n_h nh表示深度為 h h h的平衡樹中含有的最少結點數，
則有$n_0 = 0, n_1 = 2, $ 并且有 n h = n h − 1 + n h − 2 + 1 n_h = n_{h-1} + n_{h-2} + 1 nh=nh−1+nh−2+1.
是以含有 n n n個結點的平衡二叉樹的最大深度為 O ( log 2 n ) O(\log_2n) O(log2n)，平衡二叉樹的平均查找長度為 O ( log 2 n ) O(\log_2n) O(log2n)。
哈夫曼樹
帶權路徑長度
· 結點的權：有某種現實含義的數值（如：表示結點的重要性等）
· 結點的帶權路徑長度：從樹的根到該結點的路徑長度（經過的邊數）與該結點上權值的乘積
· 樹的帶權路徑長度：樹中所有葉結點的帶權路徑長度之和（WPL, Weighted Path Length)
W P L = ∑ i = 1 n w i l i WPL = \sum_{i=1}^n{w_il_i} WPL=i=1∑nwili
哈夫曼樹的定義（Huffman Tree）
在含有 n n n個帶權葉結點的二叉樹中，其中帶權路徑長度（WPL）最小的二叉樹稱為哈夫曼樹，也稱最優二叉樹。
哈夫曼樹的構造
給定 n n n個權值分别為 w 1 , w 2 , . . . , w n w_1, w_2,...,w_n w1,w2,...,wn的結點，構造哈夫曼樹的算法描述如下：
- 将這 n n n個結點分别作為 n n n棵僅含一個結點的二叉樹，構成森林 F F F；
- 構造一個新結點，從 F F F中選取兩棵根結點權值最小的樹作為新結點的左、右子樹，并且将新結點的權值置為左、右子樹上根結點的權值之和；
- 從 F F F中删除剛才選出的兩棵樹，同時将新得到的樹加入 F F F中；
- 重複步驟2和3，直至 F F F中剩下一棵樹為止。