第5章樹與二叉樹

1、基本內(nèi)容基本內(nèi)容： 樹的基本概念樹的基本概念 樹和樹林的存儲表示樹和樹林的存儲表示 樹與樹林的周游（遍歷）樹與樹林的周游（遍歷） 二叉樹二叉樹 二叉樹的存儲表示二叉樹的存儲表示 二叉樹的周游和線索二叉樹二叉樹的周游和線索二叉樹 樹、樹林與二叉樹的轉(zhuǎn)換樹、樹林與二叉樹的轉(zhuǎn)換 哈夫曼樹和哈夫曼編碼哈夫曼樹和哈夫曼編碼線性結(jié)構(gòu)線性結(jié)構(gòu)： 唯一前驅(qū)、后繼，一對一關系。唯一前驅(qū)、后繼，一對一關系。非線性結(jié)構(gòu)非線性結(jié)構(gòu)：存在兩個或兩個以上前驅(qū)或后繼。：存在兩個或兩個以上前驅(qū)或后繼。 一對多，或多對多的關系。一對多，或多對多的關系。層次關系層次關系的問題可以用樹、二叉樹表示的問題可以用樹、二叉樹表示重點重點

2、： 樹、二叉樹的存儲結(jié)構(gòu)樹、二叉樹的存儲結(jié)構(gòu) 二叉樹的操作及其運算的實現(xiàn)二叉樹的操作及其運算的實現(xiàn) 樹、樹林與二叉樹的轉(zhuǎn)換樹、樹林與二叉樹的轉(zhuǎn)換 Haffman樹與樹與Haffman編碼編碼樹的定義樹的定義樹的邏輯表示樹的邏輯表示：T = (N, R)N = A, B, C, D, E, F, G, H, I, JR = , , , , , , , , A, B, , J 結(jié)點結(jié)點 , 樹支（關系）樹支（關系）一對多的關系，允許多個后繼。一對多的關系，允許多個后繼。5.1 5.1 樹的基本概念樹的基本概念樹的定義樹的定義基本術(shù)語（概念）基本術(shù)語（概念）樹林樹林樹的基本運算樹的基本運算ABCDE

3、FGHIJ樹的遞歸定義樹的遞歸定義：n(n0)個結(jié)點的有窮集合個結(jié)點的有窮集合T，當，當T非空時非空時滿足：滿足： 有且僅有一個特別標志的稱為有且僅有一個特別標志的稱為根根的結(jié)點的結(jié)點 除根外，其余結(jié)點分為除根外，其余結(jié)點分為m0個個互不相交互不相交的非空集合的非空集合T1、T2、Tm，而且每個非空集合，而且每個非空集合Ti又是一顆樹，稱為又是一顆樹，稱為T的的子樹子樹。樹的特點樹的特點： 根無前驅(qū)，其它結(jié)點有根無前驅(qū)，其它結(jié)點有唯一前驅(qū)唯一前驅(qū) 除樹葉（無子樹的結(jié)點）結(jié)點外，其它結(jié)點有除樹葉（無子樹的結(jié)點）結(jié)點外，其它結(jié)點有一個或一個或多個后繼多個后繼空樹空樹基本術(shù)語（概念）基本術(shù)語（概念）

4、父結(jié)點、子結(jié)點、邊父結(jié)點、子結(jié)點、邊 若若y為為x的一顆子樹的根，的一顆子樹的根，x為為y的父結(jié)點的父結(jié)點 y為為x的子結(jié)點，的子結(jié)點， 有向?qū)τ邢驅(qū)閺臑閺膞到到y(tǒng)的邊的邊兄弟兄弟：同一父母的結(jié)點互為兄弟同一父母的結(jié)點互為兄弟祖先、子孫祖先、子孫 若若y在在x的一顆子樹中（的一顆子樹中（yx)， x為為y的祖先，的祖先，y為為x的子孫的子孫路徑、路徑長度路徑、路徑長度 從祖先從祖先x到子孫到子孫y的邊的序列為的邊的序列為x到到y(tǒng)的路徑，的路徑， 邊的數(shù)目為路徑長度邊的數(shù)目為路徑長度結(jié)點的層、樹的層數(shù)結(jié)點的層、樹的層數(shù) 根的層為根的層為0，其余結(jié)點的層為父結(jié)點層，其余結(jié)點的層為父結(jié)點層+1 樹

5、的層數(shù)：樹的層數(shù)：結(jié)點的最大層數(shù)結(jié)點的最大層數(shù)【空樹空樹: 0, 其它其它:11】ABDCHIFGE124389675樹的深度和高度樹的深度和高度：結(jié)點的最大層數(shù)結(jié)點的最大層數(shù) 【空樹空樹: 0, 其它其它: 11】結(jié)點的度和樹的度結(jié)點的度和樹的度 結(jié)點的子樹個數(shù)為結(jié)點的度，結(jié)點的子樹個數(shù)為結(jié)點的度， 最大結(jié)點的度為樹的度最大結(jié)點的度為樹的度樹葉和分支結(jié)點樹葉和分支結(jié)點 度數(shù)為度數(shù)為0的結(jié)點為樹葉（終端結(jié)點），的結(jié)點為樹葉（終端結(jié)點）， 其余結(jié)點為分支結(jié)點其余結(jié)點為分支結(jié)點無序樹、有序樹無序樹、有序樹： 子樹無次序的樹為無向樹，否則為有向樹子樹無次序的樹為無向樹，否則為有向樹結(jié)點的次序結(jié)點的次

6、序 在有向樹中從左往右規(guī)定結(jié)點的次序，在有向樹中從左往右規(guī)定結(jié)點的次序， 以右結(jié)點為根的子樹中所有結(jié)點以右結(jié)點為根的子樹中所有結(jié)點 皆在左結(jié)點的右邊。皆在左結(jié)點的右邊。ABDCHIFGE124389675 零顆或多顆互不相交的樹構(gòu)成樹林（森林），樹根互為兄零顆或多顆互不相交的樹構(gòu)成樹林（森林），樹根互為兄弟。對樹中每個結(jié)點而言，其子樹的集合即為樹林。弟。對樹中每個結(jié)點而言，其子樹的集合即為樹林。 就邏輯結(jié)構(gòu)而言，任何一棵樹是一個二元組就邏輯結(jié)構(gòu)而言，任何一棵樹是一個二元組Tree=(root,F),其中其中root稱為樹的根結(jié)點；稱為樹的根結(jié)點；F是是m（m=0）棵子樹構(gòu)成的樹）棵子樹構(gòu)成的樹

7、林，林，F(xiàn)=(T1, T2,Tm), 其中其中Ti=(ri,Fi)稱作根稱作根root的第的第i棵子樹；棵子樹；當當m 0時，在樹根和其子樹林之間存在下列關系時，在樹根和其子樹林之間存在下列關系: RF= | i=1,2,m, m03. 樹林樹林4. 樹的基本運算樹的基本運算 創(chuàng)建一顆空樹創(chuàng)建一顆空樹 判斷是否為空樹判斷是否為空樹 求根結(jié)點求根結(jié)點 求父結(jié)點求父結(jié)點 求第一個子結(jié)點求第一個子結(jié)點 求右兄弟求右兄弟 遍歷樹（樹的周游）遍歷樹（樹的周游）5.2 樹和樹林的存儲表示樹和樹林的存儲表示選擇存儲表示方法原則選擇存儲表示方法原則：結(jié)點本身：結(jié)點本身+結(jié)點之間的關系結(jié)點之間的關系樹的存儲表示

