數(shù)據(jù)結(jié)構(gòu)--(6)課件

1、6.1 樹的基本概念和術(shù)語6.2 二叉樹6.3 遍歷二叉樹6.4 線索二叉樹6.5 二叉樹、 樹和森林6.6 樹的應(yīng)用6.7 二叉樹的建立和遍歷C語言源程序示例第6章樹返回主目錄第6章 樹 6.1 樹的基本概念和術(shù)語 6.1.1 樹的定義樹（tree）是由一個或多個結(jié)點組成的有限集合T。 其中: (1) 有一個特定的結(jié)點稱為該樹的根（root）結(jié)點; (2) 除根結(jié)點之外的其余結(jié)點可分為m（m0）個互不相交的有限集合T1, T2, , Tm, 且其中每一個集合本身又是一棵樹, 稱之為根的子樹（subtree）。 這是一個遞歸的定義, 即在定義中又用到了樹這個術(shù)語。 它反應(yīng)了樹的固有特性?？梢哉J(rèn)

2、為僅有一個根結(jié)點的樹是最小樹, 樹中結(jié)點較多時, 每個結(jié)點都是某一棵子樹的根。 圖6.1是一棵由 11 個結(jié)點組成的樹T。 其中A是根結(jié)點, 其余結(jié)點分為三個互不相交的子集: T1 =B,E,F, T2 =C,G, T3 =D,H,I,J,K。 T1、 T2 、 T3都是樹根的子樹, 這三棵子樹的根結(jié)點分別是B、 C、 D。每棵子樹本身也是一棵樹, 可繼續(xù)劃分。 例如子樹T3以D為根結(jié)點, 它的其余結(jié)點又可分為三個互不相交的子集: T31=H, T32=I,K, T33 = J, 而其中T31 、 T33都可認(rèn)為是僅有一個根結(jié)點的子樹。 6.1.2 樹的常用術(shù)語樹結(jié)構(gòu)常常用到一些術(shù)語, 如度、

3、 雙親、 孩子、 樹深等。 結(jié)點的度是結(jié)點的子樹的個數(shù)。樹的度是樹中結(jié)點度的最大值。度為零的結(jié)點稱為葉子或終結(jié)點。度不為零的結(jié)點稱為非終端結(jié)點。圖6.1中樹T的度為。結(jié)點E, F, G, H, K, J度為零, 它們是葉子結(jié)點。 某結(jié)點的各子樹的根結(jié)點稱為該結(jié)點的孩子, 而該結(jié)點又稱為孩子們的雙親結(jié)點。具有相同雙親的結(jié)點互稱為兄弟。圖6.1中根結(jié)點A有三棵子樹, 這三棵子樹的根結(jié)點分別是B, C, D, 因此說結(jié)點A是結(jié)點B, C, D的雙親, 而結(jié)點B, C, D又都是結(jié)點A的孩子, B, C, D之間互為兄弟。 一棵樹上除根結(jié)點以外的其它結(jié)點稱為根結(jié)點的子孫。 對于樹中某結(jié)點, 從根結(jié)點開

4、始到該結(jié)點的雙親是該結(jié)點的祖先。 結(jié)點的層次值從根算起, 根的層次值為, 其余結(jié)點的層次值為雙親結(jié)點層次值加。一棵樹的深度是該樹中結(jié)點最大層次值, 例如圖6.1中的樹T的深度為。結(jié)點A、B、E、K的層次值分別為1、 2、 3、 4。 6.1.3 樹的表示方法 樹的表示形式有多種, 常見的三種方法是: (1) 倒懸樹法, 如圖6.1所示。 (2) 集合包含關(guān)系文氏圖法, 如圖6.2(a)所示。 (3) 凹入法, 如圖6.2(b)所示。 6.2 二叉樹 6.2.1 二叉樹的定義 二叉樹（binary tree）是n（n=0）個結(jié)點的有限集合。 它或為空樹（n=0）, 或為非空樹; 對于非空樹有:

5、(1) 有一個特定的稱之為根的結(jié)點。 (2) 除根結(jié)點以外的其余結(jié)點分為兩個互不相交的稱之為左子樹和右子樹的二叉樹構(gòu)成。 這個定義是遞歸的。由于左、 右子樹也是二叉樹, 因此子樹也可為空樹。 圖6.3中展現(xiàn)了五種基本形態(tài)不同的二叉樹。 6.2.2 二叉樹的重要性質(zhì) 性質(zhì)1二叉樹第i(i1)層上至多有2 i-1個結(jié)點。 根據(jù)圖6.4(a)可知, 根結(jié)點在第一層上, 這層結(jié)點數(shù)最多為1個, 即20個; 顯然第二層上最多有2個結(jié)點, 即21個; 假設(shè)第i-1層的結(jié)點最多有2 i-2個, 且每個結(jié)點最多有兩個孩子, 那么第i層上結(jié)點最多有 2* 2 i-2= 2 i-1個。 性質(zhì)2深度為k(k1)的二

6、叉樹至多有2 i-k個結(jié)點。 由性質(zhì)1可知各層結(jié)點最多數(shù)目之和為 20 + 21+ 22+ 2 k-1; 由二進(jìn)制換算關(guān)系可知: 20+ 21+ 22+ 2k-1 = 20, 因此二叉樹樹中結(jié)點的最大數(shù)目為20。 性質(zhì)3在任意二叉樹中, 若葉子結(jié)點（即度為零的結(jié)點）個數(shù)為n0, 度為1的結(jié)點個數(shù)為n1, 度為2的結(jié)點個數(shù)為n2, 那么 n0 = n2+1。 設(shè)n代表二叉樹結(jié)點總數(shù), 那么 n = n0 + n1 + n2 (6.1) 由于有n個結(jié)點的二叉樹總邊數(shù)為n-1條, 于是得 n-1=0* n0 +1* n1+2* n2 (6.2) 將式(6.1)代入式(6.2)得 n0= n2+1 有

7、兩種特殊形態(tài)的二叉樹, 它們是滿二叉樹和完全二叉樹。 深度為k并且含有2k-1個結(jié)點的二叉樹稱為滿二叉樹, 這種樹的特點是每層上的結(jié)點數(shù)都是最大結(jié)點數(shù), 如圖6.4(a)所示。對滿二叉樹的結(jié)點可以從根結(jié)點開始自上向下, 自左至右順序編號, 圖6.4(a)中每個結(jié)點斜上角的數(shù)字即是該結(jié)點的編號。 深度為k, 含有n個結(jié)點的二叉樹, 當(dāng)且僅當(dāng)每個結(jié)點的編號與相應(yīng)滿二叉樹結(jié)點順序編號從1到n相對應(yīng)時, 則稱此二叉樹為完全二叉樹, 如圖6.4(b)所示。 而圖6.4(c)則不是完全二叉樹。 質(zhì)4具有n個結(jié)點的完全二叉樹樹深為 log2n+1（其中x表示不大于x的最大整數(shù)）。 性質(zhì)5若對有n個結(jié)點的完全

