第六章樹和二叉樹

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

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

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

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

5、稱為樹的深度。樹中結(jié)點(diǎn)的最大層次稱為樹的深度。p有序樹（有序樹（ordered tree）n結(jié)點(diǎn)各子樹從左至右是有秩序的樹稱為有序樹。結(jié)點(diǎn)各子樹從左至右是有秩序的樹稱為有序樹。p無序樹（無序樹（unordered tree）n結(jié)點(diǎn)各子樹沒有秩序的樹稱為無序樹。結(jié)點(diǎn)各子樹沒有秩序的樹稱為無序樹。p森林（森林（forest ）n森林是森林是 m (m0) 棵互不相交的樹的集合。棵互不相交的樹的集合。樹的基本操作樹的基本操作p初始化操作inittree(&t)p求根函數(shù) root(t)p求雙親函數(shù) parent(t,cur_e)p求左孩子結(jié)點(diǎn)函數(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)個(gè)結(jié)點(diǎn)的有限集合，它或?yàn)榭諅€(gè)結(jié)點(diǎn)的有限集合，它或?yàn)榭諛錁?n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的左，或由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的左子樹和右子樹的二叉樹組成。子樹和右子樹的二叉樹組成。p二叉樹的特點(diǎn)：n定義是遞歸的；定

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

8、k-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(k 1)。p性質(zhì)3n對(duì)任何一棵二叉樹對(duì)任何一棵二叉樹t，如果其終端結(jié)點(diǎn)數(shù)為，如果其終端結(jié)點(diǎn)數(shù)為n0，度為，度為2的的結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù)為n2 ，則，則n0 = n2 + 1。p性質(zhì)4n具有具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n +1。二叉樹的性質(zhì)（續(xù)）二叉樹的性質(zhì)（續(xù)）p性質(zhì)5n對(duì)一棵具有對(duì)一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹個(gè)結(jié)點(diǎn)的完全二叉樹(其深度為其深度為 log2n +1)，對(duì)其結(jié)點(diǎn)按層從上至下對(duì)其結(jié)點(diǎn)按層從上至下(每層從左至右每層從左至右)進(jìn)行進(jìn)行0至至n-1的編的編號(hào)，則對(duì)任一結(jié)點(diǎn)號(hào)，則對(duì)任一結(jié)點(diǎn)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)非遞歸算法,考慮取消多余的空指針入棧,空指針個(gè)數(shù)可觀，為n+1個(gè)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é)點(diǎn)馬上彈出然后再次壓入作為節(jié)點(diǎn)馬上彈出然后再次壓入作為state1節(jié)點(diǎn)節(jié)點(diǎn)中序遍歷的非遞歸算法中序遍歷的非遞歸算法(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é)點(diǎn)值為x的結(jié)點(diǎn)p求二叉樹中每個(gè)結(jié)點(diǎn)所處的層次p求二叉樹的高度p復(fù)制一棵二叉樹6.4 樹和森林樹和森林樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu):雙親表示法雙親表示法a b c d e f g 0 01033 1 2 3 4 5 6

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

17、儲(chǔ)結(jié)構(gòu):孩子表示法孩子表示法 方法一 struct ptnode telemtype data; struct ptnode *childnum_child; ; 缺點(diǎn)：num_child值不容易確定; 空域數(shù)目太多方法二： 改進(jìn)方法1，記錄節(jié)點(diǎn)的度，分配合適大小的內(nèi)存方法三： 使用鏈表勾鏈，鏈表的每個(gè)節(jié)點(diǎn)記錄一個(gè)孩子指針優(yōu)缺點(diǎn)比較和其他存儲(chǔ)方案 選用的實(shí)際存儲(chǔ)結(jié)構(gòu)該考慮到可能需要操作（增加，刪除，檢索）樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu):孩子表示法孩子表示法(方法方法3) abcefgdabcdefg1234650123456 樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(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);樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(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é)點(diǎn)，然后依次先根遍歷根的每棵子樹； abefcdg(二叉樹先序)n后序遍歷后序遍歷p先依次后根遍歷根的每棵子樹，然后訪問樹的根結(jié)點(diǎn) efbcgda

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

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

