數(shù)據(jù)結(jié)構(gòu)第6章_樹PPT課件

1、2021-11-1316.1 6.1 樹的概念 樹的定義(遞歸定義)：樹（Tree）是n（n0）個(gè)結(jié)點(diǎn)的有限集合T，滿足兩個(gè)條件：（1）有且僅有一個(gè)特定的稱為根（Root）的結(jié)點(diǎn)，它沒有前趨；（2）其余的結(jié)點(diǎn)可分成m個(gè)互不相交的有限集合T1,T2,Tm，其中每個(gè)集合又是一棵樹，并稱為根的子樹。當(dāng)n=0時(shí)的空集合定義為空樹。第1頁/共85頁2021-11-132使用圓圈表示結(jié)點(diǎn)，連線表示結(jié)點(diǎn)之間的關(guān)系，結(jié)點(diǎn)的名字可寫在圓圈內(nèi)或圓圈旁。學(xué)校一系二系十系一室八室一室七室n樹的直觀表示法第2頁/共85頁2021-11-133n樹的基本術(shù)語l 結(jié)點(diǎn)：指樹中的一個(gè)元素，包含數(shù)據(jù)項(xiàng)及若干指向其子樹的分支。l

2、 結(jié)點(diǎn)的度：指結(jié)點(diǎn)擁有的子樹個(gè)數(shù)。l 樹的度：指樹中結(jié)點(diǎn)的度的最大值。第3頁/共85頁2021-11-134l 葉子：指度為零的結(jié)點(diǎn)，又稱為終端結(jié)點(diǎn)。l 孩子：一個(gè)結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子。l 雙親：一個(gè)結(jié)點(diǎn)的直接上層結(jié)點(diǎn)稱為該結(jié)點(diǎn)的雙親。l 兄弟：同一雙親的孩子互稱為兄弟。l 結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開始，根結(jié)點(diǎn)為第一層，根的孩子為第二層，根的孩子的孩子為第三層，依次類推。l 樹的深度：樹中結(jié)點(diǎn)的最大層次數(shù)。l 堂兄弟：雙親在同一層上的結(jié)點(diǎn)互稱為堂兄弟。第4頁/共85頁2021-11-135l 路徑：若存在一個(gè)結(jié)點(diǎn)序列k1,k2,kj, 可使k1到達(dá)kj, 則稱這個(gè)結(jié)點(diǎn)序列是k1到達(dá)kj的

3、一條路徑。l 子孫和祖先：若存在k1到kj的一條路徑k1,k2,kj，則k1,kj-1為kj的祖先，而k2,kj為k1的子孫。l 森林：m(m0)棵互不相交的樹的集合構(gòu)成森林。l 有序樹和無序樹：若將樹中每個(gè)結(jié)點(diǎn)的各個(gè)子樹都看成是從左到右有次序的（即不能互換），則稱該樹為有序樹，否則為無序樹。第5頁/共85頁2021-11-136順序存儲順序存儲時(shí)，首先必須對樹形結(jié)構(gòu)的結(jié)點(diǎn)進(jìn)行某種方式的線性化，使之成為一個(gè)線性序列，然后存儲。鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯r(shí)，使用多指針域的結(jié)點(diǎn)形式，每一個(gè)指針域指向一棵子樹的根結(jié)點(diǎn)。由于樹的分支數(shù)不固定，很難給出一種固定的存由于樹的分支數(shù)不固定，很難給出一種固定的存儲結(jié)構(gòu)，

4、通常采用二叉樹的形式存儲樹。儲結(jié)構(gòu)，通常采用二叉樹的形式存儲樹。樹的存儲結(jié)構(gòu)第6頁/共85頁2021-11-1376.2 6.2 二叉樹 定義（二叉樹的遞歸定義）：二叉樹是n（n0）個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛洌╪=0），或由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱作這個(gè)根的左子樹和右子樹的二叉樹構(gòu)成。 二叉樹的五種基本形態(tài)： 二叉樹與度為2的樹的區(qū)別：二叉樹的子樹有左右之分，而樹的子樹不分左右；第7頁/共85頁2021-11-138u滿二叉樹和完全二叉樹l 一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。滿二叉樹的特點(diǎn)是每一層的結(jié)點(diǎn)數(shù)都達(dá)到該層可具有的最大結(jié)點(diǎn)數(shù)。l 如果一個(gè)深度為k的二叉樹，它

5、的結(jié)點(diǎn)按照從根結(jié)點(diǎn)開始，自上而下，從左至右進(jìn)行連續(xù)編號后，得到的順序與滿二叉樹相應(yīng)結(jié)點(diǎn)編號順序一致，則稱這個(gè)二叉樹為完全二叉樹。完全二叉樹的1k-1層上共有2k-1-1個(gè)結(jié)點(diǎn)，第k層的結(jié)點(diǎn)集中在左邊。l 滿二叉樹一定是完全二叉樹，而完全二叉樹不一定是滿二叉樹。 1 3 7 5 6 4 2 k=3 的滿二叉樹 1 3 5 6 4 2 完全二叉樹 1 3 6 5 4 2 非完全二叉樹 第8頁/共85頁2021-11-139二叉樹的性質(zhì)-1 性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i1)。 證明：可用數(shù)學(xué)歸納法予以證明。當(dāng)i=1時(shí)，有2i-1=20=1，同時(shí)第一層上只有一個(gè)根結(jié)點(diǎn)，故命題成立