8、（三種）樹的存儲表示（三種）父結(jié)點表示法父結(jié)點表示法 雙親表示法，雙親表示法，上層（前驅(qū)）關系上層（前驅(qū)）關系子表表示法子表表示法 孩子表示法，孩子表示法，下層（后繼）關系下層（后繼）關系長子長子-兄弟表示法兄弟表示法 孩子兄弟表示法，孩子兄弟表示法，下層（長子）和同下層（長子）和同層（兄弟）關系層（兄弟）關系樹的存儲表示樹的存儲表示樹林的存儲表示樹林的存儲表示（1）父結(jié)點表示法）父結(jié)點表示法 用一組用一組連續(xù)空間連續(xù)空間存儲樹的結(jié)點，并附設一個指示器指示其存儲樹的結(jié)點，并附設一個指示器指示其雙親結(jié)點的位置。結(jié)構(gòu)類型如下：雙親結(jié)點的位置。結(jié)構(gòu)類型如下：typedef struct ParTre

9、eNode /* 樹中結(jié)點結(jié)構(gòu)樹中結(jié)點結(jié)構(gòu) */ DataTypeinfo; /* 結(jié)點信息結(jié)點信息 */intparent; /* 父結(jié)點位置父結(jié)點位置 */ ParTreeNodetypedef struct ParTreeParTreeNode nodelistMAXNUM;intn;ParTree, *PParTree;結(jié)點順序存放，結(jié)點的位置由結(jié)點在數(shù)組中的下標給出。根結(jié)點順序存放，結(jié)點的位置由結(jié)點在數(shù)組中的下標給出。根結(jié)點無父結(jié)點，因此其結(jié)點無父結(jié)點，因此其parent為為-1。優(yōu)點優(yōu)點：a) 容易求根、找父結(jié)點及其所有的祖先；容易求根、找父結(jié)點及其所有的祖先； b) 能找到結(jié)點的

10、子女和兄弟；能找到結(jié)點的子女和兄弟；缺點缺點：a) 沒有表示出結(jié)點之間的左右次序沒有表示出結(jié)點之間的左右次序 （無法求最左右兄弟）；（無法求最左右兄弟）； b) 找結(jié)點的子女和兄弟比較費事；找結(jié)點的子女和兄弟比較費事；改進方法改進方法：按一種周游次序在數(shù)組中存放結(jié)點。：按一種周游次序在數(shù)組中存放結(jié)點。 常見的一種方法是依次存放樹的常見的一種方法是依次存放樹的先根序列先根序列，如下圖：，如下圖：Infoparenta-1b0c0d1e1f2g2h4i4j4普通改進改進后，任何結(jié)點的所有子孫都在該結(jié)點后連續(xù)存放。找長子運算找長子運算：如果存在長子，必定在結(jié)點的下一個位置 if (t-nodelis

11、tp+1.parent = p)return p+1;else return -1;找右兄弟運算找右兄弟運算：與結(jié)點具有相同父結(jié)點的后面結(jié)點parent = t-nodelistp.parent; for (i = p+1; i n; i+)if (t-nodelisti.parent = parent)return i;return 1;優(yōu)點：存儲密度高，求雙親和最左子女方便缺點：求右兄弟等運算麻煩。（2）子表表示法）子表表示法typedef struct EdgeNode /* 子表中結(jié)點的結(jié)構(gòu)子表中結(jié)點的結(jié)構(gòu) */int node_position;struct EdgeNode *ne

12、xt; EdgeNode;typedef struct ChiTreeNode /* 結(jié)點表中結(jié)點的結(jié)構(gòu)結(jié)點表中結(jié)點的結(jié)構(gòu) */DataType info;EdgeNode *children; ChiTreeNode;結(jié)點表中包含所有結(jié)點，其每一元素除了包含結(jié)點信息外還包結(jié)點表中包含所有結(jié)點，其每一元素除了包含結(jié)點信息外還包含一個含一個子表子表，存放該結(jié)點的所有子結(jié)點。結(jié)點表順序存放，子，存放該結(jié)點的所有子結(jié)點。結(jié)點表順序存放，子表用鏈接表示表用鏈接表示(按照從左往右次序存放子結(jié)點）。按照從左往右次序存放子結(jié)點）。typedef struct ChiTree /* 樹結(jié)構(gòu)樹結(jié)構(gòu) */ChiT

13、reeNode node_listMAXNUM;introot; /* 根結(jié)點的位置根結(jié)點的位置 */intn; /* 結(jié)點的個數(shù)結(jié)點的個數(shù) */ ChiTree, *PChiTree;優(yōu)點優(yōu)點： 方便找左子女、找所有子女等方便找左子女、找所有子女等缺點缺點： 找父結(jié)點、找右兄弟麻煩找父結(jié)點、找右兄弟麻煩找右兄弟找右兄弟：for (m=0; m n; m+) v = t-nodelistm.children;while (v) if (v-node_position = p) if (v-next) return v-next-node_position;else return 1; v =

14、v-next; 找雙親找雙親： for (m = 0; m n; m+) v = t-nodelistm.children; while(v) if (v-nodeposition = p) return(m);v = v-next; return 1; 找到包含p的子表。在子表中，右邊的結(jié)點即為右兄弟找到包含p的子表。該子表對應的結(jié)點即為雙親如果沒有root，如何找根？（3）長子）長子-兄弟表示法兄弟表示法typedef struct CSNode/* 結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu) */DataType info;/* 結(jié)點信息結(jié)點信息 */struct CSNode *lchild;/* 最左子女最左

15、子女 */struct CSNode *rsibling;/* 右兄弟右兄弟 */ CSTree, *PCSTree;優(yōu)點優(yōu)點：方便找子女、找兄弟等運算：方便找子女、找兄弟等運算缺點缺點：找父結(jié)點麻煩：找父結(jié)點麻煩注意注意: 通過長子通過長子-兄弟表示法，將一顆樹轉(zhuǎn)換為一顆二叉樹。并兄弟表示法，將一顆樹轉(zhuǎn)換為一顆二叉樹。并且在此二叉樹中，根結(jié)點的右兄弟指針一定為空（根無兄弟），且在此二叉樹中，根結(jié)點的右兄弟指針一定為空（根無兄弟），該二叉樹根結(jié)點無右子樹，在樹林存儲表示中將用到此指針。該二叉樹根結(jié)點無右子樹，在樹林存儲表示中將用到此指針。找子女找子女： 找到長子，再沿著找右兄弟的指針找所有子女

16、找到長子，再沿著找右兄弟的指針找所有子女找父結(jié)點找父結(jié)點：首先找到長子，然后再找父結(jié)點。：首先找到長子，然后再找父結(jié)點。思考：思考：如何修改長子如何修改長子-兄弟存儲結(jié)構(gòu)，更方便找雙親？兄弟存儲結(jié)構(gòu)，更方便找雙親？typedef struct CSNode/* 結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu) */DataType info; /* 結(jié)點信息結(jié)點信息 */ struct CSNode *parent;/* 父結(jié)點父結(jié)點 */struct CSNode *lchild;/* 最左子女最左子女 */struct CSNode *rsibling;/* 右兄弟右兄弟 */ CSTree, *PCSTree;2. 樹

17、林的存儲表示（與樹對應的三種）樹林的存儲表示（與樹對應的三種）父結(jié)點表示法父結(jié)點表示法 雙親表示法雙親表示法子表表示法子表表示法 孩子表示法孩子表示法長子長子-兄弟表示法兄弟表示法 孩子兄弟表示法孩子兄弟表示法 （1）父結(jié)點表示法）父結(jié)點表示法(2) 子表表示法子表表示法(3) 長子長子-兄弟表示兄弟表示法法思考：如何求森林中包含幾棵樹？5.3 樹和樹林的周游（遍歷）樹和樹林的周游（遍歷）周游的定義：周游的定義：按照某種按照某種規(guī)則（次序）規(guī)則（次序）訪問樹或樹林中的所有結(jié)訪問樹或樹林中的所有結(jié)點，并且每個結(jié)點只能訪問一次。點，并且每個結(jié)點只能訪問一次。本質(zhì)本質(zhì)：將非線性結(jié)構(gòu)轉(zhuǎn)換為元素線性序列

18、。：將非線性結(jié)構(gòu)轉(zhuǎn)換為元素線性序列。樹的周游樹的周游按深度方向周游按深度方向周游縱向遍歷縱向遍歷 先根遍歷先根遍歷 中根遍歷中根遍歷 后根遍歷后根遍歷按寬度方向周游按寬度方向周游橫向遍歷橫向遍歷 樹的周游樹的周游樹林的周游樹林的周游與周游結(jié)合的存儲與周游結(jié)合的存儲（1）深度方向）深度方向先根遍歷先根遍歷 先訪問根，再按照從左往右先訪問根，再按照從左往右次序次序先根遍歷先根遍歷根的每顆子樹。根的每顆子樹。 先根序列先根序列(1,2,3,5,8,9,6,10,4,7)中根遍歷中根遍歷 先先中根遍歷中根遍歷最左子樹，再訪最左子樹，再訪問根，再按照從左往右次序問根，再按照從左往右次序中根遍歷中根遍歷根

19、根的其它子樹。的其它子樹。 中根次序中根次序(2,1,8,5,9,3,10,6,7,4)后根遍歷后根遍歷 按照從左往右次序按照從左往右次序后根遍歷后根遍歷根的每顆子樹，再訪問根根的每顆子樹，再訪問根 后根次序后根次序(2,8,9,5,10,6,3,7,4,1)特點特點： a) 在先、中和后根遍歷序列在先、中和后根遍歷序列中，樹結(jié)點的左右次序不變中，樹結(jié)點的左右次序不變; b) 在先根遍歷序列在先根遍歷序列中，中， 結(jié)點的所有子孫都緊密排列在該結(jié)點的右邊；結(jié)點的所有子孫都緊密排列在該結(jié)點的右邊； 假定假定post(n)表示結(jié)點表示結(jié)點n在先根序列中的位置，在先根序列中的位置， desc(n)表示