8、二叉樹進(jìn)行順序編號(1in), 那么, 對于編號為i(i1)的結(jié)點: 當(dāng)i=1時, 該結(jié)點為根, 它無雙親結(jié)點; 當(dāng)i1時, 該結(jié)點的雙親結(jié)點編號為i/2; 若2in, 則有編號為2i的左孩子, 否則沒有左孩子; 若2i+1n, 則有編號為2i+1的右孩子, 否則沒有右孩子。 對照圖6.4(a)或圖6.4(b), 讀者可看到由性質(zhì)所描述的結(jié)點與編號的對應(yīng)關(guān)系。 6.2.3 二叉樹的存儲結(jié)構(gòu) 二叉樹常用的存儲結(jié)構(gòu)有兩種, 順序存儲結(jié)構(gòu)（向量）和鏈表存儲結(jié)構(gòu)。 (1) 順序存儲結(jié)構(gòu)（向量）可以作為二叉樹的存儲結(jié)構(gòu)。 這種存儲結(jié)構(gòu)適用于完全二叉樹、滿二叉樹。假設(shè)用一維數(shù)組a存放圖6.4(a)的滿二叉

9、樹。可以發(fā)現(xiàn)圖6.4(a)中結(jié)點的編號恰好與數(shù)組元素的下標(biāo)相對應(yīng), 見圖.5。根據(jù)二叉樹性質(zhì)5, 在a數(shù)組中可以方便地由某結(jié)點ai的下標(biāo)i找到它們的雙親結(jié)點ai/2或左、 右孩子結(jié)點a2i、 a2i+1。在哈夫曼樹構(gòu)造算法中也用到順序存儲結(jié)構(gòu)。一般二叉樹較少采用順序存儲結(jié)構(gòu)。 (2) 鏈表存儲結(jié)構(gòu)通常用于二叉樹存儲。 常見的有二叉鏈表和三叉鏈表。二叉鏈表的每個結(jié)點都有一個數(shù)據(jù)域和兩個指針域, 一個指針指向左孩子, 另一個指針指向右孩子。結(jié)點結(jié)構(gòu)描述為: struct node int data; WB/* 數(shù)據(jù)域 */ struct node *lch, *rch; /* 左、 右指針域 */

10、 三叉鏈表的結(jié)點比前者多了一個指向雙親的指針域。 結(jié)點結(jié)構(gòu)描述為: struct node3 int data; /* 數(shù)據(jù)域 */ struct node *lch, *parent, *rch; /* par是雙親指針域 */ 對于圖6.6(a)中二叉樹T, 它的二叉鏈表如圖6.6(b), 三叉鏈表如圖6.6(c)。 6.2.4 二叉樹二叉鏈表的一個生成算法 此方法主要利用二叉樹的性質(zhì)5。 對任意二叉樹, 先按滿二叉樹對其進(jìn)行編號, 如圖6.7(a)所示。由于此樹并非完全二叉樹, 所以編號并不連續(xù)。 算法中使用一個輔助向量s用于存放 指向樹結(jié)點的指針, 如si中存放編號為i的結(jié)點的指針,

11、即為該結(jié)點的地址。 此例原始數(shù)據(jù)序列如圖6.7(b)所示, 照此一一輸入即可生成二叉鏈表。 當(dāng)結(jié)點編號i=1時, 所產(chǎn)生的結(jié)點為根結(jié)點, 同時將指向該結(jié)點的指針存入s1。當(dāng)結(jié)點編號i1時, 產(chǎn)生一個新的結(jié)點之后, 也要將指向該結(jié)點的指針存入si。 由性質(zhì)5可知: j=i/2 為它的雙親結(jié)點編號。 如果i為偶數(shù), 則它是雙親結(jié)點的左孩子, 即讓sj-lch = si; 如果i為奇數(shù), 則它是雙親結(jié)點的右孩子, 即讓sj-rch = si。這樣就將新輸入的結(jié)點逐一與其雙親結(jié)點相連, 生成二叉樹。 結(jié)點結(jié)構(gòu)如前所描述, 為struct node 。 輔助向量為 struct node *s20。 二

12、叉樹生成算法如算法6.1。 算法 6.1 算法 6.1 stuct node *creat( ) printf(i, x=); scanf(%d%d, &i, &x); while (i!KG-*2=0)&(x!KG-*2=0) q=(struct node*)malloc(sizeof(struct node)/* 產(chǎn)生一個結(jié)點 */ q-data=x; q-lch=NULL; q-rch=NULL; si=q; if (i=1) t=q; /* t 為部局變量, 代表樹根結(jié)點 */ else j=i/2; /* 雙親結(jié)點編號 */ if (i%2)=0) sj-lch=q; else sj

13、-rch=q; printf(i, x=); scanf(%d%d, &i, &x); return(t) /* creat end */6.3 遍 歷 二 叉 樹 前已經(jīng)指出, 對于二叉樹經(jīng)常采用鏈表做為它的存儲結(jié)構(gòu), 本節(jié)及以后對二叉樹的討論將主要針對鏈表存儲結(jié)構(gòu)來進(jìn)行 遍歷二叉樹是指以一定的次序訪問二叉樹中的每個結(jié)點, 并且每個結(jié)點僅被訪問一次。 所謂訪問結(jié)點是指對結(jié)點進(jìn)行各種操作的簡稱。 例如, 查詢結(jié)點數(shù)據(jù)域的內(nèi)容, 或輸出它的值, 或找出結(jié)點位置, 或是執(zhí)行對結(jié)點的其它操作。 遍歷二叉樹的過程實質(zhì)是把二叉樹的結(jié)點進(jìn)行線性排列的過程。假設(shè)遍歷二叉樹時, 訪問結(jié)點的操作就是輸出結(jié)點數(shù)據(jù)