6、。設(shè)當(dāng)i=k時(shí)成立，即第k層上至多有2k-1個(gè)結(jié)點(diǎn)。當(dāng)i=k+1時(shí)，由于二叉樹的每個(gè)結(jié)點(diǎn)至多有兩個(gè)孩子，所以第k+1層上至多有22k-1=2k個(gè)結(jié)點(diǎn)，故命題成立。第9頁/共85頁2021-11-1310二叉樹的性質(zhì)-2 性質(zhì)2：深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)(k1)。 證明：性質(zhì)1給出了二叉樹每一層中含有的最大結(jié)點(diǎn)數(shù)，深度為k的二叉樹的結(jié)點(diǎn)總數(shù)至多為故命題成立。k1ik1- i1-22第10頁/共85頁2021-11-1311二叉樹的性質(zhì)-3 性質(zhì)3：對任何一棵二叉樹，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。 證明：設(shè)度為1的結(jié)點(diǎn)數(shù)為n1，則一棵二叉樹的結(jié)點(diǎn)總數(shù)為

7、： n=n0+n1+n2 因?yàn)槌Y(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個(gè)進(jìn)入的分支(邊)，設(shè)B為分支總數(shù)，則n=B+1。又考慮到分支是由度為1和2的結(jié)點(diǎn)發(fā)出的，故有 B=2n2+n1，即 n=2n2+n1+1 比較兩式可得n0=n2+1，證畢。第11頁/共85頁2021-11-1312二叉樹的性質(zhì)-4 性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1或log2(n+1)。 (其中x表示不大于x的最大整數(shù)，x表示不小于x的最小整數(shù)。) 證明：設(shè)完全二叉樹的深度為k，則有 2k-1 - 1 n 2k 1 (1) (1)式變形為 2k-1 n+1 2k，兩邊取對數(shù) k-1log2（n1） k 取整得 klo

8、g2(n+1) 2k-1 n 2k （第k層至少有一個(gè)結(jié)點(diǎn)） （2） 兩邊取對數(shù) k-1 log2n 1, 則 i 的雙親為i /2若2*i n, 則 i 的左孩子為2*i，否則無左孩子若2*i+1 n, 則 i 的右孩子為2*i+1，否則無右孩子若i為偶數(shù), 且i != n, 則其右兄弟為i+1若i為奇數(shù), 且i != 1, 則其左兄弟為i-1結(jié)點(diǎn)i 所在層次為 log2i +1第13頁/共85頁2021-11-13146.3 6.3 二叉樹的存儲結(jié)構(gòu)6.3.1 順序存儲結(jié)構(gòu) 完全二叉樹 根據(jù)二叉樹性質(zhì)5，在一棵完全二叉樹中，按照從根結(jié)點(diǎn)起，自上而下，從左至右的方式對結(jié)點(diǎn)進(jìn)行順序編號，便可得

9、到一個(gè)反映結(jié)點(diǎn)之間關(guān)系的線性序列。 下圖的完全二叉樹的順序存儲結(jié)構(gòu)如下表： 左左圖圖的的完完全全二二叉叉樹樹的的順順序序存存儲儲 數(shù)組 下標(biāo) 0 1 2 3 4 5 6 7 8 9 10 結(jié)點(diǎn)值 A B C D E F G H I J 1 5 4 2 9 8 10 A D B J I H E 3 7 6 C G F 完完全全二二叉叉樹樹的的結(jié)結(jié)點(diǎn)點(diǎn)編編號號 第14頁/共85頁2021-11-1315一般二叉樹將二叉樹映射為完全二叉樹（通過虛結(jié)點(diǎn)）用完全二叉樹的方式存儲。根據(jù)性質(zhì)2，采用順序存儲結(jié)構(gòu)存儲一棵深度為k的完全二叉樹或一般二叉樹，向量的長度是2k-1。第15頁/共85頁2021-11-

10、1316由于一般二叉樹必須仿照完全二叉樹那樣存儲，可能會浪費(fèi)很多存儲空間，單支樹就是一個(gè)極端情況。存儲上述單支二叉樹，所需的向量長度為25-1=31第16頁/共85頁2021-11-13176.3.2 鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)每個(gè)結(jié)點(diǎn)含有數(shù)據(jù)域和兩個(gè)指針域，左、右指針域分別用來指向左孩子和右孩子。二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)也稱為二叉鏈表。二叉鏈表結(jié)點(diǎn)的C語言邏輯描述為：typedef int datatype；typedef struct node datatype data； struct node *lchild，*rchild；bitree；bitree *root;注：其中root是

