《數(shù)據(jù)結(jié)構(gòu)教學(xué)課件》cha

第六章樹和二叉樹,教學(xué)目的和要求,1、熟練掌握二叉樹的結(jié)構(gòu)特點(diǎn)，了解相應(yīng)的證明。2、熟悉二叉樹的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍。3、掌握二叉樹遍歷的遞歸與非遞歸算法。4、掌握二叉線索樹的相關(guān)算法。5、熟悉樹的各種存儲(chǔ)結(jié)構(gòu)及特點(diǎn)，掌握樹和森林與二叉樹的方法。6、了解最優(yōu)樹的特性，掌握最優(yōu)樹和哈夫曼編碼的方法。,1數(shù)據(jù)的邏輯結(jié)構(gòu),2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu),3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。,A線性結(jié)構(gòu),B非線性結(jié)構(gòu),A順序存儲(chǔ),B鏈?zhǔn)酱鎯?chǔ),線性表,棧,隊(duì),樹形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個(gè)主要問題,樹形結(jié)構(gòu),全校學(xué)生檔案管理的組織方式,樹形結(jié)構(gòu)結(jié)點(diǎn)間具有分層次的連接關(guān)系,6.1樹的類型定義,6.2二叉樹的類型定義,6.3二叉樹的存儲(chǔ)結(jié)構(gòu),6.4二叉樹的遍歷,6.5線索二叉樹,6.6樹和森林的表示方法,6.7樹和森林的遍歷,6.8哈夫曼樹與哈夫曼編碼,6.1樹的類型定義,數(shù)據(jù)對(duì)象D：,D是具有相同特性的數(shù)據(jù)元素的集合。,若D為空集，則稱為空樹。否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；(2)當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的有限集T1,T2,Tm，其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。,數(shù)據(jù)關(guān)系R：,A,B,C,D,E,F,G,H,I,J,M,K,L,A(B(E,F(K,L),C(G),D(H,I,J(M),T1,T3,T2,樹根,例如:,基本操作：,查找類,插入類,刪除類,Root(T)/求樹的根結(jié)點(diǎn),查找類：,Value(T,cur_e)/求當(dāng)前結(jié)點(diǎn)的元素值,Parent(T,cur_e)/求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn),LeftChild(T,cur_e)/求當(dāng)前結(jié)點(diǎn)的最左孩子,RightSibling(T,cur_e)/求當(dāng)前結(jié)點(diǎn)的右兄弟,TreeEmpty(T)/判定樹是否為空樹,TreeDepth(T)/求樹的深度,TraverseTree(T,Visit()/遍歷,InitTree(Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit();InOrderTraverse(T,Visit();PostOrderTraverse(T,Visit();LevelOrderTraverse(T,Visit();,InitBiTree(,ClearBiTree(,二叉樹的重要特性,性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)。(i1),用歸納法證明：歸納基：歸納假設(shè)：歸納證明：,i=1層時(shí)，只有一個(gè)根結(jié)點(diǎn)：2i-1=20=1；,假設(shè)對(duì)所有的j，1ji，命題成立；,二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹，則第i層的結(jié)點(diǎn)數(shù)=2i-22=2i-1。,性質(zhì)2：深度為k的二叉樹上至多含2k-1個(gè)結(jié)點(diǎn)（k1）。,證明：,基于上一條性質(zhì)，深度為k的二叉樹上的結(jié)點(diǎn)數(shù)至多為20+21+2k-1=2k-1。,性質(zhì)3：對(duì)任何一棵二叉樹，若它含有n0個(gè)葉子結(jié)點(diǎn)、n2個(gè)度為2的結(jié)點(diǎn)，則必存在關(guān)系式：n0=n2+1。,證明：,設(shè)二叉樹上結(jié)點(diǎn)總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)b=n1+2n2而b=n-1=n0+n1+n2-1由此，n0=n2+1。,兩類特殊的二叉樹：,滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。,完全二叉樹：樹中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,a,b,c,d,e,f,g,h,i,j,性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。,證明：,設(shè)完全二叉樹的深度為k則根據(jù)第二條性質(zhì)得2k-1nn，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)，否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。,（）,例題1:若一樹二叉共有1001個(gè)結(jié)點(diǎn)，且無度為1的結(jié)點(diǎn)，則葉子結(jié)點(diǎn)的個(gè)數(shù)為（）。例題2:將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的孩子編號(hào)為（）。,6.3二叉樹的存儲(chǔ)結(jié)構(gòu),二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示,一、二叉樹的順序存儲(chǔ)表示,#defineMAX_TREE_SIZE100/二叉樹的最大結(jié)點(diǎn)數(shù)typedefTElemTypeSqBiTreeMAX_TREE_SIZE;/0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)SqBiTreebt;,一、二叉樹的順序存儲(chǔ)表示,例如:,A,B,C,D,E,F,ABDCEF,012345678910111213,1,4,0,13,2,6,順序存儲(chǔ)結(jié)構(gòu)僅適用于完全二叉樹！,二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示,1.二叉鏈表,2三叉鏈表,3雙親鏈表,4線索鏈表,A,D,E,B,C,F,root,lchilddatarchild,結(jié)點(diǎn)結(jié)構(gòu):,1.二叉鏈表,typedefstructBiTNode/結(jié)點(diǎn)結(jié)構(gòu)TElemTypedata;structBiTNode*lchild,*rchild;/左右孩子指針BiTNode,*BiTree;,lchilddatarchild,結(jié)點(diǎn)結(jié)構(gòu):,C語言的類型描述如下:,A,D,E,B,C,F,root,2三叉鏈表,parentlchilddatarchild,結(jié)點(diǎn)結(jié)構(gòu):,typedefstructTriTNode/結(jié)點(diǎn)結(jié)構(gòu)TElemTypedata;structTriTNode*lchild,*rchild;/左右孩子指針structTriTNode*parent;/雙親指針TriTNode,*TriTree;,parentlchilddatarchild,結(jié)點(diǎn)結(jié)構(gòu):,C語言的類型描述如下:,0123456,dataparent,結(jié)點(diǎn)結(jié)構(gòu):,3雙親鏈表,LRTag,LRRRL,typedefstructBPTNode/結(jié)點(diǎn)結(jié)構(gòu)TElemTypedata;int*parent;/指向雙親的指針charLRTag;/左、右孩子標(biāo)志域BPTNodetypedefstructBPTree/樹結(jié)構(gòu)BPTNodenodesMAX_TREE_SIZE;intnum_node;/結(jié)點(diǎn)數(shù)目introot;/根結(jié)點(diǎn)的位置BPTree,6.4二叉樹的遍歷,一、問題的提出,二、先左后右的遍歷算法,三、算法的遞歸描述,四、中序遍歷算法的非遞歸描述,五、遍歷算法的應(yīng)用舉例,如何順著某一條搜索路徑巡訪二叉樹中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。,一、問題的提出,“訪問”的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。,“遍歷”是任何類型均有的操作，對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)，,每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。,對(duì)“二叉樹”而言，可以有三條搜索路徑：,1先上后下的按層次遍歷；2先左（子樹）后右（子樹）的遍歷；3先右（子樹）后左（子樹）的遍歷。,二、先左后右的遍歷算法,先序（根）的遍歷算法,中序（根）的遍歷算法,后序（根）的遍歷算法,若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹。,先序（根）的遍歷算法：,若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹。,中序（根）的遍歷算法：,若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點(diǎn)。,后序（根）的遍歷算法：,課堂提問：,有以下結(jié)構(gòu)的二叉樹寫出其先序、中序和后序遍歷的序列,三、算法的遞歸描述,voidPreorder(BiTreeT,void(*visit)(TElemType/遍歷右子樹,四、中序遍歷算法的非遞歸描述,BiTNode*GoFarLeft(BiTreeT,Stack*S)if(!T)returnNULL;while(T-lchild)Push(S,T);T=T-lchild;returnT;,voidInorder_I(BiTreeT,void(*visit)(TelemType/棧空表明遍歷結(jié)束/while/Inorder_I,五、遍歷算法的應(yīng)用舉例,1、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)(先序遍歷),2、求二叉樹的深度(后序遍歷),3、復(fù)制二叉樹(后序遍歷),4、建立二叉樹的存儲(chǔ)結(jié)構(gòu),1、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù),算法基本思想:,先序(或中序或后序)遍歷二叉樹，在遍歷過程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。由此，需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)，并將算法中“訪問結(jié)點(diǎn)”的操作改為：若是葉子，則計(jì)數(shù)器增1。,voidCountLeaf(BiTreeT,int/if/CountLeaf,2、求二叉樹的深度(后序遍歷),算法基本思想:,從二叉樹深度的定義可知，二叉樹的深度應(yīng)為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，算法中“訪問結(jié)點(diǎn)”的操作為：求得左、右子樹深度的最大值，然后加1。,首先分析二叉樹的深度和它的左、右子樹深度之間的關(guān)系。,intDepth(BiTreeT)/返回二叉樹的深度if(!T)depthval=0;elsedepthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeftdepthRight?depthLeft:depthRight);returndepthval;,3、復(fù)制二叉樹,其基本操作為：生成一個(gè)結(jié)點(diǎn)。,根元素,T,左子樹,右子樹,根元素,NEWT,左子樹,右子樹,左子樹,右子樹,(后序遍歷),BiTNode*GetTreeNode(TElemTypeitem,BiTNode*lptr,BiTNode*rptr)if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=item;T-lchild=lptr;T-rchild=rptr;returnT;,生成一個(gè)二叉樹的結(jié)點(diǎn)(其數(shù)據(jù)域?yàn)閕tem,左指針域?yàn)閘ptr,右指針域?yàn)閞ptr),BiTNode*CopyTree(BiTNode*T)if(!T)returnNULL;if(T-lchild)newlptr=CopyTree(T-lchild);/復(fù)制左子樹elsenewlptr=NULL;if(T-rchild)newrptr=CopyTree(T-rchild);/復(fù)制右子樹elsenewrptr=NULL;newT=GetTreeNode(T-data,newlptr,newrptr);returnnewT;/CopyTree,A,B,C,D,E,F,G,H,K,D,C,B,H,K,G,F,E,A,例如：下列二叉樹的復(fù)制過程如下：,newT,4、建立二叉樹的存儲(chǔ)結(jié)構(gòu),不同的定義方法相應(yīng)有不同的存儲(chǔ)結(jié)構(gòu)的建立算法,以字符串“A!”表示,以字符串的形式根左子樹右子樹定義一棵二叉樹,例如:,A,B,C,D,以字符“!”表示,A(B(!,C(!,!),D(!,!),空樹,只含一個(gè)根結(jié)點(diǎn)的二叉樹,A,以下列字符串表示,StatusCreateBiTree(BiTree/CreateBiTree,僅知二叉樹的先序序列“abcdefg”不能唯一確定一棵二叉樹，,由二叉樹的先序和中序序列建樹,如果同時(shí)已知二叉樹的中序序列“cbdaegf”，則會(huì)如何？,二叉樹的先序序列,二叉樹的中序序列,左子樹,左子樹,右子樹,右子樹,根,根,abcdefg,cbdaegf,例如:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,voidCrtBT(BiTreeelse/CrtBT,T=(BiTNode*)malloc(sizeof(BiTNode);T-data=preps;if(k=is)T-Lchild=NULL;elseCrtBT(T-Lchild,pre,ino,ps+1,is,k-is);if(k=is+n-1)T-Rchild=NULL;elseCrtBT(T-Rchild,pre,ino,ps+(k-is)+1,k+1,n-(k-is)-1);,例題：,1、編寫遞歸算法：對(duì)于二叉樹中每一個(gè)元素值為x的結(jié)點(diǎn)，刪除以它為根的子樹，并釋放相應(yīng)的空間。,6.5線索二叉樹,何謂線索二叉樹？線索鏈表的遍歷算法如何建立線索鏈表？,一、何謂線索二叉樹？,遍歷二叉樹的結(jié)果是，求得結(jié)點(diǎn)的一個(gè)線性序列。,A,B,C,D,E,F,G,H,K,例如:,先序序列:ABCDEFGHK,中序序列:BDCAHGKFE,后序序列:DCBHKGFEA,指向該線性序列中的“前驅(qū)”和“后繼”的指針，稱作“線索”,與其相應(yīng)的二叉樹，稱作“線索二叉樹”,包含“線索”的存儲(chǔ)結(jié)構(gòu)，稱作“線索鏈表”,ABCDEFGHK,D,C,B,E,對(duì)線索鏈表中結(jié)點(diǎn)的約定：,在二叉鏈表的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域，并作如下規(guī)定：,若該結(jié)點(diǎn)的左子樹不空，則Lchild域的指針指向其左子樹，且左標(biāo)志域的值為“指針Link”；否則，Lchild域的指針指向其“前驅(qū)”，且左標(biāo)志的值為“線索Thread”。,若該結(jié)點(diǎn)的右子樹不空，則rchild域的指針指向其右子樹，且右標(biāo)志域的值為“指針Link”；否則，rchild域的指針指向其“后繼”，且右標(biāo)志的值為“線索Thread”。,如此定義的二叉樹的存儲(chǔ)結(jié)構(gòu)稱作“線索鏈表”。,typedefstructBiThrNodTElemTypedata;structBiThrNode*lchild,*rchild;/左右指針PointerThrLTag,RTag;/左右標(biāo)志BiThrNode,*BiThrTree;,線索鏈表的類型描述：,typedefenumLink,ThreadPointerThr;/Link=0:指針，Thread=1:線索,線索二叉樹的頭結(jié)點(diǎn),添加一個(gè)頭結(jié)點(diǎn)，并令其lchild域的指針指向二叉樹的根結(jié)點(diǎn)，其rchild域的指針指向中序遍歷時(shí)訪問的最后一個(gè)結(jié)點(diǎn)；反之，令二叉樹中序序列中的第一個(gè)結(jié)點(diǎn)的lchild域指針和最后一個(gè)結(jié)點(diǎn)rchild域的指針均指向頭結(jié)點(diǎn)。這好比為二叉樹建立了一個(gè)雙向線索鏈表。(參考教材P133）,二、線索鏈表的遍歷算法:,for(p=firstNode(T);p;p=Succ(p)Visit(p);,由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡化了遍歷的算法。,例如:對(duì)中序線索化鏈表的遍歷算法,中序遍歷的第一個(gè)結(jié)點(diǎn)？,在中序線索化鏈表中結(jié)點(diǎn)的后繼？,左子樹上處于“最左下”（沒有左子樹）的結(jié)點(diǎn)。,若無右子樹，則為后繼線索所指結(jié)點(diǎn)；,否則為對(duì)其右子樹進(jìn)行中序遍歷時(shí)訪問的第一個(gè)結(jié)點(diǎn)。,voidInOrderTraverse_Thr(BiThrTreeT,void(*Visit)(TElemTypee)p=T-lchild;/p指向根結(jié)點(diǎn)while(p!=T)/空樹或遍歷結(jié)束時(shí)，p=Twhile(p-LTag=Link)p=p-lchild;/第一個(gè)結(jié)點(diǎn)if(!Visit(p-data)returnERROR;while(p-RTag=Thread/p進(jìn)至其右子樹根/InOrderTraverse_Thr,在中序遍歷過程中修改結(jié)點(diǎn)的左、右指針域，以保存當(dāng)前訪問結(jié)點(diǎn)的“前驅(qū)”和“后繼”信息。遍歷過程中，附設(shè)指針pre,并始終保持指針pre指向當(dāng)前訪問的、指針p所指結(jié)點(diǎn)的前驅(qū)。,三、如何建立線索鏈表？,voidInThreading(BiThrTreep)if(p)/對(duì)以p為根的非空二叉樹進(jìn)行線索化InThreading(p-lchild);/左子樹線索化if(!p-lchild)/建前驅(qū)線索p-LTag=Thread;p-lchild=pre;if(!pre-rchild)/建后繼線索pre-RTag=Thread;pre-rchild=p;pre=p;/保持pre指向p的前驅(qū)InThreading(p-rchild);/右子樹線索化/if/InThreading,StatusInOrderThreading(BiThrTree/InOrderThreading,if(!T)Thrt-lchild=Thrt;elseThrt-lchild=T;pre=Thrt;InThreading(T);pre-rchild=Thrt;/處理最后一個(gè)結(jié)點(diǎn)pre-RTag=Thread;Thrt-rchild=pre;,課堂練習(xí),習(xí)題集：P436.56,6.6樹和森林的表示方法,6.6.1樹的三種存儲(chǔ)結(jié)構(gòu),一、雙親表示法,二、孩子鏈表表示法,三、樹的二叉鏈表(孩子-兄弟）存儲(chǔ)表示法,A,B,C,D,E,F,G,0A-11B02C03D04E25F26G5,r=0n=6,dataparent,一、雙親表示法:,typedefstructPTNodeElemdata;intparent;/雙親位置域PTNode;,dataparent,#defineMAX_TREE_SIZE100,結(jié)點(diǎn)結(jié)構(gòu):,C語言的類型描述:,typedefstructPTNodenodesMAX_TREE_SIZE;intr,n;/根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)PTree;,樹結(jié)構(gòu):,A,B,C,D,E,F,G,0A-11B02C03D04E25F26G4,r=0n=6,datafirstchild,123,45,6,二、孩子鏈表表示法:,typedefstructCTNodeintchild;structCTNode*next;*ChildPtr;,孩子結(jié)點(diǎn)結(jié)構(gòu):,childnext,C語言的類型描述:,typedefstructElemdata;ChildPtrfirstchild;/孩子鏈的頭指針CTBox;,雙親結(jié)點(diǎn)結(jié)構(gòu),datafirstchild,typedefstructCTBoxnodesMAX_TREE_SIZE;intn,r;/結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置CTree;,樹結(jié)構(gòu):,A,B,C,D,E,F,G,ABCEDFG,root,ABCEDFG,三、樹的二叉鏈表(孩子-兄弟）存儲(chǔ)表示法,typedefstructCSNodeElemdata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;,C語言的類型描述:,結(jié)點(diǎn)結(jié)構(gòu):,firstchilddatanextsibling,6.6.2森林和二叉樹的轉(zhuǎn)換,設(shè)森林F=(T1,T2,Tn);T1=(root，t11,t12,t1m);,二叉樹B=(LBT,Node(root),RBT);,由于二叉樹可以用二叉鏈表表示，為了使一般樹也能用二叉鏈表表示，必須找出樹與二叉樹之間的關(guān)系。這樣，給定一棵樹，可以找到唯一的一棵二叉樹與之對(duì)應(yīng)。方法：對(duì)每個(gè)孩子進(jìn)行從左到右的排序；在兄弟之間加一條連線；對(duì)每個(gè)結(jié)點(diǎn)，除了左孩子外，去除其與其余孩子之間的聯(lián)系；以根結(jié)點(diǎn)為軸心，將整個(gè)樹順時(shí)針轉(zhuǎn)45度。,1、將樹轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為:,樹轉(zhuǎn)換為二叉樹,2、由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為:,若F=，則B=；否則，由ROOT(T1)對(duì)應(yīng)得到Node(root)；由(t11,t12,t1m)對(duì)應(yīng)得到LBT；由(T2,T3,Tn)對(duì)應(yīng)得到RBT。,森林轉(zhuǎn)換為二叉樹,3、由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為：,若B=，則F=；否則，由Node(root)對(duì)應(yīng)得到ROOT(T1)；由LBT對(duì)應(yīng)得到(t11,t12,，t1m)；由RBT對(duì)應(yīng)得到(T2,T3,Tn)。,將二叉樹轉(zhuǎn)換成樹或森林的方法如下：1.若某結(jié)點(diǎn)是其雙親的左孩子,則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來;2.刪除原二叉樹中所有的雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線.3.整理步驟1、2所得到的樹或森林,使結(jié)構(gòu)層次分明.,將二叉樹轉(zhuǎn)換為樹或森林的另一種描述：,將二叉樹轉(zhuǎn)換為樹或森林,若某結(jié)點(diǎn)是其雙親的左孩子,則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來;,刪除原二叉樹中所有的雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線.,由此，樹的各種操作均可對(duì)應(yīng)二叉樹的操作來完成。,應(yīng)當(dāng)注意的是，和樹對(duì)應(yīng)的二叉樹，其左、右子樹的概念已改變?yōu)椋鹤笫呛⒆樱沂切值堋?6.7樹和森林的遍歷,一、樹的遍歷,二、森林的遍歷,三、樹的遍歷的應(yīng)用,樹的遍歷可有三條搜索路徑:,按層次遍歷:,先根(次序)遍歷:,后根(次序)遍歷:,若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。,若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)。,若樹不空，則自上而下自左至右訪問樹中每個(gè)結(jié)點(diǎn)。,ABCDEFGHIJK,先根遍歷時(shí)頂點(diǎn)的訪問次序：,ABEFCDGHIJK,后根遍歷時(shí)頂點(diǎn)的訪問次序：,EFBCIJKHGDA,層次遍歷時(shí)頂點(diǎn)的訪問次序：,ABCDEFGHIJK,BCDEFGHIJK,1森林中第一棵樹的根結(jié)點(diǎn)；,2森林中第一棵樹的子樹森林；,3森林中其它樹構(gòu)成的森林。,森林由三部分構(gòu)成：,若森林不空，則訪問森林中第一棵樹的根結(jié)點(diǎn)；先序遍歷森林中第一棵樹的子樹森林；先序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。,1.先序遍歷,森林的遍歷,即：依次從左至右對(duì)森林中的每一棵樹進(jìn)行先根遍歷。,中序遍歷,若森林不空，則中序遍歷森林中第一棵樹的子樹森林；訪問森林中第一棵樹的根結(jié)點(diǎn)；中序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。,即：依次從左至右對(duì)森林中的每一棵樹進(jìn)行后根遍歷。,樹的遍歷和二叉樹遍歷的對(duì)應(yīng)關(guān)系？,先根遍歷,后根遍歷,樹,二叉樹,森林,先序遍歷,先序遍歷,中序遍歷,后序遍歷,設(shè)樹的存儲(chǔ)結(jié)構(gòu)為孩子兄弟鏈表,typedefstructCSNodeElemdata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;,一、求樹的深度,二、輸出樹中所有從根到葉子的路徑,三、建樹的存儲(chǔ)結(jié)構(gòu),intTreeDepth(CSTreeT)if(!T)return0;elseh1=TreeDepth(T-firstchild);h2=TreeDepth(T-nextsibling);/TreeDepth,return(max(h1+1,h2);,一、求樹的深度的算法：,二、輸出樹中所有從根到葉子的路徑的算法:,ABCDEFGHIJK,例如：對(duì)左圖所示的樹，其輸出結(jié)果應(yīng)為：,ABEABFACADGHIADGHJADGHK,voidAllPath(BitreeT,Stack/if(T)/AllPath,/輸出二叉樹上從根到所有葉子結(jié)點(diǎn)的路徑,voidOutPath(BitreeT,Stack/while/OutPath,/輸出森林中所有從根到葉的路徑,三、建樹的存儲(chǔ)結(jié)構(gòu)的算法:,和二叉樹類似，不同的定義相應(yīng)有不同的算法。,假設(shè)以二元組(F，C)的形式自上而下、自左而右依次輸入樹的各邊，建立樹的孩子-兄弟鏈表。,A,B,C,D,E,F,G,例如:,對(duì)下列所示樹的輸入序列應(yīng)為:,(#,A)(A,B)(A,C)(A,D)(C,E)(C,F)(E,G),A,B,C,D,(#,A),(A,B),(A,C),(A,D),(C,E),可見，算法中需要一個(gè)隊(duì)列保存已建好的結(jié)點(diǎn)的指針。,voidCreatTree(CSTree/所建為根結(jié)點(diǎn)else/非根結(jié)點(diǎn)的情況/for/CreateTree,GetHead(Q,s);/取隊(duì)列頭元素(指針值)while(s-data!=fa)/查詢雙親結(jié)點(diǎn)DeQueue(Q,s);GetHead(Q,s);if(!(s-firstchild)s-firstchild=p;r=p;/鏈接第一個(gè)孩子結(jié)點(diǎn)elser-nextsibling=p;r=p;/鏈接其它孩子結(jié)點(diǎn),習(xí)題：,配套習(xí)題集P44：6.58、6.60、6.66,6.8哈夫曼樹與哈夫曼編碼,最優(yōu)樹的定義如何構(gòu)造最優(yōu)樹前綴編碼,一、最優(yōu)樹的定義,樹的路徑長度定義為：樹中每個(gè)結(jié)點(diǎn)的路徑長度之和。,結(jié)點(diǎn)的路徑長度定義為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支的數(shù)目。,1,2,4,5,3,6,7,PL=0+1+1+2+2+2+2=10,樹的路徑長度用PL表示。,1,2,4,5,C,6,7,PL=0+1+1+2+2+3+3=12,樹的帶權(quán)路徑長度定義為：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和WPL(T)=wkLk(對(duì)所有葉子結(jié)點(diǎn))。其中：Wk為樹中每個(gè)葉子結(jié)點(diǎn)的權(quán)；Lk為每個(gè)葉子結(jié)點(diǎn)到根的路徑長度。,例如：,2,79,7,5,4,9,2,WPL(T)=72+52+23+43+92=60,WPL(T)=74+94+53+42+21=89,5,4,最優(yōu)樹,在所有含n個(gè)葉子結(jié)點(diǎn)、并帶相同權(quán)值的m叉樹中，必存在一棵其帶權(quán)路徑長度取最小值的樹，稱為“最優(yōu)樹”。,2,79,7,5,4,9,2,WPL(T)=72+52+23+43+92=60,WPL(T)=74+94+53+42+21=89,5,4,由原始數(shù)據(jù)生成森林根據(jù)給定的n個(gè)權(quán)值w1,w2,wn，構(gòu)造n棵二叉樹的集合F=T1,T2,Tn，其中每棵二叉樹中均只含一個(gè)帶權(quán)值為wi的根結(jié)點(diǎn),其左、右子樹為空樹；,二、如何構(gòu)造最優(yōu)樹,(1),(哈夫曼算法)以二叉樹為例：,在F中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和；,(2),從F中刪去這兩棵樹，同時(shí)加入剛生成的新樹；,重復(fù)(2)和(3)兩步，直至F中只含一棵樹為止。,(3),(4),例：給定權(quán)值7，5，2，4，構(gòu)造哈夫曼樹。,9,例:已知權(quán)值W=5,6,2,9,7,構(gòu)造哈夫曼樹。,5,6,2,7,5,2,7,6,9,7,6,7,13,9,5,2,7,6,7,13,9,5,2,7,9,5,2,7,16,6,7,13,29,0,0,0,0,1,1,1,1,00,01,10,110,111,三、哈夫曼樹的應(yīng)用,1、判定樹在解決某些判定問題時(shí)，利用哈夫曼樹可以得到最佳判定算法。例1將學(xué)生百分成績按分?jǐn)?shù)段分級(jí)的程序。若學(xué)生成績分布是均勻的，可用圖（a)二叉樹結(jié)構(gòu)來實(shí)現(xiàn)。,輸入10000個(gè)數(shù)據(jù)，則需進(jìn)行31500次比較。,(b),學(xué)生成績分布不是均勻的情況：,以比例數(shù)為權(quán)構(gòu)造一棵哈夫曼樹，如（b)判斷樹所示。,再將每一比較框的兩次比較改為一次，可得到（c)判定樹。,輸入10000個(gè)數(shù)據(jù)，僅需進(jìn)行22000次比較。,2、前綴編碼,“前綴編碼”指的是，任何一個(gè)字符的編碼都不是同一字符集中另一個(gè)字符的編碼的前綴。,例如：對(duì)A、B、C、D四個(gè)字符進(jìn)行以下編碼：A0B10C110D111,例：下列編碼中屬前綴碼的是(),A)1,