數(shù)據(jù)結(jié)構-樹與二叉樹

1、Chapter 6Tree & Binary Tree 教教 學學 內(nèi)內(nèi) 容容 1 1、樹和森林的概念、樹和森林的概念2 2、二叉樹的定義、性質(zhì)及運算；、二叉樹的定義、性質(zhì)及運算； 3 3、二叉樹的存儲結(jié)構、二叉樹的存儲結(jié)構 4 4、遍歷二叉樹、樹、森林、遍歷二叉樹、樹、森林5 5、森林與二叉樹的轉(zhuǎn)換、森林與二叉樹的轉(zhuǎn)換6 6、哈夫曼樹、哈夫曼編碼、哈夫曼樹、哈夫曼編碼 樹型結(jié)構（非線性結(jié)構）樹型結(jié)構（非線性結(jié)構） 結(jié)點之間有分支結(jié)點之間有分支 具有層次關系具有層次關系 生活中的哪些實例是樹型結(jié)構呢？例例 自然界自然界: :樹樹 人類社會人類社會 家譜家譜 院系組院系組織機構織機構 錦

2、城學院錦城學院 電子系電子系計科系計科系 文傳系文傳系通信通信信息工程信息工程微電子微電子通通1 1班班 通通2 2班班 通通3 3班班 樹的概念樹的概念 樹的定義樹的定義 樹是樹是 n (n 0) 個結(jié)點的有限集。若個結(jié)點的有限集。若n = 0，稱，稱為空樹；若為空樹；若 n 0，則它滿足如下兩個條件：，則它滿足如下兩個條件：有且僅有一個稱之為根有且僅有一個稱之為根(Root)的結(jié)點。的結(jié)點。當當n 1，除根以外的其它結(jié)點分為，除根以外的其它結(jié)點分為 m (m 0) 個互不相交的有限集個互不相交的有限集 T1, T2 , Tm，其中每，其中每個集合又是一棵符合本定義的樹，并且稱為個集合又是一

3、棵符合本定義的樹，并且稱為根的子樹根的子樹。ACGBDEFKLHMIJ例如例如A只有根結(jié)點的樹只有根結(jié)點的樹有有13個結(jié)點的樹個結(jié)點的樹A是根；其余數(shù)據(jù)元素分成三個互不相交的子集，是根；其余數(shù)據(jù)元素分成三個互不相交的子集，T1=B,E,F,K,L； T2=C,G； T3=D,H,I,J,M,T1,T2,T3都是根都是根A的子樹，且本身也是一棵樹。的子樹，且本身也是一棵樹。根結(jié)點根結(jié)點T1R=,ACGBDEFKLHMIJ線性結(jié)構線性結(jié)構樹結(jié)構樹結(jié)構存在唯一的沒有前驅(qū)的存在唯一的沒有前驅(qū)的“首元素首元素”存在唯一的沒有前驅(qū)的存在唯一的沒有前驅(qū)的“根結(jié)點根結(jié)點”存在唯一的沒有后繼的存在唯一的沒有后繼

4、的“尾元素尾元素”存在多個沒有后繼的存在多個沒有后繼的“葉子葉子”其余元素均存在唯一的其余元素均存在唯一的“前驅(qū)元素前驅(qū)元素”和唯一的和唯一的“后繼元素后繼元素”其余結(jié)點均存在唯一的其余結(jié)點均存在唯一的“前驅(qū)（雙親）結(jié)點前驅(qū)（雙親）結(jié)點”和和多個多個“后繼（孩子）結(jié)點后繼（孩子）結(jié)點”樹結(jié)構和線性結(jié)構作如下對照：樹結(jié)構和線性結(jié)構作如下對照：樹的基本術語樹的基本術語1層2層4層3層height= 4ACGBDEFKLHMIJ有序樹有序樹子樹之間存在確定的次序關系子樹之間存在確定的次序關系無序樹無序樹子樹之間不存在確定的次序關系子樹之間不存在確定的次序關系家族樹就屬家族樹就屬于有序樹。于有序樹。是