11、指向根結(jié)點(diǎn)的指針，當(dāng)二叉樹為空時(shí)，則root=NULL。若結(jié)點(diǎn)的某個(gè)孩子不存在時(shí)，則相應(yīng)的指針域?yàn)榭?。?7頁/共85頁2021-11-1318三叉鏈表為了能夠?qū)ふ译p親結(jié)點(diǎn)，在結(jié)點(diǎn)中增加一個(gè)指向雙親結(jié)點(diǎn)的指針域parent。 A D B C (a) 二叉樹 A ? ? B ? C ? D A ? B ? C ? D ? (b)二叉鏈表 (c)三叉鏈表 ? ? ? 第18頁/共85頁2021-11-13196.3.3 二叉樹建立（二叉鏈表的建立）第19頁/共85頁2021-11-13206.3.3 6.3.3 二叉樹建立（二叉鏈表的建立）u二叉樹的建立 指在內(nèi)存中如何建立二叉樹的存儲結(jié)構(gòu)。u基本

12、思想 對順序存儲結(jié)構(gòu)而言，只需將二叉樹各個(gè)結(jié)點(diǎn)的值按原有的邏輯關(guān)系送入相應(yīng)的向量單元中。對鏈?zhǔn)酱鎯Y(jié)構(gòu)而言，其建立算法有多種，它們依賴于按照何種形式來輸入二叉樹的邏輯結(jié)構(gòu)信息。常用的算法是按照完全二叉樹的層次順序，依次輸入結(jié)點(diǎn)信息來建立二叉鏈表。對于一般二叉樹，則必須通過先添加若干個(gè)虛結(jié)點(diǎn)使其成為完全二叉樹。第20頁/共85頁2021-11-1321u 基本步驟問題：如何將新結(jié)點(diǎn)正確地鏈接到它的雙親結(jié)點(diǎn)上？第21頁/共85頁2021-11-1322 算法具體實(shí)現(xiàn)依據(jù)先建立的結(jié)點(diǎn)，其孩子結(jié)點(diǎn)也一定先建立的特點(diǎn)先建立的結(jié)點(diǎn)，其孩子結(jié)點(diǎn)也一定先建立的特點(diǎn)，所以可以第22頁/共85頁2021-11-1

