第6章 樹型結構.ppt

1、第6章 樹,數(shù)據(jù)結構（C描述）,6.9 二叉樹的應用哈夫曼樹,6.8 樹和森林,6.7 線索二叉樹,6.4 遍歷二叉樹,6.3 二叉樹的定義及存儲結構,6.1 樹的基本概念,目錄,6.2 樹的存儲結構,6.5 二叉排序樹,6.6 平衡二叉樹,在許多領域許多問題不能或難用線性結構表示（哈夫曼編碼、判定問題），故研究非線性的數(shù)據(jù)結構。樹是一種應用十分廣泛的非線性數(shù)據(jù)結構。,6.1 樹的基本概念,6.1.1 樹的定義,樹的定義,樹是由n（n0）個結點組成的有限集合。若n=0，稱為空樹；若n0，則稱為非空樹，在任一棵非空樹中： （1）有一個特定的稱為根（root）的結點。它只有直接后繼，但沒有直接前驅

2、； （2）除根結點以外的其它結點可以劃分為m（m0）個互不相交的有限集合T0，T1，Tm-1，且每個集合Ti（i=0,1,m-1）本身又是一棵樹，稱為根的子樹。由此可知，樹的定義是一個遞歸的定義，即樹的定義中又用到了樹的概念。,從定義中看出樹結構具有以下特點：,（1）有且僅有一個結點沒有直接前驅，即根結點。 （2）除根結點之外，其余所有結點有且僅有一個直接前趨結點。 （3）包括根結點在內(nèi)，每個結點可以有多個直接后繼結點。 從此可見，樹型結構的特點是，數(shù)據(jù)元素之間存在著一對多的關系。 樹的結構參見圖6-1。,在圖6-1(c)中，樹的根結點為A，該樹還可以分為三個互不相交子集T0，T1，T2，具體

3、請參見圖6-2，其中 T0=B，E，F(xiàn)，J，K，L，T1=C，G，T2=D，H，I，M,而T0，T1，T2又可以分解成若干棵不相交子樹。如：T0可以分解成T00，T01兩個不相交子集，T00=E，J，K，L，T01=F，而T00又可以分為三個不相交子集T000，T001，T002，其中，T000=J，T001=K，T002=L。,6.1.2 基本術語,1.樹的結點 指樹中的一個數(shù)據(jù)元素，一般用一個字母表示。,2.結點的度 一個結點包含子樹的數(shù)目，稱為該結點的度。,3.樹葉（葉子） 度為0的結點，稱為葉子結點或樹葉，也叫終端結點。,4.分支結點（非終端結點） 除葉子結點外的所有結點，為分支結點。

4、通常又將除根結點之外的分支結點稱為內(nèi)部結點。,6.雙親結點 若結點X有子女Y，則X為Y的雙親結點。,7.祖先結點,8.子孫結點 某一結點的子女的子女為該結點子孫。,5.孩子結點 若結點X有子樹，則子樹的根結點為X的孩子結點，也稱為孩子。如圖6-1（c）中A的孩子為B，C，D。,10結點的層次 從根結點開始定義，根為第一層，根的孩子為第二層，依次類推。,11. 樹的高度（深度） 樹中結點所處的最大層數(shù)稱為樹的高度，如空樹的高度為0，只有一個根結點的樹高度為1。,12.樹的度 樹中結點度的最大值稱為樹的度。,9.兄弟結點 具有同一個雙親的結點，稱為兄弟結點。,13. 有序樹 若一棵樹中所有子樹從左

5、到右的排序是有順序的，不能顛倒次序。稱該樹為有序樹。,14. 無序樹 若一棵樹中所有子樹的次序無關緊要，則稱為無序樹。,15森林（樹林） 若干棵互不相交的樹組成的集合為森林。一棵樹可以看成是一個特殊的森林。 樹與森林的關系,6.1.3 樹的表示,1樹形結構表示法 （掌握） 具體參 見圖6-1 。,2. 凹入法表示法 具體參見圖6-3,3. 嵌套集合表示法 具體參 見圖6-4 。,4.廣義表表示法 對圖7-1（c）的樹結構，廣義表表示法可表示為： A（B（E（J，K，L），F(xiàn)），C（G），D（H（M），I）,6.2 樹的存儲結構 僅考慮鏈式存儲結構，有兩種：多重鏈表表示法、二重鏈表表示法 6.2

6、.1 多重鏈表表示法 每個結點由一個數(shù)據(jù)域和若干個指針域組成，其中，每個指針域指向該結點的一個孩子。一棵樹中不同結點的度數(shù)可能不同，每個結點設置的指針域的數(shù)目可能就有所不同。通常有下面的兩種方案： 1、定長結點的多重鏈表表示法,取樹的度數(shù)作為每個結點的指針域的個數(shù)。 缺點：,由于樹中多數(shù)結點的度可能小于樹的度，因而這種方法將會導致許多結點的部分指針域為空，造成空間的浪費。,2、不定長結點的多重鏈表示法 樹中每個結點都取自己的度數(shù)作為指針域的個數(shù)，顯然，對于葉結點就不必設指針域。另外，每個結點除了數(shù)據(jù)域、指針域外，還應設一個度數(shù)域用來指出該結點的度數(shù)，即指出該結點中指針域的個數(shù)。 6.2.2 二

