第5章樹與二叉樹5.1樹5.1.1樹的定義樹是一種數據結構，它是由n(n≥0)個有限結點組成一個具有層次關系的集合。空集合也是樹，稱為空樹。把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：每個結點有零個或多個子結點；沒有父結點的結點稱為根結點；每一個非根結點有且只有一個父結點；除了根結點外，每個子結點可以分為多個不相交的子樹。樹是由根結點和若干顆子樹構成的。樹是由一個集合以及在該集合上定義的一種關系構成的。集合中的元素稱為樹的結點，所定義的關系稱為父子關系。父子關系在樹的結點之間建立了一個層次結構。在這種層次結構中有一個結點具有特殊的地位，這個結點稱為該樹的根結點，或稱為樹根。5.1.2樹的基本術語下面根據下圖來介紹關于樹的基本術語和概念。孩子結點或子結點：一個結點含有的子樹的根結點稱為該結點的子結點。結點的度：一個結點含有的子結點的個數稱為該結點的度。葉結點或終端結點：度為0的結點稱為葉結點。非終端結點或分支結點：度不為0的結點。雙親結點或父結點：若一個結點含有子結點，則這個結點稱為其子結點的父結點。兄弟結點：具有相同父結點的結點互稱為兄弟結點。樹的度：一棵樹中，最大的結點的度稱為樹的度。結點的層次：從根開始定義起，根為第1層，根的子結點為第2層，以此類推。樹的高度或深度：樹中結點的最大層次。堂兄弟結點：雙親在同一層的結點互為堂兄弟。結點的祖先：從根到該結點所經分支上的所有結點。子孫：以某結點為根的子樹中任一結點都稱為該結點的子孫。有序樹：如果樹中各棵子樹的次序是有先后次序，則稱該樹為有序樹。無序樹：如果樹中各棵子樹的次序沒有先后次序，則稱該樹為無序樹。森林：由各棵互不相交的樹的集合稱為森林。路徑和路徑長度：樹中兩個結點之間的路徑是由這兩個結點之間所經過的結點序列構成的，而路徑長度是路徑上所經過邊的個數。5.1.3樹的種類無序樹：樹中任意結點的子結點之間沒有順序關系，這種樹稱為無序樹,也稱為自由樹。有序樹：樹中任意結點的子結點之間有順序關系，這種樹稱為有序樹。二叉樹：每個結點最多含有兩個子樹的樹稱為二叉樹。滿二叉樹：葉結點除外的所有結點均含有兩個子樹的樹被稱為滿二叉樹。完全二叉樹：除最后一層外，所有層都是滿結點，且最后一層缺右邊連續結點的二叉樹稱為完全二叉樹。哈夫曼樹（最優二叉樹）：帶權路徑最短的二叉樹稱為哈夫曼樹或最優二叉樹。5.1.4樹的性質樹具有如下最基本的性質：1）樹中的結點數等于所有結點的度數加上1。2）度為m的樹中第i層上至多有mi-1個結點（i≥1）。3）高度為h的m叉樹至多有(mh-1)/(m-1)個結點。4）具有n個結點的m叉樹的最小高度為?logm(n(m-1)+1)?。5.2二叉樹5.2.1二叉樹的定義及特性1．二叉樹的定義二叉樹（Binarytree）是樹形結構的一個重要類型。許多實際問題抽象出來的數據結構往往是二叉樹形式，即使是一般的樹也能簡單地轉換為二叉樹，而且二叉樹的存儲結構及其算法都較為簡單，因此二叉樹顯得特別重要。二叉樹特點是每個結點最多只能有兩棵子樹，且有左右之分，如圖所示。二叉樹是n個有限元素的集合，該集合或者為空、或者由一個稱為根（root）的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成，是有序樹。當集合為空時，稱該二叉樹為空二叉樹。在二叉樹中，一個元素也稱作一個結點。不能把二叉樹與度為2的有序樹等同起來。它們之間有如下幾個區別：①度為2的有序樹至少有3個結點，而二叉樹可以為空。②度為2的有序樹的左右次序是相對另一個孩子而言的，若某個結點只有一個孩子，則這個孩子就不需要區分左右次序；而二叉樹無論其孩子數是否為2，都需要確認其左右次序，二叉樹的結點次序是確定的。2．幾種特殊二叉樹二叉樹還有以下幾種特殊類型：1）滿二叉樹：如果一棵二叉樹只有度為0的結點和度為2的結點，并且度為0的結點在同一層上，則這棵二叉樹為滿二叉樹。一顆高度為h的滿二叉樹含有2h–1個結點，即樹中的每一層都含有最多的結點，如圖(a)所示。2）完全二叉樹：高度為h，有n個結點的二叉樹，當且僅當其每一個結點都與高度為h的滿二叉樹中編號從1到n的結點一一對應時，稱為完全二叉樹，如圖(b)所示。3）二叉排序樹：左子樹上所有結點的關鍵字均小于根結點的關鍵字；右子樹上所有結點的關鍵字均大于根結點的關鍵字；左子樹和右子樹又各是一棵二叉排序樹，如圖所示。4）平衡二叉樹：根上任一結點的左子樹和右子樹的深度之差不超過1，如圖所示。3．二叉樹性質性質1：二叉樹的第i層上至多有2i-1（i≥1）個結點。性質2：深度為h（h≥1）的二叉樹中至多含有2h-1個結點。性質3：若在任意一棵二叉樹中，有n0個葉子結點，有n2個度為2的結點，則必有n0=n2+1。證明：設度為0，1和2的結點個數分別為n0，n1和n2，結點總數n=n0+n1+n2。在二叉樹的分支數中，除根節點外，其余結點都有一個分支進入，設A為分支總數，則n=A+1。由于這些分支都是由度為1或2的結點射出的，所有A=n1+2n2。于是可得n0+n1+n2=n1+2n2+1，化簡后得n0=n2+1。性質4：具有n個結點的完全二叉樹高度為?log2(n+1)?或?log2n?+1。性質5：若對一棵有n個結點的完全二叉樹進行順序編號（0≤i＜n），那么，對于編號為i（i≥0）的結點：當i=0時，該結點為根，它無雙親結點。當i>0時，該結點的雙親結點的編號為?(i–1)/2?。若2i+1＜n，則有編號為2i+1的左結點，否則沒有左結點。若2i+2＜n，則有編號為2i+2的右結點，否則沒有右結點。5.2.2二叉樹的存儲結構二叉樹一般都采用鏈式存儲結構，用鏈表結點來存儲二叉樹中的每個結點。在二叉樹中，結點結構通常包括若干數據域和若干指針域，二叉鏈表至少包含3個域：數據域data，左指針域lchild和右指針域rchild，如圖所示。二叉樹結點類的存儲結構描述如下：二叉樹類的存儲結構描述如下：5.2.3二叉樹的遍歷遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次。由于二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。1．先序遍歷先序遍歷（PreOrder）的操作過程如下：若二叉樹為空，則什么也不做，否則，

