深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017樹與二叉樹演示文檔

.,第六章樹與二叉樹,數(shù)據(jù)結(jié)構(gòu),.,一、樹的定義(Tree),2,樹是有n(n0)個(gè)結(jié)點(diǎn)的有限集合。如果 n=0，稱為空樹；如果 n>0,稱為非空樹,對(duì)于非空樹,有且僅有一個(gè)特定的稱為根(Root)的節(jié)點(diǎn)(無直接前驅(qū))如果 n>1，則除根以外的其它結(jié)點(diǎn)劃分為 m (m>0)個(gè)互不相交的有限集 T1, T2 , Tm，其中每個(gè)集合本身又是一棵樹，并且稱為根的子樹(SubTree)。每個(gè)結(jié)點(diǎn)都有唯一的直接前驅(qū)，但可能有多個(gè)后繼,第一節(jié)樹的概念與基本術(shù)語,.,一、樹的定義(舉例),3,其中：A是根；其余結(jié)點(diǎn)分成三個(gè)互不相交的子集，T1=B,E,F,K,L； T2=C,G； T3=D,H,I,J,M,T1,T2,T3都是根A的子樹，且本身也是一棵樹,A,只有根結(jié)點(diǎn)的樹,有13個(gè)結(jié)點(diǎn)的樹,第一節(jié)樹的概念與基本術(shù)語,.,二、樹的基本術(shù)語,4,第一節(jié)樹的概念與基本術(shù)語,結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù)樹的度：樹中各結(jié)點(diǎn)的度的最大值葉結(jié)點(diǎn)：度為0的結(jié)點(diǎn),也稱終端結(jié)點(diǎn)分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)包括根結(jié)點(diǎn)，也稱非終端結(jié)點(diǎn)。,.,二、樹的基本術(shù)語,5,第一節(jié)樹的概念與基本術(shù)語,孩子：結(jié)點(diǎn)的子樹的根直接后繼，可能有多個(gè)雙親：孩子的直接前驅(qū)最多只能有一個(gè)兄弟：同一雙親的孩子子孫：以某結(jié)點(diǎn)為根的樹中的所有結(jié)點(diǎn)祖先：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn),.,二、樹的基本術(shù)語,6,第一節(jié)樹的概念與基本術(shù)語,層次：根結(jié)點(diǎn)為第一層，其孩子為第二層，依此類推深度：樹中結(jié)點(diǎn)的最大層次森林：互不相交的樹的集合。對(duì)樹中每個(gè)結(jié)點(diǎn)而言，其子樹的集合即為森林.有序樹:樹中各結(jié)點(diǎn)的子樹按照一定次序從左向右安排,相對(duì)次序不能改變,.,一、二叉樹(Binary Tree),7,第二節(jié)二叉樹,二叉樹是一種特殊的樹每個(gè)結(jié)點(diǎn)最多有棵子樹二叉樹的子樹有左右之分,二叉樹的五種基本形態(tài),.,二、二叉樹性質(zhì),8,第二節(jié)二叉樹,在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)證明：1.i=1, 只有一個(gè)根節(jié)點(diǎn)，因此2i-1=20=12.設(shè)第i-1層上，以上性質(zhì)成立，即第i-1層至多有2(i-1)-1結(jié)點(diǎn)。由二叉樹的定義可知，任何結(jié)點(diǎn)的度小于2，因此，第i層上的結(jié)點(diǎn)數(shù)最多為第i-1層上的兩倍，即2*2i-2=2i-1,.,三、二叉樹性質(zhì),9,第二節(jié)二叉樹,深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)證明：1.由性質(zhì)，已知第i層上結(jié)點(diǎn)數(shù)最多為2i-1 k2. 2i-1 = 2k-1 i=1,.,四、二叉樹性質(zhì),10,第二節(jié)二叉樹,非空二叉樹上葉結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)數(shù)加一,即n0=n2+1證明：1.設(shè)n1為度為1的結(jié)點(diǎn)，則總結(jié)點(diǎn)數(shù)= n0+n1+n22.設(shè)B為二叉樹的分支數(shù)，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且只有一個(gè)分支，因此n=B+13.每個(gè)分支皆由度為1或2的結(jié)點(diǎn)發(fā)出，B=n1+2n24.n=B+1=(n1+2n2)+1 = n0+n1+n2，因此 n0=n2+1,.,五、滿二叉樹,11,第二節(jié)二叉樹,一個(gè)深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹每層上的結(jié)點(diǎn)數(shù)都是最大數(shù)可以自上而下、自左至右連續(xù)編號(hào),.,六、完全二叉樹,12,第二節(jié)二叉樹,當(dāng)且僅當(dāng)每一個(gè)結(jié)點(diǎn)都與深度相同的滿二叉樹中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)的二叉樹葉子結(jié)點(diǎn)只在最大兩層上出現(xiàn)左子樹深度與右子樹深度相等或大,.,六、完全二叉樹(性質(zhì)),13,第二節(jié)二叉樹,具有n個(gè)結(jié)點(diǎn)的完全二叉樹,其深度為log2n +1設(shè)k為深度，由二叉樹性質(zhì)，已知 2k-1-1 < n 2k-1即 2k-1 n < 2k k-1 log2n <k即 k = log2n +1,.,六、完全二叉樹(性質(zhì)),14,第二節(jié)二叉樹,在完全二叉樹中，結(jié)點(diǎn)i的雙親為i/2結(jié)點(diǎn)i的左孩子LCHILD(i)=2i結(jié)點(diǎn)i的右孩子RCHILD(i)=2i+1,.,七、二叉樹的順序存儲(chǔ)結(jié)構(gòu),15,第二節(jié)二叉樹,用一組連續(xù)的存儲(chǔ)單元依次自上而下,自左至右存儲(chǔ)結(jié)點(diǎn),完全二叉樹的順序表示一般二叉樹的順序表示,.,七、二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),16,第二節(jié)二叉樹,1.二叉鏈表采用數(shù)據(jù)域加上左、右孩子指針,.,七、二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),17,第二節(jié)二叉樹,1.二叉鏈表(舉例)二叉樹（左）及其二叉鏈表（右）,.,七、二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),18,第二節(jié)二叉樹,.三叉鏈表采用數(shù)據(jù)域加上左、右孩子指針及雙親指針,.,七、二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),19,第二節(jié)二叉樹,.三叉鏈表(舉例)二叉樹（左）及其三叉鏈表（右）,.,課堂練習(xí),1. 樹最適合用來表示(D )。 A. 線性結(jié)構(gòu)的數(shù)據(jù) B. 順序結(jié)構(gòu)的數(shù)據(jù) C. 元素之間無前驅(qū)和后繼關(guān)系的數(shù)據(jù) D. 元素之間有包含和層次關(guān)系的數(shù)據(jù) 2. 在一棵樹中，（ C ）沒有前驅(qū)結(jié)點(diǎn)。 A.樹枝結(jié)點(diǎn) B.葉子結(jié)點(diǎn) C.樹根結(jié)點(diǎn) D.空結(jié)點(diǎn)3. 在一棵樹中，每個(gè)結(jié)點(diǎn)最多有（ B ）個(gè)前驅(qū)結(jié)點(diǎn)。 A. 0 B. 1 C.2 D.任意多個(gè)4.在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)（ B ）。 A+2 B. +1 C.+0 D.-1,.,課堂練習(xí),5. 在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于(C) A. n B. n-1 C. n+1 D.2*n6. 在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹的第4層上，最多有(B )個(gè)結(jié)點(diǎn)。 A. 4 B.8 C.15 D.167. 在一棵深度為4的完全二叉樹中，所含結(jié)點(diǎn)個(gè)數(shù)不小于（A ）。 A.8 B.9 C.15 D.168. 在一棵深度為3的二叉樹中，所含結(jié)點(diǎn)數(shù)不大于(A) A.6 B. 7 C .8 D.15,.,課堂練習(xí),9. 一棵具有35個(gè)結(jié)點(diǎn)的完全二叉樹，該樹的深度為(C),最后一層的結(jié)點(diǎn)數(shù)有(A). A4 B.5 C.6 D.710. 在一棵完全二叉樹中，若編號(hào)為i的結(jié)點(diǎn)存在左孩子，則左孩子結(jié)點(diǎn)的編號(hào)為（ A ）。 A2i B.2i-1 C.2i+1 D.2i+211. 在一棵完全二叉樹中，若編號(hào)為i的結(jié)點(diǎn)存在右孩子，則右孩子結(jié)點(diǎn)的編號(hào)為（C ）。 A2i B.2i-1 C.2i+1 D.2i+2,.,一、遍歷二叉樹,23,第三節(jié)遍歷二叉樹,樹的遍歷就是按某種次序訪問樹中的結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次一個(gè)二叉樹由根節(jié)點(diǎn)與左子樹和右子樹組成設(shè)訪問根結(jié)點(diǎn)用D表示，遍歷左、右子樹用L、R表示,.,一、遍歷二叉樹,24,第三節(jié)遍歷二叉樹,如果規(guī)定先左子樹后右子樹，則共有三種組合1.DLR 先序遍歷2.LDR 中序遍歷3.LRD 后序遍歷,.,二、先序遍歷二叉樹,25,第三節(jié)遍歷二叉樹,算法：1.若二叉樹為空，則返回；否則：2.訪問根節(jié)點(diǎn)(D)3.先序遍歷左子樹(L)4.先序遍歷右子樹(R),.,二、先序遍歷二叉樹,26,第三節(jié)遍歷二叉樹,算法(舉例)：1.若二叉樹為空，則返回；否則：2.訪問根節(jié)點(diǎn)(D)3.先序遍歷左子樹(L)4.先序遍歷右子樹(R)輸出結(jié)果：ABDEGCF,.,二、先序遍歷二叉樹(遞歸),27,第三節(jié)遍歷二叉樹,算法：void PreOrderTraverse ( BinTree T ) if (T) /非空二叉樹 cout data; PreOrderTraverse(lChild(T); PreOrderTraverse(rChild(T); ,.,第三節(jié)遍歷二叉樹,二、先序遍歷二叉樹(非遞歸)設(shè)T是指向二叉樹根結(jié)點(diǎn)的指針變量算法實(shí)現(xiàn)：若二叉樹為空，則返回；否則，令p=T； 訪問p所指向的結(jié)點(diǎn)； q=p->Rchild ，若q不為空，則q進(jìn)棧； 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é)點(diǎn)(D)4.中序遍歷右子樹(R),.,三、中序遍歷二叉樹,31,第三節(jié)遍歷二叉樹,算法(舉例)：1.若二叉樹為空，則返回；否則：2.中序遍歷左子樹(L)3.訪問根節(jié)點(diǎn)(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é)點(diǎn)(D),.,四、后序遍歷二叉樹,34,第三節(jié)遍歷二叉樹,算法(舉例)：1.若二叉樹為空，則返回；否則：2.訪問根節(jié)點(diǎn)(D)3.后序遍歷左子樹(L)4.后序遍歷右子樹(R)輸出結(jié)果：DGEBFCA,.,四、后序遍歷二叉樹,35,第三節(jié)遍歷二叉樹,算法：void PostOrderTraverse(BinTreeT) if(T) PostOrderTraverse(T->lChild); PostOrderTraverse(T->rChild); cout data; ,.,第三節(jié)遍歷二叉樹,層次遍歷二叉樹 從根結(jié)點(diǎn)開始遍歷，按層次次序“自上而下，從左至右”訪問樹中的各結(jié)點(diǎn)。算法： 設(shè)置一個(gè)隊(duì)列初始化為空,T指向根結(jié)點(diǎn)指針變量， 若二叉樹為空，返回； 否則，p=T，p入隊(duì)； 隊(duì)首元素出隊(duì)到p； 訪問p所指向的結(jié)點(diǎn)； 將p指向結(jié)點(diǎn)的左、右子結(jié)點(diǎn)依次入隊(duì)。直到隊(duì)空為止。,.,第三節(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é)點(diǎn)入隊(duì) */ while (frontdata ); if (p->Lchild!=NULL) Queue+rear=p; /* 左結(jié)點(diǎn)入隊(duì) */ if (p->Rchild!=NULL) Queue+rear=p; /* 左結(jié)點(diǎn)入隊(duì) */ ,.,課堂練習(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é)點(diǎn)數(shù)。 中根序列：c,b,d,e,a,g,I,h,j,f 后根序列：c,e,d,b,I,j,h,g,f,a,.,一、增加新指針,39,第四節(jié)線索二叉樹,最簡(jiǎn)單的方法是在每個(gè)結(jié)點(diǎn)中，增加前驅(qū)(fwd)和后繼(bkwd)指針在做二叉樹遍歷（前、中、后序），將每個(gè)結(jié)點(diǎn)的前驅(qū)和后繼信息添入fwd和bkwd域中,.,二、利用空指針,40,第四節(jié)線索二叉樹,在有n個(gè)結(jié)點(diǎn)的二叉樹中，必定存在n+1個(gè)空鏈域因?yàn)槊總€(gè)結(jié)點(diǎn)有兩個(gè)鏈域（左、右孩子指針），因此共有2n個(gè)鏈域除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)分支相連，即n-1個(gè)鏈域被使用可以利用這些空閑的指針域來存放結(jié)點(diǎn)的直接前驅(qū)和直接后繼信息。,.,二、利用空指針,41,第四節(jié)線索二叉樹,在結(jié)點(diǎn)中增加兩個(gè)標(biāo)記位（LTag, RTag)LTag=0, lChild域指示結(jié)點(diǎn)的左孩子LTag=1, lChild域指示結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)RTag=0, lChild域指示結(jié)點(diǎn)的右孩子RTag=1, lChild域指示結(jié)點(diǎn)的后繼結(jié)點(diǎn),.,第四節(jié)線索二叉樹,.,第四節(jié)線索二叉樹,線索二叉樹表示:實(shí)線表示指針，指向其左、右孩子； 虛線表示線索，指向其直接前驅(qū)(紅線)或直接后繼(綠線)。,.,第四節(jié)線索二叉樹,1.在線索樹上進(jìn)行遍歷 只要先找到序列中的第一個(gè)結(jié)點(diǎn)，然后就可以依次找結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)直到后繼為空為止。2.在線索樹中找結(jié)點(diǎn)的直接后繼(以中序遍歷為例) 樹中所有葉子結(jié)點(diǎn)的右鏈都是線索。 樹中所有非葉子結(jié)點(diǎn)的右鏈都是指針。 非葉子結(jié)點(diǎn)的直接后繼是遍歷其右子樹時(shí)訪問的第一個(gè)結(jié)點(diǎn)，即右子樹中最左下的(葉子)結(jié)點(diǎn)。如結(jié)點(diǎn)C的直接后繼：沿右指針找到右子樹的根結(jié)點(diǎn)F，然后沿左鏈往下直到Ltag=1的結(jié)點(diǎn)即為C的直接后繼結(jié)點(diǎn)H。,.,第四節(jié)線索二叉樹,3.在線索樹中找結(jié)點(diǎn)的直接前驅(qū)(以中序遍歷為例) 若結(jié)點(diǎn)的Ltag=1，則左鏈?zhǔn)蔷€索，指示其直接前驅(qū)；否則，遍歷左子樹時(shí)訪問的最后一個(gè)結(jié)點(diǎn)(即沿左子樹中最右往下的結(jié)點(diǎn)) 為其直接前驅(qū)結(jié)點(diǎn)。,.,一、樹的存儲(chǔ)結(jié)構(gòu),46,第五節(jié)樹與森林,1.雙親表示法采用一組連續(xù)的存儲(chǔ)空間由于每個(gè)結(jié)點(diǎn)只有一個(gè)雙親，只需要一個(gè)指針,0 1 2 3 4 5 6,.,一、樹的存儲(chǔ)結(jié)構(gòu),47,第五節(jié)樹與森林,2.孩子表示法可以采用多重鏈表，即每個(gè)結(jié)點(diǎn)有多個(gè)指針特點(diǎn)：鏈表結(jié)構(gòu)簡(jiǎn)單,指針域的數(shù)目就是樹的度。最大缺點(diǎn):空鏈域太多,在一棵有n個(gè)結(jié)點(diǎn)，度為k的樹中必有n(k-1)+1空指針域。,.,一、樹的存儲(chǔ)結(jié)構(gòu),48,第五節(jié)樹與森林,2.孩子表示法將每個(gè)結(jié)點(diǎn)的孩子排列起來，用單鏈表表示將每個(gè)結(jié)點(diǎn)排列成一個(gè)線性表,0123456,Root,.,一、樹的存儲(chǔ)結(jié)構(gòu),49,第五節(jié)樹與森林,3.孩子兄弟表示法采用二叉鏈表左邊指針指向第一個(gè)孩子，右邊指針指向兄弟,.,二、樹與二叉樹的對(duì)應(yīng)關(guān)系,50,第五節(jié)樹與森林,樹與二叉樹都可以采用二叉鏈表作存儲(chǔ)結(jié)構(gòu)任意給定一棵樹，可以找到一個(gè)唯一的二叉樹(沒有右子樹),樹,對(duì)應(yīng)的二叉樹,.,三、森林與二叉樹的對(duì)應(yīng)關(guān)系,51,第五節(jié)樹與森林,如果把森林中的第二棵樹的根結(jié)點(diǎn)看作是第一棵樹的根結(jié)點(diǎn)的兄弟，則可找到一個(gè)唯一的二叉樹與之對(duì)應(yīng),三棵樹的森林,對(duì)應(yīng)的二叉樹,T1 T2 T3,.,四、樹的遍歷,52,第五節(jié)樹與森林,對(duì)樹的遍歷主要有兩種：1. 先根（次序）遍歷2. 后根（次序）遍歷,.,四、樹的遍歷,53,第五節(jié)樹與森林,1. 先根（次序）遍歷 當(dāng)樹非空時(shí) 訪問根結(jié)點(diǎn) 依次先根遍歷根的各棵子樹 輸出結(jié)果：ABEFCDG,.,四、樹的遍歷,54,第五節(jié)樹與森林,2. 后根（次序）遍歷 當(dāng)樹非空時(shí)依次后根遍歷根的各棵子樹訪問根結(jié)點(diǎn) 輸出結(jié)果：EFBCGDA,.,課堂練習(xí),1. 二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，如下圖所示：(1)畫出該樹的邏輯結(jié)構(gòu)(2)寫出該樹的先序遍歷、中序遍歷和后序遍歷的結(jié)果(3)畫出把此二叉樹還原成森林的圖,.,課堂練習(xí),2. 已知一棵樹的邊集表示為,每個(gè)結(jié)點(diǎn)的孩子按照從左下到右下的次序排列，先根遍歷得到的序列為（ ）。 3. 在一棵樹的孩子兄弟鏈表表示（又稱樹的二叉鏈表表示）中，一個(gè)結(jié)點(diǎn)的右孩子是該結(jié)點(diǎn)的(A )結(jié)點(diǎn) A兄弟 B.父子 C.祖先 D.子孫,.,一、最優(yōu)二叉樹,57,第六節(jié)哈夫曼樹及其應(yīng)用,路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑路徑長(zhǎng)度：路徑上的分支數(shù)目樹的路徑長(zhǎng)度：從樹根到每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和右樹路徑長(zhǎng)度為：2*1 + 3*2 + 1*3 = 11,.,一、最優(yōu)二叉樹,58,第六節(jié)哈夫曼樹及其應(yīng)用,帶權(quán)路徑長(zhǎng)度：從結(jié)點(diǎn)到樹根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積樹的帶權(quán)路徑長(zhǎng)度(WPL)：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和WPL = 2*5+3*3+2*4=27,.,一、最優(yōu)二叉樹,59,第六節(jié)哈夫曼樹及其應(yīng)用,最優(yōu)二叉樹：假設(shè)二叉樹有n個(gè)葉子，其每個(gè)葉子結(jié)點(diǎn)帶權(quán)wi，則帶權(quán)路徑長(zhǎng)度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é)點(diǎn)離根最近權(quán)值最小的結(jié)點(diǎn)離根最遠(yuǎn),.,二、Huffman樹(算法),61,第六節(jié)哈夫曼樹及其應(yīng)用,1.根據(jù)給定的n個(gè)權(quán)值(w1, w2, , wn)構(gòu)成n棵二叉樹的集合F=T1, T2, , Tn，其中每棵二叉樹Ti中只有一個(gè)帶樹為Ti的根結(jié)點(diǎn)2.在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置其根結(jié)點(diǎn)的權(quán)值為其左右子樹權(quán)值之和3.在F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入F中4.重復(fù)2, 3，直到F只含一棵樹為止,.,二、Huffman樹(舉例),62,第六節(jié)哈夫曼樹及其應(yīng)用,.,三、Huffman編碼,63,第六節(jié)哈夫曼樹及其應(yīng)用,設(shè)給出一段報(bào)文：GOOD_GOOD_GOODGODG字符集合是 O, G, _, D ，各個(gè)字符出現(xiàn)的頻度(次數(shù))是 W 7, 5, 2, 4 。若給每個(gè)字符以等長(zhǎng)編碼O: 00 G: 10 _: 01 D: 11則總編碼長(zhǎng)度為 (2+7+4+5) * 2 = 36.,.,三、Huffman編碼,64,第六節(jié)哈夫曼樹及其應(yīng)用,若按各個(gè)字符出現(xiàn)的概率不同而給予不等長(zhǎng)編碼，可望減少總編碼長(zhǎng)度。各字符出現(xiàn)概率為 2/18, 7/18, 4/18, 5/18 ,化整為 2, 7, 4, 5 可構(gòu)成右圖所示Huffman樹,.,三、Huffman編碼,65,第六節(jié)哈夫曼樹及其應(yīng)用,令左孩子分支為編碼0，右孩子分支為編碼1得到不等長(zhǎng)編碼：O:0 G:10 _:110 D:111則總編碼長(zhǎng)度為 7*1+5*2+4*3+2*3 = 35Huffman是一種前綴編碼，解碼時(shí)不會(huì)混淆,.,第六節(jié)哈夫曼樹及其應(yīng)用,void HuffmanCoding(HuffmanTree ,.,第六節(jié)哈夫曼樹及其應(yīng)用,for (i=n+1; i<=m; i+) / 建哈夫曼樹 / 在HT1.i-1中選擇parent為且weight最小的兩個(gè)結(jié)點(diǎn)， / 其序號(hào)分別為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é)點(diǎn) weight parent lchild rchild"); for (j=1; j<=i; j+) printf("n%4d%8d%8d%8d%8d",j,HTj.weight, HTj.parent,HTj.lchild, HTj.rchild); printf(" 按任意鍵，繼續(xù)."); getch(); ,.,第六節(jié)哈夫曼樹及其應(yīng)用,實(shí)例 假設(shè)用于通信的電文僅由8個(gè)字母組成.字母在電文中出現(xiàn)頻率:0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10, 設(shè)計(jì)8個(gè)字母的Huffman編碼并比較等長(zhǎng)編碼的總編碼長(zhǎng)度.,.,算法設(shè)計(jì)練習(xí),例1求二叉樹中以值為x的結(jié)點(diǎn)為根的子樹的深度int TreeDepth(bitnode *p) /遞歸求二叉樹深度 int hl,hr,h; if ( p!=NULL ) hl=TreeDepth(p->lchild); /遞歸求左子樹深度hr=TreeDepth(p->rchild); /遞歸求右子樹深度if ( hl>hr )h=hl;elseh=hr;return(h1); /返回較大左右子樹深度加1 elsereturn(0);,.,算法設(shè)計(jì)練習(xí),例2求二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)templateint leafnum(bitreenode*root) if(root=NULL) return 0; else if(root->lchild=NULL),.,算法設(shè)計(jì)練習(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è)計(jì)練習(xí)例4 用二叉鏈表表示，判斷給定的二叉樹是否為完全二叉樹。void  wanquan(BiTree T) BiTree a100; int flag=0; int i=1,j;  BiTree p; Queue myque; /借用隊(duì)列進(jìn)行層次遍歷 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);    /層次遍歷，并進(jìn)行數(shù)組賦值 for(j=1;j<i;j+)   if (!aj)     flag=1;  if (flag /根據(jù)數(shù)組內(nèi)容判斷是否是二叉樹 ,.,算法設(shè)計(jì)練習(xí),算法描述: 樹的層次遍歷算法的改進(jìn)，用隊(duì)列來進(jìn)行層次遍歷，隊(duì)列用來存放每一層的結(jié)點(diǎn)，算法如下： i=0； 如果樹不為空，入隊(duì) While（隊(duì)不空） 隊(duì)首元素出隊(duì)，并賦給數(shù)組元素ai+； 如果隊(duì)首元素不為null，則將其左右孩子依次入隊(duì)； 遍歷數(shù)組a，如果出現(xiàn)某一個(gè)元素為空，但其后元素不為空，則可以立即判斷該二叉樹為非完全二叉樹,