第六章樹和二叉樹,教學目的和要求,1、熟練掌握二叉樹的結構特點，了解相應的證明。2、熟悉二叉樹的各種存儲結構的特點及適用范圍。3、掌握二叉樹遍歷的遞歸與非遞歸算法。4、掌握二叉線索樹的相關算法。5、熟悉樹的各種存儲結構及特點，掌握樹和森林與二叉樹的方法。6、了解最優(yōu)樹的特性，掌握最優(yōu)樹和哈夫曼編碼的方法。,1數(shù)據(jù)的邏輯結構,2、數(shù)據(jù)的存儲結構,3、數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等。,A線性結構,B非線性結構,A順序存儲,B鏈式存儲,線性表,棧,隊,樹形結構,圖形結構,數(shù)據(jù)結構的三個主要問題,樹形結構,全校學生檔案管理的組織方式,樹形結構結點間具有分層次的連接關系,6.1樹的類型定義,6.2二叉樹的類型定義,6.3二叉樹的存儲結構,6.4二叉樹的遍歷,6.5線索二叉樹,6.6樹和森林的表示方法,6.7樹和森林的遍歷,6.8哈夫曼樹與哈夫曼編碼,6.1樹的類型定義,數(shù)據(jù)對象D：,D是具有相同特性的數(shù)據(jù)元素的集合。,若D為空集，則稱為空樹。否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；(2)當n>1時，其余結點可分為m(m>0)個互不相交的有限集T1,T2,Tm，其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。,數(shù)據(jù)關系R：,A,B,C,D,E,F,G,H,I,J,M,K,L,A(B(E,F(K,L),C(G),D(H,I,J(M),T1,T3,T2,樹根,例如:,基本操作：,查找類,插入類,刪除類,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()/遍歷,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();,InitBiTree(,ClearBiTree(,二叉樹的重要特性,性質(zhì)1：在二叉樹的第i層上至多有2i-1個結點。(i1),用歸納法證明：歸納基：歸納假設：歸納證明：,i=1層時，只有一個根結點：2i-1=20=1；,假設對所有的j，1ji，命題成立；,二叉樹上每個結點至多有兩棵子樹，則第i層的結點數(shù)=2i-22=2i-1。,性質(zhì)2：深度為k的二叉樹上至多含2k-1個結點（k1）。,證明：,基于上一條性質(zhì)，深度為k的二叉樹上的結點數(shù)至多為20+21+2k-1=2k-1。,性質(zhì)3：對任何一棵二叉樹，若它含有n0個葉子結點、n2個度為2的結點，則必存在關系式：n0=n2+1。,證明：,設二叉樹上結點總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)b=n1+2n2而b=n-1=n0+n1+n2-1由此，n0=n2+1。,兩類特殊的二叉樹：,滿二叉樹：指的是深度為k且含有2k-1個結點的二叉樹。,完全二叉樹：樹中所含的n個結點和滿二叉樹中編號為1至n的結點一一對應。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,a,b,c,d,e,f,g,h,i,j,性質(zhì)4：具有n個結點的完全二叉樹的深度為log2n+1。,證明：,設完全二叉樹的深度為k則根據(jù)第二條性質(zhì)得2k-1n<2k即k-1log2nn，則該結點無左孩子，否則，編號為2i的結點為其左孩子結點；(3)若2i+1>n，則該結點無右孩子結點，否則，編號為2i+1的結點為其右孩子結點。,6.3二叉樹的存儲結構,二、二叉樹的鏈式存儲表示,一、二叉樹的順序存儲表示,#defineMAX_TREE_SIZE100/二叉樹的最大結點數(shù)typedefTElemTypeSqBiTreeMAX_TREE_SIZE;/0號單元存儲根結點SqBiTreebt;,一、二叉樹的順序存儲表示,例如:,A,B,C,D,E,F,ABDCEF,012345678910111213,1,4,0,13,2,6,順序存儲結構僅適用于完全二叉樹！,二、二叉樹的鏈式存儲表示,1.二叉鏈表,2三叉鏈表,3雙親鏈表,4線索鏈表,A,D,E,B,C,F,root,lchilddatarchild,結點結構:,1.二叉鏈表,typedefstructBiTNode/結點結構TElemTypedata;structBiTNode*lchild,*rchild;/左右孩子指針BiTNode,*BiTree;,lchilddatarchild,結點結構:,C語言的類型描述如下:,A,D,E,B,C,F,root,2三叉鏈表,parentlchilddatarchild,結點結構:,typedefstructTriTNode/結點結構TElemTypedata;structTriTNode*lchild,*rchild;/左右孩子指針structTriTNode*parent;/雙親指針TriTNode,*TriTree;,parentlchilddatarchild,結點結構:,C語言的類型描述如下:,0123456,dataparent,結點結構:,3雙親鏈表,LRTag,LRRRL,typedefstructBPTNode/結點結構TElemTypedata;int*parent;/指向雙親的指針charLRTag;/左、右孩子標志域BPTNodetypedefstructBPTree/樹結構BPTNodenodesMAX_TREE_SIZE;intnum_node;/結點數(shù)目introot;/根結點的位置BPTree,6.4二叉樹的遍歷,一、問題的提出,二、先左后右的遍歷算法,三、算法的遞歸描述,四、中序遍歷算法的非遞歸描述,五、遍歷算法的應用舉例,順著某一條搜索路徑巡訪二叉樹中的結點，使得每個結點均被訪問一次，而且僅被訪問一次。,一、問題的提出,“訪問”的含義可以很廣，如：輸出結點的信息等。,“遍歷”是任何類型均有的操作，對線性結構而言，只有一條搜索路徑(因為每個結點均只有一個后繼)，故不需要另加討論。而二叉樹是非線性結構，,每個結點有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。,對“二叉樹”而言，可以有三條搜索路徑：,1先上后下的按層次遍歷；2先左（子樹）后右（子樹）的遍歷；3先右（子樹）后左（子樹）的遍歷。,二、先左后右的遍歷算法,先序（根）的遍歷算法,中序（根）的遍歷算法,后序（根）的遍歷算法,若二叉樹為空樹，則空操作；否則，（1）訪問根結點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。,先序（根）的遍歷算法：,若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結點；（3）中序遍歷右子樹。,中序（根）的遍歷算法：,若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結點。,后序（根）的遍歷算法：,課堂提問：,有以下結構的二叉樹寫出其先序、中序和后序遍歷的序列,三、算法的遞歸描述,voidPreorder(BiTreeT,void(*visit)(TElemType/遍歷右子樹,四、中序遍歷算法的非遞歸描述,BiTNode*GoFarLeft(BiTreeT,Stack*S)if(!T)returnNULL;while(T->lchild)Push(S,T);T=T->lchild;returnT;,voidInorder_I(BiTreeT,void(*visit)(TelemType/?？毡砻鞅闅v結束/while/Inorder_I,五、遍歷算法的應用舉例,1、統(tǒng)計二叉樹中葉子結點的個數(shù)(先序遍歷),2、求二叉樹的深度(后序遍歷),3、復制二叉樹(后序遍歷),4、建立二叉樹的存儲結構,1、統(tǒng)計二叉樹中葉子結點的個數(shù),算法基本思想:,先序(或中序或后序)遍歷二叉樹，在遍歷過程中查找葉子結點，并計數(shù)。由此，需在遍歷算法中增添一個“計數(shù)”的參數(shù)，并將算法中“訪問結點”的操作改為：若是葉子，則計數(shù)器增1。,voidCountLeaf(BiTreeT,int/if/CountLeaf,2、求二叉樹的深度(后序遍歷),算法基本思想:,從二叉樹深度的定義可知，二叉樹的深度應為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，算法中“訪問結點”的操作為：求得左、右子樹深度的最大值，然后加1。,首先分析二叉樹的深度和它的左、右子樹深度之間的關系。,intDepth(BiTreeT)/返回二叉樹的深度if(!T)depthval=0;elsedepthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);depthval=1+(depthLeft>depthRight?depthLeft:depthRight);returndepthval;,3、復制二叉樹,其基本操作為：生成一個結點。,根元素,T,左子樹,右子樹,根元素,NEWT,左子樹,右子樹,左子樹,右子樹,(后序遍歷),BiTNode*GetTreeNode(TElemTypeitem,BiTNode*lptr,BiTNode*rptr)if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T->data=item;T->lchild=lptr;T->rchild=rptr;returnT;,生成一個二叉樹的結點(其數(shù)據(jù)域為item,左指針域為lptr,右指針域為rptr),BiTNode*CopyTree(BiTNode*T)if(!T)returnNULL;if(T->lchild)newlptr=CopyTree(T->lchild);/復制左子樹elsenewlptr=NULL;if(T->rchild)newrptr=CopyTree(T->rchild);/復制右子樹elsenewrptr=NULL;newT=GetTreeNode(T->data,newlptr,newrptr);returnnewT;/CopyTree,A,B,C,D,E,F,G,H,K,D,C,B,H,K,G,F,E,A,例如：下列二叉樹的復制過程如下：,newT,4、建立二叉樹的存儲結構,不同的定義方法相應有不同的存儲結構的建立算法,以字符串“A!”表示,以字符串的形式根左子樹右子樹定義一棵二叉樹,例如:,A,B,C,D,以字符“!”表示,A(B(!,C(!,!),D(!,!),空樹,只含一個根結點的二叉樹,A,以下列字符串表示,StatusCreateBiTree(BiTree/CreateBiTree,僅知二叉樹的先序序列“abcdefg”不能唯一確定一棵二叉樹，,由二叉樹的先序和中序序列建樹,如果同時已知二叉樹的中序序列“cbdaegf”，則會如何？,二叉樹的先序序列,二叉樹的中序序列,左子樹,左子樹,右子樹,右子樹,根,根,abcdefg,cbdaegf,例如:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,voidCrtBT(BiTreeelse/CrtBT,T=(BiTNode*)malloc(sizeof(BiTNode);T->data=preps;if(k=is)T->Lchild=NULL;elseCrtBT(T->Lchild,pre,ino,ps+1,is,k-is);if(k=is+n-1)T->Rchild=NULL;elseCrtBT(T->Rchild,pre,ino,ps+(k-is)+1,k+1,n-(k-is)-1);,練習題：,1、編寫遞歸算法，將二叉樹中所有結點的左、右子樹交換。2、編寫遞歸算法：對于二叉樹中每一個元素值為x的結點，刪除以它為根的子樹，并釋放相應的空間。3、編寫按層次順序（同一層自左至右）遍歷二叉樹的算法。,6.5線索二叉樹,何謂線索二叉樹？線索鏈表的遍歷算法如何建立線索鏈表？,一、何謂線索二叉樹？,遍歷二叉樹的結果是，求得結點的一個線性序列。,A,B,C,D,E,F,G,H,K,例如:,先序序列:ABCDEFGHK,中序序列:BDCAHGKFE,后序序列:DCBHKGFEA,指向該線性序列中的“前驅(qū)”和“后繼”的指針，稱作“線索”,與其相應的二叉樹，稱作“線索二叉樹”,包含“線索”的存儲結構，稱作“線索鏈表”,ABCDEFGHK,D,C,B,E,對線索鏈表中結點的約定：,在二叉鏈表的結點中增加兩個標志域，并作如下規(guī)定：,若該結點的左子樹不空，則Lchild域的指針指向其左子樹，且左標志域的值為“指針Link”；否則，Lchild域的指針指向其“前驅(qū)”，且左標志的值為“線索Thread”。,若該結點的右子樹不空，則rchild域的指針指向其右子樹，且右標志域的值為“指針Link”；否則，rchild域的指針指向其“后繼”，且右標志的值為“線索Thread”。,如此定義的二叉樹的存儲結構稱作“線索鏈表”。,typedefstructBiThrNodTElemTypedata;structBiThrNode*lchild,*rchild;/左右指針PointerThrLTag,RTag;/左右標志BiThrNode,*BiThrTree;,線索鏈表的類型描述：,typedefenumLink,ThreadPointerThr;/Link=0:指針，Thread=1:線索,二、線索鏈表的遍歷算法:,for(p=firstNode(T);p;p=Succ(p)Visit(p);,由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡化了遍歷的算法。,例如:對中序線索化鏈表的遍歷算法,中序遍歷的第一個結點？,在中序線索化鏈表中結點的后繼？,左子樹上處于“最左下”（沒有左子樹）的結點。,若無右子樹，則為后繼線索所指結點；,否則為對其右子樹進行中序遍歷時訪問的第一個結點。,voidInOrderTraverse_Thr(BiThrTreeT,void(*Visit)(TElemTypee)p=T->lchild;/p指向根結點while(p!=T)/空樹或遍歷結束時，p=Twhile(p->LTag=Link)p=p->lchild;/第一個結點if(!Visit(p->data)returnERROR;while(p->RTag=Thread/p進至其右子樹根/InOrderTraverse_Thr,在中序遍歷過程中修改結點的左、右指針域，以保存當前訪問結點的“前驅(qū)”和“后繼”信息。遍歷過程中，附設指針pre,并始終保持指針pre指向當前訪問的、指針p所指結點的前驅(qū)。,三、如何建立線索鏈表？,voidInThreading(BiThrTreep)if(p)/對以p為根的非空二叉樹進行線索化InThreading(p->lchild);/左子樹線索化if(!p->lchild)/建前驅(qū)線索p->LTag=Thread;p->lchild=pre;if(!pre->rchild)/建后繼線索pre->RTag=Thread;pre->rchild=p;pre=p;/保持pre指向p的前驅(qū)InThreading(p->rchild);/右子樹線索化/if/InThreading,StatusInOrderThreading(BiThrTree/InOrderThreading,if(!T)Thrt->lchild=Thrt;elseThrt->lchild=T;pre=Thrt;InThreading(T);pre->rchild=Thrt;/處理最后一個結點pre->RTag=Thread;Thrt->rchild=pre;,6.6樹和森林的表示方法,6.6.1樹的三種存儲結構,一、雙親表示法,二、孩子鏈表表示法,三、樹的二叉鏈表(孩子-兄弟）存儲表示法,A,B,C,D,E,F,G,0A-11B02C03D04E25F26G5,r=0n=6,dataparent,一、雙親表示法:,typedefstructPTNodeElemdata;intparent;/雙親位置域PTNode;,dataparent,#defineMAX_TREE_SIZE100,結點結構:,C語言的類型描述:,typedefstructPTNodenodesMAX_TREE_SIZE;intr,n;/根結點的位置和結點個數(shù)PTree;,樹結構:,A,B,C,D,E,F,G,0A-11B02C03D04E25F26G4,r=0n=6,datafirstchild,123,45,6,二、孩子鏈表表示法:,typedefstructCTNodeintchild;structCTNode*next;*ChildPtr;,孩子結點結構:,childnext,C語言的類型描述:,typedefstructElemdata;ChildPtrfirstchild;/孩子鏈的頭指針CTBox;,雙親結點結構,datafirstchild,typedefstructCTBoxnodesMAX_TREE_SIZE;intn,r;/結點數(shù)和根結點的位置CTree;,樹結構:,A,B,C,D,E,F,G,ABCEDFG,root,ABCEDFG,三、樹的二叉鏈表(孩子-兄弟）存儲表示法,typedefstructCSNodeElemdata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;,C語言的類型描述:,結點結構:,firstchilddatanextsibling,6.6.2森林和二叉樹的轉(zhuǎn)換,設森林F=(T1,T2,Tn);T1=(root，t11,t12,t1m);,二叉樹B=(LBT,Node(root),RBT);,由于二叉樹可以用二叉鏈表表示，為了使一般樹也能用二叉鏈表表示，必須找出樹與二叉樹之間的關系。這樣，給定一棵樹，可以找到唯一的一棵二叉樹與之對應。方法：對每個孩子進行從左到右的排序；在兄弟之間加一條連線；對每個結點，除了左孩子外，去除其與其余孩子之間的聯(lián)系；以根結點為軸心，將整個樹順時針轉(zhuǎn)45度。,1、將樹轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為:,樹轉(zhuǎn)換為二叉樹,2、由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為:,若F=，則B=；否則，由ROOT(T1)對應得到Node(root)；由(t11,t12,t1m)對應得到LBT；由(T2,T3,Tn)對應得到RBT。,森林轉(zhuǎn)換為二叉樹,3、由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為：,若B=，則F=；否則，由Node(root)對應得到ROOT(T1)；由LBT對應得到(t11,t12,，t1m)；由RBT對應得到(T2,T3,Tn)。,將二叉樹轉(zhuǎn)換成樹或森林的方法如下：1.若某結點是其雙親的左孩子,則把該結點的右孩子、右孩子的右孩子都與該結點的雙親結點用線連起來;2.刪除原二叉樹中所有的雙親結點與右孩子結點的連線.3.整理步驟1、2所得到的樹或森林,使結構層次分明.,將二叉樹轉(zhuǎn)換為樹或森林的另一種描述：,將二叉樹轉(zhuǎn)換為樹或森林,若某結點是其雙親的左孩子,則把該結點的右孩子、右孩子的右孩子都與該結點的雙親結點用線連起來;,刪除原二叉樹中所有的雙親結點與右孩子結點的連線.,由此，樹的各種操作均可對應二叉樹的操作來完成。,應當注意的是，和樹對應的二叉樹，其左、右子樹的概念已改變?yōu)椋鹤笫呛⒆?，右是兄弟?6.7樹和森林的遍歷,一、樹的遍歷,二、森林的遍歷,三、樹的遍歷的應用,樹的遍歷可有三條搜索路徑:,按層次遍歷:,先根(次序)遍歷:,后根(次序)遍歷:,若樹不空，則先訪問根結點，然后依次先根遍歷各棵子樹。,若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結點。,若樹不空，則自上而下自左至右訪問樹中每個結點。,ABCDEFGHIJK,先根遍歷時頂點的訪問次序：,ABEFCDGHIJK,后根遍歷時頂點的訪問次序：,EFBCIJKHGDA,層次遍歷時頂點的訪問次序：,ABCDEFGHIJK,BCDEFGHIJK,1森林中第一棵樹的根結點；,2森林中第一棵樹的子樹森林；,3森林中其它樹構成的森林。,森林由三部分構成：,若森林不空，則訪問森林中第一棵樹的根結點；先序遍歷森林中第一棵樹的子樹森林；先序遍歷森林中(除第一棵樹之外)其余樹構成的森林。,1.先序遍歷,森林的遍歷,即：依次從左至右對森林中的每一棵樹進行先根遍歷。,中序遍歷,若森林不空，則中序遍歷森林中第一棵樹的子樹森林；訪問森林中第一棵樹的根結點；中序遍歷森林中(除第一棵樹之外)其余樹構成的森林。,即：依次從左至右對森林中的每一棵樹進行后根遍歷。,樹的遍歷和二叉樹遍歷的對應關系？,先根遍歷,后根遍歷,樹,二叉樹,森林,先序遍歷,先序遍歷,中序遍歷,中序遍歷,設樹的存儲結構為孩子兄弟鏈表,typedefstructCSNodeElemdata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;,一、求樹的深度,二、輸出樹中所有從根到葉子的路徑,三、建樹的存儲結構,intTreeDepth(CSTreeT)if(!T)return0;elseh1=TreeDepth(T->firstchild);h2=TreeDepth(T->nextsibling);/TreeDepth,return(max(h1+1,h2);,一、求樹的深度的算法：,二、輸出樹中所有從根到葉子的路徑的算法:,ABCDEFGHIJK,例如：對左圖所示的樹，其輸出結果應為：,ABEABFACADGHIADGHJADGHK,voidAllPath(BitreeT,Stack/if(T)/AllPath,/輸出二叉樹上從根到所有葉子結點的路徑,voidOutPath(BitreeT,Stack/while/OutPath,/輸出森林中所有從根到葉的路徑,三、建樹的存儲結構的算法:,和二叉樹類似，不同的定義相應有不同的算法。,假設以二元組(F，C)的形式自上而下、自左而右依次輸入樹的各邊，建立樹的孩子-兄弟鏈表。,A,B,C,D,E,F,G,例如:,對下列所示樹的輸入序列應為:,(#,A)(A,B)(A,C)(A,D)(C,E)(C,F)(E,G),A,B,C,D,(#,A),(A,B),(A,C),(A,D),(C,E),可見，算法中需要一個隊列保存已建好的結點的指針。,voidCreatTree(CSTree/所建為根結點else/非根結點的情況/for/CreateTree,GetHead(Q,s);/取隊列頭元素(指針值)while(s->data!=fa)/查詢雙親結點DeQueue(Q,s);GetHead(Q,s);if(!(s->firstchild)s->firstchild=p;r=p;/鏈接第一個孩子結點elser->nextsibling=p;r=p;/鏈接其它孩子結點,6.8哈夫曼樹與哈夫曼編碼,最優(yōu)樹的定義如何構造最優(yōu)樹前綴編碼,一、最優(yōu)樹的定義,樹的路徑長度定義為：樹中每個結點的路徑長度之和。,結點的路徑長度定義為：從根結點到該結點的路徑上分支的數(shù)目。,1,2,4,5,3,6,7,PL=0+1+1+2+2+2+2=10,樹的路徑長度用PL表示。,1,2,4,5,C,6,7,PL=0+1+1+2+2+3+3=12,樹的帶權路徑長度定義為：樹中所有葉子結點的帶權路徑長度之和WPL(T)=wklk(對所有葉子結點)。其中：Wk為樹中每個葉子結點的權；Lk為每個葉子結點到根的路徑長度。,例如：,2,79,7,5,4,9,2,WPL(T)=72+52+23+43+92=60,WPL(T)=74+94+53+42+21=89,5,4,最優(yōu)樹,在所有含n個葉子結點、并帶相同權值的m叉樹中，必存在一棵其帶權路徑長度取最小值的樹，稱為“最優(yōu)樹”。,由原始數(shù)據(jù)生成森林根據(jù)給定的n個權值w1,w2,wn，構造n棵二叉樹的集合F=T1,T2,Tn，其中每棵二叉樹中均只含一個帶權值為wi的根結點,其左、右子樹為空樹；,二、如何構造最優(yōu)樹,(1),(赫夫曼算法)以二叉樹為例：,在F中選取其根結點的權值為最小的兩棵二叉樹，分別作為左、右子樹構造一棵新的二叉樹，并置這棵新的二叉樹根結點的權值為其左、右子樹根結點的權值之和；,(2),從F中刪去這兩棵樹，同時加入剛生成的新樹；,重復(2)和(3)兩步，直至F中只含一棵樹為止。,(3),(4),例：給定權值7，5，2，4，構造赫夫曼樹。,9,例:已知權值W=5,6,2,9,7,構造赫夫曼樹。,5,6,2,7,5,2,7,6,9,7,6,7,13,9,5,2,7,6,7,13,9,5,2,7,9,5,2,7,16,6,7,13,29,0,0,0,0,1,1,1,1,00,01,10,110,111,三、哈夫曼樹的應用,1、判定樹在解決某些判定問題時，利用哈夫曼樹可以得到最佳判定算法。例1將學生百分成績按分數(shù)段分級的程序。若學生成績分布是均勻的，可用圖（a)二叉樹結構來實現(xiàn)。,輸入10000個數(shù)據(jù)，則需進行31500次比較。,(b),學生成績分布不是均勻的情況：,以比例數(shù)為權構造一棵哈夫曼樹，如（b)判斷樹所示。,再將每一比較框的兩次比較改為一次，可得到（c)判定樹。,輸入10000個數(shù)據(jù)，僅需進行22000次比較。,2、前綴編碼,“前綴編碼”指的是，任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴。,3、赫夫曼編碼,利用赫夫曼樹可以構造一種不等長的二進制編碼，并且構造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長度最短。,各字符編碼是T；ACS000110110111上述電文編碼：11010111011101000011111000011000,方法：（1）用2，4，2，3，3作為葉子結點的權值生成一棵赫夫曼樹，并將對應權值wi的葉子結點注明對應的字符；（2）約定左分支表示字符“0”，右分支表示字符1（3）從葉子結點開始，順著雙親反推上去，直到根結點，路徑上的0或1連接的序列就是結點對應的字符的二進制編碼的逆序。,赫夫曼編碼-利用赫夫曼樹構造通訊中電文編碼（前綴碼）例：要傳輸?shù)碾娢氖荂AS；CAT；SAT；AT要傳輸?shù)淖址荄=C，A，S，T，；每個字符出現(xiàn)的頻率是W=2，4，2，3，3,注意：編碼的總長度恰好為赫夫曼樹的帶權路徑長。,構造赫夫曼樹的算法,為了實現(xiàn)構造赫夫曼樹的算法,設計哈夫曼樹中每個結點類型如下：typedefstructchardata;/*結點值*/floatweight;/*權重*/intparent;/*雙親結點*/intlchild;/*左孩子結點*/intrchild;/*右孩子結點*/HTNode,*HuffmanTree;,