數(shù)據(jù)結構第六章.ppt

1、數(shù)據(jù)結構課程的內(nèi)容,1,第6章 樹和二叉樹（ Tree 且前9層總結點數(shù)為29-1=511 (完全二叉樹的前k-1層肯定是滿的) 所以末層葉子數(shù)為1000-511=489個。,24,請注意葉子結點總數(shù)末層葉子數(shù)！ 還應當加上第k-1層（靠右邊）的0度結點個數(shù)。 分析：末層的489個葉子只占據(jù)了上層的245個結點（489/2 ) 上層（k=9)右邊的0度結點數(shù)還有29-1-245=11個！,另一法：可先求2度結點數(shù),再由此得到葉子總數(shù)。 首先，k-2層的28-1（255）個結點肯定都是2度的（完全二叉） 另外，末層葉子（剛才已求出為489）所對應的雙親也是度2， （共有489/2244個）。 所

2、以，全部2度結點數(shù)為255(k-2層)244(k-1層)=499個； 總?cè)~子數(shù)2度結點數(shù)1=500個。,第i層上的滿結點數(shù)為2i-1,所以， 全部葉子數(shù)489(末層)11(k-1層)=500個。 度為2的結點葉子總數(shù)1=499個。,3. 二叉樹的存儲結構,25,一、順序存儲結構 按二叉樹的結點“自上而下、從左至右”編號，用一組連續(xù)的存儲單元存儲。,A B C D E F G H I,問：順序存儲后能否復原成唯一對應的二叉樹形狀？ 答：若是完全/滿二叉樹則可以做到唯一復原。 而且有規(guī)律：下標值為i的雙親，其左孩子的下標值必為2i，其右孩子的下標值必為2i1（即性質(zhì)5） 例如，對應2的兩個孩子必為

3、4和5,即B的左孩子必是D,右孩子必為E。,T0一般不用,討論：不是完全二叉樹怎么辦？,26,答：一律轉(zhuǎn)為完全二叉樹！ 方法很簡單，將各層空缺處統(tǒng)統(tǒng)補上“虛結點”，其內(nèi)容為空。,A B C D E,缺點：浪費空間；插入、刪除不便,二、鏈式存儲結構用二叉鏈表即可方便表示。,27,二叉樹結點數(shù)據(jù)類型定義： typedef struct node *tree_pointer; typedef struct node int data; tree_pointer left_child, right_child; node;,一般從根結點開始存儲。（相應地，訪問樹中結點時也只能從根開始） 注：如果需要倒

4、查某結點的雙親，可以再增加一個雙親域（直接前趨）指針，將二叉鏈表變成三叉鏈表。,例：,28,6.3 遍歷二叉樹和線索二叉樹,29,一、遍歷二叉樹（Traversing Binary Tree）,遍歷定義指按某條搜索路線遍訪每個結點且不重復（又稱周游）。 遍歷用途它是樹結構插入、刪除、修改、查找和排序運算的前提，是二叉樹一切運算的基礎和核心。 遍歷方法牢記一種約定，對每個結點的查看都是“先左后右” 。,30,遍歷規(guī)則,二叉樹由根、左子樹、右子樹構成，定義為D、 L、R D、 L、R的組合定義了六種可能的遍歷方案： LDR, LRD, DLR, DRL, RDL, RLD 若限定先左后右，則有三種

5、實現(xiàn)方案： DLR LDR LRD 先 (根)序遍歷 中 (根)序遍歷 后(根)序遍歷 注：“先、中、后”的意思是指訪問的結點D是先于子樹出現(xiàn)還是后于子樹出現(xiàn)。,例1：,31,先序遍歷的結果是： 中序遍歷的結果是： 后序遍歷的結果是：,A B D E C D B E A C D E B C A,口訣： DLR先序遍歷，即先根再左再右 LDR中序遍歷，即先左再根再右 LRD后序遍歷，即先左再右再根,例2：用二叉樹表示算術表達式,32,先序遍歷 + * * / A B C D E 前綴表達式 中序遍歷 A / B * C * D + E 中綴表達式 后序遍歷 A B / C * D * E + 后

6、綴表達式 層序遍歷 + * E * D / C A B,遍歷的算法實現(xiàn)：,33,回憶1：二叉樹結點的數(shù)據(jù)類型定義： typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode,*BitTree;,34,1）先序遍歷二叉樹 算法思想: 若二叉樹非空，則： 1）訪問根結點 2）先序遍歷左子樹 3）先序遍歷右子樹,算法描述: void Preorder (BiTree bt) /bt為根結點指針 if( bt) /根非空 visit (bt-data)； Preorder (bt-lchild) ;

