第六章樹和二叉樹

1、第六章第六章 樹和二叉樹樹和二叉樹 本章內(nèi)容本章內(nèi)容p樹、二叉樹的定義、性質(zhì)和存儲結(jié)構(gòu)；p二叉樹的遍歷和線索化以及遍歷算法的各種描述形式；p樹遍歷；p二叉樹的多種應(yīng)用。 本章要點本章要點p熟練掌握二叉樹的結(jié)構(gòu)特性；p熟悉二叉樹的各種存儲結(jié)構(gòu)的特點及適用范圍；p熟練掌握二叉樹各種遍歷策略的遞歸和非遞歸算法，了解遍歷過程中“?！钡淖饔煤蜖顟B(tài)，而且能靈活運用遍歷算法實現(xiàn)二叉樹的其它操作；p理解二叉樹線索化的實質(zhì)是建立結(jié)點與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系；p熟悉樹的各種存儲結(jié)構(gòu)及其特點；p學(xué)會編寫實現(xiàn)樹的各種操作的算法；p了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和哈夫曼編碼的方法。6.1 樹的定義和

2、基本術(shù)語樹的定義和基本術(shù)語樹的定義樹的定義p樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)；p樹是n(n0)個結(jié)點的有限集，非空樹滿足：n有且僅有一個特定的稱之為有且僅有一個特定的稱之為(root)的結(jié)點；的結(jié)點；n除根以外的其余結(jié)點可分為除根以外的其余結(jié)點可分為m(0 mn)個互不相交的個互不相交的子集子集t1,t2,t3tm，其中每個子集本身又是一棵樹，其中每個子集本身又是一棵樹，且且稱為根的稱為根的。樹的表示方法樹的表示方法p特點：除根結(jié)點外，每個結(jié)點都僅有一個前趨(父)結(jié)點。p其它表示方法：n嵌套集合表示法嵌套集合表示法n凹入表表示法凹入表表示法參見教材參見教材120頁頁ab

3、 c de f g h ij1層2層3層4層樹的一些基本術(shù)語樹的一些基本術(shù)語p結(jié)點的度（結(jié)點的度（degree）n結(jié)點所擁有的子樹的數(shù)目。結(jié)點所擁有的子樹的數(shù)目。p葉子結(jié)點（葉子結(jié)點（leaf-又稱終端結(jié)點又稱終端結(jié)點 terminal node）n度為零的結(jié)點。度為零的結(jié)點。p分支結(jié)點（分支結(jié)點（branch node）n度不為零的結(jié)點度不為零的結(jié)點p孩子（孩子（ child）n結(jié)點的子樹的根稱為結(jié)點的孩子。結(jié)點的子樹的根稱為結(jié)點的孩子。樹的一些基本術(shù)語樹的一些基本術(shù)語(續(xù)續(xù))p雙親（雙親（ parent）n結(jié)點是其孩子的雙親。結(jié)點是其孩子的雙親。p祖先（祖先（ forefather）n從樹

4、根到雙親的所有結(jié)點稱為該結(jié)點的祖先。從樹根到雙親的所有結(jié)點稱為該結(jié)點的祖先。p子孫（子孫（progeny）n以結(jié)點為根的子樹的所有結(jié)點稱為該結(jié)點的子孫。以結(jié)點為根的子樹的所有結(jié)點稱為該結(jié)點的子孫。p兄弟（兄弟（sibling）n同一父母的所有孩子互稱兄弟。同一父母的所有孩子互稱兄弟。p層次（層次（level）n樹根為第一層，其孩子為第二層，孫子為第三層，以樹根為第一層，其孩子為第二層，孫子為第三層，以此類推。此類推。樹的一些基本術(shù)語樹的一些基本術(shù)語(續(xù)續(xù))p堂兄弟（堂兄弟（cousin）n雙親在同一層的結(jié)點互稱堂兄弟。雙親在同一層的結(jié)點互稱堂兄弟。p深度（深度（depth）n樹中結(jié)點的最大層次