22、ee_size; int r, n; /* 根位置和節(jié)點(diǎn)數(shù)根位置和節(jié)點(diǎn)數(shù)*/ ptree;優(yōu)點(diǎn)：簡(jiǎn)單，緊湊，易于尋找雙親節(jié)點(diǎn)優(yōu)點(diǎn)：簡(jiǎn)單，緊湊，易于尋找雙親節(jié)點(diǎn)缺點(diǎn)：查詢某節(jié)點(diǎn)的孩子效率低缺點(diǎn)：查詢某節(jié)點(diǎn)的孩子效率低樹型結(jié)構(gòu)表示集合樹型結(jié)構(gòu)表示集合p采用雙親表示法，存儲(chǔ)一個(gè)森林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í)，將數(shù)量少的集合，合并到數(shù)量多的集合中n根的根的parent記錄集合中節(jié)點(diǎn)個(gè)數(shù)，為區(qū)別于正常記錄集合中節(jié)點(diǎn)個(gè)數(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é)點(diǎn)少 */ swap(i, j); /* i中節(jié)點(diǎn)多 */ 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)思路： 檢索時(shí)壓縮路徑6.6 赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用p赫夫曼樹n最優(yōu)樹，是一類帶權(quán)路徑長(zhǎng)度最短的樹；n路徑長(zhǎng)度p指樹中兩個(gè)結(jié)點(diǎn)間路徑上所含有的分支數(shù)目。n樹的路徑長(zhǎng)度p指從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。n帶權(quán)路徑長(zhǎng)度p指結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)之積。赫夫曼樹赫夫曼樹p樹的帶權(quán)路徑長(zhǎng)度n樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度；樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度；p最優(yōu)二叉樹或赫夫曼樹nwpl 最小的二叉樹最小的二叉樹結(jié)點(diǎn)到根的路徑長(zhǎng)度權(quán)值其中：記作：kknkkklwlw

26、wpl1赫夫曼樹的特點(diǎn)赫夫曼樹的特點(diǎn)p赫夫曼樹中除葉子結(jié)點(diǎn)外，所有分支結(jié)點(diǎn)的度均為2；p葉子結(jié)點(diǎn)（外部結(jié)點(diǎn)）可看成是由分支結(jié)點(diǎn)（內(nèi)部結(jié)點(diǎn)）組成的樹擴(kuò)充出來的（擴(kuò)充二叉樹）赫夫曼樹的構(gòu)造赫夫曼樹的構(gòu)造1.根據(jù)給定的n個(gè)權(quán)值w1,w2,.wn構(gòu)成n棵二叉樹的集合f=t1,t2,.,tn，其中每棵二叉樹ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹均空；2.在f中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。3.在f中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入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赫夫曼編碼的存儲(chǔ)結(jié)構(gòu)和構(gòu)造算法赫夫曼編碼的存儲(chǔ)結(jié)構(gòu)和構(gòu)造算法p初始有n個(gè)葉子結(jié)點(diǎn)(0n-1號(hào))，構(gòu)造出的哈夫曼樹有2n-1個(gè)結(jié)點(diǎn)p用大小m=2n-1的向量存儲(chǔ)哈夫曼樹（順序存儲(chǔ)） 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個(gè)元素的weight;for (i = n; i m; i+) 在ht的前i個(gè)節(jié)點(diǎn)中尋找parent為-1且weight最小的兩個(gè)節(jié)點(diǎn)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等長(zhǎng)編碼 = 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號(hào)符號(hào)的編碼串 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解碼程序比較簡(jiǎn)單，從樹根出發(fā)按1或0分別走向右或左孩子，直到葉子節(jié)點(diǎn)，解出編碼的符號(hào)赫夫曼解碼赫夫曼解碼decode() / 求i號(hào)符號(hào)的編碼串 k = 2 * n - 2；/* 樹根節(jié)點(diǎn) */ for(j = 0; j rcv_buf_len; j+) k = rcvbufj = 0 ? htk.lchild : htk.rchild; if (k n) out_code(k); /* 解出第k號(hào)符號(hào) */ k = 2 * n 2; p解碼程序:從樹根出發(fā)按1或0分別走向右或左孩子，直到葉子節(jié)點(diǎn)，解出編碼的符號(hào)赫夫曼編碼的特點(diǎn)赫夫曼編碼的特點(diǎn)n赫夫曼編碼是不等長(zhǎng)編碼；赫夫曼編碼是不等長(zhǎng)編碼；n赫夫曼編碼是前綴編碼，即任一字符的編碼都不是另一赫夫曼編碼是前綴編碼，即任一字符的編碼都不是另一字符編碼的前綴；字符編碼的前綴；n赫夫曼編碼樹中沒有度為赫夫曼編碼樹中沒有度為1的結(jié)點(diǎn)。若葉子結(jié)點(diǎn)的個(gè)數(shù)為的結(jié)點(diǎn)。若葉子結(jié)點(diǎn)的個(gè)數(shù)為n，則赫夫曼編碼樹的結(jié)點(diǎn)總數(shù)為，則赫夫曼編碼樹的結(jié)