1）訪問根結點；

2）先序遍歷左子樹；

3）先序遍歷右子樹。先序遍歷的遞歸算法如下：在圖中所表示的二叉樹中，先序遍歷所得到的結點序列為124563。2．中序遍歷中序遍歷（InOrder）的操作過程如下：若二叉樹為空，則什么也不做，否則，

1）中序遍歷左子樹；

2）訪問根結點；3）中序遍歷右子樹。中序遍歷的遞歸算法如下：在圖中所表示的二叉樹中，中序遍歷所得到的結點序列為426513。3．后序遍歷后序遍歷（PostOrder）的操作過程如下：若二叉樹為空，則什么也不做，否則，

1）后序遍歷左子樹；

2）后序遍歷右子樹；

3）訪問根結點。后序遍歷的遞歸算法如下：在圖中所表示的二叉樹中，后序遍歷所得到的結點序列為465231。4．層次遍歷二叉樹的層次遍歷，按照層次順序對二叉樹的各個結點進行訪問，如圖。用一個隊列保存被訪問的當前結點的左右孩子以實現層序遍歷。在進行層次遍歷的時候，設置一個隊列結構，遍歷從二叉樹的根結點開始，首先將根結點指針入隊列，然后從隊頭取出一個元素，每取一個元素，執行下面兩個操作：1、訪問該元素所指向的結點2、若該元素所指結點的左右孩子結點非空，則將該元素所指結點的左孩子指針和右孩子指針順序入隊。此過程不斷進行，當隊列為空時，二叉樹的層次遍歷結束。二叉樹的層次遍歷算法如下：5．由遍歷序列構造二叉樹由二叉樹的先序序列和中序序列可以唯一地確定一棵二叉樹。由二叉樹的后序序列和中序序列可以唯一地確定一棵二叉樹。只知道二叉樹的先序序列和后序序列無法唯一確定一棵二叉樹。5.2.4二叉排序樹（BST）1．二叉排序樹的定義二叉排序樹（BinarySortTree），又稱二叉查找樹（BinarySearchTree），亦稱二叉搜索樹。是數據結構中的一類。在一般情況下，查詢效率比鏈表結構要高。二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；2）若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；3）左、右子樹也分別為二叉排序樹；4）沒有鍵值相等的結點。根據二叉排序樹的定義，左子樹結點值＜根結點值＜右子樹結點值，所以對二叉排序樹進行中序遍歷會得到一個遞增的有序序列。如圖所示，該二叉排序樹的中序遍歷序列為135679。2．二叉排序樹的查找二叉排序樹的查找從根結點開始，沿某個分支逐層向下比較的過程。若二叉排序樹非空，先將給定值與根結點的關鍵字比較，若相等，則查找成功；若不相等，如果小于根結點的關鍵字，則在根結點的左子樹上查找，否則在根結點的右子樹上查找。二叉排序樹的查找算法如下：二叉樹排序樹的查找效率主要取決于樹的高度。若二叉排序樹的左、右子樹的高度之差的絕對值不超過1，則這樣的二叉排序樹成為平衡二叉樹，它的平均查找長度為O(log2n)。若二叉排序樹是一個只有右（左）孩子的單支樹，則其平均查找長度為O(n)。3．二叉排序樹的插入二叉排序樹是一種動態樹表。其特點是：樹的結構通常不是一次生成的，而是在查找過程中，當樹中不存在關鍵字等于給定值的結點時再進行插入。新插入的結點一定是一個新添加的葉子結點，并且是查找不成功時查找路徑上訪問的最后一個結點的左孩子或右孩子結點。插入結點的過程如下：首先執行查找算法，找出被插結點的父親結點；判斷被插結點是其父親結點的左、右兒子；將被插結點作為葉子結點插入。若二叉樹為空，則首先單獨生成根結點。二叉排序樹的插入操作算法如下：4．二叉排序樹的構造從一棵空數開始，依次輸入元素，把它們插入到二叉排序樹的合適位置。構造二叉排序樹的算法如下：5.2.5平衡二叉樹平衡二叉樹（BalanceBinaryTree），由前蘇聯的數學家Adelse-Velskil和Landis在1962年提出的高度平衡的二叉樹，根據科學家的英文名也稱為AVL樹。它具有如下幾個性質：1）可以是空樹。2）假如不是空樹，任何一個結點的左子樹與右子樹都是平衡二叉樹，并且高度之差的絕對值不超過1。定義結點左子樹和右子樹的高度差為該結點的平衡因子，則平衡二叉樹結點的平衡因子值只可能為-1、0或1，如圖所示。5.2.6哈夫曼樹1．哈夫曼樹的定義給定N個權值作為N個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(HuffmanTree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。哈夫曼樹是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的路徑長度是從樹根到每一結點的路徑長度之和，記為WPL（WeightedPathLengthofTree）=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N個權值Wi（i=1,2,...n）構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li（i=1,2,...n）。例如右圖的哈夫曼樹中，該樹的WPL=8*1+5*2+2*3+3*3=33。同時該樹的WPL在所有帶這4個結點的二叉樹中里為最小值。2.哈夫曼樹的構造假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。n個權值分別設為w1、w2、…、wn，則哈夫曼樹的構造規則為：1）將w1、w2、…、wn看成是有n棵樹的森林(每棵樹僅有一個結點)；2）在森林中選出兩個根結點的權值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；3）從森林中刪除選取的兩棵樹，并將新樹加入森林；4）重復（2）、（3）步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹，如圖所示。構造哈夫曼樹的算法如下：3．哈夫曼編碼在數據通信中，需要將傳送的文字轉換成二進制的字符串，用0，1碼的不同排列來表示字符。例如，需傳送的報文為“AFTERDATAEARAREARTAREA”，這里用到的字符集為“A，E，R，T，F，D”，各字母出現的次數為{8，4，5，3，1，1}。現要求為這些字母設計編碼。要區別6個字母，最簡單的二進制編碼方式是等長編碼，固定采用3位二進制，可分別用000、001、010、011、100、101對“A，E，R，T，F，D”進行編碼發送，當對方接收報文時再按照三位一分進行譯碼。顯然編碼的長度取決報文中不同字符的個數。若報文中可能出現26個不同字符，則固定編碼長度為5。然而，傳送報文時總是希望總長度盡可能短。在實際應用中，各個字符的出現頻度或使用次數是不相同的，如A、B、C的使用頻率遠遠高于X、Y、Z，自然會想到設計編碼時，讓使用頻率高的用短碼，使用頻率低的用長碼，以優化整個報文編碼。為使不等長編碼為前綴編碼（即要求一個字符的編碼不能是另一個字符編碼的前綴），可用字符集中的每個字符作為葉子結點生成一棵編碼二叉樹，為了獲得傳送報文的最短長度，可將每個字符的出現頻率作為字符結點的權值賦予該結點上，顯然字使用頻率越小權值越小，權值越小葉子就越靠下，于是頻率小編碼長，頻率高編碼短，這樣就保證了此樹的最小帶權路徑長度效果上就是傳送報文的最短長度。因此，求傳送報文的最短長度問題轉化為求由字符集中的所有字符作為葉子結點，由字符出現頻率作為其權值所產生的哈夫曼樹的問題。利用哈夫曼樹來設計二進制的前綴編碼，既滿足前綴編碼的條件，又保證報文編碼總長最短，如圖。5.3樹與森林5.3.1樹的存儲結構樹的存儲方式有多種，既能采用順序存儲結構，也能采用鏈式存儲結構，但無論采用哪種存儲方式，都必須要滿足能夠唯一地反映樹中各結點之間的邏輯關系，下面介紹3種常用的存儲結構。1．雙親表示法雙親表示法采用順序存儲結構來實現，采用一組連續空間才存儲每個結點，同時在每個結點增設一個變量，該變量值為其雙親結點在列表中的索引位置，如圖所示。該存儲結構利用了每個結點（除根節點外）只有唯一一個雙親的性質，可以很快得到每個結點的雙親結點，但求結點的孩子時則需要遍歷整個順序表。2．孩子表示法孩子表示法是將每個結點的孩子結點都用單鏈表鏈接起來形成一個線性結構，此時n個結點就有n個孩子鏈表（葉子結點的孩子鏈表為空表）。使用孩子表示法來表示圖(a)中的樹，如圖所示。孩子表示法尋找子女的操作非常直接，但尋找雙親的操作需要遍歷n個結點中的孩子鏈表指針域所指向的n個孩子鏈表。3．孩子兄弟表示法 孩子兄弟表示法又稱二叉樹表示法，即以二叉鏈表作為樹的存儲結構。孩子兄弟表示法中，每個結點包括三個部分內容：結點值、指向結點第一個孩子結點的指針和指向結點下一個兄弟結點的指針。用孩子兄弟表示法來表示圖