5、稱為樹的深度。樹中結(jié)點的最大層次稱為樹的深度。p有序樹（有序樹（ordered tree）n結(jié)點各子樹從左至右是有秩序的樹稱為有序樹。結(jié)點各子樹從左至右是有秩序的樹稱為有序樹。p無序樹（無序樹（unordered tree）n結(jié)點各子樹沒有秩序的樹稱為無序樹。結(jié)點各子樹沒有秩序的樹稱為無序樹。p森林（森林（forest ）n森林是森林是 m (m0) 棵互不相交的樹的集合?？没ゲ幌嘟坏臉涞募稀涞幕静僮鳂涞幕静僮鱬初始化操作inittree(&t)p求根函數(shù) root(t)p求雙親函數(shù) parent(t,cur_e)p求左孩子結(jié)點函數(shù)leftchild(t,cur_e)p建樹函數(shù)crea

6、tetree(&t,definiton)p清空樹函數(shù)cleartree(&t)p插入子樹函數(shù)insertchild(&t,&p,i,c)p刪除子樹函數(shù)deletechild(&t,&p,i)p遍歷函數(shù)traversetree(t,visit()p求右兄弟函數(shù)rightsibling(t,cur_e)6.2 二叉樹二叉樹二叉樹的定義二叉樹的定義p定義n二叉樹是二叉樹是n(n 0)個結(jié)點的有限集合，它或為空個結(jié)點的有限集合，它或為空樹樹(n=0)，或由一個根結(jié)點和兩棵互不相交的左，或由一個根結(jié)點和兩棵互不相交的左子樹和右子樹的二叉樹組成。子樹和右子樹的二叉樹組成。p二叉樹的特點：n定義是遞歸的；定

7、義是遞歸的；n0 結(jié)點的度結(jié)點的度 2；n是有序樹。是有序樹。二叉樹（續(xù)）二叉樹（續(xù)）p二叉樹的五種基本形態(tài)p兩種特殊的二叉樹n滿二叉樹：每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)。滿二叉樹：每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)。n完全二叉樹：只有最下面兩層結(jié)點的度可小于完全二叉樹：只有最下面兩層結(jié)點的度可小于2，而最，而最下一層的葉結(jié)點集中在左邊若干位置上。下一層的葉結(jié)點集中在左邊若干位置上。12 34 5 6 712 34 5 6 78 9 10二叉樹的性質(zhì)二叉樹的性質(zhì)p性質(zhì)1n二叉樹的第二叉樹的第i層上至多有層上至多有2i-1(i 1)個結(jié)點。個結(jié)點。p性質(zhì)2n深度為深度為k的二叉樹至多有的二叉樹至多有2

8、k-1個結(jié)點個結(jié)點(k 1)。p性質(zhì)3n對任何一棵二叉樹對任何一棵二叉樹t，如果其終端結(jié)點數(shù)為，如果其終端結(jié)點數(shù)為n0，度為，度為2的的結(jié)點數(shù)為結(jié)點數(shù)為n2 ，則，則n0 = n2 + 1。p性質(zhì)4n具有具有n個結(jié)點的完全二叉樹的深度為個結(jié)點的完全二叉樹的深度為 log2n +1。二叉樹的性質(zhì)（續(xù)）二叉樹的性質(zhì)（續(xù)）p性質(zhì)5n對一棵具有對一棵具有n個結(jié)點的完全二叉樹個結(jié)點的完全二叉樹(其深度為其深度為 log2n +1)，對其結(jié)點按層從上至下對其結(jié)點按層從上至下(每層從左至右每層從左至右)進(jìn)行進(jìn)行0至至n-1的編的編號，則對任一結(jié)點號，則對任一結(jié)點i(0 i0，則i的雙親是(i-1)/2。p若

9、2i+1n，則i有左孩子，左孩子是2i+1。p若2(i+1)lchild); preorder(t-rchild); void inorder(bitree t) if (t) inorder(t-lchild); visit(t); inorder(t-rchild); void postorder(bitree t) if (t) postorder(t-lchild); postorder(t -rchild); visit( t ); 遍歷二叉樹的遞歸算法遍歷二叉樹的遞歸算法p利用遍歷結(jié)果確定二叉樹問題n先序序列先序序列+中序序列中序序列n中序序列中序序列+后序序列后序序列n先序序列先

