計算機數據結構大學課件第六章.ppt

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