文檔2.5樹與二叉樹

2.5樹與二叉樹樹型結構是一類很重要的非線性數(shù)據(jù)結構，在這類結構中，元素結點之間存在明顯的分支和層次關系。2.5.1樹的定義及其存儲結構樹的定義和術語樹是由n個(n≥0)結點組成的有限集合T，其中有且僅有一個結點稱為根結點(root)，其余結點可以分為m(m≥0)個互不相交的有限集合T1，T2，…，Tm,其中每個集合Ti本身又是一棵樹，稱為根結點root的子樹。當n=0時稱為空樹。這是一個遞歸的描述，即在買偶數(shù)樹時又用到樹本身這個術語。圖2.33所示為一棵樹，A為根結點，期于結點分為三個不相交的子集T1，T2，T3，它們均為根結點A下的三棵樹，而這三棵樹本身也是樹。用二元組關系來定義樹為Tree=(T,R)數(shù)據(jù)結構樹(Tree)由數(shù)據(jù)元素集合T及各種R組成，其中T是具有相同類型的數(shù)據(jù)元素集合T={x1，x2，…，xn}。若T為空集(T=?),則R=?，稱為空樹，否則R是T上某個二元關系H的集合，即R={H}。H的描述如下：(1)在T中存在唯一的稱為根的元素root，它在H關系下無前趨。(2)若T-{root}≠?，則存在m個子集T1，T2，…，Tm(m>0),對任意的j≠k(1≤j,k≤m)，有Tj∩Tk=?，則存在唯一的數(shù)據(jù)元素xi∈Ti(1≤i≤m)，滿足<root,xi>∈H。(3)對應于T1，T2，…，Tm，H-{<root，x1>，…，<root，xm>}，滿足<root，xi>∈H1，H2，…，Hm(m>0)，對任意的j≠k(1≤j,k≤m)有Hj∩Hk=?，Hj滿足在Ti上的二元關系。因此(Ti，{Hi})也是一棵符合本定義的樹，稱為根root的子樹。樹結構中常用的術語有.結點(node):表示樹中的元素。.結點的度(degree)：結點擁有的子樹數(shù)，如圖2.33中結點A的度為3，C的度為1。一棵樹中最大的結點度數(shù)為這棵數(shù)的度，圖2.33中樹的度為3。.葉子(leaf):度為零的結點，又稱為端結點。.孩子(child)：除根結點外，每個結點都是其前趨結點的孩子。.雙親(parents)：對應上述孩子結點的上層結點稱為這些結點的雙親。例如圖2.33中，D是A的孩子，A是D，C，B的雙親。.兄弟(sibling):同一雙親的孩子。.結點的層次(level)：從根結點開始算起，根為第一層，根的直接后繼結點為第二層，其余個層次依次類推。例如圖2.33中共分為4層。.深度(depth)：樹中結點的最大層次數(shù)。圖2.33中樹的深度為4。.森林(forest)：是m(m≥0)棵互不相交的樹的集合。.有序樹：樹中結點在同層中按從左至右有序排列、不能互換的稱為有序樹，反之稱為無序樹。樹的存儲結構僅討論鏈式存儲結構。異構型：節(jié)省存儲空間，運算不便。同構型：運算方便，浪費空間。假設有一棵具有n個結點的k叉樹，則有nk個指針域，其中有用的指針域為n-1個，因此空鏈域個數(shù)為nk-(n-1)=n(k-1)+1個。不同的k值進行比較:完全二叉樹如果一棵n個結點的二叉樹，按與滿二叉樹相同的編號方式對結點進行編號，若樹中n個結點和滿二叉樹1～n編號完全一致，則稱該樹為完全二叉樹，如圖2.37(a)所示；而圖2.37(b)就不是完全二叉樹。平衡二叉樹平衡二叉樹或者是一棵空樹，或者是具有下列性質的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。圖2.38(a)為平衡二叉樹，(b)為不平衡二叉樹。一般樹轉換為二叉樹在兄弟結點之間加一連線；對每個結點，除了與它的第一個孩子保持聯(lián)系外，去除與其它孩子的聯(lián)系；以樹根為軸心，將整棵樹順時針旋轉45°。2.5.3二叉樹的遍歷遍歷是指遵循某條搜索路線，依次訪問某數(shù)據(jù)結構中的全部結點，而且每個結點只被訪問一次。遍歷二叉樹的定義DLR，LDR，LRD，DRL，RDL，RLD六種遍歷形式。若規(guī)定先左后右，則歸并成下述三種形式：DLR：先序遍歷LDR：中序遍歷LRD：后序遍歷以圖2.40中的二叉樹為例，三種遍歷結果為：先序：ABCDEFG中序：CBDAEGF后序：CDBGFEA遍歷算法PROORDER(p)//先序遍歷//1.if(p<>nil)then2.{whrit(data(p));//訪問根結點//3.PROORDER(Lchild(p));//遍歷左子樹//4.PROORDER(Rchild(p));//遍歷右子樹//5.returnBRBRARARARARARERFRABCDEFGINORDER(p)//中序遍歷//1.if(p<>nil)then2.{INORDER(L,child(p));//遍歷左子樹//3.while(data(p));//訪問根結點//4.INORDER(R,child(p));//遍歷右子樹//5．ReturnBRBRARARARARARERFRCBDAEGFPOSTORDER(p)//后序遍歷//1.if(p<>nil)then2.{POSTORDER(L,child(p));//遍歷左子樹//3.POSTORDER(R,child(p));//遍歷右子樹//4.while(data(p));//訪問根結點//5．ReturnCOUNTLEFT(p,count)//p指向根結點,count為計數(shù)器，初值為01.if(p<>nil)then2.{if(Lchild(p))=nil}and(Rchild=nil)3.thencount←count+14.COUNTLEFT(L,child(p));5.COUNTLEFT(R,child(p));6.return4二叉樹的應用二叉排序樹(1)定義二叉排序樹或是空樹，或是具有下述性質的二叉樹：其左子樹上所有結點的數(shù)據(jù)均小于根結點的數(shù)據(jù)值；右子樹上所有結點的數(shù)據(jù)值均大于或等于根結點的數(shù)據(jù)值。左子樹和右子樹又各是一棵二叉排序樹。圖2.41所示就是一棵二叉排序樹。在二叉排序樹中，若按中序遍歷就可以得到由小到大的有序序列，如圖2.41中的二叉排序樹，中序遍歷可得到有序序列{2,3,4,8,9,9,10,13,15,18,21}。(2)二叉排序樹的生成二叉排序樹是一種動態(tài)表結構，即二叉排序樹的生成過程是不斷地向二叉排序樹中插入新的結點。對任意的一組數(shù)據(jù)元素序列{R1，R2，…，Rn}，要生成一棵二叉排序樹的過程為：<1>令R1為二叉排序樹的根結點。<2>若R2<R1，令R2為R1的左子樹的根結點；否則R2為R1的右子樹的根結點。<3>R3，…，Rn結點的插入方法同上。二叉排序樹插入算法如下：INSERBET(t,b)//將數(shù)值b插入根結點指針為t的二叉排序樹中,此函數(shù)返回值為指向根結點t的指針//1.if(t=nil)then//生成一個新結點,其數(shù)值域為b//2.{GETNODE(t);data(t)←;Lchild(t)←nil;Rchild(t)←nil}3.elseif(b<data(t)then{Lchild(t)←INSERTBET(Lchild(t),b)}//插入左子樹//5.else6.{Rchild(t)←INSERTBET(Rchild(t),b)}//插入右子樹//7.return(t)圖2.42所示為序列{10，18，3，8，12，2，7，3}構成一棵二叉排序樹的過程。(3)刪除二叉排序樹上的結點刪除二叉排序樹上的一個結點，也就是要在已排好序的序列中刪除一個元素，因此要求刪除一個結點后二叉樹仍然是一棵二叉排序樹。刪除二叉排序樹上結點過程較插入過程復雜，按照被刪除結點在二叉排序樹中的位置，可以有以下幾種情況：<1>被刪除結點是葉子結點，則刪除后不會影響整個二叉排序樹的結構，因此只需修改它雙親結點的指針即可。<2>被刪除結點P只有左子樹PL或右子樹PR，此時只要將左子樹或右子樹直接成為其雙親結點F的左或右子樹即可，見圖2.43(a)所示。<3>若被刪除結點P的左右子樹均為非空。這是要循著P的左子樹的根結點C，向右一直找到結點S，要求S的右子樹為空。然后將S的左子樹改為結點Q的右子樹，將S結點的數(shù)據(jù)域值取代P結點的數(shù)據(jù)域值，刪除前后如圖2.43(b)(c)所示。<4>若被刪除的結點為二叉排序樹的根結點，則刪除后應修改根結點指針。算法如下：DELNODE(t,p,f)//t為根結點指針,p指向被刪除結點,f指向其雙親,當p=t時f=nil//1.fag←0//fag=0需要修改F結點指針,fag=1不需修改//2.if(Lchild(p)=nil)thens←Rchild(p)//p為葉子或左子樹為空//3.elseif(Rchild(p)=nil)thens←Lchild(p)//p的右子樹為空//4.else{q←p;s←Lchild(p)//p的左右子樹均為空//5.while(Rchild(s)<>nil)do6.{q←s;s←Rchild(p)}尋找s結點//7.if(q=p)thenLchild(q)←Lchild(s)elseRchild(q)←Lchild(s).data(p)←datea(s)//s值代替p值//10.RET(s);fag←1//釋放s結點//}11.if(fag=0)then//修改F結點指針//{if(f=nil)thent←s//被刪除結點為根結點//13.elseif(Lchild(f)=p)thenLchild(f)←s14.elseRchild(f)←s15.RET(p)//釋放結點p//16.return哈夫曼樹哈夫曼樹又稱最優(yōu)樹，是一類帶權路徑最短的樹。(1)樹的路徑長度從樹中一個結點到另一個結點之間的分支數(shù)目稱為這對結點之間的路徑長度。樹的路徑長度是從樹根到每個結點的路徑長度之和。路徑長度用PL表示，圖2.44中(a)(b)兩棵樹的路徑長度分別為：PL=0+1+2+2+3+4+5=17；PL=0+1+1+2×4+3=13。在任何二叉樹中，都存在如下情況：路徑為0的結點至多只有1個；路徑為1的結點至多只有2個；……路徑為k的結點至多只有2k個。因此，n個結點的二叉樹路徑長度滿足log21+log22+log23+log214+log215+log216+log217+log28+…………=0+1+1+2+2+2+2+3+…………從上述關系可知，具有最小路徑長度的二叉樹為完全二叉樹。(2)樹的帶權路徑長度結點帶權路徑長度為該結點到樹根之間的路徑長度與結點上權值的乘積。樹的帶權路徑長度為樹中葉子結點的帶權路徑長度之和，記作其中wk為樹中每個葉子結點的權值，lk為每個葉子結點到根結點的路徑長度。WPL最小的二叉樹稱作最優(yōu)二叉樹或哈夫曼樹。例如圖2.45中的三棵二叉樹，都有4個葉子結點a，b，c，d，分別具有權值7，5，2，4，它們帶權路徑長度分別為：(a)WPL=7*2+5*2+2*2+4*2=36(b)WPL=7*3+5*3+2*1+4*2=46(c)WPL=7*1+5*2+2*3+4*3=35其中以(c)為最小，可以驗證(c)為哈夫曼樹。(3)哈夫曼樹的構造原則：權值越大的葉子離根結點的距離越近。<1>由給定的n個權值{w1，w2，…，wn}構成n棵二叉樹的集合F={T1，T2，…，Tn}，其中每棵二叉樹只有一個權值為wi的根結點，如圖2.46(a)所示。<2>在F中選取兩棵根結點權值最小的樹作為左右子樹構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和，如圖2.46(b)所示。<3>將新的二叉樹假如F中，去除原兩棵根結點權值最小的樹。<4>重復<2>,<3>兩步驟，直到F中只含一棵樹為止。這棵樹就是哈夫曼樹，如圖2.46(d)所示。在計算機上實現(xiàn)上述算法，首先要確定存儲結構，由于哈夫曼樹中沒有度為1的結點，因此一棵有n個葉子結點的哈夫曼樹共有2n-1個結點。結點采用數(shù)組型鏈表結構每個結點由4個數(shù)據(jù)域組成，即date:存放結點權值Lchild:左指針Rchild:右指針Prnt:雙親指針算法如下：HUFFMAN(n,Lchild,Rchild,data,Prnt,w)//w[1:n]存放n個權值,Lchild[1:m],Rchild[1:m],data[1:m],Prnt[1:m],m=2n-1//1.fori=1tondata[i]←w[i];Lchild(i)←0;Rchild(i)←0//初始化//3.end(i)4.fori=1to(2*n-1)Prnt[i]←0//初始化//5.end(i)6．fork