數(shù)據(jù)結(jié)構(gòu)(第七章樹和二叉樹)DataStructures課件

1、數(shù) 據(jù) 結(jié) 構(gòu)（第七章 樹和二叉樹） Data Structures胡學(xué)鋼 張 晶計(jì)算機(jī)與信息學(xué)院 2009年2月1第七章 樹和二叉樹 第七章 樹和二叉樹 7.1 樹的相關(guān)概念和術(shù)語 7.2 二叉樹的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu) 7.3 二叉樹的遍歷及其應(yīng)用 7.4 線索二叉樹 7.5 樹和森林 7.6 哈夫曼樹（Huffman）27.1 樹的相關(guān)概念和術(shù)語 家族關(guān)系示意圖/單位機(jī)構(gòu)組成示意圖定義：樹T是由n個(gè)結(jié)點(diǎn)組成的有限集合（n 0）。 其中有一個(gè)根結(jié)點(diǎn)， 其余結(jié)點(diǎn)可劃分成m個(gè)（m=0）互不相交的子集 T1, T2, . ,Tm， 且這些子集也分別構(gòu)成樹。 （注意：有無空樹的概念）37.1 樹的相

2、關(guān)概念和術(shù)語術(shù)語關(guān)系術(shù)語 孩子結(jié)點(diǎn) 子樹的根 父結(jié)點(diǎn) 兄弟結(jié)點(diǎn) 同一個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)互為兄弟 祖先結(jié)點(diǎn) 后代結(jié)點(diǎn)層次類術(shù)語 根的層次為1 其余結(jié)點(diǎn)的層次為其父結(jié)點(diǎn)層次加1 高度/深度 整個(gè)樹中結(jié)點(diǎn)的最大層次 度 結(jié)點(diǎn)的孩子數(shù)目稱為結(jié)點(diǎn)的度 葉子（終結(jié)點(diǎn)） 度為0 分支結(jié)點(diǎn)-度不為0的結(jié)點(diǎn)（非葉子結(jié)點(diǎn)） 樹的度 最大的結(jié)點(diǎn)度 森林 多棵樹 有序樹/無序樹 按照兄弟結(jié)點(diǎn)之間的排列是否有序47.1 樹的相關(guān)概念和術(shù)語運(yùn)算（1）初始化（2）查找 結(jié)點(diǎn)的父、兄弟、祖先、后代、根（3）插入 葉子， 子樹（4）刪除 葉子，子樹樹的存儲(chǔ)？57.2 二叉樹的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)7.2.1定義 二叉樹T：是n個(gè)結(jié)

3、點(diǎn)組成的有限集合（n = 0）， n=0時(shí)為空二叉樹， 否則：其中有一個(gè)根結(jié)點(diǎn)， 其余結(jié)點(diǎn)可以劃分成兩個(gè)互不相交的子集TL, TR， 且TL, TR也分別構(gòu)成二叉樹 左、右子樹。67.2 二叉樹的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)二叉樹與樹的區(qū)別：是兩種不同性質(zhì)的結(jié)構(gòu)；二叉樹存在空樹，樹不存在空樹；二叉樹恰有兩個(gè)子樹，樹可有多個(gè)；二叉樹子樹有序，樹無序。比較三個(gè)結(jié)點(diǎn)的樹與二叉樹的各有幾種不同的形態(tài)。 三個(gè)結(jié)點(diǎn)的樹三個(gè)結(jié)點(diǎn)的二叉樹 AABBCCAAAAABBBBBCCCCC77.2 二叉樹的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)由定義可知，依據(jù)結(jié)點(diǎn)數(shù)的多少可將二叉樹劃分為五種不同的形態(tài)：（1）空樹，即結(jié)點(diǎn)數(shù)為0（2）單結(jié)點(diǎn)二叉

4、樹，即僅有一個(gè)結(jié)點(diǎn)（3）左子樹為空右子樹不空（4）右子樹為空左子樹不空（5）左右子樹均不空87.2 二叉樹的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)7.2.2二叉樹的性質(zhì) 性質(zhì)1：第i層的結(jié)點(diǎn)數(shù)2i-1； 性質(zhì)2：高度為k（k1）的二叉樹的結(jié)點(diǎn)總數(shù)2k-1； 性質(zhì)3：設(shè)二叉樹的葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則 n0=n2+1。 證明：設(shè)總結(jié)點(diǎn)數(shù)為n，度為1的結(jié)點(diǎn)數(shù)為n1，則 n=n0+n1+n2 結(jié)點(diǎn)數(shù) （1） n-1=n1+2n2 分支數(shù) （2） 式（1）（2）得 n0=n2+1課堂練習(xí)：已知一棵二叉樹中，有20個(gè)葉子結(jié)點(diǎn)，10個(gè)結(jié)點(diǎn)只有左孩子，15個(gè)結(jié)點(diǎn)只有右孩子，求該二叉樹的總結(jié)點(diǎn)數(shù)。97.2 二