5、是m(m0)棵互不相交的樹的集合棵互不相交的樹的集合給森林中的各子樹加上一個父親結(jié)點給森林中的各子樹加上一個父親結(jié)點,森森林就變成了樹。林就變成了樹。 T3 T2 T1 ABEFKLDHMIJCGCG 二叉樹二叉樹或為或為空樹空樹，或是由一個，或是由一個根結(jié)點根結(jié)點加上加上兩棵分別稱為兩棵分別稱為左子樹左子樹和和右子樹右子樹的、的、互不交叉互不交叉的的二叉樹組成。二叉樹組成。 二叉樹二叉樹為何要重點研究每結(jié)點最多只有兩個為何要重點研究每結(jié)點最多只有兩個 “ “叉叉” ” 的樹？的樹？ 二叉樹的結(jié)構最簡單，規(guī)律性最強；二叉樹的結(jié)構最簡單，規(guī)律性最強； 可以證明，所有樹都能轉(zhuǎn)為唯一對應的二叉樹，可

6、以證明，所有樹都能轉(zhuǎn)為唯一對應的二叉樹，不失一般性。不失一般性。BDEGHCILFA根結(jié)點根結(jié)點右子樹右子樹左子樹左子樹 (a)空二叉樹空二叉樹 (b) 根和空的根和空的 左右子樹左右子樹 (c) 根和左子樹根和左子樹 (d) 根和右子樹根和右子樹 (e) 根和左右子樹根和左右子樹 注：雖然二叉樹與樹概念不同，注：雖然二叉樹與樹概念不同， 但有關樹的基本術語對二叉樹都適用。但有關樹的基本術語對二叉樹都適用。 二叉樹的五種基本形態(tài)二叉樹的五種基本形態(tài) 性質(zhì)性質(zhì)1 在二叉樹的第在二叉樹的第 i 層上至多有層上至多有 2i 1個結(jié)點。個結(jié)點。(i 1)證明：當證明：當i=1時，只有根結(jié)點，時，只有根

7、結(jié)點，2i-1=20=1。假設對所有假設對所有j，ij 1，命題成立，即第，命題成立，即第j層上至多層上至多有有2 j-1 個結(jié)點。個結(jié)點。由歸納假設第由歸納假設第i-1 層上至多有層上至多有 2i2個結(jié)點。個結(jié)點。二叉樹的每個結(jié)點的度至多為二叉樹的每個結(jié)點的度至多為2，故在第，故在第i層上的層上的最大結(jié)點數(shù)為第最大結(jié)點數(shù)為第i-1層上的最大結(jié)點數(shù)的層上的最大結(jié)點數(shù)的2倍，即倍，即2*2i2= 2i-1。二叉樹的重要特性二叉樹的重要特性 性質(zhì)性質(zhì)2 深度為深度為 k 的二叉樹至多有的二叉樹至多有 2 k-1個結(jié)點，個結(jié)點，其中其中k 1。 證明：由性質(zhì)證明：由性質(zhì)1可見，深度為可見，深度為k的

8、二叉樹的二叉樹的最大結(jié)點數(shù)為的最大結(jié)點數(shù)為20 + 21 + + 2k-1 = 2k - -1kii112 性質(zhì)性質(zhì)3 對任何一棵二叉樹對任何一棵二叉樹T, 如果其葉子結(jié)點數(shù)為如果其葉子結(jié)點數(shù)為 n0, 度為度為2的結(jié)點數(shù)為的結(jié)點數(shù)為 n2,則則n0n21。證明證明： n = nn = n0 0 + n + n1 1 + n + n2 2 e = n e = n 1 = 2n 1 = 2n2 2 + n + n1 1 因此，因此，2n2n2 2 + n + n1 1 = n = n0 0 + n + n1 1 + n + n2 2 - 1 - 1 n n0 0 = n = n2 2 + 1 +