13、323二叉樹的建立算法bitree *CREATREE( ) /* 建立二叉樹函數(shù)，函數(shù)返回指向根結(jié)點(diǎn)的指針 */char ch； /* 結(jié)點(diǎn)信息變量 */ bitree *Q maxsize； /* 設(shè)置指針類型數(shù)組來構(gòu)成隊(duì)列 * intfront, rear； /* 隊(duì)頭和隊(duì)尾指針變量 */ bitree *root, *s； /* 根結(jié)點(diǎn)指針和中間指針變量 */ root=NULL； /* 二叉樹置空 */ front=1; rear=0; /* 設(shè)置隊(duì)列指針變量初值 */*以上為初始化*/第23頁/共85頁2021-11-1324while(ch=getchar()!=#) /* 輸入

14、一個(gè)字符，當(dāng)不是結(jié)束符時(shí)執(zhí)行以下操作 */ s=NULL; if(ch!=) /* 表示虛結(jié)點(diǎn)，當(dāng)不是虛結(jié)點(diǎn)則建立新結(jié)點(diǎn) */ s=malloc(sizeof (bitree); sdata=ch; slchild=NULL; srchild=NULL; rear+; /* 隊(duì)尾指針增1，指向新結(jié)點(diǎn)地址應(yīng)存放的單元 */ Qrear=s; /* 將新結(jié)點(diǎn)地址入隊(duì)或虛結(jié)點(diǎn)指針NULL入隊(duì) */ if (rear= =1) root=s; /* 輸入的第一個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn) */ else if (s & Qfront) /* 孩子和雙親結(jié)點(diǎn)都不是虛結(jié)點(diǎn) */ if (rear % 2= =

15、0) Qfrontlchild=s;/*rear為偶數(shù)，新結(jié)點(diǎn)是左孩子*/ else Qfrontrchild=s; /* rear為奇數(shù)且不等于1，新結(jié)點(diǎn)是右孩子 */ if (rear % 2= =1) front+; /* 結(jié)點(diǎn)* Qfront的兩個(gè)孩子處理完畢，出隊(duì)列 */ return root; /* 返回根指針 */ /* CREATREE */第24頁/共85頁2021-11-13256.4 6.4 二叉樹的遍歷 所謂樹的遍歷，就是按某種次序訪問樹中的結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。 遍歷的結(jié)果：產(chǎn)生一個(gè)關(guān)于結(jié)點(diǎn)的線性序列。6.4.1 深度優(yōu)先遞歸遍歷 訪問根結(jié)點(diǎn)記作

16、D 遍歷根的左子樹記作 L 遍歷根的右子樹記作 R 則可能的遍歷次序有： 先序 DLR 逆先序 DRL 中序 LDR 逆中序 RDL 后序 LRD 逆后序 RLD第25頁/共85頁2021-11-13261. 先序遍歷DLR先序遍歷算法的遍歷過程 遍歷結(jié)果： abdefc第26頁/共85頁2021-11-13272. 中序遍歷LDR中序遍歷算法的遍歷過程點(diǎn) */ inorder (p-rchild); /* 中序遍歷右子樹 */ 遍歷結(jié)果：dbefac第27頁/共85頁2021-11-13283. 后序遍歷LRD后序遍歷算法的遍歷過程遍歷結(jié)果：dfebca第28頁/共85頁2021-11-13

17、296.4.2 二叉樹的廣度優(yōu)先遍歷（按層次遍歷二叉樹）從根開始逐層訪問。先遍歷二叉樹的第一層結(jié)點(diǎn)，然后遍歷第二層結(jié)點(diǎn)，最后遍歷最下層的結(jié)點(diǎn)。而對每一層的遍歷是按從左至右的方式進(jìn)行。在上層中先被訪問的結(jié)點(diǎn)，它的下層孩子也必然先被訪問，因此在這種遍歷算法的實(shí)現(xiàn)時(shí)，需要使用一個(gè)隊(duì)列。在遍歷進(jìn)行之前先把二叉樹的根結(jié)點(diǎn)的存儲地址入隊(duì)，然后依次從隊(duì)列中出隊(duì)結(jié)點(diǎn)的存儲地址，每出隊(duì)一個(gè)結(jié)點(diǎn)的存儲地址則對該結(jié)點(diǎn)進(jìn)行訪問，然后依次將該結(jié)點(diǎn)的左孩子和右孩子的存儲地址入隊(duì)，如此反復(fù)，直到隊(duì)空為止。廣度優(yōu)先遍歷算法第29頁/共85頁2021-11-1330Bitree *Qmaxsize;void layer(BiT

18、ree *p) BiTree *s; if (p!=NULL) rear=1; front=0; Qrear=p; while (frontdata); if (s-lchild!=NULL) /左子樹非空 rear+; Qrear=s-lchild; /左子樹根結(jié)點(diǎn)入隊(duì) 二叉樹的廣度優(yōu)先遍歷實(shí)例第30頁/共85頁2021-11-1331 if (s-rchild !=NULL) /右子樹非空 rear+; Qrear=s-lchild; /右子樹根結(jié)點(diǎn)入隊(duì) 第31頁/共85頁2021-11-1332ABCDEFG第32頁/共85頁2021-11-13336.4.3 深度優(yōu)先的非遞歸算法 分析

19、：二叉樹的深度優(yōu)先遍歷算法是以遞歸形式給出的，運(yùn)行效率低，可讀性不強(qiáng)。因遞歸調(diào)用過程要用到棧來保存每次調(diào)用的參數(shù)，所以，我們可以用棧來實(shí)現(xiàn)二叉樹的深度優(yōu)先遍歷，將遞歸算法轉(zhuǎn)化為非遞歸算法。 以中序遍歷為例，在遍歷左子樹之前，先把根結(jié)點(diǎn)入棧，當(dāng)左子樹遍歷結(jié)束后，從棧中彈出并訪問根結(jié)點(diǎn)，再遍歷右子樹。算法執(zhí)行過程第33頁/共85頁2021-11-1334void inorder(BiTree *T) SqStack *S; BiTree *P=T;/P為工作指針I(yè)nitStack(S); /*順序棧初始化*/while( P!=NULL | !Empty(S) if (P!=NULL) Push(

20、S,P); /*根結(jié)點(diǎn)入棧*/ P=P-lchild; /* 遍歷左子樹*/ else Pop(S,P); /*左子樹遍歷結(jié)束，出棧 */ printf(%c,P-data); P=P-rchild; /*遍歷右子樹*/ 第34頁/共85頁2021-11-1335&a&b&d&c棧的變化情況輸出序列為：dbac第35頁/共85頁2021-11-13366.4.4 從遍歷序列恢復(fù)二叉樹可以由DLR和LDR的遍歷序列可以唯一地確定一棵二叉樹，或者由LRD和LDR的遍歷序列可以唯一地確定一棵二叉樹。通過DLR或者LRD的遍歷序列確定二叉樹或子樹的根結(jié)點(diǎn)；通過LDR確定

21、左、右子樹的序列。第36頁/共85頁2021-11-1337例： 由先序序列 ABHFDECKG 和中序序列 HBDFAEKCG 恢復(fù)二叉樹的過程。第37頁/共85頁2021-11-13386.4.5 遍歷算法的應(yīng)用1.統(tǒng)計(jì)二叉樹的葉子結(jié)點(diǎn)數(shù)int count =0; int countleaf(bitree *p) if ( p != NULL ) count = countleaf( plchild ); /* 對左子樹上的葉子結(jié)點(diǎn)計(jì)數(shù)*/ if ( (plchild= =NULL)&(prchild= =NULL) count=count+1;count = countleaf(

22、prchild); /* 對右子樹上的葉子結(jié)點(diǎn)計(jì)數(shù)*/ return count; 請考慮如何統(tǒng)計(jì)度為1的結(jié)點(diǎn)數(shù)，度為2的結(jié)點(diǎn)數(shù)。第38頁/共85頁2021-11-13392.利用二叉樹先序遍歷計(jì)算二叉樹的深度int l=h=0; int treedepth(bitree * p, int l )if ( p!= NULL) l+; if ( lh ) h=l; h=treedepth( plchild, l ); / 計(jì)算左子樹的深度 h=treedepth( prchild, l ); /計(jì)算右子樹的深度 return h; 第39頁/共85頁2021-11-13403.求二叉樹結(jié)點(diǎn)個(gè)數(shù)i

23、nt Size(BiTree *T) if (T=NULL) return (0); else return (1 + Size (T-lchild ) + Size ( T-rchild); /二叉樹的結(jié)點(diǎn)個(gè)數(shù)是根結(jié)點(diǎn)、左右子樹結(jié)點(diǎn)個(gè)數(shù)之和4.交換左右子樹void Exchange(BiTree *T)BiTree *S;if (T!=NULL) S=T-lchild; T-lchild=T-rchild;T-rchild=S;Exchange(T-lchild);Exchange(T-rchild);第40頁/共85頁2021-11-13415.利用先序遍歷方法，以嵌套括號的形式輸出二叉樹

24、的層次結(jié)構(gòu)void OutBT(BiTree *p) if (p!=NULL) printf(“%c”,p-data); if(p-lchild!=NULL|p-rchild!=NULL) /有左子樹或右子樹 printf( “(” ); OutBT(p-lchild); /遍歷左子樹 if(p-rchild!=NULL) printf( “,” ); /有右子樹輸出逗號 OutBT(p-rchild); /遍歷右子樹 printf( “)” ); 輸出的結(jié)果第41頁/共85頁2021-11-1342輸出的結(jié)果：A（B（D（，G），E），C（F）ABCDEFG第42頁/共85頁2021-11-

25、13436.5 6.5 樹和森林任何一棵樹(T)都可以轉(zhuǎn)換為一棵二叉樹(T)，同樣一棵二叉樹也可轉(zhuǎn)換成一棵樹，而且這種轉(zhuǎn)換是具有惟一性的。1.樹轉(zhuǎn)為二叉樹 在兄弟之間增加一條連線； 對每個(gè)結(jié)點(diǎn)，除了保留與其左孩子的連線外，除去與其他孩子之間的連線。 以樹的根結(jié)點(diǎn)為軸心，將整個(gè)樹順時(shí)針旋轉(zhuǎn)45。2.二叉樹轉(zhuǎn)為樹 若結(jié)點(diǎn)X是雙親Y的左孩子，則將X的右孩子，右孩子的右孩子，都與X的雙親結(jié)點(diǎn)Y用線相連； 去掉原有的雙親到右孩子的連線。第43頁/共85頁2021-11-1344 (c) A D I G H E B C F (d) A D I G H E B C F (a) T AFDGBECIH ( b

26、 ) T (c) (c) (c)第44頁/共85頁2021-11-13456.6 6.6 線索二叉樹遍歷二叉樹是將一個(gè)非線性結(jié)構(gòu)進(jìn)行線性化的操作，使每個(gè)結(jié)點(diǎn)（除第一個(gè)和最后一個(gè)）在這些線性序列中有且僅有一個(gè)直接前趨和直接后繼。當(dāng)以二叉鏈表作為存儲結(jié)構(gòu)時(shí)，如果希望能直接得到結(jié)點(diǎn)在任一序列(先序、中序或后序)中的前驅(qū)和后繼信息，而不需要每次對二叉樹進(jìn)行遍歷，有必要引入線索二叉樹。線索是指向結(jié)點(diǎn)前趨和后繼的指針，若結(jié)點(diǎn)有左孩子，則lchild指示其左孩子，否則lchild中存儲該結(jié)點(diǎn)的前趨結(jié)點(diǎn)的指針；若結(jié)點(diǎn)有右孩子，則rchild指示其右孩子，否則rchild中存儲指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)的指針。按照不

27、同的遍歷序列，可以得到先序、中序和后序線索二叉樹。第45頁/共85頁2021-11-1346 有n個(gè)結(jié)點(diǎn)的二叉鏈表中必然存在n1個(gè)空的指針域，利用空的指針域來存放結(jié)點(diǎn)的前趨和后繼信息是可行的。線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu)實(shí)質(zhì)上利用二叉鏈表中的空指針域作為線索。 二叉樹的線索化的實(shí)質(zhì)是將二叉鏈表中的空指針改為指向前趨或后繼的線索。因?yàn)榍摆吇蚝罄^的信息只有在遍歷時(shí)才能得到，因此線索化的過程就是在遍歷過程中修改空指針的過程。第46頁/共85頁2021-11-1347中序線索二叉樹及線索鏈表中序遍歷序列：BDAEC第47頁/共85頁2021-11-13486.7 6.7 二叉樹的應(yīng)用6.7.1 哈夫曼樹及應(yīng)用

28、1.基本概念路徑長度 兩個(gè)結(jié)點(diǎn)之間的路徑長度是連接兩結(jié)點(diǎn)的路徑上的分支數(shù)。樹的路徑長度是各結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度之和。(a)PL=0+1(a)PL=0+1* *2+22+2* *4+3=134+3=13(b)PL=0+1(b)PL=0+1* *2+22+2* *3+33+3* *2=142=14第48頁/共85頁2021-11-1349帶權(quán)路徑長度 樹的帶權(quán)路徑長度是樹的各葉子結(jié)點(diǎn)所帶的權(quán)值與該結(jié)點(diǎn)到根的路徑長度的乘積的和。 其中n為樹中葉子結(jié)點(diǎn)的數(shù)目，wi為葉子結(jié)點(diǎn)i的權(quán)值，li為葉子結(jié)點(diǎn)i到根結(jié)點(diǎn)之間的路徑長度。niiilwWPL1第49頁/共85頁2021-11-1350葉子結(jié)點(diǎn)的權(quán)值相

29、同，具有不同帶權(quán)路徑長度的二叉樹哈夫曼樹 帶權(quán)路徑長度最小的二叉樹稱為哈夫曼樹（最優(yōu)二叉樹）。在哈夫曼樹中，權(quán)值越大的結(jié)點(diǎn)離根越近。第50頁/共85頁2021-11-1351哈夫曼樹的不唯一性 權(quán)值為w1,w2, ,wn 的n個(gè)葉子結(jié)點(diǎn)形成的二叉樹，可以具有多種形態(tài)，其中能被稱為哈夫曼樹的二叉樹并不是唯一的。如下圖。 b d c a 3 4 5 7 (a) (b) b a c d 3 4 5 7 不不同同形形態(tài)態(tài)的的哈哈夫夫曼曼樹樹 (a) WPL =3242527238；(b) WPL =334352738。第51頁/共85頁2021-11-1352完全二叉樹不一定是哈夫曼樹 在葉子數(shù)和權(quán)值

30、相同的二叉樹中，完全二叉樹不一定是哈夫曼樹（最優(yōu)二叉樹）。如下圖。 (a) (b) 5 a d c b 4 2 7 b d c a 2 4 5 7 完完全全二二叉叉樹樹與與哈哈夫夫曼曼樹樹 (a) WPL2242527236；(b) WPL2343527135。第52頁/共85頁2021-11-13532.哈夫曼樹的構(gòu)造哈夫曼樹的構(gòu)造 哈夫曼算法：哈夫曼算法：(1) 由給定的由給定的n個(gè)權(quán)值個(gè)權(quán)值w0, w1, w2, , wn-1，構(gòu)成具有，構(gòu)成具有n棵棵二叉樹的集合二叉樹的集合F = T0, T1, T2, , Tn-1，其中每一棵二叉，其中每一棵二叉樹樹Ti只有一個(gè)帶有權(quán)值只有一個(gè)帶有權(quán)

31、值wi的根結(jié)點(diǎn)，其左、右子樹均為的根結(jié)點(diǎn)，其左、右子樹均為空?？?。 (2) 重復(fù)以下步驟重復(fù)以下步驟, 直到直到F中僅剩下一棵樹為止：中僅剩下一棵樹為止：第53頁/共85頁2021-11-1354 又一權(quán)值集合0.1,0.02,0.1,0.08,0.1,0.3,0.4，試構(gòu)造一顆huffman樹第54頁/共85頁2021-11-1355第55頁/共85頁2021-11-13563. 哈夫曼樹的應(yīng)用最佳判定算法例：編制一個(gè)將百分制轉(zhuǎn)換成五級制的程序，使比較次數(shù)最少。各分?jǐn)?shù)段分布情況如下：百分制05960697079808990100五級制不及格（E）及格（D）中（C）良（B）優(yōu)（A）比例數(shù)0.0

