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

.,第六章樹與二叉樹,,,數(shù)據(jù)結(jié)構(gòu),,.,一、樹的定義(Tree),2,樹是有n(n≥0)個(gè)結(jié)點(diǎn)的有限集合。 如果 n=0，稱為空樹； 如果 n>0,稱為非空樹,對于非空樹,有且僅有一個(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)的最大層次 森林：互不相交的樹的集合。 　對樹中每個(gè)結(jié)點(diǎn)而言， 　其子樹的集合即為森林 .有序樹:樹中各結(jié)點(diǎn)的子樹按照一定次序從左向右安排,相對次序不能改變,.,一、二叉樹(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=1 2.設(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 　 k 2.　∑ 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+n2 2.設(shè)B為二叉樹的分支數(shù)，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且只有一個(gè)分支，因此n=B+1 3.每個(gè)分支皆由度為1或2的結(jié)點(diǎn)發(fā)出，B=n1+2n2 4.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ù)編號,.,六、完全二叉樹,12,第二節(jié)　二叉樹,當(dāng)且僅當(dāng)每一個(gè)結(jié)點(diǎn)都與深度相同的滿二叉樹中編號從1到n的結(jié)點(diǎn)一一對應(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,.,七、二叉樹的順序存儲結(jié)構(gòu),15,第二節(jié)　二叉樹,用一組連續(xù)的存儲單元依次自上而下,自左至右存儲結(jié)點(diǎn),完全二叉樹的順序表示　　　　　一般二叉樹的順序表示,.,七、二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu),16,第二節(jié)　二叉樹,1.二叉鏈表 采用數(shù)據(jù)域加上左、右孩子指針,.,七、二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu),17,第二節(jié)　二叉樹,1.二叉鏈表(舉例) 二叉樹（左）及其二叉鏈表（右）,.,七、二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu),18,第二節(jié)　二叉樹,２.三叉鏈表 采用數(shù)據(jù)域加上左、右孩子指針及雙親指針,.,七、二叉樹的鏈?zhǔn)酱鎯Y(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*n 6. 在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹的第4層上，最多有(B )個(gè)結(jié)點(diǎn)。 A. 4 B.8 C.15 D.16 7. 在一棵深度為4的完全二叉樹中，所含結(jié)點(diǎn)個(gè)數(shù)不小于（A ）。 A.8 B.9 C.15 D.16 8. 在一棵深度為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). A．4 B.5 C.6 D.7 10. 在一棵完全二叉樹中，若編號為i的結(jié)點(diǎn)存在左孩子，則左孩子結(jié)點(diǎn)的編號為（ A ）。 A．2i B.2i-1 C.2i+1 D.2i+2 11. 在一棵完全二叉樹中，若編號為i的結(jié)點(diǎn)存在右孩子，則右孩子結(jié)點(diǎn)的編號為（C ）。 A．2i 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 *Stack[MAX_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=stack[top] ; 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 50 void LevelorderTraverse( BTNode *T) { BTNode *Queue[MAX_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é)　線索二叉樹,最簡單的方法是在每個(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)。,.,一、樹的存儲結(jié)構(gòu),46,第五節(jié)　樹與森林,1.雙親表示法 采用一組連續(xù)的存儲空間 由于每個(gè)結(jié)點(diǎn)只有一個(gè)雙親，只需要一個(gè)指針,0 1 2 3 4 5 6,.,一、樹的存儲結(jié)構(gòu),47,第五節(jié)　樹與森林,2.孩子表示法 可以采用多重鏈表，即每個(gè)結(jié)點(diǎn)有多個(gè)指針 特點(diǎn)：鏈表結(jié)構(gòu)簡單,指針域的數(shù)目就是樹的度。 最大缺點(diǎn):空鏈域太多,在一棵有n個(gè)結(jié)點(diǎn)， 度為k的樹中必有n(k-1)+1空指針域。,.,一、樹的存儲結(jié)構(gòu),48,第五節(jié)　樹與森林,2.孩子表示法 將每個(gè)結(jié)點(diǎn)的孩子排列起來，用單鏈表表示 將每個(gè)結(jié)點(diǎn)排列成一個(gè)線性表,0 1 2 3 4 5 6,,Root,,,,,,,.,一、樹的存儲結(jié)構(gòu),49,第五節(jié)　樹與森林,3.孩子兄弟表示法 采用二叉鏈表 左邊指針指向第一個(gè)孩子，右邊指針指向兄弟,.,二、樹與二叉樹的對應(yīng)關(guān)系,50,第五節(jié)　樹與森林,樹與二叉樹都可以采用二叉鏈表作存儲結(jié)構(gòu) 任意給定一棵樹，可以找到一個(gè)唯一的二叉樹(沒有右子樹),樹,對應(yīng)的二叉樹,.,三、森林與二叉樹的對應(yīng)關(guān)系,51,第五節(jié)　樹與森林,如果把森林中的第二棵樹的根結(jié)點(diǎn)看作是第一棵樹的根結(jié)點(diǎn)的兄弟，則可找到一個(gè)唯一的二叉樹與之對應(yīng),三棵樹的森林,對應(yīng)的二叉樹,T1 T2 T3,.,四、樹的遍歷,52,第五節(jié)　樹與森林,對樹的遍歷主要有兩種： 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. 二叉樹采用順序存儲結(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)之間的路徑 路徑長度：路徑上的分支數(shù)目 樹的路徑長度：從樹根到 　每個(gè)結(jié)點(diǎn)的路徑長度之和 右樹路徑長度為： 　2*1 + 3*2 + 1*3 = 11,.,一、最優(yōu)二叉樹,58,第六節(jié)　哈夫曼樹及其應(yīng)用,帶權(quán)路徑長度：從結(jié)點(diǎn)到樹根之間的路徑長度與結(jié)點(diǎn)上權(quán)的乘積 樹的帶權(quán)路徑長度(WPL)：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和 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)路徑長度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è)字符以等長編碼 O: 00 G: 10 _: 01 D: 11 則總編碼長度為 (2+7+4+5) * 2 = 36.,.,三、Huffman編碼,64,第六節(jié)　哈夫曼樹及其應(yīng)用,若按各個(gè)字符出現(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 = 35 Huffman是一種前綴編碼，解碼時(shí)不會混淆,.,第六節(jié)　哈夫曼樹及其應(yīng)用,void HuffmanCoding(HuffmanTree ,.,第六節(jié)　哈夫曼樹及其應(yīng)用,for (i=n+1; i<=m; i++) { // 建哈夫曼樹 // 在HT[1..i-1]中選擇parent為且weight最小的兩個(gè)結(jié)點(diǎn)， // 其序號分別為s1和s2。 Select(HT, i-1, s1, s2); HT[s1].parent = i; HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; printf("\nselect: s1=%d s2=%d\n", s1, s2); printf(" 結(jié)點(diǎn) weight parent lchild rchild"); for (j=1; j<=i; j++) printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight, HT[j].parent,HT[j].lchild, HT[j].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編碼并比較等長編碼的總編碼長度.,.,算法設(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; else h=hr; return(h＋1); //返回較大左右子樹深度加1 } else return(0); },.,算法設(shè)計(jì)練習(xí),[例2]求二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù) template int 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 a[100]; 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);   a[i++]=p;    if (p)    { EnQueue(myque,p->lchild); EnQueue(myque,p->rchild); }   } //層次遍歷，并進(jìn)行數(shù)組賦值 for(j=1;j<i;j++)   { if (!a[j])     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ù)組元素a[i++]； 如果隊(duì)首元素不為null，則將其左右孩子依次入隊(duì)； } 遍歷數(shù)組a，如果出現(xiàn)某一個(gè)元素為空，但其后元素不為空，則可以立即判斷該二叉樹為非完全二叉樹,