一、樹和二叉樹的定義與存儲

1.樹的定義

樹是一種非線性的數據結構，它是由n個有限結點組成有層次關系的集合

樹具有以下特點：

（1）每個結點具有0個或多個子結點

（2）每個子結點只有一個父結點

（3）沒有前驅的結點為根結點

（4）除了根結點外，每個子結點又可以由m棵不相關的子樹組成

2.樹的基本術語

（1）結點的度:結點擁有的子樹數量稱為結點的度

（2）樹的度:樹內各結點度的最大值，即上圖 D結點的度就是此樹的度

（3）葉子:度為 0的節點稱為葉子或終端節點

（4）結點的層次和樹的深度

結點的從根開始定義起，根為第一層，根的孩子為第二層，以此類推，樹的深度或高度是樹中結點的最大層次

（5）森林:m棵互不相交的樹的集合

3.二叉樹與樹主要有以下區別：

（1）二叉樹每個結點至多只有兩顆子樹（即二叉樹中不能存在度大于2的結點）

（2）二叉樹的子樹有左右之分，其次序不能任意顛倒

（3）即使樹中某結點只有一顆子樹，也要區分它是左子樹還是右子樹

4.二叉樹的性質:

性質1:在二叉樹的第i層上至多有 2的i-1次方 個結點(i>=1)

性質2:深度為k的二叉樹至多有 2的k次方-1?個結點(k>=1)

性質3:對任何一棵二叉樹T，如果其終端結點數為n0,度為2的結點數為n2，則n0=n2+1

【證明】一棵二叉樹，除了終端結點(葉子結點)，就是度為1或2的結點。假設n1表示度為1的結點數，則樹T的結點總數n=n0+n1+n2,我們再換個角度，看一下樹T的連接線數，除了根節點，其他結點都有一根線表示分支進入，所以連接線數為結點總數減去1。按連接線樹算的話:n-1=n1+2n2，可推導出n0+n1+n2-1=n1+2n2，繼續推導可得n0=n2+1

性質4:具有n個結點的完全二叉樹的深度為（這里的[]是向下取整）

性質5：如果對一顆有n個結點的完全二叉樹(其深度為)的結點按層序編號(從第1層到第層，每層從左到右)，對任一結點i(1<=i<=n)有:

（1）如果 i = 1，則結點 i 是二叉樹的根，無雙親;如果 i > 1，則其雙親是結點[i/2]

（2）如果 2i > n,則結點 i 無孩子(結點 i 為葉子結點);否則其左孩子是結點 2i

（3）如果 2i+1 > n ,則結點i無右孩子;否則其右孩子是結點 2i+1

5.二叉樹的存儲：順序存儲、鏈式存儲

（1）二叉樹的順序存儲結構缺點很明顯：不能反應邏輯關系；對于特殊的二叉樹（左斜樹、右斜樹），浪費存儲空間。所以二叉樹順序存儲結構一般只用于完全二叉樹

（2）二叉樹的鏈式存儲

//二叉樹的二叉鏈表存儲表示
typedef struct BiTNode{
//結點數據域TElemType data;
//左右孩子指針struct BiTNode *1child,*r1child;
}BiTNode,*BiTree;

?

二、二叉樹的遍歷

二叉樹的遍歷:按某條搜索路徑訪問二叉樹中每一個結點，使得每個結點被訪問一次且僅被訪問一次。遍歷方法有4種:先序遍歷，中序遍歷，后序遍歷，層次遍歷

1.先序遍歷

（1）訪問根節點

（2）先序遍歷左子樹

（3）先序遍歷右子樹

先序遍歷序列（根左右）：abcdfge

2.中序遍歷

（1）中序遍歷左子樹

（2）訪問根節點

（3）中序遍歷右子樹

中序遍歷序列（左根右）：bafgdce

3.后序遍歷

（1）后序遍歷左子樹

（2）后序遍歷右子樹

（3）訪問根結點

后序遍歷序列（左右根）：bgfdeca

簡便方法：

4.層序遍歷

按層次（1-k層），每層從左到右依次訪問二叉樹中的每個結點

層次遍歷序列：abcdefg

eg：已知二叉樹先序遍歷序列是：abcdefg；中序遍歷序列是：cbdaefg