14、域的值, 那么遍歷的結(jié)果得到一個線性序列。由于二叉樹有左、右子樹, 所以遍歷的次序不同, 得到的結(jié)果就不同。 令L、 T、 R分別代表遍歷左子樹、 訪問根結(jié)點和遍歷右子樹, 則對一棵二叉樹的遍歷可以有六種不同次序: LTR, LRT, TLR, TRL, RLT, RTL。 然而經(jīng)常用到的總是先左（L）后右（R）, 若再把訪問根結(jié)點（T）的操作穿插其中, 則只有三種不同的遍歷次序: LTR、 TLR 和 LRT。 它們分別稱作中根遍歷、 先根遍歷和后根遍歷二叉樹。 在介紹常用的三種遍歷算法之前, 首先介紹一下遍歷的具體方法。例如有一棵二叉樹有4個結(jié)點。 為了便于理解遍歷的思想, 暫且為每個沒有

15、子樹的結(jié)點均補充上相應(yīng)的空子樹, 用來表示, 見圖6.8。設(shè)想有一條搜索路線（用虛線表示）, 它從根結(jié)點的左側(cè)開始, 自上而下自左至右搜索, 最后由根結(jié)點右側(cè)向上出去。 不難看出, 若考慮到空子樹的話, 恰好搜索路線途經(jīng)每個有效的樹結(jié)點都是三次。把第一次經(jīng)過就訪問的結(jié)點列出, 它們是A、 B、 C、 D, 這就是先根遍歷的結(jié)果。 那么第二次經(jīng)過才訪問的則是中根遍歷, 其結(jié)果是B、A、 D、C。第三次經(jīng)過才訪問的是后根遍歷, 結(jié)果是B、D、C、 A。 二叉樹的鏈表存儲, 其結(jié)點結(jié)構(gòu)定義如下: struct node char data; /* 假設(shè)數(shù)據(jù)類型char, 根據(jù)需要也可為其它類型 */

16、 struct node *lch, *rch; 6.3.1 先根遍歷 先根遍歷可以遞歸的描述如下: 如果根不空: (1) 訪問根結(jié)點; (2) 按先根次序遍歷左子樹; (3) 按先根次序遍歷右子樹; 否則返回。 先根遍歷的遞歸算法如算法6.2。 算法 6.2 Void preorder(struct node *p) if (p!KG-*2NULL) printf (6ct”, p-data); /* 訪問根結(jié)點 */ preorder(p-lch); /* 按先根次序遍歷左子樹 */ preorder(p-rch); /* 按先根次序遍歷右子樹 */ /* preorder */ 現(xiàn)在針對

17、圖6.8中的二叉樹, 對遞歸算法的詳細(xì)執(zhí)行情況進(jìn)行分析, 如圖6.9所示。 圖6.8中樹深度為3, 遞歸調(diào)用的深度為4層。 這就是在遇到空的子樹時, 它也調(diào)用了一次preorder函數(shù), 只不過是因為子樹的根為空立即返回而已。 還應(yīng)注意對某根結(jié)點訪問之后, 便對其左子樹進(jìn)行先根遍歷, 隨即進(jìn)入下一層遞歸調(diào)用, 當(dāng)返回本層調(diào)用時, 仍以本層根結(jié)點為基礎(chǔ)對其右子樹進(jìn)行先根遍歷。 當(dāng)從下一層遞歸調(diào)用（先根遍歷右子樹）再次返回本層時, 接著就從本層調(diào)用返回到前一層調(diào)用。依此類推, 最終返回主調(diào)程序。 6.3.2 中根遍歷 中根遍歷遞歸的思路與先根遍歷十分相似, 只是在根不空的情況下所應(yīng)執(zhí)行的三條操作稍

18、做調(diào)整即可。具體來說, 也就是把第(1)條與第(2)條進(jìn)行對換。 中根遍歷可以遞歸的描述如下: 如果根不空: (1) 按中根次序遍歷左子樹; (2) 訪問根結(jié)點; (3) 按中根次序遍歷右子樹; 否則返回。 中根遍歷遞歸算法如算法6.3。 算法 6.3 Void inorder( struct node *p) if (p! NULL) inorder(p-lch); /* 中根遍歷左子樹 */ printf(6ct”, P-data); /* 訪問根結(jié)束 */ inorder(p-rch); /* 中根遍歷右子樹 */ /* inorder */ 此遞歸算法的具體執(zhí)行情況, 請讀者自己分析。

19、 中根遍歷非遞歸算法如算法6.4。 算法 6.4 Void inorderz(struct node *p) /* 棧s是 struct node *s10 */ qp; top0; /* 棧頂指針 */ bool1; JY/* bool=1為真值繼續(xù)循環(huán); bool=0為假值棧空, 結(jié)束循環(huán)*/ do while (q! NULL) top; stopq; qq-lch; if (top=0) bool0; else qstop; top- -; printf(6ct”, q-data); /* 訪問根結(jié)點 */ qq-rch; while (bool); /* inorderz */ 對照

20、圖6.8中的二叉樹, 在中根非遞歸遍歷過程中其棧s的內(nèi)容變化如圖6.10所示。 假設(shè)二叉樹有個結(jié)點, 對每個結(jié)點都要進(jìn)行一次入棧和出棧操作, 即入棧和出棧各執(zhí)行n次, 對結(jié)點的訪問也是n次, 此算法的時間復(fù)雜度為O(n)。 所需棧的空間最多等于二叉樹深k乘以每個結(jié)點所需空間數(shù), 可以記作O(k)。 如果要寫先根遍歷非遞歸算法, 在搞清中根遍歷非遞歸方法后, 不難看出只要將訪問語句移一位置便可實現(xiàn)。 6.3.3 后根遍歷 在搞清楚先根遍歷、 中根遍歷遞歸方法之后, 可以看出, 只要將訪問根結(jié)點的語句移至遍歷左子樹、右子樹的語言后面即可得出后根遍歷遞歸算法。后根遍歷遞歸算法的描如下: 如果根不空:

21、 (1) 按后根次序遍歷左子樹; (2) 按后根次序遍歷右子樹; (3) 訪問根結(jié)點; 否則返回。 后根遍歷遞歸算法如算法6.5。 算法 6.5 Void postorder(stuct node *p) if (p!KG-*2NULL) postorder(p-lch); /* 后根遍歷左子樹 */ postorder(p-rch); /* 后根遍歷右子樹 */ printf(6ct”, p-data); /* 訪問根結(jié)點 */ /* postorder */ 后根遍歷的非遞歸算法較為復(fù)雜, 不僅在搜索線第一次經(jīng)過根結(jié)點時不訪問并且進(jìn)棧, 而且在后根遍歷它的左子樹之后, 搜索線第二次經(jīng)根結(jié)點

