數(shù)據(jù)結(jié)構(gòu) 第六章樹與二叉樹

1、第第6 6章章 樹和二叉樹樹和二叉樹 樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)。關(guān)系定義的層次結(jié)構(gòu)。6.1 樹樹的定義的定義定義：樹定義：樹(tree)是是n(n 0)個(gè)結(jié)點(diǎn)的有限集個(gè)結(jié)點(diǎn)的有限集T其中：其中：有且僅有一個(gè)特定的結(jié)點(diǎn)，稱為樹的有且僅有一個(gè)特定的結(jié)點(diǎn)，稱為樹的根根(root)當(dāng)當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為時(shí)，其余結(jié)點(diǎn)可分為m(m0)個(gè)個(gè)互不相交互不相交的有的有限集限集T1,T2,Tm，其中每一個(gè)集合本身又是一棵其中每一個(gè)集合本身又是一棵樹，稱為根的樹，稱為根的子樹子樹(subtree)特點(diǎn)：特點(diǎn)：樹中至少有一個(gè)結(jié)點(diǎn)稱為樹中至少有一

2、個(gè)結(jié)點(diǎn)稱為根根樹中各子樹是樹中各子樹是互不相交互不相交的集合的集合A只有一個(gè)根結(jié)點(diǎn)的樹只有一個(gè)根結(jié)點(diǎn)的樹ABCDEFGHIJKLMA為為根結(jié)點(diǎn)，其余分為三個(gè)互不相交的子集根結(jié)點(diǎn)，其余分為三個(gè)互不相交的子集T1=B,E,F,K,L T2=C,G T3=D,H,I,J,MT1,T2,T3都是都是根結(jié)點(diǎn)根結(jié)點(diǎn)A的子樹，且本身又是一棵樹。的子樹，且本身又是一棵樹。根基本術(shù)語(yǔ)基本術(shù)語(yǔ)結(jié)點(diǎn)結(jié)點(diǎn)(node)：包括一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支：包括一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支結(jié)點(diǎn)的度結(jié)點(diǎn)的度(degree)：結(jié)點(diǎn)擁有的子樹個(gè)數(shù)：結(jié)點(diǎn)擁有的子樹個(gè)數(shù)葉子葉子(leaf)：度為：度為0的結(jié)點(diǎn)（或稱終端結(jié)

3、點(diǎn)）的結(jié)點(diǎn)（或稱終端結(jié)點(diǎn)）分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)）：度不為分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)）：度不為0的結(jié)點(diǎn)的結(jié)點(diǎn)樹的度：樹內(nèi)各結(jié)點(diǎn)的度的最大值樹的度：樹內(nèi)各結(jié)點(diǎn)的度的最大值孩子孩子(child)：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子雙親雙親(parents): (相對(duì)孩子相對(duì)孩子)結(jié)點(diǎn)的上層結(jié)點(diǎn)結(jié)點(diǎn)的上層結(jié)點(diǎn)兄弟兄弟(sibling)：同一雙親的孩子之間互稱兄弟：同一雙親的孩子之間互稱兄弟結(jié)點(diǎn)的祖先：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)結(jié)點(diǎn)的祖先：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)子孫：某結(jié)點(diǎn)為根的子樹中的任意結(jié)點(diǎn)子孫：某結(jié)點(diǎn)為根的子樹中的任意結(jié)點(diǎn)結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次(level)：從

4、根結(jié)點(diǎn)算起，根為第一層，它的孩：從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層子為第二層深度深度(depth)：樹中結(jié)點(diǎn)的最大層次數(shù)：樹中結(jié)點(diǎn)的最大層次數(shù)森林森林(forest)：m(m 0)棵互不相交的樹的集合棵互不相交的樹的集合ADT Tree 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R：若：若D為空集，則稱為空樹；為空集，則稱為空樹； 若若D僅含一個(gè)數(shù)據(jù)元素，則僅含一個(gè)數(shù)據(jù)元素，則R為空集，否則為空集，否則RH， H是如下二元關(guān)系：是如下二元關(guān)系：(1)在在D中存在唯一的稱為根的數(shù)據(jù)元素中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)

5、系，它在關(guān)系H下下無(wú)前驅(qū)；無(wú)前驅(qū)； (2)若若Droot，則存在，則存在Droot的一個(gè)劃分的一個(gè)劃分 D1，D2，Dm（m0），對(duì)任意），對(duì)任意j k(1j, km) 有有Dj Dk = ,且對(duì)任意的且對(duì)任意的i(1im)，唯一存在數(shù)據(jù)元素，唯一存在數(shù)據(jù)元素Xi Di,有有root, Xi H;(3) 對(duì)應(yīng)于對(duì)應(yīng)于D-root的劃分的劃分,H-有唯有唯一的一個(gè)劃分一的一個(gè)劃分H1,H2,Hm(m0),對(duì)任意對(duì)任意jk(1j, km) 有有Hj Hk = ,且對(duì)任意且對(duì)任意i(1im)，Hi是是 Di上的二元關(guān)上的二元關(guān)系，（系，（Di,Hi）是一棵符合本定義的樹，稱為根）是一棵符合本定義的樹