9、 1 滿二叉樹滿二叉樹 (Full Binary Tree) 定義定義1 1 : : 一棵深度為一棵深度為k且有且有2 k-1個結(jié)點的二叉?zhèn)€結(jié)點的二叉樹稱為滿二叉樹。樹稱為滿二叉樹。兩種特殊形態(tài)的二叉樹兩種特殊形態(tài)的二叉樹754389101113 14 1512126特點特點: :每一每一層上的結(jié)點層上的結(jié)點數(shù)都達到最數(shù)都達到最大大, ,葉子全葉子全部在最底層部在最底層非完全二叉樹非完全二叉樹完全二叉樹完全二叉樹 (Complete Binary Tree) 若設二叉樹的深度為若設二叉樹的深度為h，除第，除第 h 層外，層外，其它各層其它各層 (0 h- -1) 的結(jié)點數(shù)都達到最大值，的結(jié)點數(shù)

10、都達到最大值，第第 h 層層從右向左從右向左連續(xù)缺若干結(jié)點。連續(xù)缺若干結(jié)點。完全二叉樹完全二叉樹621543BACDEGF 性質(zhì)性質(zhì)4 具有具有 n (n 0) 個結(jié)點的完全二叉樹的個結(jié)點的完全二叉樹的深度為深度為 log2(n) 1 。證明：設完全二叉樹的深度為證明：設完全二叉樹的深度為 h h，則根，則根據(jù)性質(zhì)據(jù)性質(zhì)2 2和完全二叉樹的定義有和完全二叉樹的定義有2 2h-1h-1-1-1 n n 2 2h h - 1,- 1,取對數(shù)取對數(shù) h h1 1 log log2 2n hn n，則該結(jié)點無左孩子，否則，則該結(jié)點無左孩子，否則， 編號為編號為2i的結(jié)點為其的結(jié)點為其左孩子左孩子結(jié)點。

11、結(jié)點。(3)若若2i+1n，則該結(jié)點無右孩子結(jié)點，則該結(jié)點無右孩子結(jié)點， 否則，編號為否則，編號為2i+1的結(jié)點為其的結(jié)點為其右孩子右孩子 結(jié)點。結(jié)點。3. 3. 深度為深度為9 9的二叉樹中至少有的二叉樹中至少有 個結(jié)點。個結(jié)點。) )9 9 ) )8 8 ) ) ) )9 91 12.2.深度為的二叉樹的結(jié)點總數(shù)，最多為深度為的二叉樹的結(jié)點總數(shù)，最多為 個。個。) )k-1k-1 ) log) log2 2k k ) ) k k ) )k k1.1.樹中各結(jié)點的度的最大值稱為樹樹中各結(jié)點的度的最大值稱為樹 。) ) 高度高度 ) ) 層次層次 ) ) 深度深度 ) ) 度度DCC二、二叉樹

12、的鏈式存儲表示二、二叉樹的鏈式存儲表示一、二叉樹的順序存儲表示一、二叉樹的順序存儲表示6.3 二叉樹的存儲結(jié)構二叉樹的存儲結(jié)構順序存儲表示順序存儲表示用用一組地址連續(xù)的存儲單元一組地址連續(xù)的存儲單元存儲二叉樹中的數(shù)存儲二叉樹中的數(shù)據(jù)元素。將據(jù)元素。將完全二叉樹完全二叉樹上編號為上編號為i i的結(jié)點元素的結(jié)點元素存儲在一維數(shù)組中下標為存儲在一維數(shù)組中下標為i-1i-1的分量中的分量中 BACEDFGHIJKLMNOBACEDFGHIJ12345671089練習練習 A B D C E F 0 1 2 3 4 5 ABCDEF241635對于一般的非完全對于一般的非完全二叉樹二叉樹不能直接使不能直

