數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)課件章節(jié)5

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

1）訪問根結(jié)點；

2）先序遍歷左子樹；

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

1）中序遍歷左子樹；

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

1）后序遍歷左子樹；

2）后序遍歷右子樹；

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