6、，稱為根root的的子樹。子樹?；静僮骰静僮鱌：InitTree ( &T ) ;DestroyTree ( &T ) ;CreateTree ( &T , definition ) ;ClearTree ( &T ) ;TreeEmpty ( T ) ;TreeDepth ( T ) ;Root ( T ) ;Value ( T , cur_e ) ;Assign ( T , cur_e , value ) ;Parent ( T , cur_e ) ;LeftChild ( T , cur_e ) ;RightSibling ( T , cur_e )

7、;InsertChild ( &T , &p , i , c ) ;DeleteChild ( &T , &p , i ) ;TraverseTree ( T , Visit ( ) ) ; ADT Tree6.26.2 二叉樹一、定義一、定義二叉樹是二叉樹是n(n 0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛鋫€(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹和右子樹的互或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成不相交的二叉樹構(gòu)成特點(diǎn)特點(diǎn)每個(gè)結(jié)點(diǎn)至多有二棵子樹每個(gè)結(jié)點(diǎn)至多有二棵子樹(即不存在度大于即不存在度大于2的結(jié)點(diǎn)的結(jié)點(diǎn))二叉樹

8、的子樹有左、右之分，且其次序不能任意顛倒二叉樹的子樹有左、右之分，且其次序不能任意顛倒基本形態(tài)基本形態(tài)AABABABCADT BinaryTree數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R：若若D，則，則R，稱，稱BinaryTree為空二叉樹；為空二叉樹；若若D，則，則RH，H是如下二元關(guān)系；是如下二元關(guān)系；(1) 在在D中存在唯一的稱為根的數(shù)據(jù)元素中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系，它在關(guān)系H下下無(wú)前驅(qū)；無(wú)前驅(qū)；(2) 若若D-root,則存在則存在D-rootDl,Dr,且且DlDr ；(3) 若若Dl ，則，則D

9、l中存在唯一的元素中存在唯一的元素Xl,H，且，且存在存在Dl上的關(guān)系上的關(guān)系HlH；若；若Dr，則，則Dr中存在唯一的元中存在唯一的元素素Xr，H , 且存在且存在Dr上的關(guān)系上的關(guān)系HrH； H,， Hl, Hr ;(4) (Dl, Hl)是一棵符合本定義的二叉樹是一棵符合本定義的二叉樹,稱為根的左子樹稱為根的左子樹 (Dr,Hr)是一棵符合本定義的二叉樹是一棵符合本定義的二叉樹,稱為根的右子樹稱為根的右子樹基本操作基本操作P：InitBiTree ( &T ) ;DestroyBiTree ( &T )CreateBiTree ( &T , definition

10、) ;ClearBiTree ( &T ) ;BiTreeEmpty ( T ) ;BiTreeDepth ( T ) ;Root ( T ) ;Value ( T , e ) ;Assign ( T , &e , value ) ;Parent ( T , e ) ;LeftChild ( T , e ) ;RightChild ( T , e ) ;LeftSibling ( T , e ) ;RightSibling ( T , e ) ;InsertChild ( T , p , LR , c ) ;DeleteChild ( T , p , LR ) ;PreOrde

11、rTraverse ( T , Visit ( ) ) ;InOrderTraverse ( T , Visit ( ) ) ;PostOrderTraverse ( T , Visit ( ) ) ;LevelOrderTraverse ( T , Visit ( ) ) ;ADT BinaryTree二、二叉樹的性質(zhì)二、二叉樹的性質(zhì)性質(zhì)性質(zhì)1：在二叉樹的第：在二叉樹的第i層上至多有層上至多有2i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(i1)證明：用歸納法證明證明：用歸納法證明 i=1時(shí)時(shí),只有一個(gè)根結(jié)點(diǎn)只有一個(gè)根結(jié)點(diǎn), 2i-1= 20=1 是對(duì)的是對(duì)的 假設(shè)對(duì)所有假設(shè)對(duì)所有j(1 ji)命題成立，即第命題成立

12、，即第j層上至多有層上至多有 2j-1 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) 那么，第那么，第i-1層至多有層至多有2i-2 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) 又二叉樹每個(gè)結(jié)點(diǎn)的度至多為又二叉樹每個(gè)結(jié)點(diǎn)的度至多為2 第第i層上最大結(jié)點(diǎn)數(shù)是第層上最大結(jié)點(diǎn)數(shù)是第i-1層的層的2倍，即倍，即2x2i-2= 2i-1 故命題得證故命題得證性質(zhì)性質(zhì)2：深度為：深度為k的二叉樹至多有的二叉樹至多有2k -1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(k 1)證明：由性質(zhì)證明：由性質(zhì)1知深度為知深度為k 的二叉樹最大結(jié)點(diǎn)數(shù)為的二叉樹最大結(jié)點(diǎn)數(shù)為 k k ( (第第i層上的最大結(jié)點(diǎn)數(shù)層上的最大結(jié)點(diǎn)數(shù))= )= 2i-1= 2k 1 i=1 i=1性質(zhì)性質(zhì)3：對(duì)任何一棵二叉樹：對(duì)任何