7、重鏈表表示法 這種方法是對樹中的每個結點設三個域：數(shù)據(jù)域和2個指針域，第一個指針域給出該結點的第一個孩子（即最左邊子樹的根結點，長子）的地址，第二個指針域給出該結點的右邊第一個兄弟結點（次弟）的地址。 樹的三重鏈表表示，增加了一個指針域即給出該結點的雙親結點的地址。,6.3 二叉樹 在樹型結構中，有一類簡單而又重要的樹，它的每個結點最多只有2棵子樹，這種樹被稱為二叉樹。,6.3.1 二叉樹的定義,1二叉樹的定義 和樹結構定義類似，二叉樹的定義也可以遞歸形式給出： 二叉樹是n（n0）個結點的有限集，它或者是空集（n=0），或者由一個根結點及兩棵不相交的左子樹和右子樹組成。,二叉樹的特點： 每個結

8、點最多有兩個孩子，或者說，在二叉樹中，不存在度大于2的結點 二叉樹是有序樹（樹為無序樹），其子樹的順序不能顛倒。因此，二叉樹有五種不同的形態(tài)，參見下圖。,6.3.2 二叉樹的性質,性質1 若二叉樹的層數(shù)從1開始，則二叉樹的第k層結點數(shù)，最多為個 （k0）。 可以用數(shù)學歸納法證明之。,性質2 深度（高度）為k的二叉樹最大結點數(shù)為 （k0）,證明： 深度為k的二叉樹，若要求結點數(shù)最多，則必須每一層的結點數(shù)都為最多，由性質1可知，最大結點數(shù)應為每一層最大結點數(shù)之和。即為： 20+21+2k-1=2k-1。,2k-1,2k-1,性質3 對任意一棵二叉樹，如果葉子結點個數(shù)為n0，度為2的結點個數(shù)為n2，

9、則有n0=n2+1。,證明：設二叉樹中度為1的結點個數(shù)為n1，根據(jù)二叉樹的定義（二叉樹中所有結點的度均小于或等于2)可知，該二叉樹的結點總數(shù) n=n0+n1+n2 (1)。 再看二叉樹中的分支數(shù)。除了根結點外，其余結點都有一個分支進入。設B為分支總數(shù)，則 n=B+1 由于這些分支是由度為1或2的結點射出的，所以又有B=n1+2*n2 于是得：n=n1+2n2+1 (2) 由（1）和（2）得：n0=n2+1,下面討論兩種特殊的二叉樹：滿二叉樹和完全二叉樹。,滿二叉樹 深度為k具有2k-1個結點的二叉樹，稱為滿二叉樹?；蛘哒f：如果一棵二叉樹中任何結點，或者是葉結點，或者是有兩棵非空子樹，且葉子結點

10、都集中在二叉樹的最下一層，這樣的二叉樹稱為滿二叉樹。 從定義可知：必須是二叉樹的每一層上的結點數(shù)都達到最大，否則就不是滿二叉樹。,例：深（高）度為4的滿二叉樹如圖（15個結點）,可以對滿二叉樹的結點進行編號，約定編號從根結點起，自上而下，自左而右，由此引出完全二叉樹的定義。,完全二叉樹 如果一棵具有n個結點的深度為k的二叉樹，它的每一個結點都與深度為k的滿二叉樹中編號為1 n的結點一一對應，則稱這棵二叉樹為完全二叉樹。（例：k=3,n=4,5,6）,從滿二叉樹及完全二叉樹定義可以得出如下結論： 滿二叉樹一定是一棵完全二叉樹 反之完全二叉樹不一定是一棵滿二叉樹。 滿二叉樹的葉子結點全部在最底層，

11、而完全二叉樹的葉子結點可以分布在最下面兩層。深度為4的滿二叉樹和完全二叉樹（8個結點）如圖6-6所示。,性質4 具有n個結點的完全二叉樹高度為log2(n)+1 或 log2（n+1） 。 （注意x表示取不大于x（即）的最大整數(shù)，也叫做對x下取整，x表示取不小于x（即）的最小整數(shù)，也叫做對x上取整。),1、二叉樹中度為0的結點數(shù)為50，度為1的結點數(shù)為30，總結點數(shù)為_。,湖南大學考研題,性質3：n0=n2+1,2、樹最合適用來表示_。 A有序數(shù)據(jù)元素 B 無序數(shù)據(jù)元素 C元素之間無聯(lián)系的數(shù)據(jù)D元素之間分支層次關系的數(shù)據(jù),3、對于有n 個結點的二叉樹, 其高度為（ ）【武漢交通科技大學 一、5

12、 (4分)】 Anlog2n Blog2n Clog2n+1 D不確定 4、深度為h的滿m叉樹的第k層有（ ）個結點。 (1 k h)【北京航空航天大學 一、4（2分）】 Amk-1 Bmk-1 Cmh-1 Dmh-1 5、在一棵高度為k的滿二叉樹中，結點總數(shù)為（ ）【北京工商大學 一、3 (3分)】 A2k-1 B2k C2k-1 Dlog2k+1 6、高度為 K的二叉樹最大的結點數(shù)為（ ）。 【山東大學 二、3 (1分)】 A2k B2k-1 C2k -1 D2k-1-1,7、若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點個數(shù)是（ ） A9 B11 C15 D不確定