32、50.150.40.30.1第56頁/共85頁2021-11-13571 10.40.40.60.60.30.30.30.30.150.150.150.150.050.050.10.1AEDBCs80s70s90s60EDCBAFTTFFTTF？第57頁/共85頁2021-11-1358哈夫曼編碼主要用途是實(shí)現(xiàn)數(shù)據(jù)壓縮。 設(shè)給出一段報(bào)文： abaccda 字符集合是 a, b, c, d ，各個(gè)字符出現(xiàn)的頻度(次數(shù))是 W 3, 1, 2, 1。 若給每個(gè)字符以等長編碼 a : 00 b : 01 c : 10 d : 11則總編碼為00010010101100長度為 ( 3+1+2+1 )

33、* 2 = 14 若按各個(gè)字符出現(xiàn)的概率不同而給予不等長編碼，可望減少總編碼長度。 因各字符出現(xiàn)的概率為 3/7, 1/7, 2/7, 1/7。第58頁/共85頁2021-11-1359第59頁/共85頁2021-11-1360構(gòu)造哈夫曼樹算法中的數(shù)據(jù)結(jié)構(gòu) 存儲結(jié)構(gòu)define n 葉子數(shù)目define m 2*n-1 /* 結(jié)點(diǎn)總數(shù) */ typedef char datatype; typedef struct float weight; datatype data; int lchild, rchild, parent; hufmtree;hufmtree treem; 采用順序存儲結(jié)構(gòu)