13、一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為如果其終端結(jié)點(diǎn)數(shù)為n0，度度 為為2的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n2，則則 n0=n2+1證明：設(shè)證明：設(shè)n1為二叉樹為二叉樹T中度為中度為1的結(jié)點(diǎn)數(shù)的結(jié)點(diǎn)數(shù) 因?yàn)椋憾鏄渲兴薪Y(jié)點(diǎn)的度均小于或等于因?yàn)椋憾鏄渲兴薪Y(jié)點(diǎn)的度均小于或等于2 所以：其結(jié)點(diǎn)總數(shù)所以：其結(jié)點(diǎn)總數(shù)n=n0+n1+n2 又二叉樹中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都只有一個(gè)又二叉樹中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都只有一個(gè) 分支進(jìn)入分支進(jìn)入 設(shè)設(shè)B為分支總數(shù)，則為分支總數(shù)，則n=B+1 又：分支由度為又：分支由度為1和度為和度為2的結(jié)點(diǎn)射出，的結(jié)點(diǎn)射出，B=n1+2n2 于是，于是，n=B+1=n1+2n2+1=n0

14、+n1+n2 n0=n2+1兩種特殊形式的二叉樹兩種特殊形式的二叉樹滿二叉樹滿二叉樹定義：一棵深度為定義：一棵深度為k且有且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹特點(diǎn)：特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)1231145891213671014151234567兩種特殊形式的二叉樹兩種特殊形式的二叉樹完全二叉樹完全二叉樹定義：深度為定義：深度為k，有有n個(gè)結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個(gè)結(jié)個(gè)結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個(gè)結(jié) 點(diǎn)都與深度為點(diǎn)都與深度為k的滿二叉樹中編號(hào)從的滿二叉樹中編號(hào)從1至至n的結(jié)點(diǎn)一一的結(jié)點(diǎn)一一 對(duì)應(yīng)時(shí)，稱為對(duì)應(yīng)時(shí)，稱為完全二叉樹

15、完全二叉樹特點(diǎn)：葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)特點(diǎn)：葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)對(duì)任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為對(duì)任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為l，則則其左分支下子孫的最大層次必為其左分支下子孫的最大層次必為l 或或l+1123114589126710123456性質(zhì)性質(zhì)4：具有：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n +1證明：證明：設(shè)深度為設(shè)深度為k，根據(jù)性質(zhì)，根據(jù)性質(zhì)2和完全二叉樹的定義有和完全二叉樹的定義有 2k-1 -1 n 2k-1或或 2k-1 n 2k于是于是 k-1 log2n 1， 則其雙親是則其雙親是 i/2

16、(2) 如果如果2in，則結(jié)點(diǎn)則結(jié)點(diǎn)i無(wú)左孩子；如果無(wú)左孩子；如果2i n，則其左孩子則其左孩子是是2i (3) 如果如果2i+1n，則結(jié)點(diǎn)則結(jié)點(diǎn)i無(wú)右孩子；如果無(wú)右孩子；如果2i+1 n，則其右則其右孩子是孩子是2i+1123114589126710三、二叉樹的存儲(chǔ)結(jié)構(gòu)三、二叉樹的存儲(chǔ)結(jié)構(gòu)1、順序存儲(chǔ)結(jié)構(gòu)、順序存儲(chǔ)結(jié)構(gòu) 二叉樹的順序存儲(chǔ)表示二叉樹的順序存儲(chǔ)表示 #define MAX_TREE_SIZE 100 typedef TElemType SqBiTree MAX_TREE_SIZE ; SqBiTree bt ; abckdehilfgj例如：例如： bt0 1 2 3 4 5 6

17、 7 8 9 10 11 12 abcdefghijklabcgdef bt0 1 2 3 4 5 6 7 8 9 10 11 12 abcdefgabcdefg順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中浪費(fèi)空間，適于存滿二叉樹和完全二叉樹浪費(fèi)空間，適于存滿二叉樹和完全二叉樹2 2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)dataPARENTLCHILDRCHILDlchilddataparentrchild含有三個(gè)指針域的結(jié)點(diǎn)結(jié)構(gòu)含有三個(gè)指針域的結(jié)點(diǎn)結(jié)構(gòu)lchilddatarchild含有兩個(gè)指針域的結(jié)點(diǎn)結(jié)構(gòu)含有兩個(gè)指針域的結(jié)點(diǎn)結(jié)構(gòu)ABFGDECABC

18、DEFG二叉鏈表A BCDEFG三叉鏈表二叉樹的二叉鏈表存儲(chǔ)表示二叉樹的二叉鏈表存儲(chǔ)表示typedef struct BiTNode TElemType data;struct BiTNode * lchild , * rchild ; BiTNode , * BiTree ;特點(diǎn)：特點(diǎn)： 指針直接表示關(guān)系，操作簡(jiǎn)單指針直接表示關(guān)系，操作簡(jiǎn)單 增加指針域，浪費(fèi)空間，特別是存在多個(gè)空指針域增加指針域，浪費(fèi)空間，特別是存在多個(gè)空指針域6.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹一、遍歷二叉樹一、遍歷二叉樹 遍歷二叉樹遍歷二叉樹(Traversing Binary Tree):(Tr

19、aversing Binary Tree):按某條搜索路徑按某條搜索路徑巡訪樹的每個(gè)結(jié)點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問一次，從而得巡訪樹的每個(gè)結(jié)點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問一次，從而得到樹中所有結(jié)點(diǎn)的一個(gè)線性排列。到樹中所有結(jié)點(diǎn)的一個(gè)線性排列。由二叉樹的遞歸定義可知：由二叉樹的遞歸定義可知： 二叉樹是由三個(gè)基本單元組成：二叉樹是由三個(gè)基本單元組成： 根結(jié)點(diǎn)根結(jié)點(diǎn)、左子樹左子樹、右子樹右子樹DLR則可得到六種遍歷方案：則可得到六種遍歷方案： DLRDLR、LDRLDR、LRDLRD、DRLDRL、RDLRDL、RLDRLD先序遍歷先序遍歷(DLR)(DLR)：先訪問根結(jié)點(diǎn)：先訪問根結(jié)點(diǎn), ,然后分別先序遍歷