5、叉樹的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)定義1：稱高度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹為滿二叉樹。例如，高度為14的滿二叉樹如下。 ABCGFEDANOABCGFEHIDKJMLCBA(a) 高度為1的滿二叉樹(b) 高度為2的滿二叉樹(c) 高度為3的滿二叉樹(d) 高度為4的滿二叉樹107.2 二叉樹的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)定義2：在滿二叉樹最下一層從右到左依次連續(xù)去掉若干個(gè)結(jié)點(diǎn)的二叉樹稱為完全二叉樹。 下面分別給出完全二叉樹和非完全二叉樹的示例。ABCGFEHIDKJML(a) 完全二叉樹示例MNABCGFEHIDKJL(b) 非完全二叉樹示例ON117.2 二叉樹的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)對(duì)完全二叉樹編號(hào)編

6、號(hào)的方式：從上到下，每一層中從左到右，根節(jié)點(diǎn)編號(hào)為1。例：下面完全二叉樹的編號(hào) ABCGFEHIDKJML12345678910111213127.2 二叉樹的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)性質(zhì)4：有n個(gè)（n1）結(jié)點(diǎn)的完全二叉樹的高度為 。 性質(zhì)5：對(duì)完全二叉樹進(jìn)行編號(hào)，則對(duì)編號(hào)為i的結(jié)點(diǎn)， 若存在左孩子結(jié)點(diǎn)，則其左孩子結(jié)點(diǎn)的編號(hào)為2i， 若存在右孩子結(jié)點(diǎn)，則其右孩子結(jié)點(diǎn)的編號(hào)為2i+1， 若存在父結(jié)點(diǎn)，則其父結(jié)點(diǎn)的編號(hào)為 。ABCGFEHIDKJML12345678910111213137.2 二叉樹的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)課堂練習(xí)： （1）求100個(gè)結(jié)點(diǎn)的完全二叉樹的葉子結(jié)點(diǎn)數(shù)。 解：根據(jù)性質(zhì)4，從編

7、號(hào)51到100都是葉子。共有50個(gè)葉子。 （2）已知完全二叉樹的第7層有10個(gè)結(jié)點(diǎn)，問共有多少個(gè)結(jié)點(diǎn)？多少個(gè)葉子結(jié)點(diǎn)？多少個(gè)度為1的結(jié)點(diǎn)？ 解：共有26-1+10=73個(gè)結(jié)點(diǎn)。 葉子求法： 方法1、37到73都是葉子，共37個(gè)葉子結(jié)點(diǎn)； 方法2、第7層10個(gè)結(jié)點(diǎn)都是葉子，第6層有26-1=32個(gè)結(jié)點(diǎn)，其中5 個(gè)結(jié)點(diǎn)是第7層10個(gè)結(jié)點(diǎn)的父親， 所以共有10+32-5=37個(gè)葉子結(jié)點(diǎn)。 度為1的結(jié)點(diǎn)數(shù)為0。 （3）判斷題：完全二叉樹最多有1個(gè)度為1的結(jié)點(diǎn)。（ ） （4）編號(hào)為i、j的兩個(gè)結(jié)點(diǎn)是否在同一層的條件是 。 10050147.2 二叉樹的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)7.2.3 二叉樹的存儲(chǔ) 存儲(chǔ)一

8、個(gè)結(jié)構(gòu)時(shí)，不僅要存值，還要存儲(chǔ)元素間的關(guān)系。 1. 順序存儲(chǔ)方式存儲(chǔ)方式：用數(shù)組存儲(chǔ)二叉樹各結(jié)點(diǎn)的值， 各結(jié)點(diǎn)在數(shù)組中的位置（元素下標(biāo)） -就是其在完全二叉樹中對(duì)應(yīng)結(jié)點(diǎn)的編號(hào)。例如：右圖二叉樹的存儲(chǔ)如下所示。 ABCGFEHIDKJML12345678910111213157.2 二叉樹的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)分析：這種方法有其優(yōu)點(diǎn)，但也有不足： 優(yōu)點(diǎn)：方便、簡(jiǎn)潔 缺點(diǎn)：只適合完全二叉樹 或 近似的完全二叉樹。例如，對(duì)如下形狀的二叉樹，僅有n個(gè)結(jié)點(diǎn)， 但需要的數(shù)族元素個(gè)數(shù)為2n-1。問題： 若數(shù)組元素占一個(gè)單元， 則在n=20、30時(shí)， 分別需要多大的存儲(chǔ)空間？練習(xí)：設(shè)計(jì)算法求出編號(hào)i、j的最小

