樹的應(yīng)用按考綱來看的話：
1.二叉排序樹
2.堆結(jié)構(gòu)
3.哈夫曼（Huffman）樹和哈夫曼編碼
而剛好這節(jié)課剛好都講到了。
首先亥鬓，先講
二叉排序樹
也叫二叉查找樹/二叉搜索樹 BST完沪，Binary Search Tree
主要特性是：左<中<右
一些用的到的特殊函數(shù)：
①Position Find（Elemtype X，BinTree BST）
//查找值為X的位置嵌戈，返回地址
這里用尾遞歸（可用循環(huán)實現(xiàn)）丽焊，其查找效率取決于樹的高度较剃，當(dāng)出現(xiàn)斜二叉樹時是效率很差的情況。解決方法：平衡二叉樹（后面講）
②Position FindMin（BinTree BST）
主要實現(xiàn)是不斷往左遞歸（循環(huán)也可實現(xiàn)）
③Position FindMax（BinTree BST）
往右不斷遞歸
④BinTree Insert（Elemtype X技健，BinTree BST）
//插入,注意仍保持二叉排序樹的特性：左<中<右
eg 十二個月份按字典序插入
eg BST->Right = Insert（X写穴，BST->Right）;
例子中遞歸返回的樹妖賦值給其右子樹，即記錄下插入位置
⑤BinTree Delete（Elemtype X雌贱，BinTree BST）
//刪除比較麻煩啊送，先查找后刪除，根據(jù)結(jié)點不同分三種情況
（1）刪葉結(jié)點
（2）有一個兒子的結(jié)點：讓父親->孫子
（3）有左右兩個兒子的結(jié)點：兩種方案實現(xiàn)欣孤，一是 右子樹找個最小的來代替馋没，并記得再遞歸刪掉那個結(jié)點；二是 左子樹里找個最大的來代替降传，并遞歸刪掉那個結(jié)點篷朵。
因為是最值，一定只有一個兒子婆排，可以轉(zhuǎn)至（2）（1）声旺。
例子中和插入一樣，刪除的位置要記錄段只，因此
BST->Right = Insert（X腮猖，BST->Right）;有類似這樣的表示
平衡二叉樹
AVL樹 Balanced Binary Tree
上面說到我么為了提高查找效率，引入平衡二叉樹的概念赞枕，其根本是為了降低樹的高度澈缺，最好是降到log2N。
因此我們讓左右結(jié)點炕婶、高度相差盡量低姐赡。
引入平衡因子balance fator的概念BF(T)=h左-h右
對每個結(jié)點，注意是每個BF的絕對值<=1柠掂，或本身是個空樹即是AVL樹雏吭。
高度為h的AVL樹最少有幾個結(jié)點呢？列舉可以發(fā)現(xiàn)一個規(guī)律n（h）=n（h-1）+n（h-2）+1陪踩，我們想到斐波那契數(shù)列杖们，因此算出nh的值，得出其復(fù)雜度肩狂。
n個結(jié)點AVL樹的查找效率是log2n摘完。
AVL樹的調(diào)整
我們要將不平衡->平衡屋摇，本質(zhì)還是個二叉排序樹愚屁，注意保持左<中<右的特點成立
這里算個難點粘茄，分為四種
1.右單旋（RR旋轉(zhuǎn)） 麻煩結(jié)點在右子樹的右子樹的下面（接在左右都可）
2.左單旋（LL旋轉(zhuǎn)）麻煩結(jié)點在左子樹的左子樹的下面
3.LR旋轉(zhuǎn) 麻煩結(jié)點在左子樹的右子樹的下面
4.RL旋轉(zhuǎn) 麻煩結(jié)點在右子樹的左子樹的下面
堆
CPU在處理時，肯定不能按時間順序處理歉铝，而是按優(yōu)先順序處理偷办，怎么體現(xiàn)這個優(yōu)先隊列（按優(yōu)先權(quán)大小順序取出）呢猾昆，就是用堆肪凛。
存儲方式?jīng)Q定了執(zhí)行效率，假設(shè)分別按下面幾種存儲結(jié)構(gòu)來存儲杭措，他們的時間復(fù)雜度分別如下所示：
數(shù)組：插入O（1）查找O（1）刪除O（n）
鏈表：插入O（1）查找O（n）刪除O（1）
有序數(shù)組：查找O（n）或O（logn）插入O（n）刪除O（1）
有序鏈表：查找O（n）插入O（1）刪除O（n）
樹：二叉搜索樹费什，效率很高，但一直刪除最值后手素，導(dǎo)致樹傾斜鸳址，效率明顯下降
我們重點關(guān)注刪除的復(fù)雜度。
最大堆
始終注意兩點
1.結(jié)構(gòu)性：數(shù)組表示成完全二叉樹
2.有序性：任一結(jié)點的關(guān)鍵字是其子樹的所有結(jié)點的最大（腥场）值
最大堆Maxheap/大頂堆
最小堆Minheap/大頂堆
其結(jié)構(gòu)體如下
struct HeapStruct{
Elemtype *Elements;
int Size;
int Capacity;
}
操作上主要有：
建堆
判滿
判空
插入
1.若不滿稿黍，插入到Size+1的位置，先保證其完全二叉樹結(jié)構(gòu)
2.保證其有序性崩哩，與父結(jié)點比較巡球，換位置，即[i/2]與[i]循環(huán)比較
刪除
1.先用最后元素替補最大值位置邓嘹，先保證其完全二叉樹結(jié)構(gòu)
2.保證其有序性酣栈，比較左右兒子，與大的換位置吴超，循環(huán)比較
時間復(fù)雜度為logn
最大堆的建立
法1.一個個插入 O（logn）
法2.在線性時間復(fù)雜度下建①N個形成二叉樹②先保證有序性再調(diào)整（注意是從下往上調(diào)钉嘹，從后往前調(diào)鸯乃，直至整個最大堆完成）
哈夫曼樹
最優(yōu)二叉樹/WPL最小的二叉樹
查找效率：出現(xiàn)比例*比較次數(shù)
目的：構(gòu)造效率最好的搜索樹
WPL帶權(quán)路徑長度：∑Wk·Lk
其中帶權(quán)值Wk鲸阻，根結(jié)點到每個葉結(jié)點的長度Lk
typedef struct TreeNode *HuffmanTree;
struct TreeNode {
int Weight;
HuffmanTree Left，Right;
}
構(gòu)造方法
循環(huán)將權(quán)值最小的兩個形成二叉樹
選取兩個最小值可使用剛講過的堆來實現(xiàn)（排序也可實現(xiàn)缨睡，但效率低）
復(fù)雜度O（nlogn）
哈夫曼樹的特點：
①沒有n為1的結(jié)點
②n個葉結(jié)點鸟悴，共有2n-1個結(jié)點
③左右子樹交換仍未哈夫曼樹
④同一權(quán)值可能有不同構(gòu)的哈夫曼樹，但最優(yōu)化值一樣
哈夫曼編碼
一段字符串奖年，要使存儲空間最少
eg ASCII 588=464位
實際只有8種字符的話 583=174位即可
還能更少细诸，讓出現(xiàn)頻率高的字符占用更少的空間
即不等長編碼
關(guān)鍵是避免二義性，讓根結(jié)點不成為子結(jié)點的前綴碼
把二叉樹用于編碼陋守，構(gòu)造出代價最小的二叉樹震贵，即哈夫曼樹
集合
主要涉及 交、并水评、補猩系、差、判定屬于
沒怎么認(rèn)真聽
思考：
- 關(guān)于AVL樹的調(diào)整中燥，感覺自己只是知其然寇甸，大概知道怎么調(diào)整，不知道考試的深度是怎么樣，考的有多細(xì)拿霉，mark下吧吟秩，過下一遍再看下
- 老師給的討論題 AVL樹能否用兩邊的結(jié)點樹差來定義呢？貌似挺復(fù)雜的绽淘，大家可以想一想
- 樹與森林部分是否和集合類似涵防？后續(xù)會補充這方面內(nèi)容。