20、左子樹、然后分別先序遍歷左子樹、 右子樹右子樹中序遍歷中序遍歷(LDR)(LDR)：先中序遍歷左子樹，然后訪問根結(jié)點(diǎn)，最：先中序遍歷左子樹，然后訪問根結(jié)點(diǎn)，最 后中序遍歷右子樹后中序遍歷右子樹后序遍歷后序遍歷(LRD)(LRD)：先后序遍歷左、右子樹，然后訪問根結(jié)點(diǎn)：先后序遍歷左、右子樹，然后訪問根結(jié)點(diǎn)先序遍歷二叉樹的操作定義為：先序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則若二叉樹為空，則空操作；否則（1 1）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn)（2 2）先序遍歷左子樹）先序遍歷左子樹（3 3）先序遍歷右子樹）先序遍歷右子樹中序遍歷二叉樹的操作定義為：中序遍歷二叉樹的操作定義為：若二叉樹為空，則

21、空操作；否則若二叉樹為空，則空操作；否則（1 1）中序遍歷左子樹）中序遍歷左子樹（2 2）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn)（3 3）中序遍歷右子樹）中序遍歷右子樹后序遍歷二叉樹的操作定義為：后序遍歷二叉樹的操作定義為：若二叉樹為空，則空操作；否則若二叉樹為空，則空操作；否則（1 1）后序遍歷左子樹）后序遍歷左子樹（2 2）后序遍歷右子樹）后序遍歷右子樹（3 3）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn)例：例：ABCGDEF先序序列：先序序列：ABDFEGC中序序列：中序序列：DBFGEAC后序序列：后序序列：DFGBECA先序遍歷二叉樹的遞歸算法先序遍歷二叉樹的遞歸算法Status PreOrderTraverse (

22、BiTree T , Status(* Visit)(TElemType e) ) if（T） if ( Visit ( T-data ) ) if ( PreOrderTraverse ( T-lchild , Visit ) ) if ( PreOrderTraverse ( T-rchild , Visit ) ) return OK ; return ERROR ; else return OK ;Status PreOrderTraverse ( BiTree T ) if（T） Visit ( T-data ) ; PreOrderTraverse ( T-lchild ) ; P

23、reOrderTraverse ( T-rchild ) ; 中序遍歷算法中序遍歷算法Status InOrderTraverse ( BiTree T ) if（T） InOrderTraverse ( T-lchild ) ; Visit ( T-data ) ; InOrderTraverse ( T-rchild ) ; 后序遍歷算法后序遍歷算法Status PostOrderTraverse ( BiTree T ) if（T） PostOrderTraverse ( T-lchild ) ; PostOrderTraverse ( T-rchild ) ; Visit ( T-da

24、ta ) ; 遍歷過程演示：遍歷過程演示：-*cab-*cabbt-*bac先序序列：先序序列：- * a b c遍歷過程演示：遍歷過程演示：-*cab-*cabbt-*bac先序序列：先序序列：- * a b ca*b-c中序序列：中序序列：a * b - c遍歷過程演示：遍歷過程演示：-*cab-*cabbt-*bac先序序列：先序序列：- * a b ca*b-c中序序列：中序序列：a * b - cab*c-中序序列：中序序列：a b * c -中序遍歷的非遞歸算法中序遍歷的非遞歸算法Status InOrderTraverse ( BiTree T , Status(* Visit)

25、(TElemType e) ) InitStack ( S ) ; Push ( S , T ) ; while ( ! StackEmpty ( S ) ) while ( GetTop ( S , p ) & p ) Push ( S , p - lchild ) ; Pop ( S , p ) ; if ( ! StackEmpty ( S ) ) Pop ( S , p ) ; if ( ! Visit ( p-data ) ) return ERROR ; Push ( S , p-rchild ) ; return OK;中序遍歷的非遞歸算法中序遍歷的非遞歸算法Status

26、 InOrderTraverse ( BiTree T , Status(* Visit)(TElemType e) ) InitStack ( S ) ; p = T ; while ( p | ! StackEmpty ( S ) ) if ( p ) Push ( S , p ) ; p = p - lchild ; else Pop ( S , p ) ; if ( ! Visit ( p-data ) ) return ERROR ; p = p - rchild ; return OK;按先序次序輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符），空字符按先序次序輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符），空

27、字符表示空樹，構(gòu)造二叉鏈表表示的二叉樹表示空樹，構(gòu)造二叉鏈表表示的二叉樹TStatus CreateBiTree ( BiTree &T ) scanf ( &ch ) ; if ( ch = ) T = NULL ; else if ( ! ( T = ( BiTNode * ) malloc ( sizeof ( BiTNode ) ) ) ) exit ( OVERFLOW ) ; T - data = ch ; CreateBiTree ( T - lchild ) ; CreateBiTree ( T - rchild ) ; return OK ;二、線索二叉樹（二