10、序序列+后序序列后序序列 (x) 先序序列: abcdefgh 中序序列: bdceafhgabfcgdeh思考：層序+先序/中序/后序， 能否確定？如何做？利用遍歷結(jié)果確定二叉樹問題利用遍歷結(jié)果確定二叉樹問題例如：層序abcdefghij,中序dbgehjacif 根據(jù)先序中序求后序的算法根據(jù)先序中序求后序的算法void get_post(char *pre, char *in, char *post, int n)if ( n = 0) return;for (k = 0; k n; k+) if (ink = pre0) break;if (! k rchild); push(p-lch

11、ild); 先序遍歷的非遞歸算法先序遍歷的非遞歸算法(2)非遞歸算法,考慮取消多余的空指針入棧,空指針個數(shù)可觀，為n+1個init_stack();p = t;push(null); while (p) visit(p); if (p-rchild) push(p-rchild); if (p-lchild) p = p-lchild; else p = pop();init_stack();p = t;while (!stack_empty() | p) visit(p); if (p-rchild) push(p-rchild); if (p-lchild) p = p-lchild; e

12、lse p = pop();后序遍歷的非遞歸算法后序遍歷的非遞歸算法后序遍歷的非遞歸算法后序遍歷的非遞歸算法(1)p非遞歸算法 init_stack();push(root,0);while(!stack_empty() p = pop(&state); if (p = null) continue; if (state = 0) push(p, 1); push(p-lchild, 0); else if (state = 1) push(p, 2); push(p-rchild, 0); else visit(p); 后序遍歷的非遞歸算法后序遍歷的非遞歸算法(2)p非遞歸算法 init_s

13、tack();push(root, 0);while(!stack_empty() p = pop(&state); if (p = null) continue; if (state = 0) push(p, 2); push(p-rchild, 0); push(p-lchild, 0); else visit(p); 中序遍歷的非遞歸算法中序遍歷的非遞歸算法中序遍歷的非遞歸算法中序遍歷的非遞歸算法(1)p樸素的算法 init_stack();push(root, 0);while(!stack_empty() p = pop(&state); if (p = null) continue

14、; if (state = 0) push(p, 1); push(p-lchild, 0); else if (state = 1) visit(p); push(p-rchild, 0); p效率問題效率問題 新壓入堆棧的新壓入堆棧的state0節(jié)點馬上彈出然后再次壓入作為節(jié)點馬上彈出然后再次壓入作為state1節(jié)點節(jié)點中序遍歷的非遞歸算法中序遍歷的非遞歸算法(2) init_stack(); p = root; while (p) push(p); p = p-lchild; while(!stack_empty() p = pop(); visit(p); p = p-rchild;

15、while (p) push(p); p = p-lchild; init_stack(); p = root; while (p | !stack_empty() if (p) push(p); p = p-lchild; else p = pop(); visit(p); p = p-rchild; 二叉樹遍歷的應(yīng)用二叉樹遍歷的應(yīng)用二叉樹遍歷的應(yīng)用二叉樹遍歷的應(yīng)用p在二叉樹中查找結(jié)點值為x的結(jié)點p求二叉樹中每個結(jié)點所處的層次p求二叉樹的高度p復(fù)制一棵二叉樹6.4 樹和森林樹和森林樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu):雙親表示法雙親表示法a b c d e f g 0 01033 1 2 3 4 5 6

16、abcefgd 存儲方法：使用順序結(jié)構(gòu)存儲方法：使用順序結(jié)構(gòu)#define max_tree_size 100typedef struct ptnode telemtype data; int parent; ptnode; /* 節(jié)點的存儲結(jié)構(gòu)節(jié)點的存儲結(jié)構(gòu)*/typedef struct /* 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) */ ptnode nodesmax_tree_size; int r, n; /* 根位置和節(jié)點數(shù)根位置和節(jié)點數(shù)*/ ptree;優(yōu)點：簡單，緊湊，易于尋找雙親節(jié)點優(yōu)點：簡單，緊湊，易于尋找雙親節(jié)點缺點：查詢某節(jié)點的孩子效率低缺點：查詢某節(jié)點的孩子效率低樹的存儲結(jié)構(gòu)樹的存

17、儲結(jié)構(gòu):孩子表示法孩子表示法 方法一 struct ptnode telemtype data; struct ptnode *childnum_child; ; 缺點：num_child值不容易確定; 空域數(shù)目太多方法二： 改進(jìn)方法1，記錄節(jié)點的度，分配合適大小的內(nèi)存方法三： 使用鏈表勾鏈，鏈表的每個節(jié)點記錄一個孩子指針優(yōu)缺點比較和其他存儲方案 選用的實際存儲結(jié)構(gòu)該考慮到可能需要操作（增加，刪除，檢索）樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu):孩子表示法孩子表示法(方法方法3) abcefgdabcdefg1234650123456 樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu):孩子表示法孩子表示法(方法方法2) #defin

18、e max_tree_size 100struct tnode telemtype data; int degree; int child1;struct ptree struct tnode *nodemax_tree_size; int n; ptree;struct tnode *create_tnode(void) struct tnode *p; int k, degree; scanf(“%d”, °ree); p = malloc(sizeof(struct tnode)+(degree-1)* sizeof(int); p-degree = degree; for (k

19、= 0; k childk); input_node_data(p); return(p);樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)(孩子兄弟表示法孩子兄弟表示法)p孩子兄弟表示法abcdefgabcefgd森林與二叉樹的轉(zhuǎn)換森林與二叉樹的轉(zhuǎn)換p轉(zhuǎn)換原則n按孩子兄弟表示法進(jìn)行轉(zhuǎn)換。按孩子兄弟表示法進(jìn)行轉(zhuǎn)換。p樹與二叉樹的轉(zhuǎn)換de森林與二叉樹的轉(zhuǎn)換森林與二叉樹的轉(zhuǎn)換樹和森林的遍歷樹和森林的遍歷p樹的遍歷abcde f gabecdfgn先序遍歷先序遍歷p先訪問樹的根結(jié)點，然后依次先根遍歷根的每棵子樹； abefcdg(二叉樹先序)n后序遍歷后序遍歷p先依次后根遍歷根的每棵子樹，然后訪問樹的根結(jié)點 efbcgda

20、(二叉樹中序)森林的遍歷森林的遍歷p先序遍歷：n訪問森林中第一棵樹的根結(jié)點；n先序遍歷第一棵樹中根結(jié)點的子樹森林；n先序遍歷除第一棵樹外剩余的樹構(gòu)成的森林；舉例：a b c d e f g h i jp中序遍歷n中序遍歷森林中第一棵樹的根結(jié)點的子樹森林；n訪問第一棵樹的根結(jié)點；n中序遍歷除第一棵樹外剩余的樹構(gòu)成的森林舉例：b c d a f e h j i g6.5 樹的等價問題樹的等價問題集合的查找與合并集合的查找與合并p集合的運算nfind(x) 判斷元素判斷元素x屬于哪個集合屬于哪個集合nmerge(si, sj) 將集合將集合si和和sj合并合并p集合的數(shù)據(jù)結(jié)構(gòu)有多種實現(xiàn)方法n位圖法位

21、圖法 o(1)n有序表方法有序表方法 o(n)n樹型結(jié)構(gòu)表示集合樹型結(jié)構(gòu)表示集合p采用的結(jié)構(gòu)取決于集合大小和所進(jìn)行的操作樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu):雙親表示法雙親表示法a b c d e f g 0 01033 1 2 3 4 5 6abcefgd 存儲方法：使用順序結(jié)構(gòu)存儲方法：使用順序結(jié)構(gòu)#define max_tree_size 100typedef struct ptnode telemtype data; int parent; ptnode; /* 節(jié)點的存儲結(jié)構(gòu)節(jié)點的存儲結(jié)構(gòu)*/typedef struct /* 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) */ ptnode nodesmax_tr

22、ee_size; int r, n; /* 根位置和節(jié)點數(shù)根位置和節(jié)點數(shù)*/ ptree;優(yōu)點：簡單，緊湊，易于尋找雙親節(jié)點優(yōu)點：簡單，緊湊，易于尋找雙親節(jié)點缺點：查詢某節(jié)點的孩子效率低缺點：查詢某節(jié)點的孩子效率低樹型結(jié)構(gòu)表示集合樹型結(jié)構(gòu)表示集合p采用雙親表示法，存儲一個森林type ptree mfset; int find_mfset(mfset s, int i) if (i = s.n) return -1; for (j = i; s.nodesj.parent = 0; j = s.nodesj.parent); return j;status merge_mfset(mfset

23、s, int i, int j) if (i = s.n | j = s.n) return error; s.nodei.parent = j; return ok;算法分析和改進(jìn)算法分析和改進(jìn)p分析算法的效率n合并合并o(1),檢索檢索o(d)，nd為深度，最糟糕情況下，為深度，最糟糕情況下，d = np改進(jìn)思路n合并時，將數(shù)量少的集合，合并到數(shù)量多的集合中合并時，將數(shù)量少的集合，合并到數(shù)量多的集合中n根的根的parent記錄集合中節(jié)點個數(shù)，為區(qū)別于正常記錄集合中節(jié)點個數(shù)，為區(qū)別于正常parent值，用負(fù)數(shù)值，用負(fù)數(shù)p改進(jìn)后的分析n合并合并o(1)，樹深度低于，樹深度低于log2n改進(jìn)后的

24、合并算法改進(jìn)后的合并算法void mix_mfset(mfset s, int i, int j) if (s.nodesi.parent s.nodesj.parent) /* i中節(jié)點少 */ swap(i, j); /* i中節(jié)點多 */ s.nodesi.parent += s.nodesj.parent; s.j.parent = i;改進(jìn)后的檢索算法改進(jìn)后的檢索算法int fix_mfset(mfset s, int i) for(j=i; s.nodesj.parent=0; j=s.nodesj.parent); for (k = i; k != j; k = t) t = s

25、.nodesk.parent; s.nodesk.parent = j; return j;改進(jìn)思路： 檢索時壓縮路徑6.6 赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用p赫夫曼樹n最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹；n路徑長度p指樹中兩個結(jié)點間路徑上所含有的分支數(shù)目。n樹的路徑長度p指從樹根到每一結(jié)點的路徑長度之和。n帶權(quán)路徑長度p指結(jié)點的路徑長度與該結(jié)點的權(quán)之積。赫夫曼樹赫夫曼樹p樹的帶權(quán)路徑長度n樹中所有葉子結(jié)點的帶權(quán)路徑長度；樹中所有葉子結(jié)點的帶權(quán)路徑長度；p最優(yōu)二叉樹或赫夫曼樹nwpl 最小的二叉樹最小的二叉樹結(jié)點到根的路徑長度權(quán)值其中：記作：kknkkklwlw

26、wpl1赫夫曼樹的特點赫夫曼樹的特點p赫夫曼樹中除葉子結(jié)點外，所有分支結(jié)點的度均為2；p葉子結(jié)點（外部結(jié)點）可看成是由分支結(jié)點（內(nèi)部結(jié)點）組成的樹擴充出來的（擴充二叉樹）赫夫曼樹的構(gòu)造赫夫曼樹的構(gòu)造1.根據(jù)給定的n個權(quán)值w1,w2,.wn構(gòu)成n棵二叉樹的集合f=t1,t2,.,tn，其中每棵二叉樹ti中只有一個帶權(quán)為wi的根結(jié)點，其左右子樹均空；2.在f中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。3.在f中刪除這兩棵樹，同時將新得到的二叉樹加入f中；4.重復(fù)2和3，直到f中只含一棵樹為止；5.這棵樹就是赫夫曼樹；例

27、例 w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 23148715292914871529113581923421135819234229148715295811358192342291487152958100赫夫曼樹構(gòu)造舉例赫夫曼樹構(gòu)造舉例1赫夫曼編碼的存儲結(jié)構(gòu)和構(gòu)造算法赫夫曼編碼的存儲結(jié)構(gòu)和構(gòu)造算法p初始有n個葉子結(jié)點(0n-1號)，構(gòu)造出的哈夫曼樹有2n-1個結(jié)點p用大小m=2n-1的向量存儲哈夫曼樹（順序存儲） struct htnod

28、e int weight; int parent, lchild, rchild; *ht;m = 2 * n - 1;ht = malloc(m*sizeof(struct htnode);for (p=&ht0; p parent = -1;輸入ht前n個元素的weight;for (i = n; i m; i+) 在ht的前i個節(jié)點中尋找parent為-1且weight最小的兩個節(jié)點s1,s2 hts1.parent = hts2.parent = i; hti.lchild = s1; hti.rchild = s2; hti.weight = hts1.weight + hts2.w

29、eight;例：例：已知字符 a，b，c，d，e，f，g，使用頻度分別為：0.25，0.1，0.15，0.06 ， 0.3 ，0.05，0.09，試以此構(gòu)造霍夫曼樹。gb0.19a0.44fd0.11c0.26e0.5611) 0.25 0.1 0.15 0.06 0.3 0.05 0.092) 0.25 0.1 0.15 0.3 0.09 0.11 3) 0.25 0.15 0.3 0.11 0.19 4) 0.25 0.3 0.19 0.265) 0.3 0.26 0.446) 0.44 0.567) 1.00赫夫曼樹構(gòu)造舉例赫夫曼樹構(gòu)造舉例11、最佳判定樹；2、霍夫曼編碼：gbafdce