7、Preorder (bt-rchild) ; ,二叉樹的遍歷,1）中序遍歷二叉樹 算法思想: 若二叉樹非空，則： 1）中序遍歷左子樹 2）訪問根結點 3）中序遍歷右子樹,算法描述: void Inorder (BiTree bt) /bt為根結點指針 if( bt) /根非空 Inorder (bt-lchild) ; visit (bt-data)； Inorder (bt-rchild) ; ,36,2）后序遍歷二叉樹 算法思想: 若二叉樹非空，則： 1）后序遍歷左子樹 2）后序遍歷右子樹 3）訪問根結點,算法描述: void Postorder (BiTree bt) /bt為根結點指針

8、 if( bt) /根非空 Postorder (bt-lchild) ; Postorder (bt-rchild) ; visit (bt -data)； ,對遍歷的分析：,37,1. 從前面的三種遍歷算法可以知道：如果將print語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的訪問路徑是相同的，只是訪問結點的時機不同。,從虛線的出發(fā)點到終點的路徑 上，每個結點經(jīng)過3次。,第1次經(jīng)過時訪問先序遍歷 第2次經(jīng)過時訪問中序遍歷 第3次經(jīng)過時訪問后序遍歷,2. 二叉樹遍歷的時間效率和空間效率 時間效率:O(n) /每個結點只訪問一次 空間效率:O(n) /棧占用的最大輔助

9、空間 （精確值：樹深為k的遞歸遍歷需要k+1個輔助單元?。?38,知識回顧： （1）二叉樹的存儲： 順序存儲方式： 完全二叉樹 滿二叉樹 一般樹補充成的完全二叉樹或滿二叉樹 鏈式存儲方式：適用于各種樹 （2）二叉樹的遍歷： 先序遍歷、中序遍歷、后序遍歷、層序遍歷,39,A,B,J,I,D,C,G,F,E,H,1、先序遍歷的結果為：,2、中序遍歷的結果為：,3、后序遍歷的結果為：,A B D H E C F I G J,D H B E A F I C J G,H D E B I F J G C,特點：先訪問根， 再遍歷左子樹， 再遍歷右子樹,特點：先遍歷左子樹， 再訪問根， 再遍歷右子樹,特點：