22、時也不能訪問。因此, 在搜索線第二次經(jīng)根結(jié)點時不能讓棧頂元素（根）出棧, 而是依據(jù)棧頂元素所表示的根去后根遍歷它的右子樹; 直到搜索線第三次經(jīng)過這個根結(jié)點時, 才將其出棧, 并且訪問這個根結(jié)點。 因此, 另需一個輔助棧2用來記錄經(jīng)過某根結(jié)點的次數(shù)。 兩個棧的類型為: struct node *s10; int s220。 后根遍歷的非遞歸算法如算法6.6。 算法 6.6 Void postorderz (stuct node *p) qp; top0; bool1; do while (q! NULL) top+; stopq; s2top1; qq-lch; if (top=0) bool0

23、; else if(s2top=1) s2top2; /* 第二次經(jīng)過, 不退棧 */ qstop; qq-rch; else qstop; /* 第三次經(jīng)過, 退棧并且訪問根結(jié)點 */ s2top0; top-; printf(6ct”, q-data); qNULL; while (bool); /* postorder2 */ 算法6.7 viod levelorder(struct node *p) struct node *q20; /* 輔助隊列, 假設(shè)樹結(jié)點不超過19個 */ front=0; rear=0; /* 置空隊列 */ if(p!KG-*2=NULL) rear+;

24、qrear=p; /* 根結(jié)點進(jìn)隊 */ while(front!KG-*2=rear) /* 隊首結(jié)點出隊并且訪問 */ front+; p=qfront; printf(6ct”, t-data); if(p-lch!-=NULL) rear+; qrear=p-lch; /* P左孩子不空則進(jìn)隊 */ if(p-rch!KG-*2=NULL) rear+; qrear=p-rch; /* P右孩子不空則進(jìn)隊 */ /* 當(dāng)隊列不空時, 繼續(xù)循環(huán) */ /* levelorder end */ 6.3.4 二叉樹遍歷算法的應(yīng)用 1. 統(tǒng)計二叉樹中結(jié)點個數(shù)m和 葉子結(jié)點個數(shù)n 分析: 在調(diào)用

25、遍歷算法時設(shè)兩個計數(shù)器變量m、n。我們知道所謂遍歷二叉樹, 即以某種次序去訪問二叉樹的每個結(jié)點, 且每個結(jié)點僅訪問一次, 這就提供了方便的條件。每當(dāng)訪問一個結(jié)點時, 在原訪問語句printf后邊, 加上一計數(shù)器語句m+和一個判斷該結(jié)點是否為葉子的語句, 便可解決問題。在這里, 所謂訪問結(jié)點的操作拓寬為一組語句, 見下列算法中的第4、 5、 6行。 假設(shè)用中根遍歷方法統(tǒng)計葉子結(jié)點的個數(shù), 算法如算法6.8。 算法 6.8 Void injishu(struct node *t) if (t!KG-*2=NULL) injishu(t-lch); /* 中根遍歷左子樹 */ printf(“6ct

26、”, t-data); /* 訪問根結(jié)點 */ m+; /* 結(jié)點計數(shù) */ if(t-lch=NULL)&(t-rch=NULL) n+; /* 葉子結(jié)點計數(shù) */ injishu(t-rch); /* 中根遍歷右子樹 */ /* injishu */ 該函數(shù)中的printf(“6ct”, t-data)語句輸出格式是針對圖6.8設(shè)計的。 如果數(shù)據(jù)域類型不是字符型而是整型, 語句應(yīng)該為printf(“6dt”, t-data)。 假設(shè)數(shù)據(jù)域類型更為復(fù)雜, 就應(yīng)結(jié)合具體實際重新設(shè)計輸出模塊。上面函數(shù)中m、 n是全局變量, 在主程序先置零, 在調(diào)用injishu函數(shù)結(jié)束后, m值便是結(jié)點總個數(shù),

27、 n值便是葉子結(jié)點的個數(shù)。主函數(shù)示意 如下: main( ) t=creat( ); /* 建立二叉樹t, 為全局變量 */ m=0, n=0; /* 全局變量m, n置初值 */ injishu(t); /* 求樹t中結(jié)點總數(shù)m, 葉子結(jié)點的個數(shù)n */ printf(m=%4d, n=%4d, m , n); /* 輸出結(jié)果 */ 2. 求二叉樹的樹深 首先看如下算法。 算法6.9 Void predeep(struct node *t, int i) if (t! NULL) printf(“6ct”, tdata); /* 訪問根結(jié)點 */ i+; if(kltag0; (2) p無左

28、孩子時, 令p-ltag1, 并且p-lch指向p的前趨結(jié)點; (3) p有右孩子時, 令p-rtag0; (4) p無右孩子時, 令p-rtag1, 并且讓p-rch指向p的后繼結(jié)點。 針對圖6.11(a)的二叉樹, 它的中根次序線索樹的鏈表表示如圖6.11(b)所示。 線索用帶箭頭的虛線表示。 6.4.2 線索二叉樹的邏輯表示圖 按照不同的遍歷次序進(jìn)行線索化, 可得到不同的線索二叉樹。有先根線索二叉樹、中根線索二叉樹和后根線索二叉樹。 對圖6.12(a)的二叉樹線索化, 可得到圖6.12(b)、(c)、(d)三種線索二叉樹的邏輯表示。 讀者應(yīng)能熟練掌握三種不同的線索二叉樹的邏輯圖畫法。 畫

29、圖時應(yīng)注意, 線索要畫成帶箭頭的虛線, 應(yīng)從結(jié)點的左下方和右下方出發(fā), 左右分明, 指向準(zhǔn)確。 6.4.3 中根次序線索化算法 1. 中序（中根次序）線索化遞歸算法 中序(中根次序)線索化遞歸算法如算法6.10。 算法 6.10 Void inthread(struct nodex *p) if (p!=NULL) inthread(p-lch); printf (6ct”, p-data); if (plc!=NULL) p-ltag=0; elsep-ltag=1; p-lch=pr; /* 建p結(jié)點的左線索, 指向前趨結(jié)點pr */ if (pr!=NULL) if (pr-rch!=N

30、ULL) pr-rtag=0; else pr-rtag=1; pr-rch=p; /* 前趨結(jié)點pr建右線索, 指向結(jié)點p */ZK) pr=p; /* pr跟上p, 以便p向后移動 */ inthread(p-rch); /* inthread */ 此算法中pr是全局變量, 在主程序中置初值為空。 在inthread函數(shù)中pr始終做為當(dāng)前結(jié)點p的前趨結(jié)點的指針。在線索化過程中, 邊判斷二叉樹的結(jié)點有無左、右孩子, 邊給相應(yīng)標(biāo)志域置0或1, 邊建立線索。 在閱讀此算法時, 將inthread(p-lch)和inthread(p-rch)之間的一組語句看成一個整體, 把這段語句理解為“訪問”

