計算機數(shù)據(jù)結(jié)構(gòu)大學(xué)課件第六章.ppt

第六章樹和二叉樹,2019年11月24日星期日,第2頁,【學(xué)習(xí)目標(biāo)】,1領(lǐng)會樹和二叉樹的類型定義2熟記二叉樹的主要特性3熟練掌握二叉樹的各種遍歷算法4理解二叉樹的線索化5熟練掌握二叉樹和樹的各種存儲結(jié)構(gòu)6掌握建立赫夫曼的方法。,2019年11月24日星期日,第3頁,6.1樹的定義和基本術(shù)語,樹是由n（n0）個結(jié)點組成的有限集合。若n=0，稱為空樹；若n0，則：（1）其中必有一個稱為根（root）的特定結(jié)點，它沒有直接前驅(qū)，但有零個或多個直接后繼；（2）除根結(jié)點以外的其它n-1結(jié)點可以劃分為m（m0）個互不相交的有限集合T0，T1，Tm-1，每個集合Ti（i=0,1,m-1）又是一棵樹，稱為根的子樹，每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有0個或多個直接后繼。由此可知，樹的定義是一個遞歸的定義，即樹的定義中又用到了樹的概念。,2019年11月24日星期日,第4頁,ADTTree數(shù)據(jù)對象D：,D是具有相同特性的數(shù)據(jù)元素的集合。,若D為空集，則稱為空樹。否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；(2)當(dāng)n1時，其余結(jié)點可分為m(m0)個互不相交的有限集T1,T2,Tm，其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。,數(shù)據(jù)關(guān)系R：,2019年11月24日星期日,第5頁,Root(T)/求樹的根結(jié)點,基本操作,Value(T,cur_e)/求當(dāng)前結(jié)點的元素值,Parent(T,cur_e)/求當(dāng)前結(jié)點的雙親結(jié)點,LeftChild(T,cur_e)/求當(dāng)前結(jié)點的最左孩子,RightSibling(T,cur_e)/求當(dāng)前結(jié)點的右兄弟,TreeEmpty(T)/判定樹是否為空樹,TreeDepth(T)/求樹的深度,TraverseTree(T,Visit()/遍歷,2019年11月24日星期日,第6頁,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();,基本操作,2019年11月24日星期日,第17頁,InitBiTree(,2019年11月24日星期日,第18頁,ClearBiTree(,2019年11月24日星期日,第19頁,6.2.2二叉樹的性質(zhì),性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點。(i1),2019年11月24日星期日,第21頁,性質(zhì)2：深度為k的二叉樹上至多含2k-1個結(jié)點（k1）。,2019年11月24日星期日,第22頁,性質(zhì)3：對任何一棵二叉樹，若它含有n0個葉子結(jié)點、n2個度為2的結(jié)點，則必存在關(guān)系式：n0=n2+1。,證明：,設(shè)二叉樹上結(jié)點總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)(即邊數(shù))b=n1+2n2而n=b+1=b=n-1=n0+n1+n2-1由此，n0=n2+1。,2019年11月24日星期日,第23頁,兩類特殊的二叉樹：,滿二叉樹：指的是深度為k且含有2k-1個結(jié)點的二叉樹。,完全二叉樹：樹中所含的n個結(jié)點和滿二叉樹中編號為1至n的結(jié)點一一對應(yīng)。,2019年11月24日星期日,第24頁,性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為log2n+1。,證明：,設(shè)完全二叉樹的深度為k則根據(jù)第二條性質(zhì)得2k-1-1n2k1或2k-1n2k即k-1log2nn，則該結(jié)點無右孩子結(jié)點，否則，編號為2i+1的結(jié)點為其右孩子結(jié)點。,2019年11月24日星期日,第26頁,6.2.3二叉樹的存儲結(jié)構(gòu),2019年11月24日星期日,第27頁,#defineMAX_TREE_SIZE100typedefTElemTypeSqBiTreeMAX_TREE_SIZE;SqBiTreebt;,一、二叉樹的順序存儲表示,2019年11月24日星期日,第28頁,例如:,A,B,C,D,E,F,ABDCEF,012345678910111213,1,4,0,13,2,6,將一棵二叉樹按完全二叉樹順序存放到一個一維數(shù)組中，若該二叉樹為非完全二叉樹，則必須將相應(yīng)位置空出來，使存放的結(jié)果符合完全二叉樹形狀。,2019年11月24日星期日,第29頁,二、二叉樹的鏈?zhǔn)酱鎯Ρ硎?對于一棵二叉樹,若采用順序存貯時,當(dāng)它為完全二叉樹時,比較方便,若為非完全二叉樹,將會浪費大量存貯存貯單元。最壞的非完全二叉樹是全部只有右分支,設(shè)高度為K,則需占用2K-1個存貯單元,而實際只需k個存儲單元。因此，對于非完全二叉樹，宜采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。,2019年11月24日星期日,第30頁,A,D,E,B,C,F,root,lchilddatarchild,結(jié)點結(jié)構(gòu):,1.二叉鏈表,2019年11月24日星期日,第31頁,typedefstructBiTNodeTElemTypedata;structBiTNode*lchild,*rchild;BiTNode,*BiTree;,C語言的類型描述如下:,2019年11月24日星期日,第32頁,StatusCreateBiTree(BiTree/CreateBiTree,2019年11月24日星期日,第33頁,A,D,E,B,C,F,root,2三叉鏈表,parentlchilddatarchild,結(jié)點結(jié)構(gòu):,2019年11月24日星期日,第34頁,typedefstructTriTNodeTElemTypedata;structTriTNode*lchild,*rchild;structTriTNode*parent;TriTNode,*TriTree;,parentlchilddatarchild,結(jié)點結(jié)構(gòu):,C語言的類型描述如下:,2019年11月24日星期日,第35頁,dataparent,結(jié)點結(jié)構(gòu):,3雙親鏈表,LRTag,2019年11月24日星期日,第36頁,typedefstructBPTNodeTElemTypedata;int*parent;charLRTag;BPTNodetypedefstructBPTreeBPTNodenodesMAX_TREE_SIZE;intnum_node;introot;BPTree,2019年11月24日星期日,第37頁,6.3遍歷二叉樹和線索二叉樹,2019年11月24日星期日,第38頁,順著某一條搜索路徑巡訪二叉樹中的結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。,2019年11月24日星期日,第39頁,“遍歷”是任何類型均有的操作，對線性結(jié)構(gòu)而言，只有一條搜索路徑(因為每個結(jié)點均只有一個后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)，,每個結(jié)點有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。,2019年11月24日星期日,第40頁,遍歷,先序的遍歷算法,中序的遍歷算法,后序的遍歷算法,2019年11月24日星期日,第41頁,若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。,先序的遍歷算法：,2019年11月24日星期日,第42頁,若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點；（3）中序遍歷右子樹。,中序的遍歷算法：,2019年11月24日星期日,第43頁,若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點。,后序的遍歷算法：,2019年11月24日星期日,第44頁,最早提出遍歷問題是對存儲在計算機中的表達式求值。例如：（a+b*c）-d/e。該表達式用二叉樹表示如下圖所示。當(dāng)對此二叉樹進行先序、中序、后序遍歷時，便可獲得表達式的前綴、中綴、后綴書寫形式：前綴：-+a*bc/de中綴：a+b*c-d/e后綴：abc*+de/-其中中綴形式是算術(shù)表達式的通常形式，只是沒有括號。前綴表達式稱為波蘭表達式。算術(shù)表達式的后綴表達式被稱作逆波蘭表達式。在計算機內(nèi)，使用后綴表達式易于求值。,圖算術(shù)式的二叉樹表示,2019年11月24日星期日,第45頁,voidPreordertraverse(BiTreeT,void(*visit)(TElemTypePreordertraverse(T-rchild,visit,遍歷算法的遞歸描述,2019年11月24日星期日,第46頁,遍歷算法的非遞歸描述,利用一個一維數(shù)組作為棧，來存儲二叉鏈表中結(jié)點。,先序遍歷二叉樹的非遞歸算法,2019年11月24日星期日,第47頁,算法如下：voidpreorder1(bitree*root)bitree*p,*s100;inttop=0;p=root;while(p!=NULL)|(top0)while(p!=NULL)printf(“%c”,p-data);s+top=p;p=p-lchild;p=stop-;p=p-rchild;,【算法】先序遍歷二叉樹的非遞歸算法,2019年11月24日星期日,6.3.2線索二叉樹,2019年11月24日星期日,第49頁,對線索鏈表中結(jié)點的約定：,在二叉鏈表的結(jié)點中增加兩個標(biāo)志域，并作如下規(guī)定：,若該結(jié)點的左子樹不空，則Lchild域的指針指向其左子樹，且左標(biāo)志域的值為“指針Link”；否則，Lchild域的指針指向其“前驅(qū)”，且左標(biāo)志的值為“線索Thread”。,2019年11月24日星期日,第50頁,若該結(jié)點的右子樹不空，則rchild域的指針指向其右子樹，且右標(biāo)志域的值為“指針Link”；否則，rchild域的指針指向其“后繼”，且右標(biāo)志的值為“線索Thread”。,如此定義的二叉樹的存儲結(jié)構(gòu)稱作“線索鏈表”。,2019年11月24日星期日,第51頁,typedefstructBiThrNodTElemTypedata;structBiThrNode*lchild,*rchild;PointerThrLTag,RTag;BiThrNode,*BiThrTree;,線索鏈表的類型描述：,typedefenumLink,ThreadPointerThr;/Link=0，Thread=1:,2019年11月24日星期日,第52頁,1）在中序線索樹中找前驅(qū)結(jié)點根據(jù)線索二叉樹的基本概念和存儲結(jié)構(gòu)可知，對于結(jié)點p，當(dāng)p-Ltag=1時，p-LChild指向p的前驅(qū)。當(dāng)p-Ltag=0時，p-LChild指向p的左孩子。由中序遍歷的規(guī)律可知，作為根p的前驅(qū)結(jié)點，它是中序遍歷p的左子樹時訪問的最后一個結(jié)點,2019年11月24日星期日,第53頁,2）在中序線索樹中找結(jié)點后繼對于結(jié)點p，若要找其后繼結(jié)點，當(dāng)p-Rtag=1時，p-RChild即為p的后繼結(jié)點；當(dāng)p-Rtag=0時，說明p有右子樹，此時p的中序后繼結(jié)點即為其右子樹的最左下端的結(jié)點。,2019年11月24日星期日,第54頁,線索鏈表的遍歷算法:,在線索二叉樹中，由于有線索存在，在某些情況下可以方便地找到指定結(jié)點在某種遍歷序列中的直接前驅(qū)或直接后繼。此外，在線索二叉樹上進行某種遍歷比在一般的二叉樹上進行這種遍歷要容易得多，不需要設(shè)置堆棧，且算法十分簡潔。,2019年11月24日星期日,第55頁,voidInOrderTraverse_Thr(BiThrTreeT,void(*Visit)(TElemTypee)p=T-lchild;while(p!=T)while(p-LTag=Link)p=p-lchild;if(!Visit(p-data)returnERROR;while(p-RTag=Thread/InOrderTraverse_Thr,2019年11月24日星期日,第56頁,在中序遍歷過程中修改結(jié)點的左、右指針域，以保存當(dāng)前訪問結(jié)點的“前驅(qū)”和“后繼”信息。遍歷過程中，附設(shè)指針pre,并始終保持指針pre指向當(dāng)前訪問的、指針p所指結(jié)點的前驅(qū)。,如何建立線索鏈表？,2019年11月24日星期日,第57頁,voidInThreading(BiThrTreep)if(p)InThreading(p-lchild);if(!p-lchild)p-LTag=Thread;p-lchild=pre;if(!pre-rchild)pre-RTag=Thread;pre-rchild=p;pre=p;InThreading(p-rchild);/if/InThreading,2019年11月24日星期日,第58頁,StatusInOrderThreading(BiThrTree/InOrderThreading,2019年11月24日星期日,第59頁,if(!T)Thrt-lchild=Thrt;elseThrt-lchild=T;pre=Thrt;InThreading(T);pre-rchild=Thrt;pre-RTag=Thread;Thrt-rchild=pre;,2019年11月24日星期日,第60頁,6.4樹和森林,2019年11月24日星期日,第61頁,6.4.1樹的存儲結(jié)構(gòu),一、雙親表示法,二、孩子鏈表表示法,三、樹的二叉鏈表表示法,2019年11月24日星期日,第62頁,A,B,C,D,E,F,G,0A-11B02C03D04E25F26G5,r=0n=6,dataparent,一、雙親表示法:,2019年11月24日星期日,第63頁,typedefstructPTNodeElemdata;intparent;PTNode;,dataparent,#defineMAX_TREE_SIZE100,C語言的類型描述:,2019年11月24日星期日,第64頁,typedefstructPTNodenodesMAX_TREE_SIZE;intr,n;/根結(jié)點的位置和結(jié)點個數(shù)PTree;,2019年11月24日星期日,第65頁,A,B,C,D,E,F,G,0A-11B02C03D04E25F26G5,r=0n=6,datafirstchild,123,45,6,二、孩子鏈表表示法:,-1000224,2019年11月24日星期日,第66頁,typedefstructCTNodeintchild;structCTNode*next;*ChildPtr;,childnext,C語言的類型描述:,2019年11月24日星期日,第67頁,typedefstructElemdata;ChildPtrfirstchild;CTBox;,結(jié)點,datafirstchild,2019年11月24日星期日,第68頁,typedefstructCTBoxnodesMAX_TREE_SIZE;intn,r;CTree;,2019年11月24日星期日,第69頁,A,B,C,D,E,F,G,ABCEDFG,root,三、樹的二叉鏈表存儲表示法,2019年11月24日星期日,第70頁,typedefstructCSNodeElemdata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;,C語言的類型描述:,firstchilddatanextsibling,6.4.2森林與二叉樹的轉(zhuǎn)換,2019年11月24日星期日,第72頁,圖樹與二叉樹的對應(yīng),2019年11月24日星期日,第73頁,1.森林轉(zhuǎn)換為二叉樹森林是若干棵樹的集合。樹可以轉(zhuǎn)換為二叉樹，森林同樣也可以轉(zhuǎn)換為二叉樹。因此，森林也可以方便地用孩子兄弟鏈表表示。,2019年11月24日星期日,第74頁,圖森林轉(zhuǎn)換為二叉樹的過程,2019年11月24日星期日,第75頁,將森林F看作樹的有序集F=T1，T2，,TN，它對應(yīng)的二叉樹為B（F）：（1）若N=0，則B（F）為空。（2）若N0，二叉樹B（F）的根為森林中第一棵樹T1的根；B（F）的左子樹為B（T11，T1m），其中T11，T1m是T1的子樹森林；B（F）的右子樹是B（T2，TN）。,2019年11月24日星期日,第76頁,2.二叉樹轉(zhuǎn)換為森林森林可以轉(zhuǎn)換為二叉樹，森林轉(zhuǎn)換后的二叉樹，其根結(jié)點有右孩子。,2019年11月24日星期日,第77頁,同樣，我們可以用遞歸的方法描述上述轉(zhuǎn)換過程。若B是一棵二叉樹，T是B的根結(jié)點，L是B的左子樹，R為B的右子樹，且B對應(yīng)的森林F（B）中含有的n棵樹為T1,T2,Tn，則有：（1）B為空，則F（B）為空的森林（n0）。（2）B非空，則F（B）中第一棵樹T1的根為二叉樹B的根T；T1中根結(jié)點的子樹森林由B的左子樹L轉(zhuǎn)換而成，即F（L）=T11,T1m；B的右子樹R轉(zhuǎn)換為F（B）中其余樹組成的森林，即F(R)T2,T3,Tn。,2019年11月24日星期日,第78頁,6.4.3樹和森林的遍歷,2019年11月24日星期日,第79頁,一、樹的遍歷,二、森林的遍歷,2019年11月24日星期日,第80頁,樹的遍歷可有三條搜索路徑:,按層次遍歷:,先根(次序)遍歷:,后根(次序)遍歷:,若樹不空，則先訪問根結(jié)點，然后依次先根遍歷各棵子樹。,若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點。,若樹不空，則自上而下自左至右訪問樹中每個結(jié)點。,2019年11月24日星期日,第81頁,1.先序遍歷,森林的遍歷,若森林不空，則訪問森林中第一棵樹的根結(jié)點；先序遍歷森林中第一棵樹的子樹森林；先序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。,2019年11月24日星期日,第82頁,中序遍歷,若森林不空，則中序遍歷森林中第一棵樹的子樹森林；訪問森林中第一棵樹的根結(jié)點；中序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。,即：依次從左至右對森林中的每一棵樹進行后根遍歷。,2019年11月24日星期日,第83頁,6.6哈夫曼樹及其應(yīng)用,2019年11月24日星期日,第84頁,6.6.1赫夫曼樹,赫夫曼(Huffman)樹又稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹，有著廣泛的應(yīng)用。,結(jié)點路徑：從樹中一個結(jié)點到另一個結(jié)點的之間的分支構(gòu)成這兩個結(jié)點之間的路徑。路徑長度：結(jié)點路徑上的分支數(shù)目稱為路徑長度。樹的路徑長度：從樹根到每一個結(jié)點的路徑長度之和。,基本概念,結(jié)點的帶權(quán)路徑長度：從該結(jié)點的到樹的根結(jié)點之間的路徑長度與結(jié)點的權(quán)(值)的乘積。權(quán)(值)：各種開銷、代價、頻度等的抽象稱呼。樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，記做：WPL=w1l1+w2l2+wnln=wi*li(i=1,2,n)其中：n為葉子結(jié)點的個數(shù)；wi為第i個結(jié)點的權(quán)值；li為第i個結(jié)點的路徑長度。,基本概念,Huffman樹：具有n個葉子結(jié)點(每個結(jié)點的權(quán)值為wi)的二叉樹不止一棵，但在所有的這些二叉樹中，必定存在一棵WPL值最小的樹，稱這棵樹為Huffman樹(或稱最優(yōu)樹)。在許多判定問題時，利用Huffman樹可以得到最佳判斷算法。,基本概念,2019年11月24日星期日,第88頁,WPL=72+52+23+43+92=60,2019年11月24日星期日,第89頁,根據(jù)給定的n個權(quán)值w1,w2,wn，構(gòu)造n棵二叉樹的集合F=T1,T2,Tn，其中每棵二叉樹中均只含一個帶權(quán)值為wi的根結(jié)點，其左、右子樹為空樹；,二、如何構(gòu)造最優(yōu)樹,(1),(赫夫曼算法)以二叉樹為例：,2019年11月24日星期日,第90頁,在F中選取其根結(jié)點的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點的權(quán)值為其左、右子樹根結(jié)點的權(quán)值之和；,(2)