34、，每個(gè)結(jié)點(diǎn)為一個(gè)結(jié)構(gòu)體。第60頁/共85頁2021-11-1361構(gòu)造哈夫曼樹算法實(shí)現(xiàn) HUFFMAN(hufmtree tree )int i, j, p; char ch; float small1, small2, f; for( i=0; im; i+) /* 初始化 */ treei.parent=0; treei.lchild=0; treei.rchild=0; treei.weight=0.0; treei.data= 0; for( i=0; in; i+) /輸入n個(gè)結(jié)點(diǎn)的權(quán)值和結(jié)點(diǎn)值 scanf(“ %f ”, &f); treei.weight=f; scanf

35、(“ %c ”,&ch); treei.data=ch; 第61頁/共85頁2021-11-1362 for( i=n; im ;i+ ) / 進(jìn)行n-1次合并，產(chǎn)生n-1個(gè)新結(jié)點(diǎn) p1=p2=0; / 記錄權(quán)值最小、次最小的結(jié)點(diǎn)下標(biāo) small1=small2=Maxval; /Maxval是float類型的最大值 / 從下標(biāo)0掃描到已生成的結(jié)點(diǎn)下標(biāo) for ( j=0; j=i-1; j+ ) if ( treej.parent= =0) if ( treej.weightsmall1 ) small2=small1; /改變最小權(quán)，次最小權(quán)及對應(yīng)位置 small1=treej.w