（1）畫出該二叉樹

（2）寫出后序遍歷序列??

cdbgfea

三、哈夫曼樹

1.基本概念識記

（1）路徑:從一個結點到另一個結點之間的分支序列

（2）路徑長度:從一個結點到另一個結點所經過的分支數目

（3）結點的權:根據應用的需要可以給樹的結點賦權值

（4）結點的帶權路徑長度:從根到該結點的路徑長度與該結點權的乘積

（5）樹的帶權路徑長度:樹中所有葉子結點的帶權路徑之和

其中，n是樹的葉結點個數，wk是第k個葉子的權，lk是第k個葉子到根的路徑長度。

（6）哈夫曼樹:由n個帶權葉子結點構成的所有二叉樹中帶權路徑長度最短的二叉樹

n個葉子結點的哈弗曼樹有(2n-1) 個結點

在構造哈弗曼樹時，是從葉子結點向根節點的方向進行的，每次都是兩個兩個成對的結點來形成一個新的分支結點，所以不存在度為1的結點。

2.哈夫曼樹的構造

對于有n個葉子結點，可以構造出多個二叉樹。但Huffman樹是一個帶權路徑長度最小的二叉樹，又稱最優二又樹。方法:

(1)將{w1,w2.,…,wn}看成n個二叉樹;
(2)選擇2個根結點的值最小的二叉樹，構造1個新的二叉樹;......; 直至剩1個樹止。

eg：某系統在通信聯絡中只可能出現8個字符，其出現概率分別是：

Z? ?K? ?F? ?C? ?U? ?D? ?L? ?E

2? ?7? 24? 32? 37 42? 42? 120

請構造哈夫曼樹

（1）排序：

（2）依次選取兩個最小的連在一起

進行排版：

3.哈夫曼編碼

前綴碼:如果在一個編碼系統中，任一個編碼都不是其他任何編碼的前綴，則稱該編碼系統中的編碼是前綴碼。例如，一組編碼01,001,010,100,110就不是前綴碼，因為01是010的前綴，若去掉01或010就是前綴碼。

哈夫曼編碼:對一棵具有n個葉子的哈夫曼樹，若對樹中的每個左分支賦予0，右分支賦子1，則從根到每個葉子的通路上，各分支的賦值分別構成一個二進制串，該二進制串就稱為哈夫曼編碼。

哈夫曼編碼是最優前綴碼

?

四、習題

答案：A

解釋：因為二叉樹有左孩子、右孩子之分，故一棵樹轉換成二叉樹之后，這棵二叉樹的形態是唯一的

答案：D

解釋：枚舉法

??

答案：D

解釋:設度為0結點((葉子結點)個數為A，度為1的結點個數為B，度為2的結點個數為C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉樹的性質可得B=0或1，又因為C為整數，所以B=0，C=500，A=501，即有501個葉子結點。

答案：C?

解釋:若每層僅有一個結點，則樹高h為1025；且其最小樹高為[log2 1025]+1=11，即h在11至1025之間。

?答案：A

解釋:深度為h的滿m叉樹共有 m的h次方-1 個結點，第k層有 m的k次方-1 個結點

答案：C

?解釋:因為先序遍歷結果是“根左右”，后序遍歷結果是“左右根”，當沒有左子樹時，就是“根右”和“右根”;當沒有右子樹時，就是“根左”和“左根”。則所有的結點均無左孩子或所有的結點均無右孩子均可，所以A、B不能選又所有的結點均無左孩子與所有的結點均無右孩子時，均只有一個葉子結點，故選C。

答案： B

解釋:在哈夫曼樹中沒有度為1的結點，只有度為0(葉子結點)和度為2的結點。設葉子結點的個數為n0，度為2的結點的個數為n2，由二叉樹的性質n0=n2+1，則總結點數n=n0+n2=2*n0-1，得到n0=100。

答案：A

解釋:哈夫曼樹的構造過程是每次都選取權值最小的樹作為左右子樹構造一棵新的二叉樹，所以樹中一定沒有度為1的結點、兩個權值最小的結點一定是兄弟結點、任一非葉結點的權值一定不小于下一層任一結點的權值