31、, 很明顯這里應(yīng)用了典型的中根遍歷算法思路。 在遞歸調(diào)用結(jié)束時p為空, 這表明pr已是最后一個結(jié)點, 應(yīng)該沒有后繼結(jié)點。 所以在返回主程序后還要使prrchNULL, 至此整個線索化結(jié)束。主函數(shù)語句示意如下: 初學(xué)者在這里往往易犯錯誤, 常把預(yù)處理pr=NULL和善后處理pr-rchNULL放在線索化子函數(shù)Void inthread (struct nodex *p)中, 一個放最前邊, 另一個放最后邊。這樣每遞歸調(diào)用一次, pr就置一次空, 無法記下p的前驅(qū)結(jié)點。而在從深度遞歸返回時, 每返回一次就讓pr-rch置一次空, 這顯然是錯誤的。 因此, 在描述遞歸算法時, 提倡同時寫出主函數(shù)來示

32、意遞歸調(diào)用前的初始化處理和遞歸調(diào)用結(jié)束后的善后處理。 main( ) pr=NULL; /* 全局變量 */ t=creat( ); /* 建立二叉樹 */ inthread(t); /* 中序線索化二叉樹 */ pr-rchNULL; /* 善后處理 */ 2. 中序線索化非遞歸算法 在這里需借用一個輔助結(jié)構(gòu)棧 struct nodex *s20, 如算法6.11。 算法 6.11 Void inthread2(struct nodex *t) pr=NULL; p=t; top=0; bool=1; KG6/* bool為真值 */ do while (p!=NULL) top+; sto

33、p=p; p=p-lch; if (top=0) bool=0; /* ?？? bool置假值 */ else p=stop; top-; printf(6ct, p-data); if (p-lch!=NULL) p-ltag=0; else p-ltag=1; p-lch=pr; /* 建p結(jié)點的左線索, 指向前趨結(jié)點pr */ if (pr!=NULL) if (pr-rch!=NULL) pr-rtag=0; else pr-rtag=1; pr-rch=p; /* 前趨結(jié)點pr建右線索, 指向結(jié)點p */ 在這個非遞歸算法中, pr仍做為p結(jié)點的前趨結(jié)點指針。 pr初值置NULL以及

34、pr-rch置NULL, 分別放在這個函數(shù)的開頭和結(jié)尾。這是與遞歸算法處理不同的地方。如果把算法中第819行的語句組看成“訪問”操作, 顯然是利用了中根非遞歸遍歷思路。 非遞歸中根線索化算法的時間復(fù)雜度和空間占用量與非遞歸中根遍歷二叉樹的算法是一樣的。pr=p; p=p-rch; /* else */ while (bool); pr-rchnull; ZK) /* inthread2 */ 6.4.4 在中根線索樹上檢索某結(jié)點的前趨或后繼 (1) 已知q結(jié)點, 找出它的前趨結(jié)點。 根據(jù)線索樹的基本概念, 當(dāng)q-ltag1時, q-lch就指向q的前趨。 當(dāng)q-ltag=0時, 表明q有左孩子

35、。 由中根遍歷的規(guī)律可知, 做為根q的前趨結(jié)點(或者說以根結(jié)點為后繼的結(jié)點), 它應(yīng)是中根遍歷q的左子樹時訪問的最后一個結(jié)點, 即左子樹的最右尾結(jié)點。 請看圖6.12(b), 結(jié)點D是A的左子樹的最右尾結(jié)點, 它就是A的前趨結(jié)點。 而D的后繼指針指向了A, A就是D的后繼結(jié)點。 若用p記錄q的前趨, 算法如算法6.12。 算法 6.12 struct nodex *inpre(struct nodex *q) if(q-ltag=1) p=q-lch; else r=q-lch; while (r-rtag!KG-*3=1) r=r-rch; p=r; return(p); (2) 已知q結(jié)點

36、, 找出它的后繼結(jié)點。 當(dāng)q-rtag1時, q-rch即指向q的后繼結(jié)點。 若q-rtag0, 表明q有右孩子, 那么q的后繼應(yīng)是中序遍歷q的右子樹時訪問的第一個結(jié)點, 即右子樹的最左尾結(jié)點?？磮D6.12(c), A的后繼為F, C的后繼為H。 若用p記錄q后繼結(jié)點, 算法如下: struct nodex*insucc(struct nodex *q) if(q-rtag=1) p=q-rch; else r=q-rch; while (r-ltag!=1) r=r-lcg; p=r; return(p); 6.4.5 在中根線索樹上遍歷二叉樹 算法6.13 void inthorder(s

37、tuct nodex *t) p=t; if(p! =NULL) while(p-lch!KG-*3=NULL) p=p-lch; /* 查找二叉樹的最左結(jié)點 */ printf(6c”, p-data); while(p-rch!KG-*3=NULL) p=insucc(p); /* 調(diào)用求某結(jié)點p后繼的算法 */ printf(6c”, p-data); /* inthorder */ 6.5 二叉樹、樹和森林 6.5.1 樹的存儲結(jié)構(gòu) 樹的存儲結(jié)構(gòu)有順序結(jié)構(gòu)和鏈表結(jié)構(gòu)。 順序存儲結(jié)構(gòu)即向量, 一般將樹結(jié)點按自上而下, 自左至右的順序一一存放。 如前文所介紹的完全二叉樹就可以采用順序存儲結(jié)

38、構(gòu)。對于一般樹結(jié)構(gòu)更適合使用鏈表存儲結(jié)構(gòu)。常用的有: 結(jié)點定長的多叉鏈表和孩子兄弟二叉鏈表。 圖6.13所示的樹是一個三叉樹, 可用三重鏈表來存儲, 其結(jié)點結(jié)構(gòu)為: 有一個數(shù)據(jù)域和三個指針域, 指針域用于指向該結(jié)點的各個孩子。 該樹的三重鏈表如圖6.14（a)所示。 如果用孩子-兄弟鏈表作存儲結(jié)構(gòu), 其結(jié)點結(jié)構(gòu)為: 有一個數(shù)據(jù)域和兩個指針域, 一個指針指向它的長子, 另一指針r指向它的一個兄弟。 孩子兄弟鏈表如圖6.14(b)所示。 假設(shè)把圖6.14(b)中指向兄弟的水平方向指針改為下斜45, 不難發(fā)現(xiàn)它與一棵二叉樹十分相似。由本章6.2節(jié)可知二叉樹的結(jié)構(gòu)規(guī)范、 簡單并具有一些重要的性質(zhì), 因