20、結(jié)點表示結(jié)點n的子孫個數(shù)，的子孫個數(shù)， 則結(jié)點則結(jié)點x是結(jié)點是結(jié)點n的子孫的充分必要條件為：的子孫的充分必要條件為： post(n)+desc(n) post(x) post(n) c) 在后根遍歷序列在后根遍歷序列中，中， 結(jié)點的所有子孫都緊密排列在該結(jié)點的左邊；結(jié)點的所有子孫都緊密排列在該結(jié)點的左邊； 假定假定post(n)表示結(jié)點表示結(jié)點n在后根序列中的位置，在后根序列中的位置， desc(n)表示結(jié)點表示結(jié)點n的子孫個數(shù)，的子孫個數(shù)， 則結(jié)點則結(jié)點x是結(jié)點是結(jié)點n的子孫的充分必要條件為：的子孫的充分必要條件為： post(n)-desc(n) post(x) 1, 其雙親結(jié)點是其雙親結(jié)

21、點是 【b】2in，結(jié)點結(jié)點i無左孩子；否則無左孩子；否則，其左孩子是結(jié)點其左孩子是結(jié)點2i 【c】2i+1n，結(jié)點結(jié)點i無右孩子；否則無右孩子；否則，其右孩子是結(jié)點其右孩子是結(jié)點2i+1（6） 在在擴充二叉樹擴充二叉樹中，外部結(jié)點的個數(shù)比內(nèi)部結(jié)點個數(shù)多中，外部結(jié)點的個數(shù)比內(nèi)部結(jié)點個數(shù)多1（7） 對于任意對于任意擴充二叉樹擴充二叉樹，外部路徑長度，外部路徑長度E和內(nèi)部路徑長度和內(nèi)部路徑長度I滿足如下關系：滿足如下關系：E=I+2n，其中，其中n為內(nèi)部結(jié)點個數(shù)。為內(nèi)部結(jié)點個數(shù)。2/ i) 1(log2n證明證明：n=0， E=0， I=0，結(jié)論成立，結(jié)論成立 n=1， E=2， I=0，結(jié)論成立

22、，結(jié)論成立 假定對于任意假定對于任意n，有：，有：En=In+2n 現(xiàn)在考慮現(xiàn)在考慮n+1個內(nèi)部結(jié)點的擴充二叉樹。個內(nèi)部結(jié)點的擴充二叉樹。在在n+1個內(nèi)部結(jié)點的擴充二叉樹中刪除一個原來二叉樹作為樹葉個內(nèi)部結(jié)點的擴充二叉樹中刪除一個原來二叉樹作為樹葉的、路徑長度為的、路徑長度為K的內(nèi)部結(jié)點，使之成為包含的內(nèi)部結(jié)點，使之成為包含n個內(nèi)部結(jié)點的擴個內(nèi)部結(jié)點的擴充二叉樹。由于刪除了一個路徑長度為充二叉樹。由于刪除了一個路徑長度為K的內(nèi)部結(jié)點，的內(nèi)部結(jié)點，內(nèi)部路內(nèi)部路徑長度徑長度的變化為：的變化為： In=In+1-K 刪除了一個路徑長度為刪除了一個路徑長度為K的內(nèi)部結(jié)點導致刪除了兩個外部的內(nèi)部結(jié)點導致

23、刪除了兩個外部路徑長度為路徑長度為K+1的外部結(jié)點，增加了一個路徑長度為的外部結(jié)點，增加了一個路徑長度為K的外部結(jié)的外部結(jié)點，點，外部路徑長度外部路徑長度的變化為：的變化為： En= En+1 -2(K+1)+K = En+1-K-2即，即， En+1 = En+K+2= In+2n+K+2= In+K+2(n+1)= In+1+2(n+1)因此，因此，n+1時結(jié)論成立。時結(jié)論成立。3. 二叉樹的基本運算二叉樹的基本運算創(chuàng)建創(chuàng)建一棵一棵空空二叉樹；二叉樹；判判斷某棵二叉樹是否為斷某棵二叉樹是否為空空；求二叉樹的求二叉樹的根結(jié)點根結(jié)點，若為空，則返回一特殊值；，若為空，則返回一特殊值；求二叉樹中

24、某個指定結(jié)點的求二叉樹中某個指定結(jié)點的父結(jié)點父結(jié)點，當指定結(jié)點為根時，當指定結(jié)點為根時，返回一特殊值；返回一特殊值；求二叉樹中某個指定結(jié)點的求二叉樹中某個指定結(jié)點的左子女左子女結(jié)點，當指定結(jié)點沒有結(jié)點，當指定結(jié)點沒有左子女時，返回一特殊值；左子女時，返回一特殊值；求二叉樹中某個指定結(jié)點的求二叉樹中某個指定結(jié)點的右子女右子女結(jié)點，當指定結(jié)點沒有結(jié)點，當指定結(jié)點沒有右子女時，返回一特殊值；右子女時，返回一特殊值；二叉樹的二叉樹的周游周游，即按某種方式訪問二叉樹中的所有結(jié)點，即按某種方式訪問二叉樹中的所有結(jié)點，并使每個結(jié)點恰好被訪問一次。并使每個結(jié)點恰好被訪問一次。返回二叉鏈表返回二叉鏈表5.5 二

25、叉樹的存儲表示二叉樹的存儲表示順序表示順序表示 （1）完全二叉樹）完全二叉樹 根據(jù)性質(zhì)根據(jù)性質(zhì)5，結(jié)點序號可以反映結(jié)點的邏輯關系，因此可以用，結(jié)點序號可以反映結(jié)點的邏輯關系，因此可以用一維數(shù)組按照從上到下、從左往右的順序存儲樹中所有結(jié)點，一維數(shù)組按照從上到下、從左往右的順序存儲樹中所有結(jié)點，通過通過數(shù)組元素下標反映完全二叉樹中結(jié)點的邏輯關系數(shù)組元素下標反映完全二叉樹中結(jié)點的邏輯關系。ABDHCGFEIJBACDEFGHIJ數(shù)組下標：數(shù)組下標： 0 1 2 3 4 5 6 7 8 9順序表示順序表示鏈接表示鏈接表示（2）一般二叉樹）一般二叉樹 如果仍然采用上述完全二叉樹方式存儲，則數(shù)組下標不能如

26、果仍然采用上述完全二叉樹方式存儲，則數(shù)組下標不能反映結(jié)點之間的邏輯關系。為此，可以首先對一般的二叉樹反映結(jié)點之間的邏輯關系。為此，可以首先對一般的二叉樹進行改造，進行改造，增加一些不存在的空結(jié)點，使之成為完全二叉樹增加一些不存在的空結(jié)點，使之成為完全二叉樹，然后再用一維數(shù)組順序存儲，增加的空結(jié)點用空表示。然后再用一維數(shù)組順序存儲，增加的空結(jié)點用空表示。父結(jié)點：(i-1)/2, 左子女：2i+1，右子女：2i+2與性質(zhì)5有差別（從0開始編號，性質(zhì)5從1開始）問題問題：對于完全或近似完全的二叉樹，宜采用上述順序結(jié)構(gòu)存：對于完全或近似完全的二叉樹，宜采用上述順序結(jié)構(gòu)存儲。但對于一般二叉樹，如果增加的

27、空結(jié)點非常多，則容易造儲。但對于一般二叉樹，如果增加的空結(jié)點非常多，則容易造 成空間浪費，此時不宜采用上述方法存儲。成空間浪費，此時不宜采用上述方法存儲。（3）特殊二叉樹）特殊二叉樹 對于一種特殊情況，如果二叉樹為右單支樹對于一種特殊情況，如果二叉樹為右單支樹深度為深度為k， 則需要一個長度為則需要一個長度為2k-1的一維數(shù)組，的一維數(shù)組， 造成造成（2k-1）-k個結(jié)點浪費。個結(jié)點浪費。 如果如果k=6, 則有則有57個結(jié)點空間浪費。個結(jié)點空間浪費。ABC順序存儲表示如下：順序存儲表示如下：typedef struct SeqBTree DataType nodelistMAXNODE;in

28、t n;/* 改造成完全二叉樹后改造成完全二叉樹后 結(jié)點的個數(shù)結(jié)點的個數(shù) */SeqBTree, *PSeqBTree;2. 鏈接表示鏈接表示（1）二叉鏈表）二叉鏈表 每個結(jié)點結(jié)構(gòu)為：每個結(jié)點結(jié)構(gòu)為： 其中：其中：info項存儲結(jié)點信息，項存儲結(jié)點信息，llink指向左孩子，指向左孩子，rlink指向右指向右孩子。孩子。llinkrlinkinfo基本運算基本運算n個結(jié)點的二叉鏈表中有個結(jié)點的二叉鏈表中有n+1個空指針。通過擴充二叉樹個空指針。通過擴充二叉樹中外部結(jié)點個數(shù)可以證明中外部結(jié)點個數(shù)可以證明 typedef struct BinTreeNode DataTypeinfo;struct

29、 BinTreeNode *llink;struct BinTreeNode *rlink; BinTreeNode, *PBinTreeNode, BinTree, *PBinTree基本運算實現(xiàn)基本運算實現(xiàn)llinkrlink（2）三叉鏈表）三叉鏈表每個結(jié)點結(jié)構(gòu)為：每個結(jié)點結(jié)構(gòu)為：二叉鏈表每個結(jié)點增加指向父結(jié)點的指針二叉鏈表每個結(jié)點增加指向父結(jié)點的指針plink，便得到三叉，便得到三叉鏈表存儲表示。鏈表存儲表示。三叉鏈表對于找父結(jié)點等操作非常方便，但增加了空間要求。三叉鏈表對于找父結(jié)點等操作非常方便，但增加了空間要求。llinkplinkinforlink基本運算基本運算typedef s

30、truct BinTreeNode DataTypeinfo;struct BinTreeNode *llink;struct BinTreeNode *rlink;struct BinTreeNode *plink; BinTreeNode, *PBinTreeNode, BinTree, *PBinTree（3）線索鏈表：）線索鏈表：修改空指針，指向其直接前驅(qū)或后繼的二叉鏈表修改空指針，指向其直接前驅(qū)或后繼的二叉鏈表 后面詳細討論后面詳細討論ABDCEGHFItACBDEFGHI二叉樹二叉樹tABCDEFGHI 二叉鏈表表示二叉鏈表表示（10個空指針）個空指針） 三叉鏈表表示三叉鏈表表示（

31、空指針數(shù)？）（空指針數(shù)？）5.6 二叉樹的遍歷和線索二叉樹二叉樹的遍歷和線索二叉樹1. 二叉樹的遍歷二叉樹的遍歷 (a) 定義：定義：按某條搜索路徑訪問樹中每一個結(jié)點，使得每個結(jié)點按某條搜索路徑訪問樹中每一個結(jié)點，使得每個結(jié)點被訪問一次且僅被訪問一次。通過一次完整的遍歷，可以將二被訪問一次且僅被訪問一次。通過一次完整的遍歷，可以將二叉樹結(jié)點信息由非線性序列變?yōu)榫€性序列。因此，二叉樹的遍叉樹結(jié)點信息由非線性序列變?yōu)榫€性序列。因此，二叉樹的遍歷過程實際上是非線性結(jié)構(gòu)線性化的過程。歷過程實際上是非線性結(jié)構(gòu)線性化的過程。 (b) 遍歷方法：遍歷方法：由二叉樹定義可知，二叉樹有三部分組成：根、由二叉樹定

