深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017樹與二叉樹演示文檔
《深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017樹與二叉樹演示文檔》由會員分享,可在線閱讀,更多相關(guān)《深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017樹與二叉樹演示文檔(73頁珍藏版)》請在裝配圖網(wǎng)上搜索。
.,第六章樹與二叉樹,數(shù)據(jù)結(jié)構(gòu),.,一、樹的定義(Tree),2,樹是有n(n0)個結(jié)點的有限集合。如果 n=0,稱為空樹;如果 n0,稱為非空樹,對于非空樹,有且僅有一個特定的稱為根(Root)的節(jié)點(無直接前驅(qū))如果 n1,則除根以外的其它結(jié)點劃分為 m (m0)個互不相交的有限集 T1, T2 , Tm,其中每個集合本身又是一棵樹,并且稱為根的子樹(SubTree)。每個結(jié)點都有唯一的直接前驅(qū),但可能有多個后繼,第一節(jié)樹的概念與基本術(shù)語,.,一、樹的定義(舉例),3,其中:A是根;其余結(jié)點分成三個互不相交的子集,T1=B,E,F,K,L; T2=C,G; T3=D,H,I,J,M,T1,T2,T3都是根A的子樹,且本身也是一棵樹,A,只有根結(jié)點的樹,有13個結(jié)點的樹,第一節(jié)樹的概念與基本術(shù)語,.,二、樹的基本術(shù)語,4,第一節(jié)樹的概念與基本術(shù)語,結(jié)點:包含一個數(shù)據(jù)元素及若干指向其子樹的分支結(jié)點的度:結(jié)點擁有的子樹數(shù)樹的度:樹中各結(jié)點的度的最大值葉結(jié)點:度為0的結(jié)點,也稱終端結(jié)點分支結(jié)點:度不為0的結(jié)點包括根結(jié)點,也稱非終端結(jié)點。,.,二、樹的基本術(shù)語,5,第一節(jié)樹的概念與基本術(shù)語,孩子:結(jié)點的子樹的根直接后繼,可能有多個雙親:孩子的直接前驅(qū)最多只能有一個兄弟:同一雙親的孩子子孫:以某結(jié)點為根的樹中的所有結(jié)點祖先:從根到該結(jié)點所經(jīng)分支上的所有結(jié)點,.,二、樹的基本術(shù)語,6,第一節(jié)樹的概念與基本術(shù)語,層次:根結(jié)點為第一層,其孩子為第二層,依此類推深度:樹中結(jié)點的最大層次森林:互不相交的樹的集合。對樹中每個結(jié)點而言,其子樹的集合即為森林.有序樹:樹中各結(jié)點的子樹按照一定次序從左向右安排,相對次序不能改變,.,一、二叉樹(Binary Tree),7,第二節(jié)二叉樹,二叉樹是一種特殊的樹每個結(jié)點最多有棵子樹二叉樹的子樹有左右之分,二叉樹的五種基本形態(tài),.,二、二叉樹性質(zhì),8,第二節(jié)二叉樹,在二叉樹的第i層上至多有2i-1個結(jié)點證明:1.i=1, 只有一個根節(jié)點,因此2i-1=20=12.設(shè)第i-1層上,以上性質(zhì)成立,即第i-1層至多有2(i-1)-1結(jié)點。由二叉樹的定義可知,任何結(jié)點的度小于2,因此,第i層上的結(jié)點數(shù)最多為第i-1層上的兩倍,即2*2i-2=2i-1,.,三、二叉樹性質(zhì),9,第二節(jié)二叉樹,深度為k的二叉樹至多有2k-1個結(jié)點證明:1.由性質(zhì),已知第i層上結(jié)點數(shù)最多為2i-1 k2. 2i-1 = 2k-1 i=1,.,四、二叉樹性質(zhì),10,第二節(jié)二叉樹,非空二叉樹上葉結(jié)點數(shù)等于雙分支結(jié)點數(shù)加一,即n0=n2+1證明:1.設(shè)n1為度為1的結(jié)點,則總結(jié)點數(shù)= n0+n1+n22.設(shè)B為二叉樹的分支數(shù),除根結(jié)點外,每個結(jié)點有且只有一個分支,因此n=B+13.每個分支皆由度為1或2的結(jié)點發(fā)出,B=n1+2n24.n=B+1=(n1+2n2)+1 = n0+n1+n2,因此 n0=n2+1,.,五、滿二叉樹,11,第二節(jié)二叉樹,一個深度為k且有2k-1個結(jié)點的二叉樹每層上的結(jié)點數(shù)都是最大數(shù)可以自上而下、自左至右連續(xù)編號,.,六、完全二叉樹,12,第二節(jié)二叉樹,當(dāng)且僅當(dāng)每一個結(jié)點都與深度相同的滿二叉樹中編號從1到n的結(jié)點一一對應(yīng)的二叉樹葉子結(jié)點只在最大兩層上出現(xiàn)左子樹深度與右子樹深度相等或大,.,六、完全二叉樹(性質(zhì)),13,第二節(jié)二叉樹,具有n個結(jié)點的完全二叉樹,其深度為log2n +1設(shè)k為深度,由二叉樹性質(zhì),已知 2k-1-1 n 2k-1即 2k-1 n 2k k-1 log2n Rchild ,若q不為空,則q進棧; p=p-Lchild ,若p不為空,轉(zhuǎn)(1),否則轉(zhuǎn)(4); 退棧到p ,轉(zhuǎn)(1),直到??諡橹埂?.,第三節(jié)遍歷二叉樹,void PreorderTraverse( BTNode T) BTNode *StackMAX_NODE ,*p=T, *q ; int top=0 ; if (T=NULL) printf(“ Binary Tree is Empty!n”) ; else do visit( p- data ) ; q=p-Rchild ; if ( q!=NULL ) stack+top=q ; p=p-Lchild ; if (p=NULL) p=stacktop ; top- ; while (p!=NULL) ; ,.,三、中序遍歷二叉樹,30,第三節(jié)遍歷二叉樹,算法:1.若二叉樹為空,則返回;否則:2.中序遍歷左子樹(L)3.訪問根節(jié)點(D)4.中序遍歷右子樹(R),.,三、中序遍歷二叉樹,31,第三節(jié)遍歷二叉樹,算法(舉例):1.若二叉樹為空,則返回;否則:2.中序遍歷左子樹(L)3.訪問根節(jié)點(D)4.中序遍歷右子樹(R)輸出結(jié)果:DBGEAFC,.,三、中序遍歷二叉樹,32,第三節(jié)遍歷二叉樹,算法:void InOrderTraverse ( BinTree T ) if (T) InOrderTraverse ( T-lChild ); cout data; InOrderTraverse ( T-rChild ); ,.,四、后序遍歷二叉樹,33,第三節(jié)遍歷二叉樹,算法:1.若二叉樹為空,則返回;否則:2.后序遍歷左子樹(L)3.后序遍歷右子樹(R)4.訪問根節(jié)點(D),.,四、后序遍歷二叉樹,34,第三節(jié)遍歷二叉樹,算法(舉例):1.若二叉樹為空,則返回;否則:2.訪問根節(jié)點(D)3.后序遍歷左子樹(L)4.后序遍歷右子樹(R)輸出結(jié)果:DGEBFCA,.,四、后序遍歷二叉樹,35,第三節(jié)遍歷二叉樹,算法:void PostOrderTraverse(BinTreeT) if(T) PostOrderTraverse(T-lChild); PostOrderTraverse(T-rChild); cout data; ,.,第三節(jié)遍歷二叉樹,層次遍歷二叉樹 從根結(jié)點開始遍歷,按層次次序“自上而下,從左至右”訪問樹中的各結(jié)點。算法: 設(shè)置一個隊列初始化為空,T指向根結(jié)點指針變量, 若二叉樹為空,返回; 否則,p=T,p入隊; 隊首元素出隊到p; 訪問p所指向的結(jié)點; 將p指向結(jié)點的左、右子結(jié)點依次入隊。直到隊空為止。,.,第三節(jié)遍歷二叉樹,#define MAX_NODE 50void LevelorderTraverse( BTNode *T) BTNode *QueueMAX_NODE ,*p=T ; int front=0 , rear=0 ; if (p!=NULL) Queue+rear=p; /* 根結(jié)點入隊 */ while (frontdata ); if (p-Lchild!=NULL) Queue+rear=p; /* 左結(jié)點入隊 */ if (p-Rchild!=NULL) Queue+rear=p; /* 左結(jié)點入隊 */ ,.,課堂練習(xí),1. 已知二叉樹的先根和中根序列,求該二叉樹的后根序列 先根序列:A,B,C,D,E,F(xiàn),G,H,I,J 中根序列:C,B,A,E,F(xiàn),D,I,H,J,G 2. 已知一棵二叉樹的中根和后根序列,求該二叉樹的高度和雙支,單支及葉子結(jié)點數(shù)。 中根序列:c,b,d,e,a,g,I,h,j,f 后根序列:c,e,d,b,I,j,h,g,f,a,.,一、增加新指針,39,第四節(jié)線索二叉樹,最簡單的方法是在每個結(jié)點中,增加前驅(qū)(fwd)和后繼(bkwd)指針在做二叉樹遍歷(前、中、后序),將每個結(jié)點的前驅(qū)和后繼信息添入fwd和bkwd域中,.,二、利用空指針,40,第四節(jié)線索二叉樹,在有n個結(jié)點的二叉樹中,必定存在n+1個空鏈域因為每個結(jié)點有兩個鏈域(左、右孩子指針),因此共有2n個鏈域除根結(jié)點外,每個結(jié)點都有且僅有一個分支相連,即n-1個鏈域被使用可以利用這些空閑的指針域來存放結(jié)點的直接前驅(qū)和直接后繼信息。,.,二、利用空指針,41,第四節(jié)線索二叉樹,在結(jié)點中增加兩個標(biāo)記位(LTag, RTag)LTag=0, lChild域指示結(jié)點的左孩子LTag=1, lChild域指示結(jié)點的前驅(qū)結(jié)點RTag=0, lChild域指示結(jié)點的右孩子RTag=1, lChild域指示結(jié)點的后繼結(jié)點,.,第四節(jié)線索二叉樹,.,第四節(jié)線索二叉樹,線索二叉樹表示:實線表示指針,指向其左、右孩子; 虛線表示線索,指向其直接前驅(qū)(紅線)或直接后繼(綠線)。,.,第四節(jié)線索二叉樹,1.在線索樹上進行遍歷 只要先找到序列中的第一個結(jié)點,然后就可以依次找結(jié)點的直接后繼結(jié)點直到后繼為空為止。2.在線索樹中找結(jié)點的直接后繼(以中序遍歷為例) 樹中所有葉子結(jié)點的右鏈都是線索。 樹中所有非葉子結(jié)點的右鏈都是指針。 非葉子結(jié)點的直接后繼是遍歷其右子樹時訪問的第一個結(jié)點,即右子樹中最左下的(葉子)結(jié)點。如結(jié)點C的直接后繼:沿右指針找到右子樹的根結(jié)點F,然后沿左鏈往下直到Ltag=1的結(jié)點即為C的直接后繼結(jié)點H。,.,第四節(jié)線索二叉樹,3.在線索樹中找結(jié)點的直接前驅(qū)(以中序遍歷為例) 若結(jié)點的Ltag=1,則左鏈?zhǔn)蔷€索,指示其直接前驅(qū);否則,遍歷左子樹時訪問的最后一個結(jié)點(即沿左子樹中最右往下的結(jié)點) 為其直接前驅(qū)結(jié)點。,.,一、樹的存儲結(jié)構(gòu),46,第五節(jié)樹與森林,1.雙親表示法采用一組連續(xù)的存儲空間由于每個結(jié)點只有一個雙親,只需要一個指針,0 1 2 3 4 5 6,.,一、樹的存儲結(jié)構(gòu),47,第五節(jié)樹與森林,2.孩子表示法可以采用多重鏈表,即每個結(jié)點有多個指針特點:鏈表結(jié)構(gòu)簡單,指針域的數(shù)目就是樹的度。最大缺點:空鏈域太多,在一棵有n個結(jié)點,度為k的樹中必有n(k-1)+1空指針域。,.,一、樹的存儲結(jié)構(gòu),48,第五節(jié)樹與森林,2.孩子表示法將每個結(jié)點的孩子排列起來,用單鏈表表示將每個結(jié)點排列成一個線性表,0123456,Root,.,一、樹的存儲結(jié)構(gòu),49,第五節(jié)樹與森林,3.孩子兄弟表示法采用二叉鏈表左邊指針指向第一個孩子,右邊指針指向兄弟,.,二、樹與二叉樹的對應(yīng)關(guān)系,50,第五節(jié)樹與森林,樹與二叉樹都可以采用二叉鏈表作存儲結(jié)構(gòu)任意給定一棵樹,可以找到一個唯一的二叉樹(沒有右子樹),樹,對應(yīng)的二叉樹,.,三、森林與二叉樹的對應(yīng)關(guān)系,51,第五節(jié)樹與森林,如果把森林中的第二棵樹的根結(jié)點看作是第一棵樹的根結(jié)點的兄弟,則可找到一個唯一的二叉樹與之對應(yīng),三棵樹的森林,對應(yīng)的二叉樹,T1 T2 T3,.,四、樹的遍歷,52,第五節(jié)樹與森林,對樹的遍歷主要有兩種:1. 先根(次序)遍歷2. 后根(次序)遍歷,.,四、樹的遍歷,53,第五節(jié)樹與森林,1. 先根(次序)遍歷 當(dāng)樹非空時 訪問根結(jié)點 依次先根遍歷根的各棵子樹 輸出結(jié)果:ABEFCDG,.,四、樹的遍歷,54,第五節(jié)樹與森林,2. 后根(次序)遍歷 當(dāng)樹非空時依次后根遍歷根的各棵子樹訪問根結(jié)點 輸出結(jié)果:EFBCGDA,.,課堂練習(xí),1. 二叉樹采用順序存儲結(jié)構(gòu),如下圖所示:(1)畫出該樹的邏輯結(jié)構(gòu)(2)寫出該樹的先序遍歷、中序遍歷和后序遍歷的結(jié)果(3)畫出把此二叉樹還原成森林的圖,.,課堂練習(xí),2. 已知一棵樹的邊集表示為,每個結(jié)點的孩子按照從左下到右下的次序排列,先根遍歷得到的序列為( )。 3. 在一棵樹的孩子兄弟鏈表表示(又稱樹的二叉鏈表表示)中,一個結(jié)點的右孩子是該結(jié)點的(A )結(jié)點 A兄弟 B.父子 C.祖先 D.子孫,.,一、最優(yōu)二叉樹,57,第六節(jié)哈夫曼樹及其應(yīng)用,路徑:從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑路徑長度:路徑上的分支數(shù)目樹的路徑長度:從樹根到每個結(jié)點的路徑長度之和右樹路徑長度為:2*1 + 3*2 + 1*3 = 11,.,一、最優(yōu)二叉樹,58,第六節(jié)哈夫曼樹及其應(yīng)用,帶權(quán)路徑長度:從結(jié)點到樹根之間的路徑長度與結(jié)點上權(quán)的乘積樹的帶權(quán)路徑長度(WPL):樹中所有葉子結(jié)點的帶權(quán)路徑長度之和WPL = 2*5+3*3+2*4=27,.,一、最優(yōu)二叉樹,59,第六節(jié)哈夫曼樹及其應(yīng)用,最優(yōu)二叉樹:假設(shè)二叉樹有n個葉子,其每個葉子結(jié)點帶權(quán)wi,則帶權(quán)路徑長度WPL最小的二叉樹稱為最優(yōu)二叉樹哈夫曼(Huffman)樹就是一棵最優(yōu)二叉樹WPL = 1*5+2*3+2*4=19,.,二、Huffman樹(構(gòu)造),60,第六節(jié)哈夫曼樹及其應(yīng)用,在Huffman樹中,權(quán)值最大的結(jié)點離根最近權(quán)值最小的結(jié)點離根最遠,.,二、Huffman樹(算法),61,第六節(jié)哈夫曼樹及其應(yīng)用,1.根據(jù)給定的n個權(quán)值(w1, w2, , wn)構(gòu)成n棵二叉樹的集合F=T1, T2, , Tn,其中每棵二叉樹Ti中只有一個帶樹為Ti的根結(jié)點2.在F中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹,且置其根結(jié)點的權(quán)值為其左右子樹權(quán)值之和3.在F中刪除這兩棵樹,同時將新得到的二叉樹加入F中4.重復(fù)2, 3,直到F只含一棵樹為止,.,二、Huffman樹(舉例),62,第六節(jié)哈夫曼樹及其應(yīng)用,.,三、Huffman編碼,63,第六節(jié)哈夫曼樹及其應(yīng)用,設(shè)給出一段報文:GOOD_GOOD_GOODGODG字符集合是 O, G, _, D ,各個字符出現(xiàn)的頻度(次數(shù))是 W 7, 5, 2, 4 。若給每個字符以等長編碼O: 00 G: 10 _: 01 D: 11則總編碼長度為 (2+7+4+5) * 2 = 36.,.,三、Huffman編碼,64,第六節(jié)哈夫曼樹及其應(yīng)用,若按各個字符出現(xiàn)的概率不同而給予不等長編碼,可望減少總編碼長度。各字符出現(xiàn)概率為 2/18, 7/18, 4/18, 5/18 ,化整為 2, 7, 4, 5 可構(gòu)成右圖所示Huffman樹,.,三、Huffman編碼,65,第六節(jié)哈夫曼樹及其應(yīng)用,令左孩子分支為編碼0,右孩子分支為編碼1得到不等長編碼:O:0 G:10 _:110 D:111則總編碼長度為 7*1+5*2+4*3+2*3 = 35Huffman是一種前綴編碼,解碼時不會混淆,.,第六節(jié)哈夫曼樹及其應(yīng)用,void HuffmanCoding(HuffmanTree ,.,第六節(jié)哈夫曼樹及其應(yīng)用,for (i=n+1; i=m; i+) / 建哈夫曼樹 / 在HT1.i-1中選擇parent為且weight最小的兩個結(jié)點, / 其序號分別為s1和s2。 Select(HT, i-1, s1, s2); HTs1.parent = i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; printf(nselect: s1=%d s2=%dn, s1, s2); printf( 結(jié)點 weight parent lchild rchild); for (j=1; jlchild); /遞歸求左子樹深度hr=TreeDepth(p-rchild); /遞歸求右子樹深度if ( hlhr )h=hl;elseh=hr;return(h1); /返回較大左右子樹深度加1 elsereturn(0);,.,算法設(shè)計練習(xí),例2求二叉樹中葉子結(jié)點的個數(shù)templateint leafnum(bitreenode*root) if(root=NULL) return 0; else if(root-lchild=NULL),.,算法設(shè)計練習(xí),例3將一棵二叉樹復(fù)制給另一棵二叉樹bitree *CopyTree(bnode *p) /復(fù)制一棵二叉樹 bitnode *t; if (p!=NULL ) t=(bitnode*)malloc(sizeof(bnode); t-data=p-data; t-lchild=CopyTree(p-lchild); t-rchild=CopyTree(p-rchild); return(t); else return(NULL);,.,算法設(shè)計練習(xí)例4 用二叉鏈表表示,判斷給定的二叉樹是否為完全二叉樹。void wanquan(BiTree T) BiTree a100; int flag=0; int i=1,j; BiTree p; Queue myque; /借用隊列進行層次遍歷 InitQueue(myque); if (T) EnQueue(myque,T); while(!QueueEmpty(myque) DeQueue(myque,p); ai+=p; if (p) EnQueue(myque,p-lchild); EnQueue(myque,p-rchild); /層次遍歷,并進行數(shù)組賦值 for(j=1;ji;j+) if (!aj) flag=1; if (flag /根據(jù)數(shù)組內(nèi)容判斷是否是二叉樹 ,.,算法設(shè)計練習(xí),算法描述: 樹的層次遍歷算法的改進,用隊列來進行層次遍歷,隊列用來存放每一層的結(jié)點,算法如下: i=0; 如果樹不為空,入隊 While(隊不空) 隊首元素出隊,并賦給數(shù)組元素ai+; 如果隊首元素不為null,則將其左右孩子依次入隊; 遍歷數(shù)組a,如果出現(xiàn)某一個元素為空,但其后元素不為空,則可以立即判斷該二叉樹為非完全二叉樹,- 1.請仔細閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點此認領(lǐng)!既往收益都歸您。
下載文檔到電腦,查找使用更方便
10 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該PPT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 深圳大學(xué) 數(shù)據(jù)結(jié)構(gòu) 2017 二叉 演示 文檔
鏈接地址:http://ioszen.com/p-359905.html