403
二叉樹的性質和應用
二叉樹的性質
二叉樹是圖的一種特殊情形。
二叉樹與有序樹：在隻有一個孩子結點的情況下，二叉樹有左右之分、有序樹無左右之分。
非空二叉樹中，共有n個結點，度為0的結點有n0個，度為1的結點有n1個，度為2的結點有n2個，則n0=n2+1;
推導：n=n0+n1+n2;
n-1=n1+2*n2; 聯立得解。（最愛考這個了...）
非空二叉樹第i層上至多有2^(i-1)個結點；//pow(2,i-1)
高為h的二叉樹最多有2^h-1個結點；//pow(2,h)-1
完全二叉樹的性質：
對完全二叉樹按從上到下。從左到右的次序標號1,2，...，n。有如下性質：
1.i>1時，i結點的父節點為int(i/2);
2.i結點的左孩子為2*i，右孩子為2*i+1;
3.i結點所在的層次為int (log(下標：2)(表達式：i))+1; //floor(log(i)/log(2))+1
二叉排序樹
二叉排序樹（Binary Sort Tree）又稱二叉查找樹，亦稱二叉搜索樹。 特點：左孩子結點值<=根結點值<=右孩子結點值。所以對其中序遍曆可得到遞增數列。
平衡二叉樹（AVL）
樹中每個結點的左右子樹高度差的絕對值<=1。
最優二叉樹
帶權路徑長度：根結點到x結點的路徑長度*x結點的權值；
樹的帶權路徑長度：所有葉子結點的帶權路徑長度之和；
給定n個權值作為n個葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman tree)。
哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。
哈夫曼樹的構造：
給定n個權重分別為w1,w2,...,wn的結點，構造最優二叉樹的算法見下：
1.將每個結點作為一個樹，構成森林F；
2.構造一個新結點，從森林F中挑選兩個根結點權重最小的樹T1與T2作為新結點的左右子樹；
3.從F中刪除T1、T2，將新構造的樹加入F；
4.重複步驟2、3，知道森林中隻有一棵樹為止。
數據結構：堆——可以看作特殊的完全二叉樹。
小根堆中，左孩子結點值與右孩子結點值均小於根結點值。同理有大根堆。用途之一：堆排序。
堆排序需要解決兩個問題
1.如何由無序序列組成小根堆？
2.輸出最大元素後，如何調整堆？
解答：
1.先將n個元素隨意排列成完全二叉樹。依次對n、n-1、...、1號結點進行調整。若其值小於父結點，進行對調。
2.輸出後，將最後一個結點放到堆頂，再自上而下調整，直至葉結點。
最後更新：2017-04-03 12:55:50