32、義可知，二叉樹有三部分組成：根、左子樹和右子樹。因此，遍歷整個二叉樹實質(zhì)上就是按照某種左子樹和右子樹。因此，遍歷整個二叉樹實質(zhì)上就是按照某種次序依次遍歷這三部分。次序依次遍歷這三部分。 假定假定D、L、R分別表示遍歷根、遍歷左子樹、遍歷右子樹，按分別表示遍歷根、遍歷左子樹、遍歷右子樹，按照排列組合，有照排列組合，有6種遍歷方法：種遍歷方法：DLR, LDR, LRD, DRL, RDL, RLD。遍歷定義遍歷定義遍歷算法遍歷算法二叉樹的建立二叉樹的建立線索二叉樹線索二叉樹DLR如果限定左右子樹的訪問按照如果限定左右子樹的訪問按照先左后右先左后右，則上面，則上面6種種只有只有3種符合，即：種符合

33、，即：DLR, LDR, LRD，分別稱為：，分別稱為：先先根遍歷、中根遍歷、后根遍歷根遍歷、中根遍歷、后根遍歷。(c) 先根遍歷先根遍歷 根根先根遍歷左子樹先根遍歷左子樹先根遍歷右子樹先根遍歷右子樹 遍歷結(jié)果：遍歷結(jié)果：ABDCEGFHI(d) 中根遍歷中根遍歷 中根遍歷左子樹中根遍歷左子樹根根中根遍歷右子樹中根遍歷右子樹 遍歷結(jié)果：遍歷結(jié)果：DBAEGCHFI (e) 后根遍歷后根遍歷 后根遍歷左子樹后根遍歷左子樹后根遍歷右子樹后根遍歷右子樹根根 遍歷結(jié)果：遍歷結(jié)果：DBGEHIFCAABDCEGHFI表達式表達式：(a-b)(c+d)的二叉樹形式如右圖：的二叉樹形式如右圖： 則其則其DL