39、此常將一般樹結(jié)構(gòu)轉(zhuǎn)換為二叉樹結(jié)構(gòu)進(jìn)行處理。 6.5.2 樹與二叉樹之間的轉(zhuǎn)換 對于一般樹, 樹中孩子的次序并不重要, 只要雙親與孩子的關(guān)系正確即可。 但在二叉樹中, 左、 右孩子的次序是嚴(yán)格區(qū)分的。 所以在討論二叉樹與一般樹之間的轉(zhuǎn)換時, 為了不引起混淆, 就約定按樹上現(xiàn)有結(jié)點次序進(jìn)行轉(zhuǎn)換。 1. 一般樹轉(zhuǎn)化為二叉樹 將一般樹轉(zhuǎn)化為二叉樹的思路, 主要根據(jù)樹的孩子-兄弟存儲方式而來, 步驟是: (1) 加線: 在各兄弟結(jié)點之間用虛線相鏈。 可理解為每個結(jié)點的兄弟指針指向它的一個兄弟。 (2) 抹線: 對每個結(jié)點僅保留它與其最左一個孩子的連線, 抹去該結(jié)點與其它孩子之間的連線?？衫斫鉃槊總€結(jié)點僅

40、有一個孩子指針, 讓它指向自己的長子。 (3) 旋轉(zhuǎn): 把虛線改為實線從水平方向向下旋轉(zhuǎn)45, 成右斜下方向。原樹中實線成左斜下方向。這樣就形成一棵二叉樹。 由于二叉樹中各結(jié)點的右孩子都是原一般樹中該結(jié)點的兄弟, 而一般樹的根結(jié)點又沒有兄弟結(jié)點, 因此所生成的二叉樹的根結(jié)點沒有右子樹。在所生成的二叉樹中某一結(jié)點的左孩子仍是原來樹中該結(jié)點的長子, 并且是它的最左孩子。圖6.15是一個由一般樹轉(zhuǎn)為二叉樹的實例。 2. 二叉樹還原為一般樹 二叉樹還原為一般樹, 此時的二叉樹必須是由某一樹轉(zhuǎn)換而來的沒有右子樹的二叉樹。并非隨便一棵二叉樹都能還原成一般樹。 其還原過程也分為三步: (1) 加線: 若某結(jié)

41、點i是雙親結(jié)點的左孩子, 則將該結(jié)點i的右孩子以及當(dāng)且僅當(dāng)連續(xù)地沿著右孩子的右鏈不斷搜索到所有右孩子, 都分別與結(jié)點i的雙親結(jié)點用虛線連接。 (2) 抹線: 把原二叉樹中所有雙親結(jié)點與其右孩子的連線抹去。這里的右孩子實質(zhì)上是原一般樹中結(jié)點的兄弟, 抹去的連線是兄弟間的關(guān)系。 (3) 進(jìn)行整理: 把虛線改為實線, 把結(jié)點按層次排列。 二叉樹還原為一般樹的示例, 如圖6.16所示。 6.5.3 森林與二叉樹的轉(zhuǎn)換 森林是樹的有限集合, 如圖6.17(a)所示。 1. 森林轉(zhuǎn)換為二叉樹 森林轉(zhuǎn)換為二叉樹的步驟為: (1) 將森林中每棵子樹轉(zhuǎn)換成相應(yīng)的二叉樹， 形成有若干二叉樹的森林。 (2) 按森林

42、圖形中樹的先后次序, 依次將后邊一棵二叉樹作為前邊一棵二叉樹根結(jié)點的右子樹, 這樣整個森林就生成了一棵二叉樹, 實際上第一棵樹的根結(jié)點便是生成后的二叉樹的根結(jié)點。 圖6.17是森林轉(zhuǎn)化為二叉樹的示例。 圖6.17 森林轉(zhuǎn)換為二叉樹(a) 一般樹的森林； (b) 二叉樹的森林； (c) 第二棵子樹并入第一棵子樹； (d) 最終結(jié)果 2. 二叉樹還原為森林 將一棵由森林轉(zhuǎn)換得到的二叉樹還原為森林的步驟是: (1) 抹線: 將二叉樹的根結(jié)點與其右孩子的連線以及當(dāng)且僅當(dāng)連續(xù)地沿著右鏈不斷地搜索到的所有右孩子的連線全部抹去, 這樣就得到包含有若干棵二叉樹的森林。 (2) 還原: 將每棵二叉樹按二叉樹還原

43、一般樹的方法還原為一般樹, 于是得到森林。 這部分的圖示, 請讀者自己練習(xí)畫出。 6.5.4 一般樹或森林的遍歷 一般樹的遍歷主要是先序和后序遍歷, 一般不討論中序遍歷。 樹的先序遍歷首先訪問樹的根結(jié)點, 然后從左至右逐一先序遍歷每一棵子樹。 樹的后序遍歷首先后序遍歷樹的最左邊的第一棵子樹, 接著從左至右逐一后序遍歷每一棵子樹, 最后訪問樹的根結(jié)點。 由于一般樹轉(zhuǎn)換為二叉樹后, 此二叉樹沒有右子樹, 對此二叉樹的中序遍歷結(jié)果與上述一般樹的后序遍歷結(jié)果相同。 因此, 有的教科書中把一般樹的后序遍歷稱為中序遍歷。一般樹的孩子-兄弟鏈表存儲結(jié)構(gòu)如下: struct nodet int data; s

44、truct nodet *child, *brather; (1) 利用一般樹的孩子-兄弟鏈表存儲結(jié)構(gòu), 先序遍歷該樹的算法如算法6.14。 算法6.14 Void preordertre(struct nodet *root) /* root 一般樹的根結(jié)點 */ /* s30是輔助棧 */ qroot; top0; /* 棧頂指針 */ bool1; /* bool=1為真值繼續(xù)循環(huán); bool=0為假值?？? 結(jié)束循環(huán)*/ do while (q! NULL) printf(6d”, q-data); /* 訪問根結(jié)點 */ top; stopq; qq-child; /* 搜索根結(jié)點的

45、第一個孩子結(jié)點 */ if (top=0) bool0; else qstop; top-; qq-brather; /* 對出棧后的結(jié)點找它的下一個兄弟結(jié)點 */) while (bool); printf( n); /* preordertre */ (2) 利用森林轉(zhuǎn)換成的二叉樹, 按層遍歷該森林的算法如算法6.15。 算法6.15 Void leveltraverse(struct node *root) struct node *q20; /* 輔助隊列, 假設(shè)樹結(jié)點不超過19個 */ front=0; rear=0; /* 置空隊列 */ p=root; if(p!=NULL) r