9、公共祖先。x2x3x1xn1372n-1167.2 二叉樹的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu) 2. 動(dòng)態(tài)二叉鏈表存儲(chǔ)方式： 二叉樹中每個(gè)結(jié)點(diǎn)用一個(gè)有兩個(gè)分叉的結(jié)點(diǎn)（二叉結(jié)點(diǎn)）來存儲(chǔ)， 每個(gè)分叉指向左右孩子結(jié)點(diǎn)中的一個(gè) -左右孩子結(jié)點(diǎn)指針）。由此可得到二叉樹的二叉鏈表結(jié)構(gòu)。 設(shè)二叉結(jié)點(diǎn)類型為bnode, 其中： 左右孩子指針分別為 lchild和rchild， 存儲(chǔ)結(jié)點(diǎn)值的字段為data， 則結(jié)點(diǎn)的類型描述如下：typedef struct elementtype data; bnode *lchild, *rchild; bnode;lchild data rchild指向左孩子的指針指向右孩子的指針bn

10、ode177.2 二叉樹的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)例：下面二叉樹對(duì)應(yīng)的二叉鏈表結(jié)構(gòu)如圖所示。相關(guān)問題：（1）如圖所示，根結(jié)點(diǎn)的指針為T， 則如何表示其左右孩子指針的標(biāo)識(shí)符？（2）從圖中可知，二叉鏈表中有值為空的指針， 有n個(gè)結(jié)點(diǎn)的二叉鏈表中有多少個(gè)這樣的空指針？AGFEDCB G AB E C D F T187.3 二叉樹的遍歷及其應(yīng)用 7.3.1 遍歷的基本方法二叉樹的遍歷 按照某種次序依次訪問二叉樹T中每個(gè)結(jié)點(diǎn)一次且僅一次。分析：（1）若T為空，遍歷結(jié)束；（2）否則，設(shè)二叉樹的形態(tài)如右圖所示。a . 假設(shè)左右子樹能分別遍歷 （用L，R分別表示其遍歷），則整個(gè)二 叉樹可有如下形式的遍歷： 先左后

11、右：DLR LDR LRD 先右后左：DRL RDL RLD 先根序 中根序 后根序b.對(duì)于左右子樹的遍歷， 可按照與整個(gè)二叉樹相同的方式遍歷（遞歸調(diào)用）DLR197.3 二叉樹的遍歷及其應(yīng)用有關(guān)遍歷方法的例題： 例：分別寫出下圖二叉樹的先序、中序和后序序列ABCDEFGHICDBEFAHGIDCFEBHIGADEIAGFCBH先序中序：后序：求解過程討論求解過程討論求解過程討論207.3 二叉樹的遍歷及其應(yīng)用 例：已知一棵二叉樹的先序序列和中序序列，要求還原該二叉樹。 先序：ABCDEFG 中序：CDBEAGFGFDCBCDECDBEFGGFCDCDBAAABEFGGFE217.3 二叉樹的

12、遍歷及其應(yīng)用結(jié)論：已知中序序列和后序序列，或中序序列和先序序列，可 以唯一確定一棵二叉樹； 而已知先序序列和后序序列不能唯一確定二叉樹。課堂練習(xí)：已知二叉樹中序序列和后序序列，還原此二叉樹。AGFEDCB中序：CBDAGEF后序：CDBGFEA227.3 二叉樹的遍歷及其應(yīng)用7.3.2遍歷算法遍歷方法先序遍歷二叉樹T若T不空，則： 訪問根； 先序訪問其左子樹； 先序訪問其右子樹 中序遍歷二叉樹T若T不空，則： 中序訪問其左子樹； 訪問根； 中序訪問其右子樹。遍歷算法void preorder(bnode *t) if(t!=null) visit(t); preorder(t-lchild);

13、 preorder(t-rchlid); void inorder(bnode *t) if(t!=null) inorder(t-lchild); visit(t); inorder(t-rchlid); 237.3 二叉樹的遍歷及其應(yīng)用 后序遍歷二叉樹T 若T不空，則： 后序訪問其左子樹； 后序訪問其右子樹。 訪問根； void postorder (bnode *t) if(t!=null) postorder (t-lchild); postorder (t-rchlid); visit(t); 247.3 二叉樹的遍歷及其應(yīng)用 練習(xí)： （1）對(duì)前述二叉樹，按照閱讀遞歸算法的方法，模擬