34、R遍歷為：遍歷為：-ab+cd 前綴表達，波蘭式前綴表達，波蘭式 LDR遍歷為：遍歷為：a-bc+d 中綴表達中綴表達 LRD遍歷為：遍歷為：ab-cd+ 后綴表達，逆波蘭式后綴表達，逆波蘭式任何一個算術(shù)表達式，都可以給出其對應的二叉樹形式，其遍任何一個算術(shù)表達式，都可以給出其對應的二叉樹形式，其遍歷結(jié)果可以得到表達式的各種表達形式。歷結(jié)果可以得到表達式的各種表達形式。-+abcd2. 二叉樹的遍歷算法二叉樹的遍歷算法 1 遞歸算法遞歸算法 a)先根先根 b)中根中根 c)后根后根 2 非遞歸算法非遞歸算法 利用利用棧棧實現(xiàn)遍歷非遞歸算法。棧保實現(xiàn)遍歷非遞歸算法。棧保存遍歷過程中結(jié)點或結(jié)點的左

35、右孩子。存遍歷過程中結(jié)點或結(jié)點的左右孩子。數(shù)組數(shù)組SM作為棧，作為棧，Top為棧頂指針，為棧頂指針，假定?？臻g足夠大，不會產(chǎn)生溢出問假定?？臻g足夠大，不會產(chǎn)生溢出問題。題。Void PreOrder(BinTree t) if (!t) return; visit(t); PreOrder(t-llink); PreOrder(t-rlink);Void InOrder(BinTree t) if (!t) return; InOrder(t-llink); visit(t); InOrder(t-rlink);Void PostOrder(BinTree t) if (!t) return;

36、 PostOrder(t-llink); PostOrder(t-rlink); visit(t);與樹類似，但有差別！二叉樹基本運算中，無找右兄弟運算。如有：某些遍歷更簡單！但需要選擇合適的存儲表示。a)先根先根 思想思想：從根開始，沿左子樹一直走到末端為止，在走的過：從根開始，沿左子樹一直走到末端為止，在走的過程中訪問所遇結(jié)點，并依次將所遇程中訪問所遇結(jié)點，并依次將所遇結(jié)點的非空右孩子進棧結(jié)點的非空右孩子進棧。當左子樹結(jié)點全處理完后，從棧頂退出某結(jié)點的右孩子，此當左子樹結(jié)點全處理完后，從棧頂退出某結(jié)點的右孩子，此時該結(jié)點的左子樹已經(jīng)遍歷完，再按照上述過程遍歷結(jié)點的時該結(jié)點的左子樹已經(jīng)遍歷完

37、，再按照上述過程遍歷結(jié)點的右子樹，如此重復直到?？諡橹?。右子樹，如此重復直到棧空為止。 先根非遞歸算法先根非遞歸算法 也可壓結(jié)點本身，彈棧時（根+左子樹已經(jīng)遍歷完） 通過右孩子進入右子樹?！绢愃茦涞南雀闅v】b) 中根中根 思想思想：與先根遍歷基本類同，只是在沿左分支（左子樹）向：與先根遍歷基本類同，只是在沿左分支（左子樹）向前搜索過程中將遇到的前搜索過程中將遇到的結(jié)點進棧結(jié)點進棧，待遍歷完左子樹后，從棧，待遍歷完左子樹后，從棧頂退出結(jié)點并訪問，然后再遍歷右子樹。頂退出結(jié)點并訪問，然后再遍歷右子樹。 中根非遞歸算法中根非遞歸算法 由于只有左、右子女，與樹相比，簡單。 也可以同時壓右子女，彈棧時

38、（左子樹已經(jīng)遍歷完）訪問結(jié)點， 通過右孩子進入右子樹?！绢愃茦涞闹懈闅v】c) 后根后根 思想思想：使用棧實現(xiàn)后根遍歷要比先、中根遍歷復雜。在后：使用棧實現(xiàn)后根遍歷要比先、中根遍歷復雜。在后根遍歷中，當搜索指針指向某個根結(jié)點時，不能馬上進行訪根遍歷中，當搜索指針指向某個根結(jié)點時，不能馬上進行訪問，而先要遍歷左子樹，所以要求根結(jié)點進棧保存。當遍歷問，而先要遍歷左子樹，所以要求根結(jié)點進棧保存。當遍歷完左子樹后，再次搜索到該結(jié)點時，還不能進行訪問，還要完左子樹后，再次搜索到該結(jié)點時，還不能進行訪問，還要遍歷其右子樹。所以，遍歷其右子樹。所以，需要再次將該結(jié)點進棧需要再次將該結(jié)點進棧保存。為了保存。為