46、ear+; qrear=p; /* 根結(jié)點進(jìn)隊 */ while(front!KG-*3=rear) front+; p=qfront;/* 隊首結(jié)點出隊 */ While(p! =NULL) printf(6c, t-data); if(p-child!KG-*3=NULL) rear+; /* P第一個孩子不空則進(jìn)隊 */ qrear=p-child; p=p-brather;/* 找p的下一個兄弟結(jié)點 */ /* 當(dāng)隊列不空時, 繼續(xù)循環(huán) */ /* leveltraverse end */ 6.6 樹的應(yīng)用 6.6.1 二叉排序樹 1. 二叉排序樹的定義和特點 定義: 二叉排序樹(bi

47、nary sort tree)或是空樹; 或是非空樹 。 對于非空樹: （1） 若左子樹不空, 則左子樹上各結(jié)點的值均小于它的根結(jié)點的值; （2） 若右子樹不空, 則右子樹上各結(jié)點的值均大于等于它的根結(jié)點的值; （3） 它的左、 右子樹又分別是二叉排序樹。 例如圖6.18所示為一棵二叉排序樹。 特點: 對二叉排序樹進(jìn)行中序遍歷, 可得到一個由小到大的序列。 例如, 對圖6.18的二叉排序樹進(jìn)行中根遍歷, 則得到序列: 2, 3, 6, 8, 9, 10, 15, 18, 19。 2. 建立二叉排序樹的算法建立二叉排序樹, 實質(zhì)上是不斷地進(jìn)行插入結(jié)點的操作。 設(shè)有一組數(shù)據(jù):=k1 k2 , ,

48、kn , 將它們一一輸入建成二叉排序樹。 我們用二叉鏈表做為存儲結(jié)構(gòu)。 結(jié)點結(jié)構(gòu)如下: struct nodb int data; struct nodb *lch, rch; 思路分析: (1) 讓k1做根; (2) 對于k2, 若k2 k1, 令k2做k1的左孩子; 否則令k2做k1的右孩子; (3) 對于k3, 從根k1開始比較。 若k3 k1 ，到左子樹中找； 否則到右子樹中找；找到適當(dāng)位置進(jìn)行插入； (4) 對于k4, k5, , kn, 重復(fù)第(3)步, 直到kn處理完為止。 在建立過程之中, 每輸入一個數(shù)據(jù)元素, 就插入一次。 現(xiàn)把插入一個結(jié)點的算法單獨編寫, 而在建立二叉排序樹

49、的函數(shù)中對其進(jìn)行調(diào)用。 首先看建立二叉排序樹的主體算法: 算法 6.16struct nodb creat( ) Printf(n?); scanf(d, n ); t=NULL; for(i=1; idatak; s-lchNULL; s-rchNULL; insert1(t, s); /* 或調(diào)用insert2(t, s) */ return(t); 在二叉排序樹中, 插入一個結(jié)點s的遞歸算法: 算法 6.17Void insertl(struct nodb *t, struct nodb *s) if(t=NULL) t=s; else if(s-data t-data)insert1(

50、t-lch, s ); /* 將s插入t的左子樹 */ else insert1(t-rch, s); /*將s插入t的右子樹 */ 在二叉排序樹中, 插入一個結(jié)點s的非遞歸算法: 算法 6.18Void insert2(styoct nodb *t, struct nodb *s) if(t=NULL) t=s; else p=t; while(p!KG-*3=NULL) qp; /* 當(dāng)P向子樹結(jié)點移動時, q記P的雙親位置 */ if(s-data p-data) pp-lch; else pp-rch; if(s-data q-data) q-lch=s; else q-rch=s;

51、/*當(dāng)p為空時, q就是可插入的地方*/ 假設(shè)給出一組數(shù)據(jù)10, 3, 18, 6, 20, 2, 對照上述算法生成二叉排序樹的過程如圖6.19所示。 由此可見, 在二叉排序樹上插入結(jié)點不需要遍歷樹, 僅需從根結(jié)點出發(fā), 走一條根到某個有空子樹的結(jié)點的路徑, 使該結(jié)點的空指針指向被插入結(jié)點, 使被插入結(jié)點成為新的葉子結(jié)點。 如果仍使用前邊6個數(shù)據(jù), 但輸入先后順序改為2, 3, 6, 10, 18, 20, 那么生成的二叉排序樹如何？請思考。 3. 在二叉排序樹中刪除結(jié)點在二叉排序樹上刪除一個結(jié)點, 應(yīng)該在刪除之后仍保持二叉排序樹的特點。要刪除某結(jié)點p, p結(jié)點和它的雙親結(jié)點f都是已知條件,

52、這里的關(guān)鍵是怎樣找一個結(jié)點s來替換p結(jié)點。 下面分三種情況來討論。 (1) p結(jié)點無右孩子, 則讓p的左孩子s上移替代p結(jié)點， 如圖6.20(a)、 (b)所示。 (2) p結(jié)點無左孩子, 則讓p的右孩子s上移替代p結(jié)點， 如圖6.20(c)、 (d)所示。 (3) p結(jié)點有左孩子和右孩子, 可用它的前趨（或后繼）結(jié)點s代替p結(jié)點?，F(xiàn)假定用它的后繼結(jié)點來代替, 這個結(jié)點s應(yīng)是p的右子樹中數(shù)據(jù)域值最小的結(jié)點, 或者說是p的右子樹中最左結(jié)點。 因其值域最小(在右子樹中)， 所以它一定沒有左孩子。 這時先讓p結(jié)點取s結(jié)點的值, 然后可按第(2)種情況處理刪除s結(jié)點, 這就等效刪除了原p結(jié)點。 如圖6

53、.20(e)所示。 參見算法6.19, 其中t, f, p為已知條件, t指向根結(jié)點, f指向p的雙親, p指向被刪除結(jié)點。 另設(shè)s, q指針, 分別指向替代結(jié)點及其雙親。 算法6.19Void delet(struct node *t, struct node *p, struct node *f) bool1; if(p-lch=NULL) sp-rch; else if (p-rch=NULL) sp-lch; else q=p; sp-rch; /* p左, 右孩子均 不空的情況 */ while(s-lch ! =NULL) qs; ss-lch; if (q=p) q-rchs-r

54、ch; else q-lchs-rch; p-datas-data; free(s); bool0; /* 刪除完成 */ if (bool=1) /* p不是有左, 右兩個孩子的情況 */ if(f=NULL) ts; /* f=NULL即是p=t情況 */ 6.6.2 哈夫曼樹及其應(yīng)用 哈夫曼樹（Huffman）, 又稱最優(yōu)二叉樹, 是一類帶權(quán)路徑長度最短的樹, 有著廣泛的應(yīng)用。 1. 哈夫曼樹的基本概念 在討論哈夫曼樹之前首先需要弄清楚關(guān)于路徑和路徑長度的概念。 樹中兩個結(jié)點之間的路徑由一個結(jié)點到另一結(jié)點的分支構(gòu)成。 兩結(jié)點之間的路徑長度是路徑上分支的數(shù)目。樹的路徑長度是從根結(jié)點到每一個

55、結(jié)點的路徑長度之和。 設(shè)一棵二叉樹有n個葉子結(jié)點, 每個葉子結(jié)點擁有一個權(quán)值1,2, ,n, 從根結(jié)點到每個葉子結(jié)點的路徑長度分別為L1, L2, Ln, 那么樹的帶權(quán)路徑長度為每個葉子的路徑長度與該葉子權(quán)值乘積之和， 通常記作: 為了直觀起見, 在圖中把帶權(quán)的葉子結(jié)點畫成方形, 其它非葉子結(jié)點仍為圓形。請看圖6.21中的三棵二叉樹以及它們的帶權(quán)路徑長。 請注意, 這三棵二叉樹葉子結(jié)點數(shù)相同, 它們的權(quán)值也相同, 但是它們的WPL帶權(quán)路徑長各不相同。 圖6.21(c)WPL最小。 它就是哈夫曼樹, 最優(yōu)樹。哈夫曼樹是在具有同一組權(quán)值的葉子結(jié)點的不同二叉樹中, 帶權(quán)路徑長度最短的樹也稱最優(yōu)樹。

56、2. 哈夫曼樹的構(gòu)造及其算法 1) 構(gòu)造哈夫曼樹的方法 對于已知的一組葉子的權(quán)值1,2,n : (1) 首先把n個葉子結(jié)點看做n棵樹（有一個結(jié)點的二叉樹）, 把它們看做一個森林。 (2) 在森林中把權(quán)值最小和次小的兩棵樹合并成一棵樹, 該樹根結(jié)點的權(quán)值是兩棵子樹權(quán)值之和。這時森林中還有n-1棵樹。 (3) 重復(fù)第(2)步直到森林中只有一棵為止。 此樹就是哈夫曼樹。 現(xiàn)給一組(n=4)具體的權(quán)值2, 4, 5, 8, 圖 6.22是構(gòu)造哈夫曼樹的具體過程。 2) 哈夫曼算法實現(xiàn) 討論算法實現(xiàn)需選擇合適的存儲結(jié)構(gòu), 這里選用的是順序存儲結(jié)構(gòu)。 因為哈夫曼樹中沒有度為1的結(jié)點。 由二叉樹性質(zhì)可知n0