14、執(zhí)行。 （2）證明preorder(bnode * T)對(duì)二叉樹遍歷的正確性（所有結(jié)點(diǎn)訪問一次僅且一次） （3） 設(shè)計(jì)算法求二叉樹的結(jié)點(diǎn)數(shù)257.3 二叉樹的遍歷及其應(yīng)用7.3.3遍歷算法的應(yīng)用例題：設(shè)計(jì)算法輸出二叉樹的所有葉子結(jié)點(diǎn)的值 設(shè)計(jì)算法先序輸出二叉樹中所有結(jié)點(diǎn)值及其對(duì)應(yīng)層次/序號(hào) 設(shè)計(jì)算法輸出從根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的路徑（利用棧） 7.3.4 遍歷方法的應(yīng)用 1、求給定二叉樹的高度：（1）若T為空，則高度為0，遍歷結(jié)束；（2）否則，設(shè)二叉樹的形態(tài)如右圖所示。a、假設(shè)左右子樹能分別求出高度為hl、hr， 則整個(gè)二叉樹的高度為： max(hl, hr) + 1;b、對(duì)于左右子樹高度的求解

15、，可按照 與整個(gè)二叉樹相同的方式進(jìn)行（遞歸調(diào)用）T L R267.3 二叉樹的遍歷及其應(yīng)用 設(shè)函數(shù)int high(bnode *t)為求T的高度算法，則 int high( bnode *T ) if ( T = NULL ) return(0); else return max( high( T - lchild ), high( T - rchild ) ) + 1 ; 或者 int high( bnode * T ) if ( T = NULL ) return(0); else hl = high( T - lchild ); hr = high( T - rchild ); h =

16、 max( hl, hr ) + 1; return(h); 注意：hl,hr是局部變量還是全局變量？有何差異？如何體現(xiàn)？277.3 二叉樹的遍歷及其應(yīng)用2、設(shè)計(jì)算法求二叉樹的結(jié)點(diǎn)數(shù)：分析: （1）設(shè)置一個(gè)全局變量，在遍歷二叉樹的過程中，對(duì)訪問的結(jié)點(diǎn)累計(jì)計(jì)數(shù)。 （2） 設(shè)函數(shù)void num( bnode *T )表示對(duì)以T為根的二叉樹遍歷和計(jì)數(shù)，分析如下： 如果T = NULL 結(jié)點(diǎn)數(shù)為0，不必累計(jì)； 否則 結(jié)點(diǎn)數(shù) = 左子樹結(jié)點(diǎn)數(shù) 右子樹結(jié)點(diǎn)數(shù)+1。 void num( bnode *T ) /設(shè)k是全局變量，初始化k=0 if ( T != NULL ) k+; num( T - lch

17、ild ); num( T - rchild ); 287.3 二叉樹的遍歷及其應(yīng)用也可以設(shè)一個(gè)參數(shù)返回累計(jì)的結(jié)點(diǎn)數(shù)。void num( bnode *T, int &k ) /設(shè)調(diào)用時(shí)k對(duì)應(yīng)的實(shí)參初始化為0 if ( T != NULL ) k+; num( T - lchild ); num( T - rchild ); 可以設(shè)計(jì)為int型函數(shù)形式： int num( bnode * T ) if ( T = NULL ) return(0); else return num( T - lchild ) + num( T - rchild ) + 1; 297.3 二叉樹的遍歷及其應(yīng)用3、

18、設(shè)計(jì)算法求二叉樹的葉子結(jié)點(diǎn)數(shù)：分析：可以設(shè)計(jì)出多種形式的函數(shù)： int型函數(shù)，void型函數(shù)； 可以通過全局變量返回值，參數(shù)形式返回等。 void leaf( bnode *T, int &k ) /設(shè)調(diào)用時(shí)k對(duì)應(yīng)的實(shí)參初始化為0 if ( T != NULL ) if ( T - lchild = NULL & T - rchild = NULL ) k+; leaf( T - lchild ); leaf( T - rchild ); 307.3 二叉樹的遍歷及其應(yīng)用練習(xí)：（1）設(shè)計(jì)一個(gè)非遞歸算法以輸出二叉樹t中先序序列中最后一個(gè)結(jié)點(diǎn) 的值。分析：首先需要知道這一結(jié)點(diǎn)的條件，然后才能正確地

19、求解。請(qǐng)注意下面的算法中的相關(guān)條件，以及求解的思路。void print(bnod *t) p=t; while (p - lchild != NULL | p - rchild != NULL ) if ( p - rchild = NULL ) p = p - lchild; else p = p - rchild; cout data;317.3 二叉樹的遍歷及其應(yīng)用（2）設(shè)計(jì)算法將二叉鏈表存儲(chǔ)的二叉樹轉(zhuǎn)換為順序存儲(chǔ)形式。 存儲(chǔ)在 A中，并將對(duì)應(yīng)空結(jié)點(diǎn)的元素的值設(shè)置為“”。例如，下面是一棵二叉樹及其對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu)A的示例。 ABCGFEHDIKJ123456789101213327.3