39、了區(qū)區(qū)別同一結(jié)點的兩次入棧別同一結(jié)點的兩次入棧，需要一個特別的標志：，需要一個特別的標志：1表示該結(jié)點表示該結(jié)點首次進棧首次進棧遍歷左子樹前入棧遍歷左子樹前入棧，2表示第二次進棧表示第二次進棧遍歷右子樹遍歷右子樹前入棧前入棧。為此，有兩種辦法實現(xiàn)：。為此，有兩種辦法實現(xiàn)： * 設立兩個棧，一個棧設立兩個棧，一個棧s1M用于存放結(jié)點，一個用于存放結(jié)點，一個s2M 棧用于存放結(jié)點進棧標志。棧用于存放結(jié)點進棧標志。 * 修改原來的棧，增加標志項（教材中的方法）修改原來的棧，增加標志項（教材中的方法） 后根非遞歸算法后根非遞歸算法教材中還給出了一種犧牲資源的后根遍歷算法。教材中還給出了一種犧牲資源的后

40、根遍歷算法。是否可參考樹的后根遍歷實現(xiàn)？左子樹遍歷完后，如何進入右子女。二叉樹無右兄弟基本運算！DLR3. 二叉樹的建立二叉樹的建立“遍歷遍歷”是二叉樹各種操作的基礎，可以在遍歷過程中進行是二叉樹各種操作的基礎，可以在遍歷過程中進行各種操作，如可以在遍歷過程中生成結(jié)點，從而建立一棵各種操作，如可以在遍歷過程中生成結(jié)點，從而建立一棵二叉樹。二叉樹。順序存儲時：順序存儲時：按照順序要求，把二叉樹中的結(jié)點加按照順序要求，把二叉樹中的結(jié)點加以擴充，轉(zhuǎn)換成一個完全二叉樹形式，然后按層次以擴充，轉(zhuǎn)換成一個完全二叉樹形式，然后按層次周游順序把各個結(jié)點的信息輸入到周游順序把各個結(jié)點的信息輸入到nodelist

41、數(shù)組中即數(shù)組中即可。可。二叉鏈表存儲：按先根遍歷次序生成二叉樹二叉鏈表存儲：按先根遍歷次序生成二叉樹： 例如要生成右面的二叉樹，只要按照下列例如要生成右面的二叉樹，只要按照下列順序輸入字符，即可建立相應的二叉鏈表。順序輸入字符，即可建立相應的二叉鏈表。 ABDCEGFHI其中，其中，為空結(jié)點為空結(jié)點(對應于擴充二叉樹中的外部結(jié)點對應于擴充二叉樹中的外部結(jié)點)。ABDCEGHFIBinTree CreateBinTree() BinTree t; char ch; scanf(“%c”, &ch); if (c = ) t = NULL; else t = (BinTree)malloc

42、(sizeof(BinNode); t-data = ch; /根根 t-llink = CreateBinTree(); /左子樹左子樹 t-rlink = CreateBinTree(); /右子樹右子樹 return t;A AB BD DC CE EG GH HF FI I對于每個結(jié)點，需要給出其左右子女結(jié)點信息。4. 線索二叉樹線索二叉樹（1） 問題的提出問題的提出遍歷可以將二叉樹中結(jié)點排列為一個線性表，因此結(jié)點的前遍歷可以將二叉樹中結(jié)點排列為一個線性表，因此結(jié)點的前驅(qū)、后繼可以在此線性表中得到。但是，二叉樹的存儲結(jié)構(gòu)驅(qū)、后繼可以在此線性表中得到。但是，二叉樹的存儲結(jié)構(gòu)中并沒有反映這

43、種邏輯上的關系，只能通過對二叉樹進行遍中并沒有反映這種邏輯上的關系，只能通過對二叉樹進行遍歷得到。歷得到。問題問題：如果通過一次遍歷，保存主要信息，后面重復遍歷時利用這些信息，則可大大加快后面的遍歷速度。如何在遍歷過程中保存結(jié)點的前驅(qū)、后繼結(jié)點信息？解決辦法解決辦法1：每個結(jié)點增加指向前驅(qū)、后繼結(jié)點的指針，遍歷過程中完成指針的設置。缺點：存儲空間增加，存儲要求提高，降低空間效率來提高時間效率。解決辦法解決辦法2：前面證明過：在n個結(jié)點二叉樹的二叉鏈表存儲結(jié)構(gòu)中，有n+1個空指針。修改這些空指針讓其指向前驅(qū)或后繼結(jié)點，空llink指向前驅(qū)，空rlink指向后繼。線索線索： 指向前驅(qū)或后繼的指針稱

44、為線索。指向前驅(qū)或后繼的指針稱為線索。線索樹線索樹： 加進線索的二叉樹加進線索的二叉樹線索化線索化： 修改空指針為線索的過程為線索化，即通過線索修改空指針為線索的過程為線索化，即通過線索 化將二叉樹變?yōu)榫€索二叉樹?；瘜⒍鏄渥?yōu)榫€索二叉樹。線索化與二叉樹的遍歷規(guī)則相互對應，本節(jié)主要討論線索化與二叉樹的遍歷規(guī)則相互對應，本節(jié)主要討論中序遍歷中序遍歷下的線索化。下的線索化。在線索二叉樹中，指針有兩類：在線索二叉樹中，指針有兩類： 指向其左右孩子的指針和指指向其左右孩子的指針和指向前驅(qū)、后繼的線索。向前驅(qū)、后繼的線索。 如何區(qū)分它們？如何區(qū)分它們？typedef struct ThrTreeNode

45、 DataType info; struct ThrTreeNode *llink, *rlink; int ltag, rtag;ThrTree, *PThrTree, *PThrTreeNode;每個結(jié)點增加兩個每個結(jié)點增加兩個標志項標志項，分別標志左右指針的類別：，分別標志左右指針的類別：ltag = 0 llink為指針，指向左孩子為指針，指向左孩子 1 llink為線索，指向結(jié)點的前驅(qū)為線索，指向結(jié)點的前驅(qū)rtag = 0 rlink為指針，指向右孩子為指針，指向右孩子 1 rlink為線索，指向結(jié)點的后繼為線索，指向結(jié)點的后繼（2）線索樹結(jié)構(gòu)描述：）線索樹結(jié)構(gòu)描述：rtagDATA

46、llinkrlinkltag(3) 中序線索化算法中序線索化算法給定一棵樹，要將它按照中序線索化，其思想就是按照中序遍給定一棵樹，要將它按照中序線索化，其思想就是按照中序遍歷原則遍歷該二叉樹，歷原則遍歷該二叉樹，在遍歷過程中用線索代替空指針在遍歷過程中用線索代替空指針。在未線索化之前，所有的在未線索化之前，所有的llink和和rlink皆為指針，因此所有的皆為指針，因此所有的ltag和和rtag為為0。假定當前正在訪問的結(jié)點為假定當前正在訪問的結(jié)點為p，pr指向其中序遍歷前驅(qū)結(jié)點指向其中序遍歷前驅(qū)結(jié)點上上次剛訪問的結(jié)點次剛訪問的結(jié)點，修改線索包括兩步：，修改線索包括兩步：a 如果如果pr的右指