30、000000111111a: 01b: 001c: 101d: 1001e: 11f: 1000g: 000e: 100a: 000b: 001c: 010d: 011f: 101g: 110000000111111gbafdce0wpl霍夫曼編碼 = 2.56wpl等長編碼 = 3 利用霍夫曼編碼可提高效率：( 3 - 2.56 ) / 3 15%霍夫曼樹的應(yīng)用霍夫曼樹的應(yīng)用赫夫曼編碼赫夫曼編碼p主數(shù)據(jù)結(jié)構(gòu)：構(gòu)造哈夫曼編碼表，使用ht的parent域p輔助數(shù)據(jù)結(jié)構(gòu)：char cdn;char *get_code(int i) / 求i號符號的編碼串 cdn - 1 = 0; start =

31、n - 1; for (c = i, f = htc.parent; f != -1; c = f, f = htf.parent) cd-start = htf.lchild = c ? 0 : 1; return &cdstart;p解碼程序比較簡單，從樹根出發(fā)按1或0分別走向右或左孩子，直到葉子節(jié)點，解出編碼的符號赫夫曼解碼赫夫曼解碼decode() / 求i號符號的編碼串 k = 2 * n - 2；/* 樹根節(jié)點 */ for(j = 0; j rcv_buf_len; j+) k = rcvbufj = 0 ? htk.lchild : htk.rchild; if (k n) out_code(k); /* 解出第k號符號 */ k = 2 * n 2; p解碼程序:從樹根出發(fā)按1或0分別走向右或左孩子，直到葉子節(jié)點，解出編碼的符號赫夫曼編碼的特點赫夫曼編碼的特點n赫夫曼編碼是不等長編碼；赫夫曼編碼是不等長編碼；n赫夫曼編碼是前綴編碼，即任一字符的編碼都不是另一赫夫曼編碼是前綴編碼，即任一字符的編碼都不是另一字符編碼的前綴；字符編碼的前綴；n赫夫曼編碼樹中沒有度為赫夫曼編碼樹中沒有度為1的結(jié)點。若葉子結(jié)點的個數(shù)為的結(jié)點。若葉子結(jié)點的個數(shù)為n，則赫夫曼編碼樹的結(jié)點總數(shù)為，則赫夫曼編碼樹的結(jié)