### 一、樹的定義
定義：樹是n個結點的有限集。n=0時稱為空樹。在任意一棵非空樹中：（1）有且僅有一個特定的稱為根的結點；（2）當n>1時，其余結點可以分為m個互不相交的有限集T1、T2、...Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹。
對于樹的定義還需要強調兩點：
1.n>0時根節點是唯一的；
2.m>0時，子樹的個數沒有限制，但他們一定是互不相交的。
結點的分類
結點擁有的子樹數稱為結點的度（Degree）。度為0的結點稱為葉子結點（leaf），度不為0的結點稱為分支結點。樹的度是樹內各結點的度的最大值，如圖所示樹的度為3。
結點的子樹的根稱為該結點的孩子，相應的該結點稱為孩子的雙親（Parent）。同一個雙親的孩子之間互稱為兄弟。結點的祖先是從根到該節點所經分支上的所有結點。以某結點為根的子樹中任一結點都稱為該結點的子孫。
樹的層次（Level）的概念：
樹中結點的最大層次稱為樹的深度（Depth）。
最后，對比線性表與樹的結構：
### 二、樹的抽象數據類型
下面給出樹的一些基本和常用操作：
### 三、二叉樹的定義
二叉樹（Binary Tree）是n（n>=0）個結點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根節點和兩顆互不交互的、分別稱為根節點的左子樹和右子樹的二叉樹組成。
特殊二叉樹：
1.滿二叉樹：在一棵二叉樹中，如果所有的分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹就稱為滿二叉樹。
2.完全二叉樹：對一棵具有n個結點的二叉樹按層序編號，如果編號為i（1<i<n）的結點與同樣深度的滿二叉樹中編號為i的結點在二叉樹中位置完全相同，則這棵二叉樹稱為完全二叉樹，如圖：（除最后一層外，每一層上的結點數均達到最大值；在最后一層上只缺少右邊的若干結點）
所以滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。
四、二叉樹的性質
性質1：在二叉樹的第i層上之多有2^i-1個結點（i>=1）;
性質2：深度為K的二叉樹至多有2^k-1個結點（k>=1）；
性質3：對于任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0=n2+1。
性質4：具有n個結點的完全二叉樹的深度為【log2n】+1（【x】表示不大于x的最大整數）
### 四、二叉樹的存儲結構
1.二叉樹的順序存儲結構：
順序存儲一般適用于完全二叉樹
2.二叉鏈表
二叉樹每個結點最多有兩個孩子，所以為它涉及一個數據域和兩個指針域是比較自然的想法，我們稱這樣的鏈表叫做二叉鏈表。如圖所示：
二叉鏈表的結點結構定義代碼如下：
結構示意圖如下：
### 五、遍歷二叉樹
二叉樹的遍歷是指從根節點出發，按照某種次序依次訪問二叉樹中的所有結點，使得每個結點被訪問一次，且僅被訪問一次。
二叉樹的遍歷方法
1.前序遍歷：規則是若二叉樹為空，則空操作返回，否則先訪問根節點，然后前序遍歷左子樹，再前序遍歷右子樹。如圖所示：（根左右）
2.中序遍歷：（左根右）
3.后序遍歷（左右根）
4.層序遍歷：
下面來看一下前序遍歷算法
二叉樹的定義是用遞歸的方式，所以，實現遍歷算法也可以采用遞歸，而且極其簡潔明了：
中序遍歷算法：
后序遍歷算法：
### 六、二叉樹的建立
為了能讓每個結點確認是否有左右孩子，我們對它進行了擴展，如圖：
擴展二叉樹就可以做到一個遍歷序列確定一個二叉樹了，上圖的前序遍歷序列就是AB#D##C##。有了這樣的準備，我們就可以來看看如何生成一棵二叉樹了。實現算法如下：
### 七、霍夫曼樹及其應用
最基本的壓縮編碼方法-霍夫曼編碼，在介紹霍夫曼編碼前，我們必須得介紹霍夫曼樹，而介紹霍夫曼樹。帶權路徑長度WPL最小的二叉樹稱作霍夫曼樹。也有不少樹中稱為最優二叉樹。
二叉樹a的WPL=315，二叉樹b的WPL=220。
下面介紹一下霍夫曼樹的構造：
一、對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉樹Ti中只有一個權值為Wi的根結點，它的左右子樹均為空。（為方便在計算機上實現算 法，一般還要求以Ti的權值Wi的升序排列。）
二、在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。
三、從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中。
四、重復二和三兩步，直到集合F中只有一棵二叉樹為止。
簡易的理解就是，假如我有A,B,C,D,E五個字符，出現的頻率（即權值）分別為5,4,3,2,1,那么我們第一步先取兩個最小權值作為左右子樹構造一個新樹，即取1，2構成新樹，其結點為1+2=3，如圖：
[](http://images.cnblogs.com/cnblogs_com/Jezze/201112/201112231832079219.png)
虛線為新生成的結點，第二步再把新生成的權值為3的結點放到剩下的集合中，所以集合變成{5,4,3,3}，再根據第二步，取最小的兩個權值構成新樹，如圖：
[](http://images.cnblogs.com/cnblogs_com/Jezze/201112/20111223183207124.png)
再依次建立哈夫曼樹，如下圖：
[](http://images.cnblogs.com/cnblogs_com/Jezze/201112/201112231832082109.jpg)
其中各個權值替換對應的字符即為下圖：
[](http://images.cnblogs.com/cnblogs_com/Jezze/201112/201112231832085730.jpg)
所以各字符對應的編碼為：A->11,B->10,C->00,D->011,E->010
下面研究一下霍夫曼編碼：
一般地，設需要編碼的字符集為{d1,d2,......dn},各字符在電文中出現的次數或頻率的集合為{w1,w2,......wn}，以d1,d2,......dn作為葉子結點，以w1,w2,......wn作為相應葉子結點的權值來構造一棵霍夫曼樹。規定霍夫曼樹的左分支代表0，右分支代表1，則從根節點到葉子結點所經過的路徑分支組成的0和1的序列便為該結點對應字符編碼，這就是霍夫曼編碼。
例子：我們在發送電報的時候用到了六個字母，其出現的概率分別為：A 27，B 8，C 15， D 15，E 30，F 5,合起來正好是百分之百。
怎么獲得霍夫曼編碼呢？
首先按照比率作為權值畫霍夫曼樹，然后將左分支代表0，右分支代表1，如圖：
從根節點到葉子結點所經過的路徑分支組成的0和1的序列便為該結點對應字符編碼，即：
這樣就獲得了霍夫曼編碼。