47、針為空，的右指針為空， 修改修改pr的右指針指向的右指針指向p p為為pr的后繼的后繼；b 如果如果p的左指針為空，的左指針為空， 修改修改p的左指針指向的左指針指向prpr為為p的前驅(qū)的前驅(qū)。要實現(xiàn)非遞歸中序遍歷，需要一個附加的控制棧，要實現(xiàn)非遞歸中序遍歷，需要一個附加的控制棧，棧結(jié)構(gòu)如下：棧結(jié)構(gòu)如下：#define MAXNUM 1000struct SeqStack PThrTreeNode sMAXNUM;/順序棧順序棧 int t; /棧頂棧頂type struct SeqStack *PSeqStack;中序線索化算法中序線索化算法(4) 線索二叉樹遍歷線索二叉樹遍歷線索樹由于線索

48、的存在，使得二叉樹的某些操作變得非常容易。線索樹由于線索的存在，使得二叉樹的某些操作變得非常容易。例如：在某種次序遍歷序列中找結(jié)點的前驅(qū)、后繼不需要遍歷例如：在某種次序遍歷序列中找結(jié)點的前驅(qū)、后繼不需要遍歷整個二叉樹，可直接根據(jù)線索或指針找到。整個二叉樹，可直接根據(jù)線索或指針找到。找后繼找后繼：在中序線索二叉樹中，如果結(jié)點：在中序線索二叉樹中，如果結(jié)點p的右指針為線索，則的右指針為線索，則直接指向后繼；否則，其后繼為其右子樹最左下角的結(jié)點直接指向后繼；否則，其后繼為其右子樹最左下角的結(jié)點 中序中序遍歷右子樹第一個被訪問的結(jié)點遍歷右子樹第一個被訪問的結(jié)點 。找前驅(qū)找前驅(qū)：在中序線索二叉樹中，如果

49、結(jié)點：在中序線索二叉樹中，如果結(jié)點p的左指針為線索，則的左指針為線索，則直接指向前驅(qū)；否則，其前驅(qū)為其左子樹最右下角的結(jié)點直接指向前驅(qū)；否則，其前驅(qū)為其左子樹最右下角的結(jié)點 中序中序遍歷左子樹最后一個被訪問的結(jié)點遍歷左子樹最后一個被訪問的結(jié)點 。ABDCEGHFIDLR這樣，線索二叉樹的遍歷就不需要另設棧，算法簡單直接：這樣，線索二叉樹的遍歷就不需要另設棧，算法簡單直接： a 找第一個被訪問的結(jié)點；找第一個被訪問的結(jié)點； b 沿著找后繼的辦法，找結(jié)點的后繼；沿著找后繼的辦法，找結(jié)點的后繼； c 重復重復b，直到結(jié)點的后繼為空為止。，直到結(jié)點的后繼為空為止。找第一個被訪問的結(jié)點也非常容易。對于中

50、序線索二叉樹，找第一個被訪問的結(jié)點也非常容易。對于中序線索二叉樹，第一個被訪問的結(jié)點是：從根結(jié)點出發(fā)沿左指針不斷往下走，第一個被訪問的結(jié)點是：從根結(jié)點出發(fā)沿左指針不斷往下走，左指針為空的結(jié)點左指針為空的結(jié)點 二叉樹最左下結(jié)點二叉樹最左下結(jié)點 。ABDCEGHFI（5）單邊線索二叉樹）單邊線索二叉樹從上面的討論可以看出：線索二叉樹中既有指向前驅(qū)的左線從上面的討論可以看出：線索二叉樹中既有指向前驅(qū)的左線索，又有指向后繼的右線索。如果只保留一邊索，又有指向后繼的右線索。如果只保留一邊左或右左或右線索，線索，便得到單邊線索二叉樹。便得到單邊線索二叉樹。左線索二叉樹左線索二叉樹：只將：只將llink為空

51、的指針修改為指向其前驅(qū)的線為空的指針修改為指向其前驅(qū)的線索，索，rlink不改動；不改動；右線索二叉樹右線索二叉樹：只將：只將rlink為空的指針修改為指向其后繼的線為空的指針修改為指向其后繼的線索，索，llink不改動；不改動；單邊線索二叉樹應用也非常廣泛。單邊線索二叉樹應用也非常廣泛。ABDCEGHFINULLABDCEGHFINULL5.7 樹、樹林與二叉樹的轉(zhuǎn)換樹、樹林與二叉樹的轉(zhuǎn)換樹、樹林轉(zhuǎn)換為二叉樹樹、樹林轉(zhuǎn)換為二叉樹樹、樹林和二叉樹皆可以通過二叉鏈表作為存儲結(jié)構(gòu)，因此借樹、樹林和二叉樹皆可以通過二叉鏈表作為存儲結(jié)構(gòu)，因此借助二叉鏈表可以實現(xiàn)它們之間的轉(zhuǎn)換。助二叉鏈表可以實現(xiàn)它們之

52、間的轉(zhuǎn)換。通過樹、樹林的通過樹、樹林的孩子孩子-兄弟表示法兄弟表示法得到的二得到的二叉鏈表作為轉(zhuǎn)換工具。叉鏈表作為轉(zhuǎn)換工具。樹對應的二叉樹中，樹對應的二叉樹中，右子樹一定為空。右子樹一定為空。樹林對應的二叉樹中，樹林對應的二叉樹中，最后一棵樹的右子樹最后一棵樹的右子樹必為空。必為空。樹轉(zhuǎn)換為二叉樹樹轉(zhuǎn)換為二叉樹二叉樹轉(zhuǎn)換為樹二叉樹轉(zhuǎn)換為樹轉(zhuǎn)換步驟：轉(zhuǎn)換步驟：在所有相鄰的兄弟結(jié)點之間加一條線；在所有相鄰的兄弟結(jié)點之間加一條線；對每個非終端結(jié)點，只保留它與最左子女的連線，刪除它對每個非終端結(jié)點，只保留它與最左子女的連線，刪除它與其它子女的連線；與其它子女的連線； 以根為軸心，將整顆樹順時針旋轉(zhuǎn)以根

53、為軸心，將整顆樹順時針旋轉(zhuǎn)45度，使其結(jié)構(gòu)分明。度，使其結(jié)構(gòu)分明。2. 二叉樹轉(zhuǎn)換為樹、樹林二叉樹轉(zhuǎn)換為樹、樹林如某結(jié)點為其父母的左子女，則把該結(jié)點的右子女，如某結(jié)點為其父母的左子女，則把該結(jié)點的右子女， 右子女的右子女，右子女的右子女，都與該結(jié)點的父母用虛線連，都與該結(jié)點的父母用虛線連 接起來；接起來；去掉原二叉樹中所有父母到右子女的連線；去掉原二叉樹中所有父母到右子女的連線；整理上面得到的樹或樹林，并將虛線改為實線。整理上面得到的樹或樹林，并將虛線改為實線。5.8 哈夫曼樹及其應用哈夫曼樹及其應用HaffMan樹的定義樹的定義 擴充二叉樹擴充二叉樹外部路徑長度外部路徑長度： 其中，其中，L

