




已閱讀5頁(yè),還剩148頁(yè)未讀, 繼續(xù)免費(fèi)閱讀
版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
第六章樹(shù)和二叉樹(shù),教學(xué)目的和要求,1、熟練掌握二叉樹(shù)的結(jié)構(gòu)特點(diǎn),了解相應(yīng)的證明。2、熟悉二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍。3、掌握二叉樹(shù)遍歷的遞歸與非遞歸算法。4、掌握二叉線索樹(shù)的相關(guān)算法。5、熟悉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及特點(diǎn),掌握樹(shù)和森林與二叉樹(shù)的方法。6、了解最優(yōu)樹(shù)的特性,掌握最優(yōu)樹(shù)和哈夫曼編碼的方法。,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ì),樹(shù)形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個(gè)主要問(wèn)題,樹(shù)形結(jié)構(gòu),全校學(xué)生檔案管理的組織方式,樹(shù)形結(jié)構(gòu)結(jié)點(diǎn)間具有分層次的連接關(guān)系,6.1樹(shù)的類型定義,6.2二叉樹(shù)的類型定義,6.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu),6.4二叉樹(shù)的遍歷,6.5線索二叉樹(shù),6.6樹(shù)和森林的表示方法,6.7樹(shù)和森林的遍歷,6.8哈夫曼樹(shù)與哈夫曼編碼,6.1樹(shù)的類型定義,數(shù)據(jù)對(duì)象D:,D是具有相同特性的數(shù)據(jù)元素的集合。,若D為空集,則稱為空樹(shù)。否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root;(2)當(dāng)n1時(shí),其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的有限集T1,T2,Tm,其中每一棵子集本身又是一棵符合本定義的樹(shù),稱為根root的子樹(shù)。,數(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,樹(shù)根,例如:,基本操作:,查找類,插入類,刪除類,Root(T)/求樹(shù)的根結(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)/判定樹(shù)是否為空樹(shù),TreeDepth(T)/求樹(shù)的深度,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(,二叉樹(shù)的重要特性,性質(zhì)1:在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)。(i1),用歸納法證明:歸納基:歸納假設(shè):歸納證明:,i=1層時(shí),只有一個(gè)根結(jié)點(diǎn):2i-1=20=1;,假設(shè)對(duì)所有的j,1ji,命題成立;,二叉樹(shù)上每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù),則第i層的結(jié)點(diǎn)數(shù)=2i-22=2i-1。,性質(zhì)2:深度為k的二叉樹(shù)上至多含2k-1個(gè)結(jié)點(diǎn)(k1)。,證明:,基于上一條性質(zhì),深度為k的二叉樹(shù)上的結(jié)點(diǎn)數(shù)至多為20+21+2k-1=2k-1。,性質(zhì)3:對(duì)任何一棵二叉樹(shù),若它含有n0個(gè)葉子結(jié)點(diǎn)、n2個(gè)度為2的結(jié)點(diǎn),則必存在關(guān)系式:n0=n2+1。,證明:,設(shè)二叉樹(shù)上結(jié)點(diǎn)總數(shù)n=n0+n1+n2又二叉樹(shù)上分支總數(shù)b=n1+2n2而b=n-1=n0+n1+n2-1由此,n0=n2+1。,兩類特殊的二叉樹(shù):,滿二叉樹(shù):指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。,完全二叉樹(shù):樹(shù)中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹(shù)中編號(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)的完全二叉樹(shù)的深度為log2n+1。,證明:,設(shè)完全二叉樹(shù)的深度為k則根據(jù)第二條性質(zhì)得2k-1nn,則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn),否則,編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。,(),例題1:若一樹(shù)二叉共有1001個(gè)結(jié)點(diǎn),且無(wú)度為1的結(jié)點(diǎn),則葉子結(jié)點(diǎn)的個(gè)數(shù)為()。例題2:將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下,從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào),根結(jié)點(diǎn)的編號(hào)為1,則編號(hào)為49的結(jié)點(diǎn)的孩子編號(hào)為()。,6.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu),二、二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示,一、二叉樹(shù)的順序存儲(chǔ)表示,#defineMAX_TREE_SIZE100/二叉樹(shù)的最大結(jié)點(diǎn)數(shù)typedefTElemTypeSqBiTreeMAX_TREE_SIZE;/0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)SqBiTreebt;,一、二叉樹(shù)的順序存儲(chǔ)表示,例如:,A,B,C,D,E,F,ABDCEF,012345678910111213,1,4,0,13,2,6,順序存儲(chǔ)結(jié)構(gòu)僅適用于完全二叉樹(shù)!,二、二叉樹(shù)的鏈?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語(yǔ)言的類型描述如下:,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語(yǔ)言的類型描述如下:,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/樹(shù)結(jié)構(gòu)BPTNodenodesMAX_TREE_SIZE;intnum_node;/結(jié)點(diǎn)數(shù)目introot;/根結(jié)點(diǎn)的位置BPTree,6.4二叉樹(shù)的遍歷,一、問(wèn)題的提出,二、先左后右的遍歷算法,三、算法的遞歸描述,四、中序遍歷算法的非遞歸描述,五、遍歷算法的應(yīng)用舉例,如何順著某一條搜索路徑巡訪二叉樹(shù)中的結(jié)點(diǎn),使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次,而且僅被訪問(wèn)一次。,一、問(wèn)題的提出,“訪問(wèn)”的含義可以很廣,如:輸出結(jié)點(diǎn)的信息等。,“遍歷”是任何類型均有的操作,對(duì)線性結(jié)構(gòu)而言,只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼),故不需要另加討論。而二叉樹(shù)是非線性結(jié)構(gòu),,每個(gè)結(jié)點(diǎn)有兩個(gè)后繼,則存在如何遍歷即按什么樣的搜索路徑遍歷的問(wèn)題。,對(duì)“二叉樹(shù)”而言,可以有三條搜索路徑:,1先上后下的按層次遍歷;2先左(子樹(shù))后右(子樹(shù))的遍歷;3先右(子樹(shù))后左(子樹(shù))的遍歷。,二、先左后右的遍歷算法,先序(根)的遍歷算法,中序(根)的遍歷算法,后序(根)的遍歷算法,若二叉樹(shù)為空樹(shù),則空操作;否則,(1)訪問(wèn)根結(jié)點(diǎn);(2)先序遍歷左子樹(shù);(3)先序遍歷右子樹(shù)。,先序(根)的遍歷算法:,若二叉樹(shù)為空樹(shù),則空操作;否則,(1)中序遍歷左子樹(shù);(2)訪問(wèn)根結(jié)點(diǎn);(3)中序遍歷右子樹(shù)。,中序(根)的遍歷算法:,若二叉樹(shù)為空樹(shù),則空操作;否則,(1)后序遍歷左子樹(shù);(2)后序遍歷右子樹(shù);(3)訪問(wèn)根結(jié)點(diǎn)。,后序(根)的遍歷算法:,課堂提問(wèn):,有以下結(jié)構(gòu)的二叉樹(shù)寫(xiě)出其先序、中序和后序遍歷的序列,三、算法的遞歸描述,voidPreorder(BiTreeT,void(*visit)(TElemType/遍歷右子樹(shù),四、中序遍歷算法的非遞歸描述,BiTNode*GoFarLeft(BiTreeT,Stack*S)if(!T)returnNULL;while(T-lchild)Push(S,T);T=T-lchild;returnT;,voidInorder_I(BiTreeT,void(*visit)(TelemType/??毡砻鞅闅v結(jié)束/while/Inorder_I,五、遍歷算法的應(yīng)用舉例,1、統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)(先序遍歷),2、求二叉樹(shù)的深度(后序遍歷),3、復(fù)制二叉樹(shù)(后序遍歷),4、建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu),1、統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù),算法基本思想:,先序(或中序或后序)遍歷二叉樹(shù),在遍歷過(guò)程中查找葉子結(jié)點(diǎn),并計(jì)數(shù)。由此,需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù),并將算法中“訪問(wèn)結(jié)點(diǎn)”的操作改為:若是葉子,則計(jì)數(shù)器增1。,voidCountLeaf(BiTreeT,int/if/CountLeaf,2、求二叉樹(shù)的深度(后序遍歷),算法基本思想:,從二叉樹(shù)深度的定義可知,二叉樹(shù)的深度應(yīng)為其左、右子樹(shù)深度的最大值加1。由此,需先分別求得左、右子樹(shù)的深度,算法中“訪問(wèn)結(jié)點(diǎn)”的操作為:求得左、右子樹(shù)深度的最大值,然后加1。,首先分析二叉樹(shù)的深度和它的左、右子樹(shù)深度之間的關(guān)系。,intDepth(BiTreeT)/返回二叉樹(shù)的深度if(!T)depthval=0;elsedepthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeftdepthRight?depthLeft:depthRight);returndepthval;,3、復(fù)制二叉樹(shù),其基本操作為:生成一個(gè)結(jié)點(diǎn)。,根元素,T,左子樹(shù),右子樹(shù),根元素,NEWT,左子樹(shù),右子樹(shù),左子樹(shù),右子樹(shù),(后序遍歷),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è)二叉樹(shù)的結(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ù)制左子樹(shù)elsenewlptr=NULL;if(T-rchild)newrptr=CopyTree(T-rchild);/復(fù)制右子樹(shù)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,例如:下列二叉樹(shù)的復(fù)制過(guò)程如下:,newT,4、建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu),不同的定義方法相應(yīng)有不同的存儲(chǔ)結(jié)構(gòu)的建立算法,以字符串“A!”表示,以字符串的形式根左子樹(shù)右子樹(shù)定義一棵二叉樹(shù),例如:,A,B,C,D,以字符“!”表示,A(B(!,C(!,!),D(!,!),空樹(shù),只含一個(gè)根結(jié)點(diǎn)的二叉樹(shù),A,以下列字符串表示,StatusCreateBiTree(BiTree/CreateBiTree,僅知二叉樹(shù)的先序序列“abcdefg”不能唯一確定一棵二叉樹(shù),,由二叉樹(shù)的先序和中序序列建樹(shù),如果同時(shí)已知二叉樹(shù)的中序序列“cbdaegf”,則會(huì)如何?,二叉樹(shù)的先序序列,二叉樹(shù)的中序序列,左子樹(shù),左子樹(shù),右子樹(shù),右子樹(shù),根,根,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、編寫(xiě)遞歸算法:對(duì)于二叉樹(shù)中每一個(gè)元素值為x的結(jié)點(diǎn),刪除以它為根的子樹(shù),并釋放相應(yīng)的空間。,6.5線索二叉樹(shù),何謂線索二叉樹(shù)?線索鏈表的遍歷算法如何建立線索鏈表?,一、何謂線索二叉樹(shù)?,遍歷二叉樹(shù)的結(jié)果是,求得結(jié)點(diǎn)的一個(gè)線性序列。,A,B,C,D,E,F,G,H,K,例如:,先序序列:ABCDEFGHK,中序序列:BDCAHGKFE,后序序列:DCBHKGFEA,指向該線性序列中的“前驅(qū)”和“后繼”的指針,稱作“線索”,與其相應(yīng)的二叉樹(shù),稱作“線索二叉樹(shù)”,包含“線索”的存儲(chǔ)結(jié)構(gòu),稱作“線索鏈表”,ABCDEFGHK,D,C,B,E,對(duì)線索鏈表中結(jié)點(diǎn)的約定:,在二叉鏈表的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域,并作如下規(guī)定:,若該結(jié)點(diǎn)的左子樹(shù)不空,則Lchild域的指針指向其左子樹(shù),且左標(biāo)志域的值為“指針Link”;否則,Lchild域的指針指向其“前驅(qū)”,且左標(biāo)志的值為“線索Thread”。,若該結(jié)點(diǎn)的右子樹(shù)不空,則rchild域的指針指向其右子樹(shù),且右標(biāo)志域的值為“指針Link”;否則,rchild域的指針指向其“后繼”,且右標(biāo)志的值為“線索Thread”。,如此定義的二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)稱作“線索鏈表”。,typedefstructBiThrNodTElemTypedata;structBiThrNode*lchild,*rchild;/左右指針PointerThrLTag,RTag;/左右標(biāo)志BiThrNode,*BiThrTree;,線索鏈表的類型描述:,typedefenumLink,ThreadPointerThr;/Link=0:指針,Thread=1:線索,線索二叉樹(shù)的頭結(jié)點(diǎn),添加一個(gè)頭結(jié)點(diǎn),并令其lchild域的指針指向二叉樹(shù)的根結(jié)點(diǎn),其rchild域的指針指向中序遍歷時(shí)訪問(wèn)的最后一個(gè)結(jié)點(diǎn);反之,令二叉樹(shù)中序序列中的第一個(gè)結(jié)點(diǎn)的lchild域指針和最后一個(gè)結(jié)點(diǎn)rchild域的指針均指向頭結(jié)點(diǎn)。這好比為二叉樹(shù)建立了一個(gè)雙向線索鏈表。(參考教材P133),二、線索鏈表的遍歷算法:,for(p=firstNode(T);p;p=Succ(p)Visit(p);,由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息,從而簡(jiǎn)化了遍歷的算法。,例如:對(duì)中序線索化鏈表的遍歷算法,中序遍歷的第一個(gè)結(jié)點(diǎn)?,在中序線索化鏈表中結(jié)點(diǎn)的后繼?,左子樹(shù)上處于“最左下”(沒(méi)有左子樹(shù))的結(jié)點(diǎn)。,若無(wú)右子樹(shù),則為后繼線索所指結(jié)點(diǎn);,否則為對(duì)其右子樹(shù)進(jìn)行中序遍歷時(shí)訪問(wèn)的第一個(gè)結(jié)點(diǎn)。,voidInOrderTraverse_Thr(BiThrTreeT,void(*Visit)(TElemTypee)p=T-lchild;/p指向根結(jié)點(diǎn)while(p!=T)/空樹(shù)或遍歷結(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)至其右子樹(shù)根/InOrderTraverse_Thr,在中序遍歷過(guò)程中修改結(jié)點(diǎn)的左、右指針域,以保存當(dāng)前訪問(wèn)結(jié)點(diǎn)的“前驅(qū)”和“后繼”信息。遍歷過(guò)程中,附設(shè)指針pre,并始終保持指針pre指向當(dāng)前訪問(wèn)的、指針p所指結(jié)點(diǎn)的前驅(qū)。,三、如何建立線索鏈表?,voidInThreading(BiThrTreep)if(p)/對(duì)以p為根的非空二叉樹(shù)進(jìn)行線索化InThreading(p-lchild);/左子樹(shù)線索化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);/右子樹(shù)線索化/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樹(shù)和森林的表示方法,6.6.1樹(shù)的三種存儲(chǔ)結(jié)構(gòu),一、雙親表示法,二、孩子鏈表表示法,三、樹(shù)的二叉鏈表(孩子-兄弟)存儲(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語(yǔ)言的類型描述:,typedefstructPTNodenodesMAX_TREE_SIZE;intr,n;/根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)PTree;,樹(shù)結(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語(yǔ)言的類型描述:,typedefstructElemdata;ChildPtrfirstchild;/孩子鏈的頭指針CTBox;,雙親結(jié)點(diǎn)結(jié)構(gòu),datafirstchild,typedefstructCTBoxnodesMAX_TREE_SIZE;intn,r;/結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置CTree;,樹(shù)結(jié)構(gòu):,A,B,C,D,E,F,G,ABCEDFG,root,ABCEDFG,三、樹(shù)的二叉鏈表(孩子-兄弟)存儲(chǔ)表示法,typedefstructCSNodeElemdata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;,C語(yǔ)言的類型描述:,結(jié)點(diǎn)結(jié)構(gòu):,firstchilddatanextsibling,6.6.2森林和二叉樹(shù)的轉(zhuǎn)換,設(shè)森林F=(T1,T2,Tn);T1=(root,t11,t12,t1m);,二叉樹(shù)B=(LBT,Node(root),RBT);,由于二叉樹(shù)可以用二叉鏈表表示,為了使一般樹(shù)也能用二叉鏈表表示,必須找出樹(shù)與二叉樹(shù)之間的關(guān)系。這樣,給定一棵樹(shù),可以找到唯一的一棵二叉樹(shù)與之對(duì)應(yīng)。方法:對(duì)每個(gè)孩子進(jìn)行從左到右的排序;在兄弟之間加一條連線;對(duì)每個(gè)結(jié)點(diǎn),除了左孩子外,去除其與其余孩子之間的聯(lián)系;以根結(jié)點(diǎn)為軸心,將整個(gè)樹(shù)順時(shí)針轉(zhuǎn)45度。,1、將樹(shù)轉(zhuǎn)換成二叉樹(shù)的轉(zhuǎn)換規(guī)則為:,樹(shù)轉(zhuǎn)換為二叉樹(shù),2、由森林轉(zhuǎn)換成二叉樹(shù)的轉(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)換為二叉樹(shù),3、由二叉樹(shù)轉(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)。,將二叉樹(shù)轉(zhuǎn)換成樹(shù)或森林的方法如下:1.若某結(jié)點(diǎn)是其雙親的左孩子,則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來(lái);2.刪除原二叉樹(shù)中所有的雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線.3.整理步驟1、2所得到的樹(shù)或森林,使結(jié)構(gòu)層次分明.,將二叉樹(shù)轉(zhuǎn)換為樹(shù)或森林的另一種描述:,將二叉樹(shù)轉(zhuǎn)換為樹(shù)或森林,若某結(jié)點(diǎn)是其雙親的左孩子,則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來(lái);,刪除原二叉樹(shù)中所有的雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線.,由此,樹(shù)的各種操作均可對(duì)應(yīng)二叉樹(shù)的操作來(lái)完成。,應(yīng)當(dāng)注意的是,和樹(shù)對(duì)應(yīng)的二叉樹(shù),其左、右子樹(shù)的概念已改變?yōu)椋鹤笫呛⒆?,右是兄弟?6.7樹(shù)和森林的遍歷,一、樹(shù)的遍歷,二、森林的遍歷,三、樹(shù)的遍歷的應(yīng)用,樹(shù)的遍歷可有三條搜索路徑:,按層次遍歷:,先根(次序)遍歷:,后根(次序)遍歷:,若樹(shù)不空,則先訪問(wèn)根結(jié)點(diǎn),然后依次先根遍歷各棵子樹(shù)。,若樹(shù)不空,則先依次后根遍歷各棵子樹(shù),然后訪問(wèn)根結(jié)點(diǎn)。,若樹(shù)不空,則自上而下自左至右訪問(wèn)樹(shù)中每個(gè)結(jié)點(diǎn)。,ABCDEFGHIJK,先根遍歷時(shí)頂點(diǎn)的訪問(wèn)次序:,ABEFCDGHIJK,后根遍歷時(shí)頂點(diǎn)的訪問(wèn)次序:,EFBCIJKHGDA,層次遍歷時(shí)頂點(diǎn)的訪問(wèn)次序:,ABCDEFGHIJK,BCDEFGHIJK,1森林中第一棵樹(shù)的根結(jié)點(diǎn);,2森林中第一棵樹(shù)的子樹(shù)森林;,3森林中其它樹(shù)構(gòu)成的森林。,森林由三部分構(gòu)成:,若森林不空,則訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn);先序遍歷森林中第一棵樹(shù)的子樹(shù)森林;先序遍歷森林中(除第一棵樹(shù)之外)其余樹(shù)構(gòu)成的森林。,1.先序遍歷,森林的遍歷,即:依次從左至右對(duì)森林中的每一棵樹(shù)進(jìn)行先根遍歷。,中序遍歷,若森林不空,則中序遍歷森林中第一棵樹(shù)的子樹(shù)森林;訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn);中序遍歷森林中(除第一棵樹(shù)之外)其余樹(shù)構(gòu)成的森林。,即:依次從左至右對(duì)森林中的每一棵樹(shù)進(jìn)行后根遍歷。,樹(shù)的遍歷和二叉樹(shù)遍歷的對(duì)應(yīng)關(guān)系?,先根遍歷,后根遍歷,樹(shù),二叉樹(shù),森林,先序遍歷,先序遍歷,中序遍歷,后序遍歷,設(shè)樹(shù)的存儲(chǔ)結(jié)構(gòu)為孩子兄弟鏈表,typedefstructCSNodeElemdata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;,一、求樹(shù)的深度,二、輸出樹(shù)中所有從根到葉子的路徑,三、建樹(shù)的存儲(chǔ)結(jié)構(gòu),intTreeDepth(CSTreeT)if(!T)return0;elseh1=TreeDepth(T-firstchild);h2=TreeDepth(T-nextsibling);/TreeDepth,return(max(h1+1,h2);,一、求樹(shù)的深度的算法:,二、輸出樹(shù)中所有從根到葉子的路徑的算法:,ABCDEFGHIJK,例如:對(duì)左圖所示的樹(shù),其輸出結(jié)果應(yīng)為:,ABEABFACADGHIADGHJADGHK,voidAllPath(BitreeT,Stack/if(T)/AllPath,/輸出二叉樹(shù)上從根到所有葉子結(jié)點(diǎn)的路徑,voidOutPath(BitreeT,Stack/while/OutPath,/輸出森林中所有從根到葉的路徑,三、建樹(shù)的存儲(chǔ)結(jié)構(gòu)的算法:,和二叉樹(shù)類似,不同的定義相應(yīng)有不同的算法。,假設(shè)以二元組(F,C)的形式自上而下、自左而右依次輸入樹(shù)的各邊,建立樹(shù)的孩子-兄弟鏈表。,A,B,C,D,E,F,G,例如:,對(duì)下列所示樹(shù)的輸入序列應(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),可見(jiàn),算法中需要一個(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哈夫曼樹(shù)與哈夫曼編碼,最優(yōu)樹(shù)的定義如何構(gòu)造最優(yōu)樹(shù)前綴編碼,一、最優(yōu)樹(shù)的定義,樹(shù)的路徑長(zhǎng)度定義為:樹(shù)中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。,結(jié)點(diǎn)的路徑長(zhǎng)度定義為:從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支的數(shù)目。,1,2,4,5,3,6,7,PL=0+1+1+2+2+2+2=10,樹(shù)的路徑長(zhǎng)度用PL表示。,1,2,4,5,C,6,7,PL=0+1+1+2+2+3+3=12,樹(shù)的帶權(quán)路徑長(zhǎng)度定義為:樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和WPL(T)=wkLk(對(duì)所有葉子結(jié)點(diǎn))。其中:Wk為樹(shù)中每個(gè)葉子結(jié)點(diǎn)的權(quán);Lk為每個(gè)葉子結(jié)點(diǎn)到根的路徑長(zhǎng)度。,例如:,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)樹(shù),在所有含n個(gè)葉子結(jié)點(diǎn)、并帶相同權(quán)值的m叉樹(shù)中,必存在一棵其帶權(quán)路徑長(zhǎng)度取最小值的樹(shù),稱為“最優(yōu)樹(shù)”。,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棵二叉樹(shù)的集合F=T1,T2,Tn,其中每棵二叉樹(shù)中均只含一個(gè)帶權(quán)值為wi的根結(jié)點(diǎn),其左、右子樹(shù)為空樹(shù);,二、如何構(gòu)造最優(yōu)樹(shù),(1),(哈夫曼算法)以二叉樹(shù)為例:,在F中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹(shù),分別作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù),并置這棵新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和;,(2),從F中刪去這兩棵樹(shù),同時(shí)加入剛生成的新樹(shù);,重復(fù)(2)和(3)兩步,直至F中只含一棵樹(shù)為止。,(3),(4),例:給定權(quán)值7,5,2,4,構(gòu)造哈夫曼樹(shù)。,9,例:已知權(quán)值W=5,6,2,9,7,構(gòu)造哈夫曼樹(shù)。,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,三、哈夫曼樹(shù)的應(yīng)用,1、判定樹(shù)在解決某些判定問(wèn)題時(shí),利用哈夫曼樹(shù)可以得到最佳判定算法。例1將學(xué)生百分成績(jī)按分?jǐn)?shù)段分級(jí)的程序。若學(xué)生成績(jī)分布是均勻的,可用圖(a)二叉樹(shù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。,輸入10000個(gè)數(shù)據(jù),則需進(jìn)行31500次比較。,(b),學(xué)生成績(jī)分布不是均勻的情況:,以比例數(shù)為權(quán)構(gòu)造一棵哈夫曼樹(shù),如(b)判斷樹(shù)所示。,再將每一比較框的兩次比較改為一次,可得到(c)判定樹(shù)。,輸入10000個(gè)數(shù)據(jù),僅需進(jìn)行22000次比較。,2、前綴編碼,“前綴編碼”指的是,任何一個(gè)字符的編碼都不是同一字符集中另一個(gè)字符的編碼的前綴。,例如:對(duì)A、B、C、D四個(gè)字符進(jìn)行以下編碼:A0B10C110D111,例:下列編碼中屬前綴碼的是(),A)1,
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 智能制造與工業(yè)園區(qū)的協(xié)同發(fā)展路徑
- 公共服務(wù)體系優(yōu)化對(duì)經(jīng)開(kāi)區(qū)發(fā)展的影響
- A-Level化學(xué)(A2)2024-2025年度有機(jī)合成與分析化學(xué)模擬試卷(含解析)
- 2025年校園欺凌防治與干預(yù)制度:加強(qiáng)學(xué)生心理輔導(dǎo)隊(duì)伍建設(shè)
- 2025年注冊(cè)安全工程師化工安全模擬試卷:化工工藝與安全管理實(shí)戰(zhàn)技巧精講集
- 教聯(lián)體與社會(huì)資本的合作發(fā)展模式
- 推動(dòng)健美操創(chuàng)新的現(xiàn)狀及總體形勢(shì)
- 影視產(chǎn)業(yè)對(duì)區(qū)域人才培養(yǎng)與引進(jìn)的促進(jìn)作用
- 提高學(xué)生急救實(shí)踐能力的教學(xué)工具開(kāi)發(fā)
- 小麥抗白粉病育種的面臨的問(wèn)題、機(jī)遇與挑戰(zhàn)
- 休閑會(huì)所轉(zhuǎn)讓合同范本
- 骨科專業(yè)疾病臨床診療規(guī)范2025年版
- 上海市徐匯區(qū)2023-2024學(xué)年八年級(jí)下學(xué)期期末語(yǔ)文試題(解析版)
- 2025雅安事業(yè)單位筆試真題
- 血脂異常健康管理專題
- 端午節(jié)文化傳承課件
- 兒童輪狀病毒胃腸炎免疫預(yù)防專家共識(shí)(2024年版)解讀
- 經(jīng)濟(jì)學(xué)習(xí)題含參考答案解析
- 網(wǎng)絡(luò)微短劇的內(nèi)容創(chuàng)新策略及其傳播效果
- 檢驗(yàn)危急值在急危重病臨床應(yīng)用的專家共識(shí)
- BIM技術(shù)在建筑行業(yè)工程項(xiàng)目施工質(zhì)量改進(jìn)與持續(xù)改進(jìn)報(bào)告
評(píng)論
0/150
提交評(píng)論