57、 n2 1, 而現(xiàn)在總結(jié)點數(shù)為n0 n2, 也即2 n0 1, 葉子數(shù)n0若用n表示則二叉樹結(jié)點總數(shù)為2n1。 向量的大小就定義為2n1。假設(shè)n10, 存儲結(jié)構(gòu)如下: struct nodeh int data; /*權(quán)值域*/ int lch, rch; /*左、 右孩子結(jié)點在數(shù)組中的下標(biāo)*/ int tag; /* tag=0 結(jié)點獨立; tag=1 結(jié)點已并入樹中*/ struct nodeh r; 首先需將葉子權(quán)值輸入r向量, lch, rch, tag域全置零, 如果用前邊的一組數(shù)值2, 4, 5, 8初始化向量r, 見圖6.23(a)。 然后執(zhí)行算法, 可得出如圖6.23(b)所示

58、的結(jié)果。設(shè)t為指向哈夫曼樹的根結(jié)點（在此是數(shù)組元素）的指針，算法如算法6.20。 算法 6.20 int huffmah (struct node r20) scanf(nd, n); /* n為葉子結(jié)點的個數(shù) */ for(j=1; j=n; j+) scanf(d, rj.data); rj.tag0; rj.lch0; rj.rch0; i0; while (in-1) /* 合并n-1次 */ x1=0; m1 =32767; /* m1是最小值單元, x1為下標(biāo)號 */ x2 =0; m2 =32767; /* m2為次小值單元, x2為下標(biāo)號 */ for(j=1; j=n+i;

59、j+) if (rj.datam1)&(rj.tag=0)） m2 = m1; x2 = x1; m1 =rj.data; x1 =j; else if (rj.data=90)、 良(80=x90)、中(70=x80)、 及格(60=x70)、 不及格(x60) 5 個等級。若不考慮學(xué)生考試分?jǐn)?shù)的分布概率, 程序判定過程很容易寫成圖6.23(a)所示的方法。 我們知道, 一般來講學(xué)生考分大多分布在7080分之間, 從圖6.23(a)可看出這種情況的x值要比較2至3 次才能確定等級。而學(xué)生中考試不及格的人數(shù)很少, x值比較一次即可定等級。能否使出現(xiàn)次數(shù)多的在7080分之間的x值比較次數(shù)減少些,

60、 而使很少出現(xiàn)的低于60分的x值比較次數(shù)多一些, 以便提高程序的運行效率呢？ 假設(shè)學(xué)生成績對于不及格、及格、中等、良好和優(yōu)秀的分布概率分別為5, 15, 40, 30, 10, 以它們?yōu)槿~子的權(quán)值來構(gòu)造哈夫曼樹, 如圖6.23(b)所示。 此時帶權(quán)路徑長最短, 其值為205。 它可以使大部分的分?jǐn)?shù)值經(jīng)過較少的比較次數(shù)得到相應(yīng)的等級。但是, 事情往往不是絕對的, 此時每個判斷框內(nèi)的條件較為復(fù)雜, 比較兩次, 反而降低運行效率。所以我們采用折衷作法, 調(diào)整后得圖6.23(c)判定樹。它更加切合實際。 (2) 用于通信編碼。 在通信及數(shù)據(jù)傳輸中多采用二進(jìn)制編碼。為了使電文盡可能的縮短, 可以對電文中