13、【北京工商大學一.7(3分)】,性質3 對任意一棵二叉樹，如果葉子結點個數(shù)為n0，度為2的結點個數(shù)為n2，則有n0=n2+1。,6.3.3 二叉樹的存貯結構,1順序存貯結構,即用一維數(shù)組TM來存儲二叉樹的數(shù)據(jù)元素，按照二叉樹的結點層次編號依次來存放。 如：見圖 這種結構適合于存儲完全二叉樹和滿二叉樹，若是一般二叉樹應如何處理？,必須按完全二叉樹的形式來存貯樹中的結點，這就要虛設很多空結點才能使它成為一棵完全二叉樹。如圖可見這將造成空間的浪費。,例：k=3的一般二叉樹,對于一棵二叉樹,若采用順序存貯時,當它為完全二叉樹（或滿二叉樹）時,比較方便,若為非完全二叉樹,將會浪費大量存貯存貯單元。 最壞

14、情況的非完全二叉樹是全部只有右分支,設高度為K,則需占用個 存貯單元,而實際只有k個元素,實際只需k個存儲單元。因此，對于非完全二叉樹，宜采用下面的鏈式存儲結構。,2K-1,2二叉鏈表存貯結構,（1）二叉鏈表表示 將一個結點分成三部分,一部分存放結點本身信息,另外兩部分為指針,分別存放左、右孩子的地址。,二叉鏈表中一個結點可描述為:,對于圖6-7所示二叉樹,用二叉鏈表形式描述見圖6-8。,（2）二叉鏈表的類型說明 二叉鏈表的數(shù)據(jù)類型描述如下: typedef struct btnode int data ; /結點數(shù)據(jù)類型 struct btnode *lchild, *rchild; /定義

15、左、右孩子為指 針型 bitree; 有時，為了便于找到結點中的雙親，還可在結點結構中增加一個指向雙親的指針域，這種存貯結構稱為三叉鏈表。,6.4 遍歷二叉樹 （二叉樹的運算）,所謂遍歷二叉樹，就是遵從某種次序，訪問二叉樹中的所有結點，使得每個結點僅被訪問一次。 這里提到的“訪問”是指對結點施行某種操作，操作可以是輸出結點信息，修改結點的數(shù)據(jù)值等，但要求這種訪問不破壞它原來的數(shù)據(jù)結構。在本書中，我們規(guī)定訪問是輸出結點信息data，且以二叉鏈表作為二叉樹的存貯結構。 遍歷對線性結構而言非常簡單，只需順序掃描每個數(shù)據(jù)元素即可。但對非線性結構，要找到一種規(guī)律，以便二叉樹上各結點能排列成一個線性序列。