36、eight; p2=p1; p1=j; else if( treej.weightsmall2 ) /改變次小權(quán)及位置 small2=treej.weight; p2=j; treep1.parent=i; /給合并的兩個(gè)結(jié)點(diǎn)的雙親域賦值 treep2.parent=i; treei.lchild=p1;/ 給新生成的結(jié)點(diǎn)的左右孩子域賦值 treei.rchild=p2; treei.weight =treep1.weight+treep2.weight;/給新生成的結(jié)點(diǎn)的權(quán)值域賦值 /* HUFFMAN */第62頁/共85頁2021-11-1363構(gòu)造哈夫曼樹算法的基本思想：對m=2n-1

37、個(gè)結(jié)點(diǎn)初始化，將雙親域，左、右孩子域，權(quán)值，結(jié)點(diǎn)值置0；輸入n個(gè)葉子結(jié)點(diǎn)的權(quán)值和結(jié)點(diǎn)值；循環(huán)體執(zhí)行n-1次，進(jìn)行n-1次合并，產(chǎn)生n-1個(gè)新結(jié)點(diǎn)： 在i個(gè)結(jié)點(diǎn)中找出兩個(gè)雙親域?yàn)?（即沒有被合并的結(jié)點(diǎn)）且權(quán)值最小的結(jié)點(diǎn)，p1指示權(quán)值最小的結(jié)點(diǎn)，p2指示權(quán)值次最小的結(jié)點(diǎn)； 將兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹進(jìn)行合并： treep1.parent=i; /i為新結(jié)點(diǎn)，即新產(chǎn)生的雙親結(jié)點(diǎn)treep2.parent=i; treei.lchild=p1; /新產(chǎn)生的雙親結(jié)點(diǎn)指向左、右子樹的根結(jié)點(diǎn) treei.rchild=p2; treei.weight = treep1.weight+treep2.weig

38、ht; /新結(jié)點(diǎn)的權(quán)值是左、右子樹根結(jié)點(diǎn)權(quán)值之和。第63頁/共85頁2021-11-1364哈夫曼編碼的數(shù)據(jù)結(jié)構(gòu)編碼數(shù)組結(jié)構(gòu)描述如下：typedef char datatype;typedef struct char bitsn; /編碼數(shù)組位串，其中n為葉子結(jié) 點(diǎn)數(shù)目 int start; /編碼在位串的起始位置 datatype data; /結(jié)點(diǎn)值 codetype;codetype coden; 一個(gè)字符的哈夫曼編碼在數(shù)組bits中從高位到低位順序存儲。第64頁/共85頁2021-11-1365哈夫曼編碼的算法的基本思想 從葉子到根逆向求哈夫曼編碼 從葉子treei出發(fā)，利用雙親地址找

39、到雙親結(jié)點(diǎn)treep，再利用treep的lchild和rchild指針域判斷treei是treep的左孩子還是右孩子，然后決定分配代碼的 0 還是代碼 1 , 然后以treep為出發(fā)點(diǎn)繼續(xù)向上回溯，直到根結(jié)點(diǎn)為止。第65頁/共85頁2021-11-1366哈夫曼編碼算法實(shí)現(xiàn)void HUFFMANCODE(codetype code ，hufmtree tree )/code 存放求出的哈夫曼編碼的數(shù)組， tree已知的哈夫曼樹 int i, c, p; codetype cd; / 緩沖變量 for ( i=0; in; i+ ) /n為葉子結(jié)點(diǎn)數(shù)目 ，循環(huán)產(chǎn)生n個(gè)字符的哈夫曼編碼 cd.