20、二叉樹的遍歷及其應(yīng)用 void trans( bnode *t, int i ) if ( t != NULL ) Ai = t - data; trans( t - lchild,2 * i ); trans( t - rchild,2 * i + 1 ); 調(diào)用該算法前，將數(shù)組所有元素先設(shè)置為“”。(2) 設(shè)計(jì)算法輸出二叉樹先序遍歷的前k個(gè)結(jié)點(diǎn)判斷題： 先序和中序相同的二叉樹，所有結(jié)點(diǎn)左孩子為空。（ ） 先序和中序相反的二叉樹，所有結(jié)點(diǎn)右孩子為空。（ ） 先序序列中最后一個(gè)結(jié)點(diǎn)是葉子結(jié)點(diǎn)。 （ ） 后序序列中第一個(gè)結(jié)點(diǎn)是葉子結(jié)點(diǎn)。 （ ） 中序序列中第一個(gè)結(jié)點(diǎn)是葉子結(jié)點(diǎn)。 （ ）337.4

21、 線索二叉樹1?；靖拍顔栴}： 對(duì)給定二叉樹（二叉鏈表），求某結(jié)點(diǎn)在給定次序（先、中、后序）中的前驅(qū)或后繼。 例如，右圖中的結(jié)點(diǎn)E，在先序、中序、后序前驅(qū)、后繼結(jié)點(diǎn)。 求解方法 （1）從頭開始遍歷 -費(fèi)時(shí)； （2）給每個(gè)結(jié)點(diǎn)增設(shè)前驅(qū)/后繼指針 費(fèi)空間； （3）利用二叉鏈表中n+1個(gè)為空的指針域 -可行的一種考慮 DEIAGFCBH347.4 線索二叉樹 將二叉鏈表中空的指針修改為指向前驅(qū)或后繼，即 將其中的值為空的左孩子指針改為指向前驅(qū)， 將其中的值為空的右孩子指針改為指向后繼。 -線索。 -線索二叉樹。 例如，右圖就是一個(gè) 先序線索二叉樹。 其中線索用虛線表示。 線索化將二叉樹修改為線索二叉

22、樹的過程。 ABCDEFHGIJ357.4 線索二叉樹為了區(qū)分孩子指針和線索（雖然由圖中可以“直觀地”區(qū)分出來，但在算法中卻不行）。在每個(gè)結(jié)點(diǎn)中需再引入兩個(gè)區(qū)分標(biāo)志ltag和rtag，并且約定如下：ltag=0： lchild指示該結(jié)點(diǎn)的左孩子。 ltag=1： lchild指示該結(jié)點(diǎn)的前驅(qū)。 rtag=0： rchild指示該結(jié)點(diǎn)的右孩子。 rtag=1： rchild指示該結(jié)點(diǎn)的后繼。0A00B01C10D01E11F10G11H00I11J1367.4 線索二叉樹為簡(jiǎn)便起見，通常將線索二叉樹畫成如下的形式。ABCDGFEHI先序線索二叉樹EIHDCGBAF中序線索二叉樹377.4 線索二

23、叉樹 2。線索二叉樹的結(jié)構(gòu)描述 如前所述，為區(qū)分結(jié)點(diǎn)中的孩子指針和線索，結(jié)點(diǎn)中增設(shè)了兩個(gè)標(biāo)志ltag和rtag，并約定： 0 結(jié)點(diǎn)中的 lchild字段指向左孩子； ltag= 1 結(jié)點(diǎn)中的 lchild字段指向前驅(qū)； 0 結(jié)點(diǎn)中的 rchild字段指向右孩子； rtag= 1 結(jié)點(diǎn)中的 rchild字段指向后繼； 由此可知，結(jié)點(diǎn)的類型描述 typedef struct tbnode elementtype data; tbnode *lchild, *rchild; int ltag, rtag; tbnode; 387.4 線索二叉樹3.線索二叉樹中前驅(qū)和后繼的求解 (1) 先序線索二叉樹