28、、線索二叉樹（Threaded Binary）-+/-a*cdefb一棵具有一棵具有n個(gè)結(jié)點(diǎn)二叉樹，用二叉鏈表表示時(shí)，樹中存在個(gè)結(jié)點(diǎn)二叉樹，用二叉鏈表表示時(shí)，樹中存在空指針域的個(gè)數(shù)為：空指針域的個(gè)數(shù)為：n+1利用空指針域指向結(jié)點(diǎn)的前驅(qū)或后繼利用空指針域指向結(jié)點(diǎn)的前驅(qū)或后繼結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)lchildrchildltagdatartag其中：其中：ltag = 0 lchild指向結(jié)點(diǎn)的左孩子指向結(jié)點(diǎn)的左孩子 ltag = 1 lchild指向結(jié)點(diǎn)的前驅(qū)指向結(jié)點(diǎn)的前驅(qū) rtag = 0 rchild指向結(jié)點(diǎn)的右孩子指向結(jié)點(diǎn)的右孩子 rtag = 1 rchild指向結(jié)點(diǎn)的后繼指向結(jié)點(diǎn)的后繼 以這

29、種結(jié)構(gòu)構(gòu)成的二叉鏈表叫線索鏈表，其中指以這種結(jié)構(gòu)構(gòu)成的二叉鏈表叫線索鏈表，其中指向前驅(qū)和后繼的指針稱作線索，加上線索的二叉樹成向前驅(qū)和后繼的指針稱作線索，加上線索的二叉樹成為線索二叉樹。為線索二叉樹。二叉樹的二叉線索存儲(chǔ)表示二叉樹的二叉線索存儲(chǔ)表示Typedef enum Link , Thread PointerTag ;Typedef struct BiThrNode TElemType data ; struct BiThrNode * lchild , * rchild ; PointerTag LTag , RTag ; BiThrNode , * BiThrTree ;-+/-a*

30、cdefb01-00+00/00e11a11*00f11b11-00c11d11thrtbt例如：例如：中序序列：中序序列：a+b*c-d-e/fStatus InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e) P = T - lchild ; while ( p != T ) while ( p - LTag = = Link ) p = p - lchild ; if ( ! Visit ( p - data ) ) return ERROR; while ( p - RTag = = Thread & p - r

31、child != T) p = p - rchild ; Visit ( p - data ) ; p = p - rchild ; return OK中序序列：中序序列：a+b*c-d-e/f01-00+00/00e11a11*00f11b11-00c11d11thrtbt線索化二叉樹線索化二叉樹01thrt空線索化二叉樹空線索化二叉樹Status InOrderThreading ( BiThrTree &Thrt , BiThrTree T ) if ( ! ( Thrt = ( BiThrTree ) malloc ( sizeof ( BithrNode ) ) ) ) ex

32、it ( OVERFLOW ) ; Thrt - LTag = Link ; Thrt - Rtag = Thread ; Thrt - rchild = Thrt ; if ( !T ) Thrt - lchild = Thrt ; else Thrt - lchild = T ; pre = Thrt ; InThreading ( T ) ; pre - rchild = Thrt ; pre - RTag = Thread ; Thrt - rchild = pre ; return OKvoid InThreading ( BiThrTree p ) if ( p ) InThrea

33、ding ( p - lchild ) ; if ( !p-lchild ) p-LTag=Thread ; p-lchild=pre ; if ( !pre-rchild ) pre-RTag=Thread ;pre-rchild=p; pre = p ; InThreading ( p - rchild ) ; 01-00+00/00e11a11*00f11b11-00c11d11thrtbt例：求中序線索樹中給定結(jié)點(diǎn)的后繼結(jié)點(diǎn)例：求中序線索樹中給定結(jié)點(diǎn)的后繼結(jié)點(diǎn)BiThrTree inordernext ( BiThrTree p ) if ( p-RTag = Thread ) ret

34、urn ( p-rchild ) ; else q = p-rchild ; while ( q-LTag=Link ) q = q-lchild ; return ( q ) ; 6.4 6.4 樹與森林樹與森林一、樹的存儲(chǔ)結(jié)構(gòu)一、樹的存儲(chǔ)結(jié)構(gòu)1 1、雙親表示法、雙親表示法用結(jié)構(gòu)數(shù)組存放樹的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)含兩個(gè)域：用結(jié)構(gòu)數(shù)組存放樹的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)含兩個(gè)域：數(shù)據(jù)域：存放結(jié)點(diǎn)本身信息數(shù)據(jù)域：存放結(jié)點(diǎn)本身信息雙親域：指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中位置雙親域：指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中位置 特點(diǎn)特點(diǎn): 找雙親容易，找孩子難找雙親容易，找孩子難ABCHDEIFGA-1B0C0D1E1F2G4H4I40

35、12345678data parent樹的雙親表示樹的雙親表示#define MAX_TREE_SIZE 100typedef struct PTNode TElemType data ; int parent ; PTNode ; typedef struct PTNode nodes MAX_TREE_SIZE ;int n ; PTree ;例：求結(jié)點(diǎn)例：求結(jié)點(diǎn)ti的長(zhǎng)子的長(zhǎng)子Int FirstChild ( Ptree t , int i ) for ( j= i+1 ; j t.n ; j+ ) if ( t.nodesj.parent = i ) return ( j ) ; re