40、start=n; /從葉子結(jié)點(diǎn)出發(fā)向上回溯 ，在bits中， 從高位開始存儲 c=i; /c指示第i個(gè)葉子結(jié)點(diǎn) p=treec.parent; /p指示結(jié)點(diǎn)c的雙親結(jié)點(diǎn) cd.data=treec.data; /對結(jié)點(diǎn)數(shù)據(jù)域賦值 第66頁/共85頁2021-11-1367 while( p!=0 ) /c指示到根結(jié)點(diǎn)時(shí)，p為0 cd.start - ; if( treep. lchild = = c) cd.bitscd.start= 0; else cd.bits cd.start=1; /若結(jié)點(diǎn)c是雙親結(jié)點(diǎn)p的左孩子，置0；否則就是右孩子，置1 c=p; /雙親結(jié)點(diǎn)p作為孩子結(jié)點(diǎn)，用c指示

41、 p=treec.parent; /p指示結(jié)點(diǎn)c的雙親結(jié)點(diǎn) codei=cd; /一個(gè)字符的編碼存入codei /for_end / HUFFMANCODE第67頁/共85頁2021-11-1368哈夫曼編碼結(jié)果 對下圖所示的哈夫曼樹進(jìn)行編碼，可得到下表所示的編碼表。code下標(biāo)bitsstartdata0123003a11101b2102c31111d第68頁/共85頁2021-11-1369哈夫曼樹譯碼 定義：哈夫曼樹譯碼是指由給定的代碼求出代碼所表示的結(jié)點(diǎn)值。 譯碼的過程是：從根結(jié)點(diǎn)出發(fā)，逐個(gè)讀入電文中的二進(jìn)制代碼；若代碼為0則走向左孩子，否則走向右孩子；一旦到達(dá)葉子結(jié)點(diǎn)，便可譯出代碼所

42、對應(yīng)的字符。然后又重新從根結(jié)點(diǎn)開始繼續(xù)譯碼，直到二進(jìn)制電文結(jié)束。第69頁/共85頁2021-11-1370哈夫曼樹譯碼算法void HUFFMANDECODE(codetype code ，hufmtree tree )int i, c, p, b; int endflag=-1; /* 電文結(jié)束標(biāo)志取-1 */ i=m-1; /* 從根結(jié)點(diǎn)開始向下搜索 */ scanf ( “%d”, &b); /* 讀入一個(gè)二進(jìn)制代碼 */ while ( b != endflag) if( b= =0) i=treei.lchild; /* 走向左孩子 */ else i=treei.rchil

43、d; /* 走向右孩子 */ if ( treei.lchild= =0 ) /* treei是葉子結(jié)點(diǎn) */ putchar( codei.data); i=m-1; /* 回到根結(jié)點(diǎn) */ scanf(“%d”, &b); /* 讀入下一個(gè)二進(jìn)制代碼 */ if (treei.lchild!=0)&(i!=m-1) ) /* 電文讀完尚未到葉子結(jié)點(diǎn) */ printf( “n ERRORn”); /* 輸入電文有錯 */ /* HUFFMANDECODE */ 說明：treei.lchild為0，treei.rchild也必然為0，因?yàn)楣蚵鼧錄]有度為1的結(jié)點(diǎn)，所以tree

44、i是葉子結(jié)點(diǎn)。第70頁/共85頁2021-11-13716.7.2 二叉排序樹二叉排序樹的概念： 二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹： 每個(gè)結(jié)點(diǎn)都有一個(gè)關(guān)鍵字(key)，所有結(jié)點(diǎn)的關(guān)鍵字互不相同。 左子樹(若非空)上所有結(jié)點(diǎn)的關(guān)鍵字都小于根結(jié)點(diǎn)的關(guān)鍵字。 右子樹(若非空)上所有結(jié)點(diǎn)的關(guān)鍵字都大于根結(jié)點(diǎn)的關(guān)鍵字。 左子樹和右子樹也是二叉排序樹。第71頁/共85頁2021-11-1372幾個(gè)二叉排序樹的例子幾個(gè)二叉排序樹的例子第72頁/共85頁2021-11-1373二叉排序樹的數(shù)據(jù)結(jié)構(gòu) 二叉排序樹的二叉鏈表存儲結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)描述如下：typedef int keytype;typ

45、edef struct keytype key; /關(guān)鍵字項(xiàng) datatype other; / 其它數(shù)據(jù)項(xiàng) struct node *lchild, *rchild; /左、右指針域 bstnode;第73頁/共85頁2021-11-1374二叉排序樹的構(gòu)造 構(gòu)造一棵二叉排序樹，就是從空的二叉排序樹開始，逐個(gè)結(jié)點(diǎn)插入到二叉排序樹中。 對于一組數(shù)據(jù)元素 R1, R2, , Rn , 可按以下方法來構(gòu)造二叉排序樹：說明：每次插入的新結(jié)點(diǎn)都是當(dāng)前二叉樹的葉子結(jié)點(diǎn) 給定的關(guān)鍵字序列不同，二叉排序樹的形態(tài)則不同 二叉排序樹中不存在兩個(gè)結(jié)點(diǎn)的關(guān)鍵字相同的結(jié)點(diǎn)第74頁/共85頁2021-11-1375例：給定關(guān)鍵字序列10、18、3