24、中先序后繼的求解-先序后繼 對(duì)先序線索二叉樹中任意結(jié)點(diǎn)P，求其先序后繼.。 討論： (a) 若*p有左孩子 按照遍歷的過程描述（PPlPr）可知， 其后繼應(yīng)為：左子樹Pl中的第一個(gè)結(jié)點(diǎn)， 即*p的左孩子結(jié)點(diǎn)， 因此， p-lchild為其后繼； (b) 否則，*p有右孩子 類似地，可知 p-rchild為其后繼； (c) 否則， p-rchild為其后繼線索；由此得算法如下： tbnode *presuc(bnode *p) if ( p - ltag = 0 ) return ( p - lchild ); else return ( p - rchild ); P PLPR(a)PPR(b

25、)(c)P397.4 線索二叉樹 (2) 先序線索二叉樹中先序前驅(qū)的求解-先序前驅(qū) 對(duì)二叉樹先序中任意的結(jié)點(diǎn)P，求其前驅(qū).。 討論： (a) 若*P是根結(jié)點(diǎn) 無前驅(qū) (b) 若*P是其父結(jié)點(diǎn)的左孩子 前驅(qū)是其父結(jié)點(diǎn)； (c) 否則，若*P是其父結(jié)點(diǎn)的右孩子 無左兄弟結(jié)點(diǎn) 前驅(qū)是父結(jié)點(diǎn)； 有左兄弟結(jié)點(diǎn) 前驅(qū)是左兄弟子樹中 最右下的葉子結(jié)點(diǎn)。 練習(xí)：(1) 設(shè)計(jì)一個(gè)非遞歸算法，以先序遍歷先序線索二叉樹（且不用棧） 407.4 線索二叉樹(3) 中序線索二叉樹中中序后繼的求解-中序后繼分析：按照中序遍歷的過程描述（PLPPR）可知， (a) 若*P有右孩子 其后繼應(yīng)在其右子樹中， 即右子樹的中序序列

26、的 第一個(gè)結(jié)點(diǎn)為*p的后繼。 如何求解此結(jié)點(diǎn)？ -從右孩子結(jié)點(diǎn)望左下“滑行”到 。？ (b) 若*P無右孩子 則p - rchild 就是其后繼線索。PPR(a)(b)PPP1P2Pk41N Y7.4 線索二叉樹 tbnode * insuc ( tbnode *p ) if ( p - rtag = 1 ) return ( p - rchild ); else q = p - rchild; while ( q - ltag = 0 ) q = q - lchild; return(q); P有右孩子Yq=p-rchildq有左孩子q=q-lchildNReturn p-rchildRet

27、urn q 由討論得流程圖如下：427.4 線索二叉樹 (4) 中序前驅(qū)的求解 與中序后繼對(duì)稱 分析： (a) 若有左孩子 前驅(qū)是左子樹中序序列的最后一個(gè)結(jié)點(diǎn)； (b) 若無左孩子 前驅(qū)線索p-lchild。 tbnode * inpre ( tbnode *p ) if ( p - ltag = 1 ) return ( p - lchild ); else q = p - lchild; while ( q - rtag = 0 ) q = q - rchild; return(q); 437.4 線索二叉樹 (5) 后序前驅(qū)的求解分析： (a) 若*p有右孩子 右孩子結(jié)點(diǎn)是其前驅(qū)； (b

28、) 否則，若*P有左孩子 左孩子結(jié)點(diǎn)是其前驅(qū)； (c) 否則 p - lchild是其前驅(qū)線索 。 與先序后繼的求解方式對(duì)稱。 (6) 后序后繼的求解分析： (a) 根 無后繼； (b) 若*p是其父結(jié)點(diǎn)的右孩子 父結(jié)點(diǎn)是其后繼； (c) 若是父結(jié)點(diǎn)的左孩子 無右兄弟 父結(jié)點(diǎn)是其后繼 有右兄弟 右兄弟子樹的后序序列的第一個(gè)結(jié)點(diǎn)是其后繼 -右兄弟子樹中最左下的葉子結(jié)點(diǎn)。447.4 線索二叉樹4。線索二叉樹中插入結(jié)點(diǎn)在結(jié)構(gòu)中插入一個(gè)元素或結(jié)點(diǎn)是常見的運(yùn)算。在線索二叉樹中插入一個(gè)結(jié)點(diǎn)時(shí)，不僅要實(shí)現(xiàn)指定結(jié)點(diǎn)的父子關(guān)系的運(yùn)算，還需要在插入結(jié)點(diǎn)后，通過修改線索，以維護(hù)二叉樹的線索關(guān)系。例如，在右圖線索二叉

29、樹中，將某結(jié)點(diǎn)插入到作為結(jié)點(diǎn)F的左孩子。如何實(shí)現(xiàn)相關(guān)的操作？s先序線索二叉樹ABCDGFEHI457.4 線索二叉樹分析：對(duì)這類插入操作，通常從兩個(gè)方面來考慮其實(shí)現(xiàn)： （1）一個(gè)是父子關(guān)系的連接實(shí)現(xiàn) 按照指定關(guān)系連接即可 （2）線索關(guān)系的維護(hù) 這一關(guān)系的實(shí)現(xiàn)有一定的難度。下面分別討論。（1）父子關(guān)系的連接實(shí)現(xiàn) 對(duì)前述問題，由問題描述可知， 假設(shè)指針P指示到了F結(jié)點(diǎn)， 連接操作如圖所示，操作如下： p-lchild=s; p-ltag=0;先序線索二叉樹ABCDGFEHIPs467.4 線索二叉樹（2）線索關(guān)系的維護(hù)這一操作主要由如下4項(xiàng)組成：（某些操作可能因具體問題而不必）設(shè)置新插入結(jié)點(diǎn)的前驅(qū)

