293
樹 總述
樹
樹是n個結點的有限集。
當n等於0時，為空樹。
當n等於1時，為根結點。
當n大於1時，其餘節點可以分為m個互不相交的有限集T1、T2、...、Tm。每個集合本身又是一棵樹，並且稱為一根結點的子樹。
顯然，樹是一種遞歸的數據結構。
樹中某結點的孩子個數稱為該結點的度。樹的度=max{結點的度}。
樹中結點數等於所有結點的度數和加1。
結點編號通常從1起，從上到下、從左到右遞增。
通常認為樹高從1算起，根結點第一層，最後一個葉結點層數最大。
節點間關係有父、祖先、兄弟、孩子、子孫。
兩個結點A、B之間的路徑就是從A到B所經過的結點的序列。路徑長度就是所經過的邊的個數。
二叉樹
二叉樹是度不大於2的 且 單個孩子結點分左右的 有序樹。在一棵有序樹中，隻有一個結點做孩子時不分左右。
二叉樹的存儲——數組、鏈表。
滿二叉樹：除葉節點外每個結點度都為2。
完全二叉樹：對一棵滿二叉樹，從後往前連續刪除若幹個結點，就成了完全二叉樹。
完全二叉樹兩個特點：(1)葉子節點隻出現在最高兩層上；(2)度為1的結點最多隻能有1個，且它隻有左孩子。
樹中數學規律
最優二叉樹
樹中結點的值代表該結點權重。從根到任意結點的路徑長度（即經過的邊數）與該結點權重之積為該結點的帶權路徑長度。
樹的帶權路徑長度，WPL，Weighted Path Length of Tree。表示樹中所有葉結點的帶權路徑長度之和。
最優二叉樹也稱為哈夫曼樹。表示帶權路徑長度最小的二叉樹。
對於一個待處理的字符序列，如果對不同字符采用同樣的編碼長度，這種編碼方式叫固定長度編碼。如果采用不等長度的二進製位表示，叫可變長度編碼。
哈夫曼編碼可以對高頻字符賦以短編碼，達到壓縮數據的目的。
給定n個權值分別為w1,w2,、、、,wn的結點，最優二叉樹的構造算法如下：
1. 將這n個結點看作n棵二叉樹組成的森林F；
2. 構造一個新節點，從森林F中選取兩棵根結點權值最小的樹作為新結點的左右子樹，並且將新結點的權值置為兩個選中樹根的權值之和。
3. 從F中刪除選中的兩棵樹，並將新構造的樹加入F。
4. 重複步驟2和3，直至F中剩下最後一棵樹為止。
平衡二叉樹
平衡樹——樹中任意一個結點的平衡因子的絕對值不大於1。
二叉樹的遍曆
字典樹
樹種一個節點的所有子孫都有相同的前綴，故常用於搜索提示。
最後更新：2017-04-03 05:40:09