16、,二叉樹由三部分組成：根結點（D），左子樹（L），右子樹（R）。要遍歷這三個基本部分，可有六種可能的順序：DLR（先序或前序） DRL（逆先序遍歷） LDR(中序） RDL（逆中序） LRD （后序） RLD（逆后序） 規(guī)定：二叉樹中必須先左后右(左右順序不能顛倒)，則只有DLR、LDR、LRD三種遍歷規(guī)則。 DLR稱為前根遍歷(或前序遍歷、先序遍歷、先根遍歷)，LDR稱為中根遍歷(或中序遍歷)，LRD稱為后根遍歷(或后序遍歷)。,6.4.1先序遍歷 所謂先序遍歷，就是根結點最先遍歷，其次左子樹，最后右子樹。,遞歸遍歷,先序遍歷二叉樹的遞歸遍歷算法描述為： 若二叉樹為空，則算法結束;否則 （1

17、）輸出（訪問）根結點； （2）再按先序遍歷方式遍歷根結點的左子樹; （3）最后按先序遍歷方式遍歷根結點的右子樹;,遞歸算法如下: void preorder(bitree *root) if(root!=NULL) printf(“%d”,root-data); preorder(root-lchild); preorder (root-rchild); ,6.4.2中序遍歷 所謂中序遍歷，就是根在中間，先左子樹，然后根結點，最后右子樹。,遞歸遍歷,中序遍歷二叉樹的遞歸遍歷算法描述為： 若二叉樹為空，則算法結束；否則 中序遍歷左子樹; 輸出根結點; 中序遍歷右子樹。,算法如下: void in

18、order(biteee *root) if (root!=NULL) inorder(root-lchild); printf(“%d”,root-data); inorder(root-rchild); ,6.4.3 后序遍歷 所謂后序遍歷，就是根在最后，即先左子樹，然后右子樹，最后根結點。,遞歸遍歷,后序遍歷二叉樹的遞歸遍歷算法描述為： 若二叉樹為空，則算法結束;否則 （1）后序遍歷左子樹: （2）后序遍歷右子樹; （3）訪問根結點。,算法如下: void postorder( bitree *root) if (root!=NULL) postorder (root-lchild);

19、postorder (root-rchild); printf(“%d”,root-data); ,例如，可以利用上面介紹的遍歷算法，寫出如下圖所示二叉樹的三種遍歷序列為：,先序遍歷序列：ABDGCEFH 中序遍歷序列： BGDAECFH 后序遍歷序列： GDBEHFCA 例題,另外，在編譯原理中，有用二叉樹來表示一個算術表達式的情形。在一棵二叉樹中，若用操作數(shù)代表樹葉，運算符代表非葉子結點，則這樣的樹可以代表一個算術表達式。 若按前序、中序、后序對該二叉樹進行遍歷，則得到的遍歷序列分別稱為前綴表達式(或稱波蘭式)、中綴表達式、后綴表達式(逆波蘭式)。具體參見圖6-12。,右圖所對應的前綴表達

20、式： -*abc。 右圖所對應的中綴表達式：a*b-c。 右圖所對應的后綴表達式：ab*c-。,6.4.4 遍歷二叉樹的非遞歸算法,遞歸算法：簡明，但效率較低，且有的程序設計語言不允許函數(shù)遞歸調用。 故要討論遍歷二叉樹的非遞歸算法。 均用棧保存遍歷過程中經(jīng)歷的結點的左右孩子（指向孩子的指針），用一維數(shù)組SM作為棧存放元素，top為棧頂指針。,1、先序遍歷二叉樹的非遞歸算法 利用一個一維數(shù)組作為棧，來存儲二叉鏈表中結點，,算法思想為： 從二叉樹根結點開始，先輸出結點信息，沿左子樹一直走到末端(左孩子為空)為止，在走的過程中，遇到結點有右孩子的，則把指向結點右孩子的指針進棧，當左子樹為空時，從棧頂

21、退出一個指針信息（即退出某結點的右孩子）。如此重復，直到棧為空。,void preorder(bitree *root) bitree *p,*s100; int top=0; /top為棧頂指針 p=root; do while(p!=NULL) printf(“%d”,p-data); if(p-rchild!=NULL) stop+=p-rchild; p=p-lchild; if(top=0) p=s-top; while(top=0);,2中序遍歷二叉樹的非遞歸算法,同樣利用一個一維數(shù)組作棧，來存貯二叉鏈表中結點， 算法思想為： 從二叉樹根結點開始，沿左子樹一直走到末端(左孩子為空)

22、為止，在走的過程中，把依次遇到的結點進棧,待左子樹為空時,從棧中退出結點并訪問,然后再轉向它的右子樹。如此重復，直到?？栈蛑羔槥榭罩埂?算法如下: void inorder ( bitree *root) bitree *p,*s100; /s為一個棧，top為棧頂指針 int top=0; p=root; do while(p!=NULL) stop +=p;p=p-lchild; if(top=0) p=s-top; printf(“%d”,p-data); p=p-rchild; while(top=0);,6.4.5 遍歷算法應用舉例,例1 由二叉樹的前序序列和中序序列建立該二叉樹,分

23、析： 若二叉樹的任意兩個結點的值都不相同，則二叉樹的前序序列和中序序列能唯一確定一棵二叉樹。 另外，由前序序列和中序序列的定義可知，前序序列中第一個結點必為根結點，而在中序序列中，根結點剛好是左、右子樹的分界點，因此，可按如下方法建立二叉樹：,1.用前序序列的第一個結點作為根結點;,2.在中序序列中查找根結點的位置，并以此為界將中序序列劃分為左、右兩個序列(左、右子樹);,3.根據(jù)左、右子樹的中序序列中的結點個數(shù)，將前序序列去掉根結點后的序列劃分為左、右兩個序列，它們分別是左、右子樹的前序序列;,4.對左、右子樹的前序序列和中序序列遞歸地實施同樣方法，直到所得左、右子樹為空。,假設前序序列為A

24、BDGHCEFI，,中序序列為GDHBAECIF，,則得到的二叉樹如下頁所示,1。A為根結點,A BDGH CEFI,GDHB A ECIF,2. B為左子樹的根結點,B DGH,GDH B,3. D為左子樹的左子樹的根結點,4。C為右子樹的根結點,5。F為右子樹的右子樹的根結點,C E FI,E C IF,思考：能否根據(jù)中序、后序求前序？能否根據(jù)前序、后序求中序？,例2 按層次遍歷一棵二叉樹,對于一棵二叉樹，若規(guī)定遍歷順序為從上到下(上層遍歷完才進入下層)，從左到右(同一層從左到右進行，這樣的遍歷稱為按層次遍歷：例1的樹的層次遍歷序列為：ABCDEFGHI。下面用一個一維數(shù)組來模擬隊列，實現(xiàn)

25、二叉樹的層次遍歷。,Void lorder (bitree * t) bitree *qmaxsize,*p; / maxsize為最大容量 int f,r; / f,r類似于頭尾指針 q0=t; f=r=0; while (fdata); if(p -lchild!=NULL) r+; qr=p-1child; /入隊 if (p-rchild!=NULL) r+; qr=p-rchild; /入隊 ,作業(yè)： 1、一棵度為2的樹與一棵二叉樹有何區(qū)別？ 2、用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHIJKL，寫出該二叉樹的前序、中序、后序遍歷序列。 3、假設一棵二叉樹的前序序列為EBAD

26、CFHGIKJ和中序序列為ABCDEFGHIJK，請寫出二叉樹的后序遍歷序列。 4、假設一棵二叉樹的中序序列為DCBGEAHFIJK和后序序列為DCEGBFHKJIA。請寫出二叉樹前序遍歷序列。,6.5 二叉排序樹(二叉搜索樹，二叉查找樹） 1什么是二叉排序樹,二叉排序樹（Binary Sorting Tree），它或者是一棵空樹，或者是一棵具有如下特征的非空二叉樹： (1)若它的左子樹非空，則左子樹上所有結點的關鍵字均小于根結點的關鍵字； (2)若它的右子樹非空，則右子樹上所有結點的關鍵字均大于等于根結點的關鍵字； (3)左、右子樹本身又都是一棵二叉排序樹。 下圖各例是否為二叉排序樹？（為了

27、討論問題的方便，假設樹中每個結點的值是一個十進制整數(shù)）,2、下面給出構造二叉排序樹的算法： 將一個給定的數(shù)據(jù)元素構造為相應的二叉排序樹，通常采用逐步插入結點的方法來構造二叉排序樹。 設k=k1,k2,.,kn為數(shù)據(jù)元素序列，從k1開始依次取序列中的元素，每取出一個元素ki,按下列原則建立二叉排序樹的一個新結點： （1）若二叉排序樹為空，則新的數(shù)據(jù)元素就是二叉排序樹的根結點。 （2）若二叉排序樹非空，則將新的數(shù)據(jù)元素與該二叉樹的根結點的值進行比較，若小于根結點的值，則將新的數(shù)據(jù)元素插入到根結點的左子樹中；否則，插入到右子樹中。 這個過程是一個遞歸的過程，因為數(shù)據(jù)元素插入到左子樹或右子樹也同樣是按

28、這個原則遞歸進行的。（例）,例如，結定關鍵字序列79，62，68，90，88，89，17，5，100，120，生成二叉排序樹過程如下圖所示。,（注：排列順序不一樣，得到的二叉排序樹也不一樣）,二叉排序樹與關鍵字排列順序有關嗎?,a、遞歸算法 bitree *Inserttree(bitree *t, int x) if(t=NULL) t=( bitree *)malloc(sizeof(bitree); t-data=x; t-lchild=NULL; t-rchild=NULL; else,若二叉排序樹為空，則新的數(shù)據(jù)元素就是二叉排序樹的根結點。,if(xdata) t-lchild=In

29、serttree(t-lchild,x); else t-rchild=Inserttree(t-rchild,x); return(t); b、生成二叉排序樹的非遞歸算法： bitree *creat(bitree *t) bitree *s,*p,*q; int x;,若二叉排序樹非空，則將新的數(shù)據(jù)元素與該二叉樹的根結點的值進行比較，若小于根結點的值，則將新的數(shù)據(jù)元素插入到根結點的左子樹中；否則，插入到右子樹中。,scanf(“%d”,while(p) q=p; if(s-datadata) p=p-lchild; else p=p-rchild; if(s-datadata) q-lch

30、ild=s; else q-rchild=s; /插入結點算法,scanf(“%d”, ,3、二叉排序 樹上的查找(檢索算法）,（1）二叉排序 樹的查找思想 若二叉排樹為空，則查找 失敗，否則，先拿根結點值與待查值進行比較，若相等，則查找成功，若根結點值大于待查值，則進入左子樹重復此步驟，否則，進入右子樹重復此步驟，若在查找過程中遇到二叉排序樹的葉子結點時，還沒有找到待找結點，則查找不成功。 （2）二叉排序樹查找的算法實現(xiàn),a、遞歸算法：,bitree *bstsrch(bitree *t,int k) if(t=NULL)|(t-data=k) return(t); else if(t-da

31、ta rchild,k); else return(bstsrch(t-lchild,k); ,b、非遞歸算法,bitree *search(bitree *t,int k) while(t!=NULL) if(t-data=k) return(t); else if(t-datarchild; else t=t-lchild; return(NULL); ,4、刪除運算 在二叉排序樹上刪除一個結點需注意：要保證刪除后所得的二叉樹仍是一棵二叉檢索樹。考慮下面三種情況： 1）若要刪除的是葉子結點 最簡單的一種，只要將其雙親結點與它之間的鏈接的指針置空即可。如圖 2）若要刪除的結點只有左子樹或只有

32、右子樹，即單支結點。 a、若被刪除的結點沒有左子樹，則可用其右子樹的根結點取代被刪除結點的位置。 b、若被刪除結點沒有右子樹，則可用其左子樹的根結點取代被刪除結點的位置。,3）若刪除的結點具有左、右子樹。,方法：首先將該結點的中序前趨結點的值賦給該結點的值，然后再刪除它的中序前趨結點。由于此時，它的中序前趨結點的右指針為空，只要將中序前趨結點的左指針鏈接到中序前趨結點所在的鏈接位置即可。,5二叉排序樹查找的性能分析,在二叉排序樹查找中，成功的查找次數(shù)不會超過二叉樹的深度，而具有n個結點的二叉排序樹的深度，最好為 log2（n+1） ，最壞為n。因此，二叉排序樹查找的最好時間復雜度為O(log2

33、n)，最壞的時間復雜度為O(n)，一般情形下，其時間復雜度大致可看成O(log2n)，比順序查找效率要好，但比二分查找要差。 即使關鍵字相同的一組數(shù)據(jù)，若先后插入的次序不同，所生成的二叉排序樹也不同，則查找的時間性能也不同，當要求查找的性能較高時，要對構成二叉排序樹的過程進行“平衡化”處理，形成二叉平衡樹。,6.6 平衡二叉樹 1平衡二叉樹的概念,平衡二叉樹(balanced binary tree)是由阿德爾森一維爾斯和蘭迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又稱為AVL樹。,平衡二叉樹: 若一棵二叉樹中每個結點的左、右子樹的深度之差的絕對值

34、不超過1，則稱這樣的二叉樹為平衡二叉樹。 平衡因子：將該結點的左子樹深度減去右子樹深度的值，稱為該結點的平衡因子(balance factor)。 也就是說，一棵二叉排序樹中，所有結點的平衡因子只能為0、1、-1時，則該二叉排序樹就是一棵平衡二叉樹，,2. 非平衡二叉樹的平衡處理,若一棵二叉排序樹是平衡二叉樹，扦入某個結點后，可能會變成非平衡二叉樹，這時，就可以對該二叉樹進行平衡處理，使其變成一棵平衡二叉樹。 處理的原則應該是處理與扦入點最近的、而平衡因子又比1大或比-1小的結點。下面將分四種情況討論平衡處理。,（1）LL型 的處理(左左型) 如圖7-10所示，在C的左孩子B上扦入一個左孩子結

35、點A，使C的平衡因子由1變成了2，成為不平衡的二叉樹序樹。這時的平衡處理為：將C順時針旋轉，成為B的右子樹，而原來B的右子樹則變成C的左子樹，待扦入結點A作為B的左子樹。(注：圖中結點旁邊的數(shù)字表示該 結點的平衡因子),（2）LR型的處理(左右型) 如圖7-11所示，在C的左孩子A上扦入一個右孩子B，使的C的平衡因子由1變成了2，成為不平衡的二叉排序樹。這是的平衡處理為：將B變到A與C 之間，使之成為LL型，然后按第(1)種情形LL型處理。,（3）RR型的處理(右右型) 如圖7-12所示，在A的右孩子B上扦入一個右孩子C，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹。這時的平衡處理為：

36、將A逆時針旋轉，成為B的左子樹，而原來B的左子樹則變成A的右子樹，待扦入結點C成為B的右子樹。,（4）RL型的處理(右左型) 如圖7-13所示，在A的右孩子C上扦入一個左孩子B，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹。這時的平衡處理為：將B變到A與C之間，使之成為RR型，然后按第(3) 種情形RR型處理。,例1，給定一個關鍵字序列4,5,7,2,1,3,6，試生成一棵平衡二叉樹。 分析：平衡二叉樹實際上也是一棵二叉排序樹，故可以按建立二叉排序樹的思想建立，在建立的過程中，若遇到不平衡，則進行相應平衡處理，最后就可以建成一棵平衡二叉樹。具體生成過程見圖7-14。,例2：給定一個關鍵

37、字序列13，24，37，90，53，試生成一棵平衡二叉樹。 作業(yè)：將一組關鍵字（47,16,21,36,29,59,19,54)生成一二叉平衡樹。,3平衡二叉樹的查找及性能分析 平衡二叉樹本身就是一棵二叉排序樹，故它的查找與二叉排序樹完全相同。但它的查找 性能優(yōu)于二叉排序樹，不像二叉排序樹一樣，會出現(xiàn)最壞的時間復雜度O(n)，它的時間復雜度與二叉排序樹的最好時間復雜相同，都為O(log2n)。 一般二叉平衡樹主要應用于查找。,例3，對例1給定的關鍵字序列4,5,7,2,1,3,6，試用二叉排序樹和平衡二叉樹兩種方法查找，給出查找6的次數(shù)及成功的平均查找長度。 分析：由于關鍵字序列的順序己經(jīng)確定

38、，故得到的二叉排序樹和平衡二叉樹都是唯一的。得到的平衡二叉樹見圖7-14，得到的二叉排序樹見圖7-15。,從圖7-15的二叉排序樹可知，查找6需4次，假設7個記錄的查找概率相等，為1/7，則該二叉排序樹的平均查找長度為 ASL=(1+2+2+3+3+3+4)/7=18/72.57。 從圖7-16的平衡二叉樹可知，查找6需2次，平均查找長度 ASL=(1+2+2+3+3+3+3)/7=17/72.43。,從結果可知，平衡二叉樹的查找性能優(yōu)于二叉排序樹。,#includeh1.h #include #include bitree *creat(bitree *t) bitree *s,*p,*q;

39、 int x; printf(input the nodes value:0-ENDn); scanf(%d, ,if(s-datadata) q-lchild=s; else q-rchild=s; printf(input the nodes value:n); scanf(%d, ,湖南大學01-03,1、樹最合適用來表示_。 A有序數(shù)據(jù)元素 B 無序數(shù)據(jù)元素 C元素之間無聯(lián)系的數(shù)據(jù)D元素之間分支層次關系的數(shù)據(jù) 2、中序遍歷二叉排序樹就可以得到排好序的結點序列。（ ）（判斷正誤）,一維數(shù)組存放一棵完全二叉樹: ABCDEFGHIJK，請給出該二叉樹的后序遍歷序列。 算法設計題略,1、在二

40、叉排序樹上成功地找到一個結點，在平均情況下的時間復雜性是 , 在最壞情況下的時間復雜性是 。設結點個數(shù)為 n，以大O形式給出時間復雜性。 2、已知一棵二叉樹是以二叉鏈表的形式存儲的，其結點結構說明如下：（本題10 分。） struct node int data; / 結點的數(shù)據(jù)場。 struct node *left; / 給出結點的左兒子的地址。 struct node * right; / 給出結點的右兒子的地址。 ； 請在1、2二題的 處進行填空，完成題目要求的功能。注意，每空只能填一個語句，多填為 0 分。 (1) 求出以T 為根的二叉樹或子樹的結點個數(shù)。 int size (str

41、uct node * T ) if ( ) return 0; else ; (2) 求出以T為根的二叉樹或子樹的高度。注：高度定義為樹的總的層次數(shù)。 int height(struct node * T ) if ( T = NULL ) ; else ; ,上海交通大學2004年數(shù)據(jù)結構考研試題,提示： 用遞歸形式,O(log2n) O(n) T = NULL return ( 1 +size(T-left) + size(T-right) ) return 0 return 1 +( ( height(T-left) height(T-right)? height(T-left): he

42、ight(T-right) ),6.7線索二叉樹 6.7.1 線索的概念,遍歷二叉樹：就是將樹中所有結點排成一個線性序列。好處：在這樣的線性序列中，很容易求得某個結點在某種遍歷下的直接前驅和后繼。,帶來麻煩，希望不進行遍歷就能快速找到某個結點在某種遍歷下的直接前驅和后繼，這樣，就應該把每個結點的直接前驅和直接后繼記錄下來。 為了做到這一點，可以在原來的二叉鏈表結點中，再增加兩個指針域，一個指向前驅，一個指向后繼，但這樣做將會浪費大量存貯單元，存貯空間的利用率相當?shù)?一個結點中有4個指針，1個指左孩子，1個指右孩子，1個指前驅，1個指后繼)，而原來的左、右孩子域有許多空指針又沒有利用起來。,為了

43、不浪費存貯空間，我們利用原有的孩子指針為空時來存放直接前驅和后繼，這樣的指針稱為“線索”（thread)，加線索的過程稱為線索化，加了線索的二叉樹，稱為線索二叉樹，對應的二叉鏈表稱為線索二叉鏈表（簡稱為線索鏈表）。 在線索二叉樹中，由于有了線索，無需遍歷二叉樹就可以得到任一結點在某種遍歷下的直接前驅和后繼。 但是，我們怎樣來區(qū)分孩子指針域中存放的是左、右孩子信息還是直接前驅或直接后繼信息呢?為此，在二叉鏈表結點中，還必須增加兩個標志域ltag、rtag。,ltag和rtag定義如下：,0 lchild域指向結點的左孩子 ltag= 1 lchild域指向結點在某種遍歷下的直 接前驅,0 rch

44、ild域指向結點的右孩子 rtag= 1 rchild域指向結點在某種遍歷下的直接后繼,這樣，二叉鏈表中每個結點還是有5個域，但其中只有2個指針，較原來的4個指針要方便。增加線索后的二叉鏈表結點結構可描述如下：,2線索的分類,另外，根據(jù)遍歷的不同要求，線索二叉樹可以分為： （1）前序前驅線索二叉樹(只需畫出前驅) （2）前序后繼線索二叉樹(只需畫出后繼),（3）前序線索二叉樹(前驅和后繼都要標出) （4）中序前驅線索二叉樹(只需畫出前驅) （5）中序后繼線索二叉樹(只需畫出中序后繼) （6）中序線索二叉樹(中序前驅和后繼都要標出) （8）后序前驅線索二叉樹(只需畫出后序前驅) （8）后序后繼線

45、索二叉樹(中需畫出后序后驅) （9）后序線索二叉樹(前驅和后繼都要標出),6.7.2線索的描述,1結點數(shù)據(jù)類型描述,typedef struct bithrnode int data; int ltag ,rtag; /左、右標志域 struct bithrnode *lchild, *rchild; binode ;,2線索的畫法,在二叉樹或二叉鏈表中，若左孩子為空，則畫出它的直接前驅，右孩子為空時，則畫出它的直接后繼，左右孩子不為空時，不需畫前驅和后繼。這樣就得到了線索二叉樹或線索二叉鏈表。,前序序列為：ABCD,中序序列為：BADC,后序序列為：BDCA,仿線性表的存儲結構，在二叉樹的線

46、索鏈表上添加一個頭結點，其中l(wèi)child指向根結點，rchild指向自己，并且原先指向空的線索均指向該頭結點。如此處理，使得在線索二叉樹中查找某結點的前趨、后繼結點的算法中不必再判斷線索是否為空的情況。,6.8 樹和森林 6.8.1 樹、森林和二叉樹的轉換 1樹轉換成二叉樹,可以分為三步： （1） 連線 指相鄰兄弟之間連線，加一虛線。,（2） 抹線 指抹掉雙親與除最左孩子外其它孩子之間的連線。,（3） 旋轉 只需將樹作適當?shù)男D，具體：將圖形上原有的實線均向左斜，加上的虛線均向右斜，且變成實線，調整成二叉樹的樹型結構。,具體實現(xiàn)過程見圖7-20。,由轉換可知：在二叉樹中，左分支上的各結點在原來

47、的樹中是父子關系，而右分支上的各結點在原來的樹中是兄弟關系。,由于根結點沒有兄弟，所以變換后的二叉樹的根結點的右孩子必為空,2森林轉換成二叉樹,（1）將森林中每一棵樹分別轉換成二叉樹 這在剛才的樹轉換成二叉樹中已經(jīng)介紹過。,（2）合并 使第n棵樹接入到第n-1棵的右邊并成為它的右子樹，第 n-1 棵二叉樹接入到第n-2 棵的右邊并成為它的右子樹，第2棵二叉樹接入到第1棵的右邊并成為它的右子樹，直到最后剩下一棵二叉樹為止。,3二叉樹還原成樹,與樹轉換成二叉樹的步驟剛好相反： a. 加線：若某節(jié)點I是雙親節(jié)點的左孩子，則將該節(jié)點的右孩子及沿著此右孩子的右鏈不斷搜索到的所有右孩子，都分別與節(jié)點I的雙

48、親節(jié)點用虛線連接起來。 b. 抹線：抹掉原二叉樹中所有雙親節(jié)點與右孩子的連線。 c. 旋轉：將樹中虛線均變?yōu)閷嵕€，并按層次排好。,A,B,E,C,D,F,A,B,C,D,E,F,調整后,A,B,C,D,E,F,4. 二叉樹還原成森林,(1) 右鏈斷開（即抹線） 將二叉樹的根結點的右鏈及右鏈的右鏈等全部斷開，得到若干棵無右子樹的二叉樹。 具體操作見圖7-21(b)。 （2）二叉樹還原成樹,具體操作步驟見圖7-21(c)。,6.8.2 樹和森林的遍歷,在樹和森林中，一個結點可能有兩棵以上的子樹，因而不便討論它們的中序遍歷。故樹和森林的遍歷通常有兩種方式，先序遍歷和后序遍歷。 下面分別討論：,（1）

49、樹的先序遍歷 若樹非空，則先訪問根結點，然后按照從左到右的順序先序遍歷各子樹。 例： （2）樹的后序遍歷 若樹非空，則依次后序遍歷各子樹，最后訪問根結點。 例： 樹的先序遍歷與其轉換的相應的二叉樹的先序遍歷的結果序列相同；后序遍歷與相應二叉樹的中序序列相同。,（2）森林的后序遍歷 按順序后序遍歷森林中的每一棵樹。,同樣，森林的先序遍歷等價于它轉換成的二叉樹的先序遍歷，森林的后序遍歷等價于它轉換成的二叉樹的中序遍歷。,森林的遍歷有兩種方式：先序遍歷和后序遍歷。 （1）先序遍歷 若森林非空，則先訪問森林中第一棵樹的根結點，再先序遍歷第一棵樹各子樹，接著先序遍歷第二棵樹、第三棵樹、直到最后一棵樹。,

50、6.9 二叉樹的應用 哈夫曼樹 (Huffman),6.9.1基本術語,1路徑、路徑長度、樹的路徑長度 路徑：在一棵樹中，從一個結點到另一個結點之間的分 支構成這兩個結點之間的路徑。 路徑長度：路徑上分支的數(shù)目?；蚵窂缴线叺臄?shù)目。 樹的路徑長度：是從樹根到每一個結點的路徑長度之和。一般記為PL。,哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權路徑最短的樹，有廣泛的應用。,2結點的權及帶權路徑長度、樹的帶權路徑長度 結點的權：在許多應用中，常將樹中結點賦上一個有著某種含義的數(shù)值，則這個數(shù)值稱為該結點的權。 結點的帶權路徑長度：從根結點到該結點之間的路徑長度與該結點的權的乘積。 樹的帶權路徑長度：是樹中的所有

51、葉子結點的帶權路徑長度之和。與樹的路徑長度區(qū)別 通常記作 wpl= ，其中n 為葉子結點數(shù)目，wi為第i 個 葉子結點的權值，li 為第i 個葉子結點的路徑長度，即根到第i個葉子結點的路徑長度。,7.9.2 哈夫曼樹構造,1哈夫曼樹的定義 在一棵二叉樹中，若帶權路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman tree)。因為構造這種樹的算法最早由哈夫曼于1952年提出，故稱為哈夫曼樹。,例如，給定葉子結點的權分別為1,3,5,8，則可以得到如圖7-22所示的不同二叉樹。 從圖7-22可知，圖7-22 (b)的長度最短，圖7-22 (c)為較差情形，當然讀者還可以自已構造出具有不同的wpl情形來。,從上可見，滿二叉樹不一定是最優(yōu)二叉樹。 2哈夫曼樹的構造 即哈夫曼算法 假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 w1,w2,wn,則哈夫曼樹的構造規(guī)則為：,將給定的一組權值w1,w2,wn生成有n 棵樹的森林F=T1，T2，T3，.Tn；(每棵樹僅有一個結點) (2) 在森林F中選出兩個根結點的權值最小的樹作為一棵