30、、后繼線索修改新結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的后繼線索修改新結(jié)點(diǎn)的后繼結(jié)點(diǎn)的前驅(qū)線索就本題而言，首先需要明確：新結(jié)點(diǎn)的前驅(qū)、后繼位置及其指針： 由圖可知，前驅(qū)后繼結(jié)點(diǎn)分別是 F結(jié)點(diǎn)和G結(jié)點(diǎn) 更一般情況下，可由*P及其后繼求得。 先序線索二叉樹ABCDGFEHIPs477.4 線索二叉樹下面先討論線索操作的一般性方法，然后給出本題的操作實(shí)現(xiàn)。假設(shè)當(dāng)前結(jié)點(diǎn)為*P，由于線索關(guān)系使得結(jié)點(diǎn)之間建立了線性關(guān)系，因此，插入結(jié)點(diǎn)時(shí)的線索維護(hù)類似于雙鏈表中插入結(jié)點(diǎn)。由于新結(jié)點(diǎn)是作為*P的后繼，因此，可有如下的邏輯圖：GFPxs487.4 線索二叉樹本題的線索維護(hù)操作如下：請(qǐng)標(biāo)出其操作示意圖。 s-lchild=p; s-lt

31、ag=1; s-rchild=p-rchild; s-rtag=1; p-rchild=s; P-rtag=1; if (s-rchild-ltag=1) s-rchild-lchild=s;習(xí)題：設(shè)計(jì)算法將s結(jié)點(diǎn)作為A的右子樹的最左下的葉子結(jié)點(diǎn)的左孩子插入到先序線索二叉樹中，并維護(hù)其線索關(guān)系。先序線索二叉樹ABCDGFEHIPs497.4 線索二叉樹void create ( bitre &T ) cin x; if ( x = . ) T = NULL; T = new bnode; T - data = x; create ( T - lchild ); create ( T - rch

32、ild );507.5 樹和森林7.5.1樹/森林的存儲(chǔ)結(jié)構(gòu)1. 雙親表示法 存儲(chǔ)每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的位置信息。例如： 優(yōu)點(diǎn)：簡(jiǎn)潔， 形式一致； 搜索父結(jié)點(diǎn)、祖先容易 缺點(diǎn)：搜索孩子結(jié)點(diǎn)費(fèi)時(shí)； 插入刪除時(shí)需注意維護(hù)關(guān)系A(chǔ)-1B0C0D0E1F1G2H3I3J3K4ABCGFEHIJKDdata parents517.5 樹和森林2. 孩子鏈表表示法存儲(chǔ)每個(gè)結(jié)點(diǎn)的孩子信息，因而是鏈表形式。 優(yōu)點(diǎn)：找孩子結(jié)點(diǎn)/后代容易缺點(diǎn)：重復(fù) 結(jié)構(gòu)不一致BCD EF G K H I J ABCGFEHIJKDdata children_link527.5 樹和森林3. 孩子兄弟鏈表表示法表示方法：采用鏈表結(jié)構(gòu)來

33、存儲(chǔ)樹， 鏈表中結(jié)點(diǎn)與樹中結(jié)點(diǎn)對(duì)應(yīng)， 每個(gè)結(jié)點(diǎn)存儲(chǔ)其第一個(gè)孩子結(jié)點(diǎn) 和下一個(gè)兄弟結(jié)點(diǎn)。由此而得名。也叫二叉鏈表表示法，或二叉樹表示法。firstson data nextbrother 指向其第一個(gè)孩子結(jié)點(diǎn)指向其下一個(gè)兄弟結(jié)點(diǎn)537.5 樹和森林前述樹所對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu)如下： A F B G C K D J I H EABCGFEHIJKD547.5 樹和森林將前述孩子兄弟鏈表順時(shí)針旋轉(zhuǎn)45。，對(duì)應(yīng)到一個(gè)二叉鏈表，因此也對(duì)應(yīng)到一棵二叉樹。 H G D F A B C E I K J ABCGFEHIJKD557.5 樹和森林如果是森林，其存儲(chǔ)如何？ 森林 二叉鏈表（二叉樹） 由圖可知，這其實(shí)是二

