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

第六章樹和二叉樹,2019年11月24日星期日,第2頁,【學(xué)習(xí)目標(biāo)】,1領(lǐng)會(huì)樹和二叉樹的類型定義2熟記二叉樹的主要特性3熟練掌握二叉樹的各種遍歷算法4理解二叉樹的線索化5熟練掌握二叉樹和樹的各種存儲(chǔ)結(jié)構(gòu)6掌握建立赫夫曼的方法。,2019年11月24日星期日,第3頁,6.1樹的定義和基本術(shù)語,樹是由n（n0）個(gè)結(jié)點(diǎn)組成的有限集合。若n=0，稱為空樹；若n0，則：（1）其中必有一個(gè)稱為根（root）的特定結(jié)點(diǎn)，它沒有直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼；（2）除根結(jié)點(diǎn)以外的其它n-1結(jié)點(diǎn)可以劃分為m（m0）個(gè)互不相交的有限集合T0，T1，Tm-1，每個(gè)集合Ti（i=0,1,m-1）又是一棵樹，稱為根的子樹，每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)直接后繼。由此可知，樹的定義是一個(gè)遞歸的定義，即樹的定義中又用到了樹的概念。,2019年11月24日星期日,第4頁,ADTTree數(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：,2019年11月24日星期日,第5頁,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()/遍歷,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個(gè)結(jié)點(diǎn)。(i1),2019年11月24日星期日,第21頁,性質(zhì)2：深度為k的二叉樹上至多含2k-1個(gè)結(jié)點(diǎn)（k1）。,2019年11月24日星期日,第22頁,性質(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ù)(即邊數(shù))b=n1+2n2而n=b+1=b=n-1=n0+n1+n2-1由此，n0=n2+1。,2019年11月24日星期日,第23頁,兩類特殊的二叉樹：,滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。,完全二叉樹：樹中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。,2019年11月24日星期日,第24頁,性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。,證明：,設(shè)完全二叉樹的深度為k則根據(jù)第二條性質(zhì)得2k-1-1n2k1或2k-1n2k即k-1log2nn，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)，否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。,2019年11月24日星期日,第26頁,6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu),2019年11月24日星期日,第27頁,#defineMAX_TREE_SIZE100typedefTElemTypeSqBiTreeMAX_TREE_SIZE;SqBiTreebt;,一、二叉樹的順序存儲(chǔ)表示,2019年11月24日星期日,第28頁,例如:,A,B,C,D,E,F,ABDCEF,012345678910111213,1,4,0,13,2,6,將一棵二叉樹按完全二叉樹順序存放到一個(gè)一維數(shù)組中，若該二叉樹為非完全二叉樹，則必須將相應(yīng)位置空出來，使存放的結(jié)果符合完全二叉樹形狀。,2019年11月24日星期日,第29頁,二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示,對(duì)于一棵二叉樹,若采用順序存貯時(shí),當(dāng)它為完全二叉樹時(shí),比較方便,若為非完全二叉樹,將會(huì)浪費(fèi)大量存貯存貯單元。最壞的非完全二叉樹是全部只有右分支,設(shè)高度為K,則需占用2K-1個(gè)存貯單元,而實(shí)際只需k個(gè)存儲(chǔ)單元。因此，對(duì)于非完全二叉樹，宜采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。,2019年11月24日星期日,第30頁,A,D,E,B,C,F,root,lchilddatarchild,結(jié)點(diǎn)結(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é)點(diǎn)結(jié)構(gòu):,2019年11月24日星期日,第34頁,typedefstructTriTNodeTElemTypedata;structTriTNode*lchild,*rchild;structTriTNode*parent;TriTNode,*TriTree;,parentlchilddatarchild,結(jié)點(diǎn)結(jié)構(gòu):,C語言的類型描述如下:,2019年11月24日星期日,第35頁,dataparent,結(jié)點(diǎn)結(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é)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。,2019年11月24日星期日,第39頁,“遍歷”是任何類型均有的操作，對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)，,每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。,2019年11月24日星期日,第40頁,遍歷,先序的遍歷算法,中序的遍歷算法,后序的遍歷算法,2019年11月24日星期日,第41頁,若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹。,先序的遍歷算法：,2019年11月24日星期日,第42頁,若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹。,中序的遍歷算法：,2019年11月24日星期日,第43頁,若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點(diǎn)。,后序的遍歷算法：,2019年11月24日星期日,第44頁,最早提出遍歷問題是對(duì)存儲(chǔ)在計(jì)算機(jī)中的表達(dá)式求值。例如：（a+b*c）-d/e。該表達(dá)式用二叉樹表示如下圖所示。當(dāng)對(duì)此二叉樹進(jìn)行先序、中序、后序遍歷時(shí)，便可獲得表達(dá)式的前綴、中綴、后綴書寫形式：前綴：-+a*bc/de中綴：a+b*c-d/e后綴：abc*+de/-其中中綴形式是算術(shù)表達(dá)式的通常形式，只是沒有括號(hào)。前綴表達(dá)式稱為波蘭表達(dá)式。算術(shù)表達(dá)式的后綴表達(dá)式被稱作逆波蘭表達(dá)式。在計(jì)算機(jī)內(nèi)，使用后綴表達(dá)式易于求值。,圖算術(shù)式的二叉樹表示,2019年11月24日星期日,第45頁,voidPreordertraverse(BiTreeT,void(*visit)(TElemTypePreordertraverse(T-rchild,visit,遍歷算法的遞歸描述,2019年11月24日星期日,第46頁,遍歷算法的非遞歸描述,利用一個(gè)一維數(shù)組作為棧，來存儲(chǔ)二叉鏈表中結(jié)點(diǎn)。,先序遍歷二叉樹的非遞歸算法,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頁,對(duì)線索鏈表中結(jié)點(diǎn)的約定：,在二叉鏈表的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域，并作如下規(guī)定：,若該結(jié)點(diǎn)的左子樹不空，則Lchild域的指針指向其左子樹，且左標(biāo)志域的值為“指針Link”；否則，Lchild域的指針指向其“前驅(qū)”，且左標(biāo)志的值為“線索Thread”。,2019年11月24日星期日,第50頁,若該結(jié)點(diǎn)的右子樹不空，則rchild域的指針指向其右子樹，且右標(biāo)志域的值為“指針Link”；否則，rchild域的指針指向其“后繼”，且右標(biāo)志的值為“線索Thread”。,如此定義的二叉樹的存儲(chǔ)結(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é)點(diǎn)根據(jù)線索二叉樹的基本概念和存儲(chǔ)結(jié)構(gòu)可知，對(duì)于結(jié)點(diǎn)p，當(dāng)p-Ltag=1時(shí)，p-LChild指向p的前驅(qū)。當(dāng)p-Ltag=0時(shí)，p-LChild指向p的左孩子。由中序遍歷的規(guī)律可知，作為根p的前驅(qū)結(jié)點(diǎn)，它是中序遍歷p的左子樹時(shí)訪問的最后一個(gè)結(jié)點(diǎn),2019年11月24日星期日,第53頁,2）在中序線索樹中找結(jié)點(diǎn)后繼對(duì)于結(jié)點(diǎn)p，若要找其后繼結(jié)點(diǎn)，當(dāng)p-Rtag=1時(shí)，p-RChild即為p的后繼結(jié)點(diǎn)；當(dāng)p-Rtag=0時(shí)，說明p有右子樹，此時(shí)p的中序后繼結(jié)點(diǎn)即為其右子樹的最左下端的結(jié)點(diǎn)。,2019年11月24日星期日,第54頁,線索鏈表的遍歷算法:,在線索二叉樹中，由于有線索存在，在某些情況下可以方便地找到指定結(jié)點(diǎn)在某種遍歷序列中的直接前驅(qū)或直接后繼。此外，在線索二叉樹上進(jìn)行某種遍歷比在一般的二叉樹上進(jìn)行這種遍歷要容易得多，不需要設(shè)置堆棧，且算法十分簡(jiǎn)潔。,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é)點(diǎn)的左、右指針域，以保存當(dāng)前訪問結(jié)點(diǎn)的“前驅(qū)”和“后繼”信息。遍歷過程中，附設(shè)指針pre,并始終保持指針pre指向當(dāng)前訪問的、指針p所指結(jié)點(diǎn)的前驅(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樹的存儲(chǔ)結(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é)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(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é)點(diǎn),datafirstchild,2019年11月24日星期日,第68頁,typedefstructCTBoxnodesMAX_TREE_SIZE;intn,r;CTree;,2019年11月24日星期日,第69頁,A,B,C,D,E,F,G,ABCEDFG,root,三、樹的二叉鏈表存儲(chǔ)表示法,2019年11月24日星期日,第70頁,typedefstructCSNodeElemdata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;,C語言的類型描述:,firstchilddatanextsibling,6.4.2森林與二叉樹的轉(zhuǎn)換,2019年11月24日星期日,第72頁,圖樹與二叉樹的對(duì)應(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，它對(duì)應(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é)點(diǎn)有右孩子。,2019年11月24日星期日,第77頁,同樣，我們可以用遞歸的方法描述上述轉(zhuǎn)換過程。若B是一棵二叉樹，T是B的根結(jié)點(diǎn)，L是B的左子樹，R為B的右子樹，且B對(duì)應(yīng)的森林F（B）中含有的n棵樹為T1,T2,Tn，則有：（1）B為空，則F（B）為空的森林（n0）。（2）B非空，則F（B）中第一棵樹T1的根為二叉樹B的根T；T1中根結(jié)點(diǎn)的子樹森林由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é)點(diǎn)，然后依次先根遍歷各棵子樹。,若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)。,若樹不空，則自上而下自左至右訪問樹中每個(gè)結(jié)點(diǎn)。,2019年11月24日星期日,第81頁,1.先序遍歷,森林的遍歷,若森林不空，則訪問森林中第一棵樹的根結(jié)點(diǎn)；先序遍歷森林中第一棵樹的子樹森林；先序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。,2019年11月24日星期日,第82頁,中序遍歷,若森林不空，則中序遍歷森林中第一棵樹的子樹森林；訪問森林中第一棵樹的根結(jié)點(diǎn)；中序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。,即：依次從左至右對(duì)森林中的每一棵樹進(jìn)行后根遍歷。,2019年11月24日星期日,第83頁,6.6哈夫曼樹及其應(yīng)用,2019年11月24日星期日,第84頁,6.6.1赫夫曼樹,赫夫曼(Huffman)樹又稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹，有著廣泛的應(yīng)用。,結(jié)點(diǎn)路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。路徑長度：結(jié)點(diǎn)路徑上的分支數(shù)目稱為路徑長度。樹的路徑長度：從樹根到每一個(gè)結(jié)點(diǎn)的路徑長度之和。,基本概念,結(jié)點(diǎn)的帶權(quán)路徑長度：從該結(jié)點(diǎn)的到樹的根結(jié)點(diǎn)之間的路徑長度與結(jié)點(diǎn)的權(quán)(值)的乘積。權(quán)(值)：各種開銷、代價(jià)、頻度等的抽象稱呼。樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，記做：WPL=w1l1+w2l2+wnln=wi*li(i=1,2,n)其中：n為葉子結(jié)點(diǎn)的個(gè)數(shù)；wi為第i個(gè)結(jié)點(diǎn)的權(quán)值；li為第i個(gè)結(jié)點(diǎn)的路徑長度。,基本概念,Huffman樹：具有n個(gè)葉子結(jié)點(diǎn)(每個(gè)結(jié)點(diǎn)的權(quán)值為wi)的二叉樹不止一棵，但在所有的這些二叉樹中，必定存在一棵WPL值最小的樹，稱這棵樹為Huffman樹(或稱最優(yōu)樹)。在許多判定問題時(shí)，利用Huffman樹可以得到最佳判斷算法。,基本概念,2019年11月24日星期日,第88頁,WPL=72+52+23+43+92=60,2019年11月24日星期日,第89頁,根據(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),(赫夫曼算法)以二叉樹為例：,2019年11月24日星期日,第90頁,在F中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和；,(2)