10、 先遍歷左子樹， 再遍歷右子樹 最后訪問根，,注：要實現(xiàn)遍歷運算必須先把二叉樹存入機內(nèi)。,40,思路：利用前序遍歷來建樹 （結點值陸續(xù)從鍵盤輸入，用DLR為宜） Status createBiTree( BiTree ,怎樣建樹？見教材P131程序。,例：編寫遞歸算法，計算二叉樹中葉子結點的數(shù)目。,41,思路：輸出葉子結點比較簡單，用任何一種遍歷算法，凡是左右指針均空者，則為葉子，將其統(tǒng)計并打印出來。,DLR(BiTree *root) if ( root!=NULL ) if(!root-lchild /遞歸遍歷右子樹，直到葉子處； ,習題討論：,42,1. 求二叉樹深度，或從x結點開始的子

11、樹深度。 算法思路：只查各結點后繼鏈表指針，若左(右)孩子的左(右)指針非空，則層次數(shù)加1；否則函數(shù)返回。,Height=max(hl,hr)+1,43,后序遍歷求二叉樹的高度遞歸算法： Int PostTreeDepth(BiTree bt) int hl,hr,max; if(bt!=NULL) hl=PostTreeDepth（bt-Lchild); /求左子樹的深度 hr=PostTreeDepth(bt-Rchild); /求右子樹的深度 max=hlhr?hl:hr; /*得到左、右子樹深度較大者*/ return (max+1); /*返回樹的深度*/ else return 0

12、; ,44,2. 按層次輸出二叉樹中所有結點。 算法思路：既然要求從上到下，從左到右，則利用隊列存放各子樹結點的指針是個好辦法，而不必拘泥于遞歸算法。 技巧：當根結點出隊后，令其左、右孩子結點入隊，而左孩子出隊時又令它的左右孩子結點入隊，由此便可產(chǎn)生按層次輸出的效果。,Void Layout(BiTree root) EnQueue(s,root); While(!QueueEmpty(s) DeQueue(s,p); printf(“%c”,s-data); EnQueue(s,p-lchild); EnQueue(s,p-rchild); ,6.3.3 遍歷的非遞歸(迭代)算法以中序遍歷,

13、45,算法思路：若不用遞歸，則要實現(xiàn)二叉樹遍歷的“嵌套”規(guī)則，必用堆棧?？芍苯佑脀hile語句和push/pop操作。參見教材P130-131程序。,在中序遍歷中，我們是通過順著左子樹的根直走到最左端，然后訪問最左端元素，遍歷右，再返回上一層，訪問結點，遍歷右，然后再訪問上一層，這樣又順著左子樹的根回到A。 在遞歸調(diào)用中，返回上一層的操作是通過調(diào)用函數(shù)執(zhí)行結束自然返回上一層的。如果不用遞歸，如何返回上一層。 先從A走到F，在從F返回到A，最后走到的先訪問，所以可以用棧。 把根和左子樹的根全部入棧 然后判斷是否有右子樹，如果有，則遍歷右子樹，,46,知識回顧：,1、按層遍歷,Void Layou

14、t(BiTree root) EnQueue(s,root); While(!QueueEmpty(s) DeQueue(s,p); printf(“%c”,root-data); EnQueue(s,p-lchild); EnQueue(s,p-rchild); ,47,2、非遞歸中序遍歷,首先走到最左邊（肯定沒有左子樹） 接著訪問根節(jié)點 再非遞歸中序遍歷右子樹,Status NoInOrderTraverse(BiTree T) InitStack( ,48,2、非遞歸先序遍歷,Status NoInOrderTraverse(BiTree T) InitStack( ,49,2、非遞歸后

15、序遍歷,Status NoPostTraverse(BiTree T) InitStack( ,50,知識回顧：,二叉樹的建立 二叉樹的應用： （1）求二叉樹葉子節(jié)點的個數(shù) （2）求二叉樹的深度 非遞歸遍歷二叉樹 （1）層序遍歷二叉樹 （2）非遞歸先序遍歷二叉樹 （3）非遞歸中序遍歷二叉樹 （4）非遞歸后序遍歷二叉樹,特別討論：若已知先序/后序遍歷結果和中序遍歷結果，能否“恢復”出二叉樹？,證明：由一棵二叉樹的先序序列和中序序列可唯一確定這棵二叉樹。,51,例：已知一棵二叉樹的中序序列和后序序列分別是BDCEAFHG 和 DECBHGFA，請畫出這棵二叉樹。 分析： 由后序遍歷特征，根結點必在

16、后序序列尾部（即A）； 由中序遍歷特征，根結點必在其中間，而且其左部必全部是左子樹子孫（即BDCE），其右部必全部是右子樹子孫（即FHG）； 繼而，根據(jù)后序中的DECB子樹可確定B為A的左孩子，根據(jù)HGF子串可確定F為A的右孩子；以此類推。,中序遍歷：B D C E A F H G后序遍歷：D E C B H G F A,52,（B D C E）,（ F H G）,A,B,F,（D C E）,（ H G）,C,D E,G,H,A,B,B,F,F,2020/9/1,53,6.3.2 線索二叉樹 問題的提出：通過遍歷二叉樹可得到結點的一個線性序列，在線性序列中，很容易求得某個結點的直接前驅(qū)和后繼。

17、,例如中序遍歷結果：B D C E A F H G，實際上已將二叉樹轉(zhuǎn)為線性排列，顯然具有唯一前驅(qū)和唯一后繼！,但是在二叉樹上只能找到結點的左孩子、右孩子，結點的前驅(qū)和后繼只有在遍歷過程中才能得到，那么，如何保存遍歷二叉樹后動態(tài)得到的線性序列，以便快速找到某個結點的直接前驅(qū)和后繼？,增加兩個標志域，一個指向前驅(qū)、一個指向后繼。這樣使結構的存儲密度大大降低。,54,置空,置空,置空,置空,55,2. 分析： n個結點有n-1個前驅(qū)和n-1個后繼； 一共有2n個鏈域，其中：n+1個空鏈域，n-1個指針域； 因此, 可以用空鏈域來存放結點的前驅(qū)和后繼。 線索二叉樹就是利用n+1個空鏈域來存放結點的前

18、驅(qū)和后繼結點的信息。 3. 線索二叉樹： 有效利用二叉鏈表中空的存儲空間，指定原有的孩子指針為空的域來存放指向前驅(qū)和后繼的信息，這樣的指針被稱為“線索”。加線索的過程稱為線索化，由此得到的二叉樹稱作線索二叉樹。 (1),規(guī) 定：,1）若結點有左子樹，則lchild指向其左孩子； 否則， lchild指向其直接前驅(qū)(即線索)；,2）若結點有右子樹，則rchild指向其右孩子； 否則， rchild指向其直接后繼(即線索) 。,56,為了避免混淆，增加兩個標志域，如下圖所示：,約定:,當Tag域為0時,表示正常情況;,當Tag域為1時,表示線索情況.,注：在線索化二叉樹中，并不是每個結點都能直接找

19、到其后繼的，當標志為0時，則需要通過一定運算才能找到它的后繼。,線索鏈表：用這種結點結構所構成的二叉鏈表 線索：指向結點前驅(qū)和后繼的指針 線索二叉樹：加上線索的二叉樹（圖形式樣） 線索化：對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程,2020/9/1,57,按中序遍歷得到的線索二叉樹稱為中序線索二叉樹； 按先序遍歷得到的線索二叉樹稱為先序線索二叉樹； 按后序遍歷得到的線索二叉樹稱為后序線索二叉樹；,例2：畫出以下二叉樹對應的中序線索二叉樹。,58,懸空？,懸空？,解：該二叉樹中序遍歷結果為: H, D, I, B, E, A, F, C, G 所以添加線索應當按如下路徑進行：,為避免懸空態(tài)，

20、應增設一個頭結點,59,對應的中序線索二叉樹存儲結構如圖所示：,注：此圖中序遍歷結果為: H, D, I, B, E, A, F, C, G,60,（2）整體結構 增設一個頭結點，令其lchild指向二叉樹的根結點ltag=0、rtag=1； 并將該結點作為遍歷訪問的第一個結點的前驅(qū)和最后一個結點的后繼；最后用頭指針指示該頭結點。,4 給定如圖所示二叉樹T，請畫出與其對應的中序線索二叉樹。,61,解:因為中序遍歷序列是：55 40 25 60 28 08 33 54 對應線索樹應當按此規(guī)律連線，即在原二叉樹中添加虛線。,62,typedef struct BiThrNode TElemType

21、 data; struct BiThrNode *lchild, *rchild; / 左右指針 PointerThr LTag, RTag; / 左右標志 BiThrNode, *BiThrTree;,線索鏈表的類型描述：,typedef enum Link, Thread PointerThr; / Link=0:指針，Thread=1:線索,2. 線索二叉樹的生成,63,線索化過程就是在遍歷過程中修改空指針的過程： 將空的lchild改為結點的直接前驅(qū)； 將空的rchild改為結點的直接后繼。,非空指針呢？仍然指向孩子結點（稱為“正常情況”）,目的：在依某種順序遍歷二叉樹時修改空指針，添

22、加前驅(qū)或后繼。,注解：為方便添加結點的前驅(qū)或后繼，需要設置兩個指針： p指針當前結點之指針； pre指針前驅(qū)結點之指針。,技巧：當結點p的左/右域為空時，只改寫它的左域（裝入前驅(qū)pre）, 而其右域（后繼）留給下一結點來填寫。 或者說，當前結點的指針p應當送到前驅(qū)結點的空右域中。,若p-lchildNULL,則p-Ltag=1;p-lchildpre; /p的前驅(qū)結點指針pre存入左空域 若pre-rchildNULL, 則pre-Rtag1;pre-rchild=p; /p存入其前驅(qū)結點pre的右空域,線索二叉樹的生成算法,64,頭結點,0,1,pre,pre,p,pre,p,1,65,vo

23、id InThreading(BiThrTree p) 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,66,Status InOrderThrea

24、ding(BiThrTree / InOrderThreading,67,3. 線索二叉樹的遍歷,理論上，只要找到序列中的第一個結點，然后依次訪問結點的后繼直到后繼為空時結束。,但是，在線索化二叉樹中，并不是每個結點都能直接找到其后繼的，當標志為0時，R_child=右孩子地址指針，并非后繼！需要通過一定運算才能找到它的后繼。,以中序線索二叉樹為例： 對葉子結點（RTag=1），直接后繼指針就在其rchild域內(nèi)； 對其他結點（RTag=0），直接后繼是其右子樹最左下的結點； （因為中序遍歷規(guī)則是LDR，先左再根再右）,線索二叉樹的中序遍歷算法（參見教材P134）,68,程序注解 (非遞歸，不

25、用棧）： P=T-lchild; /從頭結點進入到根結點； while( p!=T) while (p-LTag=link) p=p-lchild; /先找到中序遍歷起點 if (!visit(p-data) return ERROR; /若起點值為空則出錯告警 while (p-RTag=Thread ) p=p-rchild; Visit(p-data); /若有后繼標志，則直接提取p-rchild中線索并訪問后繼結點； p=p-rchild; /當前結點右域不空或已經(jīng)找好了后則一律從結點的右子樹開始重復的全部過程。 return OK;,LTag=0,RTag=1,6.4 樹和森林,69

26、,1. 樹和森林與二叉樹的轉(zhuǎn)換 2. 樹和森林的存儲方式 3. 樹和森林的遍歷,70,如何存儲一棵樹呢？,71,利用除根結點外每個結點只有唯一的雙親的性質(zhì)，以一組連續(xù)的空間存儲樹的結點，同時在每個結點中附設一個指示域指示其雙親結點在存儲空間中的位置。,6.4 樹的存儲結構 一、雙親表示法,#define MAX_TREE_SIZE 100 結點結構： Typedef struct PTNode Elem data; int parent; PTNode;,Data parent,Typedef struct PTNode nodesMAX_TRee_size; int r,n; ,6 .4 樹

27、的存儲結構,72,6,H,6,G,3,F,1,E,1,D,0,C,0,B,0,A,-1,R,K,6,0 1 2 3 4 5 6 7 8 9,R=0 N=10,73,特點： 1）求結點的雙親操作可以在常量時間內(nèi)實現(xiàn)； 2）求結點的孩子時需要遍歷整個向量。,74,二、孩子表示法,孩子結點： Typedef struct CTNode int child; struct CTNode *next; *childPtr;,雙親結點: Typedef struct Elem data; childPtr firstchild; CTBox;,75,樹結構： Typedef struct CTBox no

28、desMAX_TREE_SIZE; int n,r; Ctree;,76,F,E,B,C,A,D,G,R=0 N=7,0 1 2 3 4 5 6,A B C D E F G,1,2,3,4,5,6,-1,0,0,0,2,2,5,77,三、樹的二叉鏈表 （孩子-兄弟）存儲表示法 typedef struct CSNode Elem data; struct CSNode *firstchild,*nextsibling; CSNode,*CSTree;,78,F,E,B,C,A,D,G,1. 樹和森林與二叉樹的轉(zhuǎn)換,79,轉(zhuǎn)換步驟： step1: 將樹中同一結點的兄弟相連; step2: 保留結

29、點的最左孩子連線，刪除其它孩子連線； step3: 將同一孩子的連線繞左孩子旋轉(zhuǎn)45度角。,加線,抹線,旋轉(zhuǎn),討論1：樹如何轉(zhuǎn)為二叉樹？,樹轉(zhuǎn)二叉樹舉例：,80,方法：加線抹線旋轉(zhuǎn),兄弟相連,長兄為父,孩子靠左,根結點肯定沒有右孩子！,討論2：二叉樹怎樣還原為樹？,81,要點：把所有右孩子變?yōu)樾值埽?82,法一： 各森林先各自轉(zhuǎn)為二叉樹； 依次連到前一個二叉樹的右子樹上。,討論3：森林如何轉(zhuǎn)為二叉樹？,法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹,（參見教材P138圖6.17，兩種方法都有轉(zhuǎn)換示意圖）,森林轉(zhuǎn)二叉樹舉例：（法二）,83,兄弟相連 長兄為父 孩子靠左 頭根為根,A,討論4：二叉樹如何還原為

30、森林？,84,要點：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值?85,樹的遍歷可有三條搜索路徑： 先根序（次序）遍歷 若樹不空，則先訪問根結點，然后依次先根遍歷各棵子樹。 后根（次序）遍歷 若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結點。 按層次遍歷 若樹不空，則自上而下自左至右訪問樹中每個結點。,86,先根遍歷時頂點的訪問次序： A B E F C D G H I J K 后根遍歷時頂點的訪問次序： E F B C I J K H G D A 層序遍歷時頂點的訪問次序： A B C D E F G H I J K,森林的遍歷,87,先序遍歷 若森林為空，返回； 訪問森林中第一棵樹的根結點

31、； 先序遍歷第一棵樹中根結點的子樹森林； 先序遍歷除去第一棵樹之后剩余的樹構成的森林。 中序遍歷 若森林為空，返回； 中序遍歷森林中第一棵樹的根結點的子樹森林； 訪問第一棵樹的根結點； 中序遍歷除去第一棵樹之后剩余的樹構成的森林。,88,A,B,C,D,E,F,G,H,K,I,L,J,6.5 Huffman樹及其應用,89,路 徑： 路徑長度： 樹的路徑長度： 帶權路徑長度： 樹的帶權路徑長度： 霍 夫 曼 樹：,一、最優(yōu)二叉樹（霍夫曼樹）,由一結點到另一結點間的分支所構成,路徑上的分支數(shù)目,從樹根到每一結點的路徑長度之和。,結點到根的路徑長度與結點上權的乘積,預備知識：若干術語,樹中所有葉子

32、結點的帶權路徑長度之和,帶權路徑長度最小的樹。,ae的路徑長度,樹長度,2,10,Huffman樹簡介：,90,樹的帶權路徑長度如何計算？,經(jīng)典之例：,WPL=36,WPL=46,WPL= 35,哈夫曼樹則是：WPL 最小的樹。,Huffman樹,Weighted Path Length,構造霍夫曼樹的基本思想：,91,(1) 由給定的 n 個權值w0, w1, w2, , wn-1，構造具有 n 棵擴充二叉樹的森林F = T0, T1, T2, , Tn-1 ，其中每一棵擴充二叉樹 Ti 只有一個帶有權值 wi 的根結點，其左、右子樹均為空。 (2) 重復以下步驟, 直到 F 中僅剩下一棵樹

33、為止： 在 F 中選取兩棵根結點的權值最小的擴充二叉樹, 做為左、右子樹構造一棵新的二叉樹。置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和。 在 F 中刪去這兩棵二叉樹。 把新的二叉樹加入 F。,構造Huffman樹的步驟（即Huffman算法）：,權值大的結點用短路徑，權值小的結點用長路徑。,先舉例！,構造Huffman樹的步驟：,92,操作要點：對權值的合并、刪除與替換 在權值集合7,5,2,4中，總是合并當前值最小的兩個權,注：方框表示外結點（葉子，字符對應的權值）， 圓框表示內(nèi)結點（合并后的權值）。,6.2.2 赫夫曼編碼,93,例2：設有4個字符d,i,a,n，出現(xiàn)的頻度

34、分別為7,5,2, 4，怎樣編碼才能使它們組成的報文在網(wǎng)絡中傳得最快？,法1：等長編碼。例如用二進制編碼來實現(xiàn)。 取 d=00，i=01，a=10，n=11,法2：不等長編碼，例如用前綴編碼來實現(xiàn)。 取 d=0; i=10, a=110, n=111,最快的編碼是哪個？,是非等長的前綴編碼！,任一個字符的編碼都不是另一個字符編碼的前綴,約定： 左分支表示0 右分支表示1 則從根結點到葉子結點的路徑上分支字符組成的字符串作為該葉子的編碼。,94,如何得到電文長度最短的二進制前綴編碼？,若按各個字符出現(xiàn)的概率不同而給予不等長編碼，可望減少總編碼長度。,d,i,a,n，出現(xiàn)的頻度分別為7,5,2,4

35、,假設每種字符在電文中出現(xiàn)的次數(shù)為wi,，其編碼長度為Li,電文中只有n種字符，則電文總長度為,由此可見，設計電文總長最短的二進制前綴編碼即為以n種字符出現(xiàn)的頻率作權，設計一顆赫夫曼樹的問題，由此得到的二進制前綴編碼便稱為赫夫曼編碼。,對應到二叉樹上，若置wi為葉子結點的權， Li恰為從根到葉子的路徑長度。則： 恰為二叉樹上帶權路徑長度。,操作要點：按左0右1對Huffman樹的所有分支編號！,95,Huffman編碼結果：d=0, i=10, a=110, n=111 WPL=1bit72bit5+3bit(2+4)=35,特點：每一碼都不是另一碼的前綴，絕不會錯譯! 稱為前綴碼,將 Huf

36、fman樹 與 Huffman編碼 掛鉤,例2（嚴題集6.26）：假設用于通信的電文僅由8個字母 a, b, c, d, e, f, g, h 構成，它們在電文中出現(xiàn)的概率分別為 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10，試為這8個字母設計哈夫曼編碼。如果用07的二進制編碼方案又如何？,96,霍夫曼編碼的基本思想是：概率大的字符用短碼，概率小的用長碼。由于霍夫曼樹的WPL最小，說明編碼所需要的比特數(shù)最少。這種編碼已廣泛應用于網(wǎng)絡通信中。,解：先將概率放大100倍，以方便構造哈夫曼樹。權值集合 w=7, 19, 2, 6, 32, 3, 21, 10， 按哈夫曼