36、turn (-1) ;2 2、孩子表示法、孩子表示法l多重鏈表：每個(gè)結(jié)點(diǎn)有多個(gè)指針域，分別指向其子樹多重鏈表：每個(gè)結(jié)點(diǎn)有多個(gè)指針域，分別指向其子樹 的根的根u結(jié)點(diǎn)同構(gòu)：結(jié)點(diǎn)的指針個(gè)數(shù)相等，為樹的度結(jié)點(diǎn)同構(gòu)：結(jié)點(diǎn)的指針個(gè)數(shù)相等，為樹的度d ddatachild1 child2childdu結(jié)點(diǎn)不同構(gòu)：結(jié)點(diǎn)指針個(gè)數(shù)不等，結(jié)點(diǎn)不同構(gòu)：結(jié)點(diǎn)指針個(gè)數(shù)不等， degreedegree為該結(jié)點(diǎn)的度為該結(jié)點(diǎn)的度d ddatachild1child2childddegree浪費(fèi)空間操作不便ABCHDEIFGl孩子鏈表表示：孩子鏈表表示：ABCDEFGHI01234567813467852data firstch

37、ild如何找雙親結(jié)點(diǎn)ABCHDEIFGl孩子鏈表表示：孩子鏈表表示：A-1B0C0D1E1F2G4H4I401234567813467852data parent firstchild樹的孩子鏈表存儲(chǔ)表示樹的孩子鏈表存儲(chǔ)表示typedef struct CTNode int child; struct CTNode * next ; * ChildPtr ;typedef struct TElemType data ; Childptr firstchild ; CTBox;typedef struct CTBox nodes MAX_TREE_SIZE ; int n, r; /結(jié)點(diǎn)數(shù)和根的

38、位置結(jié)點(diǎn)數(shù)和根的位置 CTree ;3 3、孩子兄弟表示法：、孩子兄弟表示法： -二叉鏈表表示法二叉鏈表表示法 用二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)用二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)typedef struct CSNode ElemType data; struct CSNode * firstchild , * nextsibling ; CSNode , *CSTree ; firstchilddatanextsibling例：例：ABCHDEIFGA B C D E F G

39、 H I 二、森林與二叉樹的轉(zhuǎn)換二、森林與二叉樹的轉(zhuǎn)換 借助于二叉鏈表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)樹與二叉樹的轉(zhuǎn)換借助于二叉鏈表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)樹與二叉樹的轉(zhuǎn)換ACBED樹樹 A B C D E ABCDE二叉樹 A B C D E A B C D E 存儲(chǔ)存儲(chǔ)解釋解釋存儲(chǔ)存儲(chǔ)解釋解釋加線：在兄弟之間加一連線刪線：對(duì)每個(gè)結(jié)點(diǎn)，除了其長(zhǎng)子孩子外，去除其與其余 孩子之間的關(guān)系旋轉(zhuǎn)：以樹的根結(jié)點(diǎn)為軸心，將整樹順時(shí)針旋轉(zhuǎn)ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹轉(zhuǎn)換成的二叉樹其右子樹一定為空樹轉(zhuǎn)換成的二叉樹其右子樹一定為空將樹轉(zhuǎn)換成二叉樹 從樹與二叉樹的轉(zhuǎn)換可知：任何一棵

40、和樹對(duì)應(yīng)的二叉從樹與二叉樹的轉(zhuǎn)換可知：任何一棵和樹對(duì)應(yīng)的二叉樹，其右子樹必為空，若把森林中第二棵樹的根結(jié)點(diǎn)看成樹，其右子樹必為空，若把森林中第二棵樹的根結(jié)點(diǎn)看成是第一棵樹根結(jié)點(diǎn)的兄弟，則可導(dǎo)出森林和二叉樹的對(duì)應(yīng)是第一棵樹根結(jié)點(diǎn)的兄弟，則可導(dǎo)出森林和二叉樹的對(duì)應(yīng)關(guān)系。關(guān)系。森林轉(zhuǎn)換成二叉樹森林轉(zhuǎn)換成二叉樹如果如果F T1，T2，Tm是森林，則可按如下規(guī)則轉(zhuǎn)是森林，則可按如下規(guī)則轉(zhuǎn)換成一棵二叉樹換成一棵二叉樹B（ root , LB , RB ）。）。（1）若）若F為空，即為空，即m0，則，則B為空樹為空樹（2）若）若F非空，即非空，即m0，則，則B的根的根root即為森林中第一棵即為森林中第一棵

41、樹的根樹的根ROOT（T1）；）；B的左子樹的左子樹LB是從是從T1中根結(jié)點(diǎn)的子中根結(jié)點(diǎn)的子樹森林樹森林F1T11，T12，T1m1轉(zhuǎn)換而成的二叉樹；轉(zhuǎn)換而成的二叉樹；其右子樹其右子樹RB是從森林是從森林F=T2，T3，Tm轉(zhuǎn)換而成的轉(zhuǎn)換而成的二叉樹。二叉樹。二叉樹轉(zhuǎn)換成森林二叉樹轉(zhuǎn)換成森林如果如果B（ root , LB , RB ）是一棵二叉樹，則可按如下規(guī)）是一棵二叉樹，則可按如下規(guī)則轉(zhuǎn)換成森林則轉(zhuǎn)換成森林FT1，T2，Tm；（1）若）若B為空，則為空，則F為空；為空；（2）若）若B非空，則非空，則F中第一棵樹中第一棵樹T1的根的根ROOT（T1）即為）即為二叉樹二叉樹B的根的根root