13、接使用二叉樹的順序存用二叉樹的順序存儲結(jié)構。儲結(jié)構?？梢允紫仍诜峭耆鏄渲性鎏硪恍┎⒉淮婵梢允紫仍诜峭耆鏄渲性鎏硪恍┎⒉淮嬖诘目战Y(jié)點使之變成完全二叉樹的形態(tài)，然在的空結(jié)點使之變成完全二叉樹的形態(tài)，然后再用順序存儲結(jié)構存儲。后再用順序存儲結(jié)構存儲。 BACDEGFBACDEGF(a)一般二叉樹一般二叉樹 (b)完全二叉樹形態(tài)完全二叉樹形態(tài) 單支樹單支樹鏈表存儲表示鏈表存儲表示ADEBCF rootlchild data rchild結(jié)點結(jié)構結(jié)點結(jié)構二叉鏈表二叉鏈表ADEBCF root 三叉鏈表三叉鏈表parent lchild data rchild結(jié)點結(jié)構結(jié)點結(jié)構6.3 二叉樹的遍歷二

14、叉樹的遍歷 遍歷概念遍歷概念 順著某一條搜索路徑順著某一條搜索路徑巡訪巡訪二叉樹中的結(jié)點，使二叉樹中的結(jié)點，使 得每個結(jié)點得每個結(jié)點均被訪問一次均被訪問一次，而且，而且僅被訪問一次僅被訪問一次?！啊钡暮x很廣，可以是對結(jié)點作各種的含義很廣，可以是對結(jié)點作各種處理，如：輸出結(jié)點的信息、修改結(jié)點的數(shù)據(jù)處理，如：輸出結(jié)點的信息、修改結(jié)點的數(shù)據(jù)值等，但要求這種訪問值等，但要求這種訪問。 遍歷方法遍歷方法 依次遍歷二叉樹中的三依次遍歷二叉樹中的三個組成個組成 部分，便是遍歷部分，便是遍歷了整個二叉樹了整個二叉樹 假設：假設：L：遍歷左子樹：遍歷左子樹 v：訪問根結(jié)點：訪問根結(jié)點 R：遍：遍歷右子樹歷右子

15、樹,則遍歷整個二叉樹方案共有：則遍歷整個二叉樹方案共有： 遍歷目的遍歷目的 得到樹中所有結(jié)點的一個得到樹中所有結(jié)點的一個線性線性排列。排列。 根結(jié)點根結(jié)點 左子樹左子樹 右子樹右子樹 vLR、LvR、LRv 、 vRL、RvL、RLv 六種。六種。 根結(jié)點根結(jié)點 左子樹左子樹 右子樹右子樹 遍歷二叉樹的操作定義：遍歷二叉樹的操作定義： 若二叉樹為空，則空操作；否則若二叉樹為空，則空操作；否則 (1) 訪問根結(jié)點；訪問根結(jié)點； (2) 前序遍歷左子樹；前序遍歷左子樹； (3) 前序遍歷右子樹。前序遍歷右子樹。 前序遍歷：前序遍歷：ABC A B E L D H M I J A B C A B D

16、 E LH M I J 遍歷二叉樹的操作定義：遍歷二叉樹的操作定義： 若二叉樹為空，則空操作；否則若二叉樹為空，則空操作；否則 (1) 中序遍歷左子樹；中序遍歷左子樹； (2) 訪問根結(jié)點；訪問根結(jié)點； (3) 中序遍歷右子樹。中序遍歷右子樹。 中序遍歷：中序遍歷：BAC E L B A M H I D J A B C A B D E LH M I J 遍歷二叉樹的操作定義：遍歷二叉樹的操作定義： 若二叉樹為空，則空操作；否則若二叉樹為空，則空操作；否則 (1) 后序遍歷左子樹；后序遍歷左子樹； (2) 后序遍歷右子樹；后序遍歷右子樹； (3) 訪問根結(jié)點。訪問根結(jié)點。 后序遍歷：后序遍歷：B

