樹型結構：非線性結構，以分支關系定義的層次結構。
主要內容：
樹和二叉樹的概念、性質
二叉樹的存儲
二叉樹的遍歷
線索二叉樹
樹與二叉樹的轉化
Huffman樹（最優樹）
樹(Tree)是n(n≧0)個結點的有限集合T，若n=0時稱為空樹，否則：
⑴ 有且只有一個特殊的稱為樹的根(Root)結點；
⑵ 若n>1時，其余的結點被分為m(m>0)個互不相交的子集 T1, T2, T3…Tm，其中每個子集本身又是一棵樹，稱其為根的子樹(Subtree)。
這是樹的遞歸定義，即用樹來定義樹，只有一個結點的樹僅由根組成。
⑴ 結點(node)：一個數據元素及其若干指向其子樹的分支（指針）。
⑵ 結點的度(degree) ：結點所擁有的子樹的棵數
(3)樹的度: 樹中結點度的最大值。
(4) 葉子(leaf)結點：樹中度為0的結點,又稱為終端結點。
(5) 非葉子結點:度不為0的結點，又稱為非終端結點或分支結點)。除根結點外，分支結點又稱為內部結點。
(6) 孩子結點、雙親結點、兄弟結點
一個結點的子樹的根稱為該結點的孩子結點(child)或子結點；
相應地，該結點是其孩子結點的雙親結點(parent)或父結點。
同一雙親結點的所有子結點互稱為兄弟結點
(7) 層次：規定樹中根結點的層次為1，其余結點的層次等於其雙親結點的層次加1。
若某結點在第l(l≧1)層，則其子結點在第l+1層。
(8) 堂兄弟結點：雙親結點在同一層上的所有結點.
在圖6-1(b)中結點E、F、G、H、I、J。
(9) 結點的層次路徑: 從根結點開始，到達某結點p所經過的所有結點 (有且只有一條)。
(10) 祖先：結點p的層次路徑上的所有結點（p除外） 。
(11) 子孫(descent) ：以某一結點為根的子樹中的任意結點 。
(12) 樹的深度(depth)：樹中結點的最大層次值, 在圖6-1(b)中樹的高度為4。
(13) 有序樹和無序樹：若將樹中各結點的子樹（若有）看成從左至右室有次序的（即不能互換），則該樹稱為有序樹，否則稱為無序樹。
在有序樹中，最左邊的子樹的根稱為第一個孩子，最右邊的稱為最後一個孩子。
(14)森林(forest)：m(m≧0)棵互不相交的樹的集合。
若將一棵樹的根結點刪除，剩余的子樹就構成了森林。
ADT Tree{
數據對象D：D是具有相同數據類型的數據元素的集合。
數據關系R：若D為空集，則稱為空樹；
……
基本操作：
……
} ADT Tree
1 二叉樹的定義
二叉樹是n(n≥0)個結點的有限集合。n=0時稱為空樹，否則：
⑴ 有且只有一個特殊的稱為樹的根(Root)結點；
⑵ 若n>1時，其余的結點被分成為二個互不相交的子集T1,T2，分別稱之為左、右子樹，並且左、右子樹又都是二叉樹。
二叉樹的定義是遞歸的。
說明：
1、二叉樹每個結點最多有兩棵子樹，所有結點的度都不超過2；
2、左子樹和右子樹有順序之分，次序不能顛倒；即使某結點只有一棵子樹，也要區分左右。
二叉樹在樹結構中起著非常重要的作用。因為二叉樹結構簡單，存儲效率高，樹的操作算法相對簡單，且任何樹都很容易轉化成二叉樹結構。
以上引入的有關樹的術語也都適用於二叉樹。
滿二叉樹的特點：
滿二叉樹的所有的分支結點都有左、右子樹；
所有的葉子結點都在只能出現在最下層；
非葉子結點的度一定是2；
在同樣深度的二叉樹中，滿二叉樹的結點數最多，葉子結點最多（即每一層上的結點數達到最大）；
完全二叉樹(Complete Binary Tree)：
對一顆具有n個結點的二叉樹按層序編號，如果編號為i（1<=i<=n）與同樣深度的滿二叉樹中編號為i的結點在二叉樹中位置完全相同，則該二叉樹稱為完全二叉樹。
說明：
深度為k的滿二叉樹中編號從1到n的前n個結點構成了一棵深度為k的完全二叉樹， 其中2k-1 ≦ n≦2k-1 。
完全二叉樹是滿二叉樹的一部分，而滿二叉樹是完全二叉樹的特例。
完全二叉樹的特點：
葉子結點只能出現在最下兩層；
最下層的葉子結點一定集中在左邊連續位置；
倒數第二層若有葉子結點，一定都在右邊連續位置；
如果結點度=1，則該結點只有左孩子，即不存在只有右子樹的情況；
同樣結點樹的二叉樹，完全二叉樹的深度最小；
對於任一結點，如果其右子樹的最大層次為l，則其左子樹的最大層次為l或l+1。
性質1：在非空二叉樹中，第i層上至多有2i-1個結點(i≧1)。
證明：用數學歸納法證明。
當i=1時：只有一個根結點，21-1=20 =1，命題成立。
現假設對i>1時，處在第i-1層上至多有2(i-1)-1個結點。
由歸納假設知，第i-1層上至多有2i-2個結點。由於二叉樹每個結點的度最大為2，故在第i層上最大結點數為第i-1層上最大結點數的2倍。
即 2×2i-2＝2i-1
證畢性質2：深度為k的二叉樹至多有2k-1個結點（k≧1) 。
證明：深度為k的二叉樹的最大的結點數為二叉樹中每層上的最大結點數之和。
由性質1知，二叉樹的第1層、第2層?第k層上的結點數至多有： 20、21 …2k-1 。
∴ 總的結點數至多有： 20+21+ …+2k-1=2k-1
證畢
性質3：對任何一棵二叉樹，若其葉子結點數為n0，度為2的結點數為n2，則n0=n2+1。
證明：設二叉樹中度為1的結點數為n1，二叉樹中總結點數為N，因為二叉樹中所有結點均小於或等於2，則有：N=n0+n1+n2
再看二叉樹中的分支數：除根結點外，其余每個結點都有唯一的一個分支進入，設B為二叉樹中的分支總數，則有：N=B+1。
而所有這些分支都是由度為1和2的結點發出的，所以：B＝n1+2?n2
∴ N=B+1=n1+2?n2+1
∴ n0+n1+n2=n1+2?n2+1
即 n0=n2+1 證畢
性質4：n個結點的完全二叉樹深度為：?㏒2n? +1。
其中符號： ?x?表示不大於x的最大整數（下整數）。
?x? 表示不小於x的最小整數（上整數）。
證明：假設完全二叉樹的深度為k，則根據性質2及完全二叉樹的定義有：
2k-1-1<n≦2k-1 或 2 k-1≦n<2k
取對數得：k－1<=㏒2n<k 因為k是整數。
∴ k= ?㏒2n? +1
證畢
性質5：若對一棵有n個結點的完全二叉樹(深度為?㏒2n? +1)的結點按層（從第1層到第?㏒2n? +1層)序自左至右進行編號,則對於編號為i（1≦i≦n)的結點：
⑴ 若i=1：則結點i是二叉樹的根，無雙親結點；若i>1，則其雙親結點編號是 ?i/2? 。
⑵ 如果2i>n：則結點i為葉子結點，無左孩子；否則，其左孩子結點編號是2i。
⑶ 如果2i+1>n：則結點i無右孩子；否則，其右孩子結點編號是2i+1。
證明：用數學歸納法證明。首先證明⑵和⑶，然後由⑵和⑶導出⑴。
當i=1時，由完全二叉樹的定義知，結點i的左孩子的編號是2，右孩子的編號是3。
若2>n，則二叉樹中不存在編號為2的結點，說明結點i的左孩子不存在。
若3>n，則二叉樹中不存在編號為3的結點，說明結點i的右孩子不存在。
現假設對於編號為j(1≦j≦i)的結點，(2)和(3)成立。即：
◆ 當2j≦n ：結點j的左孩子編號是2j；當2j>n時，結點j的左孩子結點不存在。
◆ 當2j+1≦n ：結點j的右孩子編號是2j+1；當2j+1>n時，結點j的右孩子結點不存在。