42、；T1中根結(jié)點(diǎn)的子樹森林中根結(jié)點(diǎn)的子樹森林F1是由是由B的左的左子樹子樹LB轉(zhuǎn)換而成的森林；轉(zhuǎn)換而成的森林；F中除中除T1之外其余樹組成的森林之外其余樹組成的森林F=T2，T3，Tm是由是由B的右子樹的右子樹RB轉(zhuǎn)換而成的森轉(zhuǎn)換而成的森林林。將各棵樹分別轉(zhuǎn)換成二叉樹將各棵樹分別轉(zhuǎn)換成二叉樹將每棵樹的根結(jié)點(diǎn)用線相連將每棵樹的根結(jié)點(diǎn)用線相連以第一棵樹根結(jié)點(diǎn)為二叉樹的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，以第一棵樹根結(jié)點(diǎn)為二叉樹的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)構(gòu)成二叉樹型結(jié)構(gòu)ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ森林轉(zhuǎn)換成二叉樹森林轉(zhuǎn)換成二叉

43、樹三、樹和森林的遍歷三、樹和森林的遍歷RT1T1T11)1)先根遍歷先根遍歷2)2)后根遍歷后根遍歷三、樹和森林的遍歷三、樹和森林的遍歷先根（序）遍歷先根（序）遍歷 若若T非空，則：非空，則： 1、訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn)R 2、依次先序遍歷根的各子樹依次先序遍歷根的各子樹ABCHDEIFG先根序列：先根序列：A BDGEHICF三、樹和森林的遍歷三、樹和森林的遍歷后根（序）遍歷后根（序）遍歷 若若T非空，則：非空，則： 1、依次后序遍歷根的各子樹依次后序遍歷根的各子樹 2、訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn)RABCHDEIFG先根序列：先根序列：A BDGEHICF后根序列：后根序列：D G HEIBF CA

44、ABCHDEIFG先根序列：先根序列： A BDGEHICF后根序列：后根序列：D G HEIBF CAABCHDEIFG先序序列：先序序列： A BDGEHICF中序序列：中序序列： D G HEIBF CA后序序列：后序序列： IH GDEFC BA按照森林和樹的相互遞歸定義，可推出森林的兩種遍歷方法按照森林和樹的相互遞歸定義，可推出森林的兩種遍歷方法1)1)先序遍歷森林先序遍歷森林 若森林非空，則若森林非空，則 訪問森林中第一棵樹的根結(jié)點(diǎn)訪問森林中第一棵樹的根結(jié)點(diǎn) 先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林 先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林先序遍歷除去

45、第一棵樹之后剩余的樹構(gòu)成的森林ABCHDEIFGJ先序序列先序序列A B CEDF G H IJ按照森林和樹的相互遞歸定義，可推出森林的兩種遍歷方法按照森林和樹的相互遞歸定義，可推出森林的兩種遍歷方法2)2)中序遍歷森林中序遍歷森林 若森林非空，則若森林非空，則 中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林 訪問第一棵樹的根結(jié)點(diǎn)訪問第一棵樹的根結(jié)點(diǎn) 中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林ABCHDEIFGJ先序序列先序序列A B CEDF G H IJ中序序列中序序列B C DFAE H JIGABCHDEIFG

46、J先序序列先序序列A B CEDF G H IJ中序序列中序序列B C DFAE H JIGABCHDEIFGJ先序序列先序序列A B CEDF G H IJ中序序列中序序列B C DFAE H JIG后序序列后序序列D C BJFIH G E A6.6 赫夫曼赫夫曼(Huffman)樹及其應(yīng)用樹及其應(yīng)用一、赫夫曼一、赫夫曼(Huffman)樹樹-最優(yōu)樹最優(yōu)樹l路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這 兩個(gè)結(jié)點(diǎn)間的路徑兩個(gè)結(jié)點(diǎn)間的路徑l路徑路徑長(zhǎng)度：路徑上的分支數(shù)長(zhǎng)度：路徑上的分支數(shù)l樹的路徑長(zhǎng)度：從樹根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和樹的路徑

47、長(zhǎng)度：從樹根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和l結(jié)點(diǎn)的帶權(quán)路徑結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：長(zhǎng)度： 該結(jié)點(diǎn)到根的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積。該結(jié)點(diǎn)到根的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積。l樹的帶權(quán)路徑樹的帶權(quán)路徑長(zhǎng)度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。長(zhǎng)度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。 n記作：記作： wpl = wklk k=1定義：給定一組權(quán)定義：給定一組權(quán)w1 w2 wn , 且且w1 w2 wn ，設(shè)有一個(gè)二叉樹，共有設(shè)有一個(gè)二叉樹，共有n片葉子，分別帶權(quán)片葉子，分別帶權(quán)w1 w2 wn ，該二叉樹稱為帶權(quán)二叉樹。該二叉樹稱為帶權(quán)二叉樹。最優(yōu)二叉樹或最優(yōu)二叉樹或Huffman樹樹設(shè)有設(shè)有n個(gè)權(quán)值個(gè)權(quán)值w