17、CA L E B M I H J D A A B C A B D E LH M I J a+b(a+b)c d/e d/ea+bc 分析表達式和二叉樹的關系分析表達式和二叉樹的關系ab+abc+abc+(a+b)cabcde- -+/遍歷結(jié)果：遍歷結(jié)果： 前序：前序： - - + ab - - c d / e f 中序：中序： a + bc - - d - - e / f 后序：后序： a b c d - -+ e f / - - 表達式的表達式的前綴表示前綴表示表達式的表達式的中綴表示中綴表示 表達式的表達式的后綴表示后綴表示template class BinTreeNode privat

18、e: BinTreeNode *LChild,*RChild; Type data; public: BinTreeNode( ) LChild= RChild=NULL; BinTreeNode(const Type &val, BinTreeNode *lchild = NULL, BinTreeNode *rchild = NULL) data = val ; LChild= lchild; RChild= rchild ; ;template class BinaryTree / 二叉樹類二叉樹類 protected: BinTreeNode *root; void PreOr

19、derHelp( BinTreeNode *r, void (*Visit)(const Type &) ) const; void InOrderHelp( BinTreeNode *r, void (*Visit)(const Type &) ) const; void PostOrderHelp( BinTreeNode *r, void (*Visit)(const Type &) ) const;先、中、后序遍歷先、中、后序遍歷（輔助函數(shù)）（輔助函數(shù)） public: BinaryTree( );/ 建立以建立以r為根的二叉樹為根的二叉樹 BinaryTree