54、i是從根到第是從根到第i個外部結(jié)點的路徑長度，個外部結(jié)點的路徑長度， m為外部結(jié)點個數(shù)為外部結(jié)點個數(shù) 如果所有的外部結(jié)點都有一定的加權(quán)值，則外部路徑長度可以如果所有的外部結(jié)點都有一定的加權(quán)值，則外部路徑長度可以推廣為推廣為“帶權(quán)的外部路徑長度帶權(quán)的外部路徑長度”： 其中，其中，wi是第是第i個外部結(jié)點的加權(quán)值，個外部結(jié)點的加權(quán)值， 其它同上。其它同上。miilE1miiilwWPL1HaffMan樹的定義樹的定義HaffMan算法構(gòu)造最優(yōu)二叉樹算法構(gòu)造最優(yōu)二叉樹HaffMan編碼編碼w1w2w3w4w5w6w7假定有一組實數(shù)假定有一組實數(shù)w1, w2, , wm，現(xiàn)在要構(gòu)造一棵有，現(xiàn)在要構(gòu)造一

55、棵有m個外部個外部結(jié)點的擴充二叉樹，外部結(jié)點的加權(quán)值序列為結(jié)點的擴充二叉樹，外部結(jié)點的加權(quán)值序列為w1, w2, , wm，這樣的擴充二叉樹有許多，這樣的擴充二叉樹有許多，帶權(quán)外部長度帶權(quán)外部長度WPL最小最小所對應的擴充二叉樹稱為所對應的擴充二叉樹稱為“HaffMan樹樹”或或“最優(yōu)二叉最優(yōu)二叉樹樹”。例如：給定權(quán)值序列例如：給定權(quán)值序列2, 3, 4, 11，可以構(gòu)造出不同的擴充，可以構(gòu)造出不同的擴充 二叉樹，并且可以計算出它們的二叉樹，并且可以計算出它們的WPL值，其中值，其中WPL最小最小 值所對應的擴充二叉樹為值所對應的擴充二叉樹為HaffMan樹。樹。114231142311423

56、WPL=1x11+2x4+3x(2+3)=34 WPL=2x3+3x(4+11)+1x2=53 WPL=2x(2+11+3+4)=40對于擴充二叉樹，外部結(jié)點個數(shù)對于擴充二叉樹，外部結(jié)點個數(shù)=內(nèi)部結(jié)點個數(shù)內(nèi)部結(jié)點個數(shù)+1。另外，從上面圖可以看出，在不同的擴充二叉樹中，為了另外，從上面圖可以看出，在不同的擴充二叉樹中，為了WPL值盡可能小，必須是：值盡可能小，必須是：加權(quán)值較大的外部結(jié)點應盡可能加權(quán)值較大的外部結(jié)點應盡可能地靠近根地靠近根（路徑長度短），這樣才能使得總的（路徑長度短），這樣才能使得總的WPL值降低。值降低。給定一組加權(quán)值，有沒有一個通用的方法來尋找給定一組加權(quán)值，有沒有一個通用的

57、方法來尋找WPL最小的最小的HaffMan樹？樹？2. HaffMan算法構(gòu)造最優(yōu)二叉樹算法構(gòu)造最優(yōu)二叉樹HaffMan最早給出了一種構(gòu)造最優(yōu)二叉樹的方法，因此稱為最早給出了一種構(gòu)造最優(yōu)二叉樹的方法，因此稱為HaffMan算法算法：(1) 根據(jù)給定的根據(jù)給定的n個權(quán)值個權(quán)值w1,w2,wn，構(gòu)成，構(gòu)成n棵二叉樹的集合棵二叉樹的集合F=T1,T2,Tn，其中每一棵二叉樹，其中每一棵二叉樹Ti中只有一個帶權(quán)為中只有一個帶權(quán)為wi的根結(jié)點，其左右子樹為空。的根結(jié)點，其左右子樹為空。(2) 在在F中選取兩棵權(quán)值最小的樹作為左右子樹以構(gòu)造一棵新的二中選取兩棵權(quán)值最小的樹作為左右子樹以構(gòu)造一棵新的二叉樹，

58、且新二叉樹的根結(jié)點的權(quán)值為其左右子樹根結(jié)點權(quán)值叉樹，且新二叉樹的根結(jié)點的權(quán)值為其左右子樹根結(jié)點權(quán)值之和。之和。(3) 在在F中刪除這兩棵樹，同時將新得到的二叉樹加入中刪除這兩棵樹，同時將新得到的二叉樹加入F中。中。(4) 重復重復(2)和和(3)，直到，直到F中只含一棵樹為止。中只含一棵樹為止。114232311423411234114棵只有根的二叉樹棵只有根的二叉樹2、3合并得到合并得到3棵二叉樹棵二叉樹5、4合并得到合并得到2棵二叉樹棵二叉樹9、11合并得到合并得到1棵二叉樹棵二叉樹* 左右選擇不同，得到的HaffMan樹形態(tài)不同，但WPL相同。HaffMan樹構(gòu)造的樹構(gòu)造的HaffMan

59、算法實現(xiàn)算法實現(xiàn)：存儲結(jié)構(gòu)可以有多種，如二叉鏈表、三叉鏈表等。下面給出一存儲結(jié)構(gòu)可以有多種，如二叉鏈表、三叉鏈表等。下面給出一種順序結(jié)構(gòu)種順序結(jié)構(gòu)(一維數(shù)組），結(jié)點定義：一維數(shù)組），結(jié)點定義： ww: 以該結(jié)點為根的子樹中所有外部結(jié)點的加權(quán)和。以該結(jié)點為根的子樹中所有外部結(jié)點的加權(quán)和。 parent: 父結(jié)點在數(shù)組中的存儲位置（下標），父結(jié)點在數(shù)組中的存儲位置（下標）， 根無父，設為根無父，設為-1。 llink: 左孩子存儲位置，對于外部結(jié)點，無孩子，設為左孩子存儲位置，對于外部結(jié)點，無孩子，設為-1。 rlink: 右孩子存儲位置，對于外部結(jié)點，無孩子，設為右孩子存儲位置，對于外部結(jié)點，無

60、孩子，設為-1。wwparentllinkrlink靜態(tài)鏈表：三叉鏈表w1plrw2 假定外部結(jié)點個數(shù)為假定外部結(jié)點個數(shù)為m，則內(nèi)部結(jié)點個數(shù)必為，則內(nèi)部結(jié)點個數(shù)必為m-1，最后得到，最后得到的的HaffMan樹必定有樹必定有2m-1個結(jié)點。因此，用個結(jié)點。因此，用2m-1個元素的一維個元素的一維數(shù)組就可以存儲該數(shù)組就可以存儲該HaffMan樹。每個元素表示一個結(jié)點，樹。每個元素表示一個結(jié)點，前前m個個存儲外部結(jié)點，后存儲外部結(jié)點，后m-1個用于內(nèi)部結(jié)點（個用于內(nèi)部結(jié)點（需要構(gòu)造的結(jié)點需要構(gòu)造的結(jié)點）。struct HtNode int ww; int parent, llink, rlink; str