48、1 w2 wn ，構(gòu)造一棵有構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子的個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子的權(quán)值為權(quán)值為wi,則則wpl最小的最小的那棵那棵二叉樹叫二叉樹叫最優(yōu)二叉樹或最優(yōu)二叉樹或Huffman樹樹.例有例有4 4個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn), ,權(quán)值分別為權(quán)值分別為7,5,2,4,7,5,2,4,構(gòu)造有構(gòu)造有4 4個(gè)葉子結(jié)點(diǎn)的二叉樹個(gè)葉子結(jié)點(diǎn)的二叉樹abcd7524(1) WPL=7*2+5*2+2*2+4*2=36dcab2475(2) WPL= 4* 2+7*3+5*3+2*1=46abcd7524(3) WPL=7*1+5*2+2*3+4*3=35例：將百分制成績(jī)轉(zhuǎn)換成例：將百分制成績(jī)轉(zhuǎn)換成5

49、 5級(jí)分制成績(jī)級(jí)分制成績(jī)if ( a60 ) b = “bad” ;else if ( a70 ) b = “pass” ; else if ( a80 ) b = “general” ; else if ( a90 ) b = “good” ; else b = “excellent” 分?jǐn)?shù)分?jǐn)?shù) 比例比例 0-59 60-69 70-79 80-89 90-100 0.05 0.15 0.40 0.30 0.10a80a70a60a90不及格不及格及格及格中等中等良好良好優(yōu)秀優(yōu)秀YYYYNNNN設(shè)有設(shè)有10000個(gè)記錄個(gè)記錄需需31500次比較次比較需需22000次比較次比較定理：定理：u設(shè)

50、設(shè)T為帶權(quán)為帶權(quán)w1 w2 wn 的最優(yōu)樹的最優(yōu)樹 則則 a ) 帶權(quán)帶權(quán)w1, ,w2的葉子的葉子Vw1,Vw2是兄弟是兄弟 b ) 以以Vw1,Vw2為兒子的分枝點(diǎn)，其通路長(zhǎng)度最長(zhǎng)。為兒子的分枝點(diǎn)，其通路長(zhǎng)度最長(zhǎng)。u設(shè)設(shè)T為帶權(quán)為帶權(quán)w1 w2 wn 的最優(yōu)樹，若將以帶權(quán)的最優(yōu)樹，若將以帶權(quán)w1, ,w2 的樹葉為兒子的分枝點(diǎn)改為帶權(quán)的樹葉為兒子的分枝點(diǎn)改為帶權(quán)w1+ +w2的樹葉，得到新樹的樹葉，得到新樹T， 則則T也是最優(yōu)樹。也是最優(yōu)樹。Huffman樹的樹的構(gòu)造構(gòu)造 根據(jù)給定的根據(jù)給定的n個(gè)權(quán)值個(gè)權(quán)值w1,w2,wn構(gòu)構(gòu)成成n棵二叉樹的棵二叉樹的集合集合F=T1,T2,Tn，其中每棵

51、二叉樹，其中每棵二叉樹Ti中中只有一只有一個(gè)帶權(quán)為個(gè)帶權(quán)為Wi的的結(jié)點(diǎn)，其左右子樹均為空。結(jié)點(diǎn)，其左右子樹均為空。 在在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作左右子樹，構(gòu)中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，造一棵新的二叉樹，且且置新的二叉樹根結(jié)點(diǎn)的權(quán)值為置新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左右子樹根結(jié)點(diǎn)權(quán)值之和。其左右子樹根結(jié)點(diǎn)權(quán)值之和。 在在F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入森中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入森林中林中1. 重復(fù)重復(fù)2、3上述兩步，上述兩步，直到直到F只含一棵樹為止，這棵樹只含一棵樹為止，這棵樹即即為為哈夫曼樹。哈夫曼樹。例a7b5c2d4a7b5c

52、2d46a7b5c2d4611a7b5c2d461118例 w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 23148715292914871529113581923421135819234229148715295811358192342291487152958100二、二、Haffman編碼編碼前綴碼：給定一個(gè)序列的集合，若沒有一個(gè)序列是另一個(gè)前綴碼：給定一個(gè)序列的集合，若沒有一個(gè)序列是另一個(gè)序列的前綴，該序列集合稱為前綴碼。序列的前綴，該序列

53、集合稱為前綴碼。例如：例如： 000，001，01，10，11 1 ，0001，000 定理：任意一棵二叉樹的樹葉可對(duì)應(yīng)一個(gè)前綴碼。定理：任意一棵二叉樹的樹葉可對(duì)應(yīng)一個(gè)前綴碼。定理：任何一個(gè)前綴碼都對(duì)應(yīng)一棵二叉樹。定理：任何一個(gè)前綴碼都對(duì)應(yīng)一棵二叉樹。 數(shù)據(jù)傳輸過程中字符的編碼問題。數(shù)據(jù)傳輸過程中字符的編碼問題。 在為字符編碼時(shí)，總希望總的編碼長(zhǎng)度盡可能地短，因在為字符編碼時(shí)，總希望總的編碼長(zhǎng)度盡可能地短，因電文中每個(gè)字符出現(xiàn)的頻率不同，所以可用前綴碼，對(duì)常電文中每個(gè)字符出現(xiàn)的頻率不同，所以可用前綴碼，對(duì)常出現(xiàn)的字符用短碼表示，使得到電文總長(zhǎng)度最短。出現(xiàn)的字符用短碼表示，使得到電文總長(zhǎng)度最短。 假設(shè)每個(gè)字符在電文中出現(xiàn)的次數(shù)為假設(shè)每個(gè)字符在電文中出現(xiàn)的次數(shù)為wi，其編碼長(zhǎng)度，其編碼長(zhǎng)度為為li，電文中只有，電文中只有n中字