20、(BinTreeNode *r); virtual BinaryTree();/ 析構函數(shù)析構函數(shù) BinTreeNode *GetRoot( ) const; bool Empty() const; void InOrder(void (*Visit)(const Type &) const;/ 二叉樹的中序遍歷二叉樹的中序遍歷 void PreOrder(void (*Visit)(const Type &) const;/ 二叉樹的前序遍歷二叉樹的前序遍歷 void PostOrder(void (*Visit)(const Type &) const;/ 二叉樹

21、的后序遍歷二叉樹的后序遍歷/ 二叉樹的層次遍歷二叉樹的層次遍歷/ 插入左孩子插入左孩子/ 插入右孩子插入右孩子template void BinaryTree:PreOrderHelp ( BinTreeNode *r, void (*Visit)(const Type &) ) const if (r != NULL) (*Visit)(r-data);/ 訪問根結(jié)點訪問根結(jié)點 PreOrderHelp(r-leftChild, Visit); PreOrderHelp(r-rightChild, Visit);template void BinaryTree:PreOrder (v

22、oid (*Visit)(Type &) / 操作結(jié)果：前序遍歷二叉樹操作結(jié)果：前序遍歷二叉樹PreOrderHelp(root, Visit);template void write (const Type &e) cout e “ “; 二叉樹前序遍歷二叉樹前序遍歷非遞歸算法非遞歸算法template void BinaryTree:PreOrder( ) StackBinTreeNode * s; BinTreeNode *p =root; do while ( p != NULL ) cout pdata; Push ( s, p ); p = pLChild; if

23、( !Empty ( s ) ) p = pop ( s ); p = pRChild; while ( ( !Empty ( s ) ) | ( p != NULL ) ) ;二叉樹中序遍歷二叉樹中序遍歷非遞歸算法非遞歸算法template void BinaryTree:InOrder( ) BinTreeNode *p=root; Stack BinTreeNode * s; do while ( p != NULL ) Push ( s, p ); p = pLChild; if ( !Empty ( s ) ) p = pop ( s ); cout pdata; p = pRChi

24、ld; while ( ( !Empty ( s ) ) | ( p != NULL ) ) ;層次遍歷層次遍歷(Levelorder Traversal)二叉樹的重建二叉樹的重建由二叉樹的由二叉樹的前序前序序列和序列和中序中序序列序列可可以以唯一地確定一棵二叉樹唯一地確定一棵二叉樹由二叉樹的由二叉樹的后序后序序列和序列和中序中序序列序列可可以以唯一地確定一棵二叉樹唯一地確定一棵二叉樹由二叉樹的由二叉樹的前序前序序列和序列和后序后序序列序列不不可可唯一地確定一棵二叉樹唯一地確定一棵二叉樹僅知二叉樹的前序序列僅知二叉樹的前序序列“abcdefg” 不不能唯一確定一棵二叉樹，能唯一確定一棵二叉樹，

25、 如果同時已知如果同時已知二叉樹的中序序列二叉樹的中序序列“cbdaegf”，則會如，則會如何？何？ 由二叉樹的前序和中序序列建樹由二叉樹的前序和中序序列建樹二叉樹的前序序列二叉樹的前序序列二叉樹的中序序列二叉樹的中序序列左子樹左子樹左子樹左子樹 右子樹右子樹右子樹右子樹根根根根a b c d e f gc b d a e g faab bccddeeffggabcdefg前序序列前序序列中序序列中序序列前序序列前序序列 A B H F D E C K G 中序序列中序序列 H B D F A E K C G template void BinaryTree:InsertRightChild

26、(BinTreeNode *cur, const Type &e) if (cur != NULL) / 插入右孩子插入右孩子,元素值為元素值為e結(jié)點結(jié)點 BinTreeNode *child = new BinTreeNode(e); if (cur-rightChild != NULL) child-rightChild = cur-rightChild; cur-rightChild = child;/ e成為成為cur的右孩子的右孩子 template void BinaryTree:InsertLeftChild (BinTreeNode *cur, const Type &

27、amp;e) if (cur != NULL) / 插入左孩子插入左孩子,元素值為元素值為e的結(jié)點的結(jié)點 BinTreeNode *child = new BinTreeNode(e);if (cur-leftChild != NULL) / cur的左孩子非空的左孩子非空,原有左子樹成為原有左子樹成為e的左子樹的左子樹 child-leftChild = cur-leftChild;/ curcur-leftChild = child; / e成為成為cur的左孩子的左孩子 int main(void)BinTreeNode *cur;int c;cur = new BinTreeNode(

28、2);BinaryTree bt(cur);/ 建立二叉樹建立二叉樹c = 3; bt.InsertLeftChild(cur, c);/ 插入左孩子插入左孩子cur = bt.LeftChild(cur);c = 4;bt.InsertRightChild(cur, c);/ 插入右孩子插入右孩子cur = bt.GetRoot();/ 取出根結(jié)點取出根結(jié)點c = 6;bt.InsertRightChild(cur, c);/ 插入右孩子插入右孩子return 0;6.6 樹和森林樹和森林一、樹的存儲表示一、樹的存儲表示 ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5

29、 F 26 G 5data father父父親親表表示示法法孩子表示法孩子表示法0 A 1 B 2 C 3 D 4 E 5 F 6 G data child 1 2 34 56ABCDEFG改進：改進：父親、孩子表示法結(jié)合父親、孩子表示法結(jié)合0 A 1 B 2 C 3 D 4 E 5 F 6 G data 1 2 34 56-1000225ABCDEFG data firstChildnextSibling孩子兄弟表示法孩子兄弟表示法 AB C E D F Groot練習練習ABCDEFG樹的遍歷樹的遍歷深度優(yōu)先遍歷深度優(yōu)先遍歷樹的先根次序遍歷樹的先根次序遍歷樹的后根次序遍歷樹的后根次序遍歷廣

30、度優(yōu)先遍歷廣度優(yōu)先遍歷樹的層次次序遍歷樹的層次次序遍歷 A B C DE F G H I J K 先根遍歷先根遍歷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 B C DE F G H I J K1森林中第一棵森林中第一棵樹的根結(jié)點樹的根結(jié)點2森林中第一棵森林中第一棵樹的子樹森林樹的子樹森林3森林中其它樹森林中其它樹構成的森林構成的森林森林由三部分構成森林由三部分構成森林的先根遍歷森林的先根遍歷若森林若森林F為空為空, , 返回返回否則否則: : 訪問訪問F的第一棵樹的根結(jié)

31、點的第一棵樹的根結(jié)點 先根次序遍歷第一棵樹的子樹森林先根次序遍歷第一棵樹的子樹森林 先根次序遍歷其它樹組成的森林先根次序遍歷其它樹組成的森林結(jié)果：結(jié)果：B E F C D G H I J KBHIFCDEGJK森林的后根遍歷森林的后根遍歷若森林若森林F為空，返回為空，返回否則否則: : 后根次序遍歷第一棵樹的子樹森林后根次序遍歷第一棵樹的子樹森林 訪問訪問F的第一棵樹的根結(jié)點的第一棵樹的根結(jié)點 后根次序遍歷其它樹組成的森林后根次序遍歷其它樹組成的森林結(jié)果：結(jié)果：E F B C I J K H G DBHIFCDEGJK森林的層次遍歷森林的層次遍歷若森林若森林F為空，返回為空，返回否則否則: :

32、 依次遍歷各棵樹的根結(jié)點依次遍歷各棵樹的根結(jié)點 依次遍歷各棵樹根結(jié)點的所有子女依次遍歷各棵樹根結(jié)點的所有子女 依次遍歷這些子女結(jié)點的子女結(jié)點依次遍歷這些子女結(jié)點的子女結(jié)點結(jié)果：結(jié)果：B C D E F G H I J K BHIFCDEGJK6.7 哈哈 夫夫 曼曼 樹樹 (Huffman Tree) 與與哈哈 夫夫 曼曼 編編 碼碼 結(jié)點的路徑長度結(jié)點的路徑長度 從根結(jié)點到該結(jié)點的路徑上分從根結(jié)點到該結(jié)點的路徑上分 支的數(shù)目支的數(shù)目樹的路徑長度樹的路徑長度 樹中每個結(jié)點的路徑長度之和樹中每個結(jié)點的路徑長度之和樹的樹的帶權路徑長度帶權路徑長度( (Weighted Path Length,WP

33、LWeighted Path Length,WPL) ) 樹的樹的各葉子各葉子結(jié)點所帶的權值與結(jié)點所帶的權值與 該結(jié)點到根的路徑長度的乘積該結(jié)點到根的路徑長度的乘積 的和的和結(jié)點的帶權路徑長度結(jié)點的帶權路徑長度 從該結(jié)點到到根結(jié)點之間的路從該結(jié)點到到根結(jié)點之間的路 徑長度與結(jié)點上權的乘積。徑長度與結(jié)點上權的乘積。10niiilwWPL 在所有含在所有含n n個葉子結(jié)點、并帶有各個葉子結(jié)點、并帶有各自自權值的權值的m m叉樹中，必存在一棵其叉樹中，必存在一棵其帶權帶權路徑長度取最小值路徑長度取最小值的樹，稱為的樹，稱為“最優(yōu)最優(yōu)樹樹”,或或“哈夫曼樹哈夫曼樹” 哈哈夫曼樹中，權值大的結(jié)點離根最近

34、夫曼樹中，權值大的結(jié)點離根最近具有不同帶權路徑長度的二叉樹具有不同帶權路徑長度的二叉樹WPL(a)= 7 2+5 2+2 3+4 3+9 2=60WPL(b)= 7 4+9 4+5 3+4 2+2 1=89 根據(jù)給定的根據(jù)給定的 n 個權值個權值 w1, w2, , wn，造，造 n 棵二叉樹的集合棵二叉樹的集合 F = T1, T2, , Tn， 其中每棵二叉樹中均只含一個帶權其中每棵二叉樹中均只含一個帶權 值為值為 wi 的根結(jié)點，其左、右子樹為的根結(jié)點，其左、右子樹為 空樹；空樹； 在在 F 中選中選取其根結(jié)點的權值為最取其根結(jié)點的權值為最 小的兩棵二叉樹小的兩棵二叉樹，分別作為左、，分

35、別作為左、 右子樹構造一棵新的二叉樹，并右子樹構造一棵新的二叉樹，并 置這棵新的二叉樹根結(jié)點的權值置這棵新的二叉樹根結(jié)點的權值 為其左、右子樹根結(jié)點的權值之為其左、右子樹根結(jié)點的權值之 和；和； 從從F中刪去這兩棵樹，同時加入中刪去這兩棵樹，同時加入 剛生成的新樹剛生成的新樹 重復重復 和和 兩步，直至兩步，直至 F 中只中只 含一棵樹為止含一棵樹為止哈夫曼樹的構造過程哈夫曼樹的構造過程哈夫曼編碼哈夫曼編碼 哈夫曼樹的應用很廣，哈夫曼編碼就是其在電訊通信中的應用之一。在電訊通信業(yè)務中，通常用二進制編碼來表示字母或其他字符，并用這樣的編碼來表示字符序列。 例：例：如果需傳送的電文為如果需傳送的電

36、文為 ABACCDA，它只用到，它只用到四種字符，用兩位二進制編碼便可分辨。四種字符，用兩位二進制編碼便可分辨。假設假設 A, B, C, D 的編碼分別為的編碼分別為 00, 01, 10, 11，則上述電文便為，則上述電文便為 00010010101100（共（共 14 位），譯碼員按兩位進行位），譯碼員按兩位進行分組譯碼，便可恢復原來的電文。分組譯碼，便可恢復原來的電文。 能否使編碼總長度更短呢能否使編碼總長度更短呢？ 實際應用中各字符的出現(xiàn)頻度不相同實際應用中各字符的出現(xiàn)頻度不相同 用用（長長）編碼表示頻率）編碼表示頻率（小?。┑淖址┑淖址?使得編碼序列的總長度最小，使所需總空間量最

37、少使得編碼序列的總長度最小，使所需總空間量最少 若假設若假設 A, B, C, D 的編碼分別為的編碼分別為 0，00，1，01，則電文則電文 ABACCDA 便為便為 000011010（共（共 9 位）。位）?？勺g為可譯為 BBCCDA、ABACCDA、AAAACCACA 存在多義性存在多義性要求任一字符的編碼都不能是另一字符編碼的前綴！要求任一字符的編碼都不能是另一字符編碼的前綴！ 這種編碼稱為這種編碼稱為（其實是非前綴碼）。（其實是非前綴碼）。 譯碼的惟一性問題譯碼的惟一性問題 利用最優(yōu)二叉樹可以很好地解決上述兩個問題利用最優(yōu)二叉樹可以很好地解決上述兩個問題 在編碼過程要考慮兩個問題在編碼過程要考慮兩個問題 數(shù)據(jù)的最小冗余編碼問題數(shù)據(jù)的最小冗余編碼問題 譯碼的惟一性問題譯碼的惟一性問題 以電文中的字符作為葉子結(jié)點構造二叉樹。然后將二叉樹中以電文中的字符作為葉子結(jié)點構造二叉樹。然后將二叉樹中 結(jié)點引向其左孩子的分支標結(jié)點引向其左孩子的分支標 0，引向其右孩子的分支標，引向其右孩子的分支標 1； 每每 個字符的編碼即為從根到每個葉子的路徑上得到的個字符的編碼即為從根到每個葉子的路徑上得到的 0, 1 序列。如序列。如 此得到的即為二進制前綴編碼。此得到的即為二進制前綴編碼。