34、叉鏈表結(jié)構(gòu)，所以任意一棵樹（森林）必然與唯一的一棵二叉樹一一對(duì)應(yīng)。ABCGFEHIJKDLMNABCGFEHIJKDMNL567.5 樹和森林7.5.2 樹/森林與二叉樹之間相互轉(zhuǎn)換1樹/森林 F=（T1，T2，Tm） = 二叉樹 BT(1) T1的根 = BT的根(2) T1的子樹/森林 = BT的左子樹(3) （T2，Tm）= BT的右子樹2二叉樹 BT = 樹/森林 F=（T1，T2，Tm）如果BT不空，則：(1) BT的根 = T1的根(2) BT的左子樹 = T1的子樹/森林 (3) BT的右子樹 =（T2，Tm） 577.5 樹和森林練習(xí)：將下面的森林轉(zhuǎn)換為對(duì)應(yīng)的二叉樹。兩者關(guān)系(

35、1) 某結(jié)點(diǎn)在樹中為葉子結(jié)點(diǎn)，在二叉樹中未必為葉子結(jié)點(diǎn)；(2) 二叉樹中為葉子結(jié)點(diǎn)，在樹中沒有孩子的老?。?3) 兩者分支數(shù)不一定相同。（樹相同，森林則不同）ABCGFEHIJKDLMNOPQR587.5 樹和森林7.5.3 樹/森林的遍歷按照根結(jié)點(diǎn)與子樹的訪問次序， 有兩種遍歷森林的方法。 -先序遍歷和后序遍歷。 1、先序遍歷 樹（森林）F = （T1，T2，Tm）如果F不空，則：(1) 訪問T1的根；(2) 先序遍歷T1的子樹森林；(3) 先序遍歷（T2，T3，Tm）。597.5 樹和森林例如，對(duì)前述的森林，其先序遍歷的序列ABCGFEHIJKDLMNABCGFEHIJKDMNLABEKF

36、CGDHIJLMNABEKFCGDHIJLMN再看一下對(duì)應(yīng)的二叉樹的先序序列，也是607.5 樹和森林先序遍歷森林的算法如下： void preorder( tree T ) if ( T != NULL ) visite ( T); preorder( T - firstson ); preorder( T - nextbrother ); 617.5 樹和森林2、后序遍歷樹/森林 F = （T1，T2，Tm）如果T不空，則： (1) 后序遍歷T1子樹森林； (2)訪問T1的根； (3)后序遍歷E（T2，T3，Tm）。627.5 樹和森林例： ABCGFEHIJKDLMNABCGFEHIJK

37、DMNLKEFBGCHIJDALNMKEFBGCHIJDALNM對(duì)應(yīng)二叉樹的中序序列：后序遍歷森林的序列：637.5 樹和森林后序遍歷森林的算法如下：void postorder( tree T ) if ( T != NULL ) postorder( T - firstson ); visite ( T - data ); postorder( T - nextbrother ); 練習(xí)： 設(shè)計(jì)算法求樹/森林中的葉子結(jié)點(diǎn) 設(shè)計(jì)算法求樹/森林的高度 設(shè)計(jì)算法求樹/森林中所有的父子對(duì)647.6 哈夫曼樹（Huffman）引言 例：考試成績(jī)轉(zhuǎn)換 90100： A 8089 ： B 7079 ：

38、C 6069 ： D 0 59 ： E S=90S=80S=70S=60NNYYEDYNYNABC判斷流程一657.6 哈夫曼樹（Huffman）判斷流程二 判斷流程三 S60S70S80S=70S=80S=90S=60NYYNABCYNDEYN667.6 哈夫曼樹（Huffman）假設(shè)個(gè)分?jǐn)?shù)段的分布如下，A： 5% 500份B： 15% 1500份C： 30% 3000份D： 35% 3500份： 15% 1500份則各流程圖的判斷次數(shù)存在差異：流程一的判斷次數(shù)： 50011500230003350041500432500次S=90S=80S=70S=60NNYYEDYNYNABC677.6

39、 哈夫曼樹（Huffman）流程二判斷次數(shù)： 50041500430003350021500125500次流程三判斷次數(shù)： 50031500330002350021500222000次結(jié)論：選擇不同的求解次序造成比較/判斷次數(shù)的差異判斷流程二 判斷流程三 YNS60S70S80S=70S=80S=90S=60NYYNBCYNDEYN687.6 哈夫曼樹（Huffman）定義： 給定一組數(shù)值w1，w2,wn，作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造一棵二叉樹。若二叉樹滿足 WPL= 最?。ㄆ渲蠰i為wi對(duì)應(yīng)的葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度），則稱此二叉樹為最優(yōu)二叉樹，也稱哈夫曼樹，并稱WPL為帶權(quán)路徑長(zhǎng)度。697.6 哈夫曼樹（Huffman）哈夫曼樹的構(gòu)造 對(duì)給定的w=w1，w2,wn，如何以此