算法與數(shù)據(jù)結構第6章2

1、1第第6章章 樹和二叉樹（樹和二叉樹（ Tree & Binary Tree ）6.1 樹的基本概念樹的基本概念6.2 二叉樹二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 樹和森林樹和森林6.5 赫夫曼樹及其應用赫夫曼樹及其應用上機內(nèi)容：上機內(nèi)容： （實驗要求參見嚴題集（實驗要求參見嚴題集P149 P149 ）26.2 6.2 二叉樹二叉樹為何要重點研究每結點最多只有兩個為何要重點研究每結點最多只有兩個 “ “叉叉” ” 的樹？的樹？ 二叉樹的結構最簡單，規(guī)律性最強；二叉樹的結構最簡單，規(guī)律性最強； 可以證明，所有樹都能轉為唯一對應的二叉樹，不失一般性?？梢宰C明，所

2、有樹都能轉為唯一對應的二叉樹，不失一般性。1. 二叉樹的定義二叉樹的定義2. 二叉樹的性質(zhì)二叉樹的性質(zhì)3. 二叉樹的存儲結構二叉樹的存儲結構（二叉樹的運算見下一節(jié)）（二叉樹的運算見下一節(jié)）3性質(zhì)性質(zhì)1: 1: 在二叉樹的第在二叉樹的第i i層上至多有層上至多有個結點（個結點（i0i0）。）。性質(zhì)性質(zhì)2: 2: 深度為深度為k k的二叉樹至多有的二叉樹至多有個結點（個結點（k0k0）。）。性質(zhì)性質(zhì)3: 3: 對于任何一棵二叉樹，若對于任何一棵二叉樹，若2 2度的結點數(shù)有度的結點數(shù)有n n2 2個，個，則葉子數(shù)（則葉子數(shù)（n n0 0）必定為必定為n n2 21 1 （即（即n0=n2+1）課堂練

3、習：課堂練習：1. 1. 樹中各結點的度的最大值稱為樹的樹中各結點的度的最大值稱為樹的 。 ) ) 高度高度 ) ) 層次層次 ) ) 深度深度 ) ) 度度2.2.深度為深度為k的二叉樹的結點總數(shù)，最多為的二叉樹的結點總數(shù)，最多為 個。個。 ) )k-1k-1 ) ) loglog2 2k k ) ) k k ) )k k3. 3. 深度為深度為9 9的二叉樹中至少有的二叉樹中至少有 個結點。個結點。 ) )9 9 ) )8 8 ) ) ) )9 91 14對于兩種特殊形式的二叉樹（對于兩種特殊形式的二叉樹（滿二叉樹和完全二叉樹滿二叉樹和完全二叉樹），），還特別具備以下還特別具備以下2 2個

4、性質(zhì)：個性質(zhì)：性質(zhì)性質(zhì)4: 4: 具有具有n n個結點的完全二叉樹的深度必為個結點的完全二叉樹的深度必為 loglog2 2n n 1 1性質(zhì)性質(zhì)5: 5: 對完全二叉樹，若從上至下、從左至右編號，對完全二叉樹，若從上至下、從左至右編號，則編號為則編號為i 的結點，其左孩子編號必為的結點，其左孩子編號必為2i，其右孩子編號，其右孩子編號為為2i1；其雙親的編號必為；其雙親的編號必為i/2（i1 時為根時為根, ,除外除外）。）。 證明：根據(jù)性質(zhì)證明：根據(jù)性質(zhì)2 2，深度為，深度為k k的二叉樹最多只有的二叉樹最多只有2 2k k-1-1個結點，且完全二叉樹的定個結點，且完全二叉樹的定義是與同深

5、度的滿二叉樹前面編號相同，即它的總結點數(shù)義是與同深度的滿二叉樹前面編號相同，即它的總結點數(shù)n n位于位于k k層和層和k-1k-1層滿層滿二叉樹容量之間，即二叉樹容量之間，即 2 2k-1k-1-1n2-1n2k k-1 -1 或或2 2k-1k-1n n 2 2k k三邊同時取對數(shù)，于是有：三邊同時取對數(shù)，于是有：k-1logk-1log2 2nk n1)f=n*fact(n-1); else f=1; return(f); 16先序遍歷算法先序遍歷算法DLR( liuyu *root )if (root !=NULL) /非空二叉樹非空二叉樹 printf(“%d”,root-data);

6、 /訪問訪問D DDLR(root-lchild); /遞歸遍歷左子樹遞歸遍歷左子樹DLR(root-rchild); /遞歸遍歷右子樹遞歸遍歷右子樹 return(0); 中序遍歷算法中序遍歷算法LDR(x*root)if(root !=NULL) LDR(root-lchild); printf(“%d”,root-data); LDR(root-rchild); return(0);后序遍歷算法后序遍歷算法LRD (x*root)if(root !=NULL) LRD(root-lchild); LRD(root-rchild); printf(“%d”,root-data); retu

7、rn(0);結點數(shù)據(jù)類型自定義結點數(shù)據(jù)類型自定義typedef struct liuyuint data; struct liuyu *lchild,*rchild； liuyu;liuyu *root; 17對遍歷的分析：對遍歷的分析：1. 從前面的三種遍歷算法可以知道：如果將從前面的三種遍歷算法可以知道：如果將print語句抹去，語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的遍歷算法的訪問路徑是相同的，只是訪問結點的時機不同訪問路徑是相同的，只是訪問結點的時機不同。從虛線的出發(fā)點到終點的路徑從虛線的出發(fā)點到終點的

8、路徑上，每個結點經(jīng)過上，每個結點經(jīng)過3次次。AFEDCBG第第1次次經(jīng)過時訪問經(jīng)過時訪問先序先序遍歷遍歷第第2次次經(jīng)過時訪問經(jīng)過時訪問中序中序遍歷遍歷第第3次次經(jīng)過時訪問經(jīng)過時訪問后序后序遍歷遍歷2. 2. 二叉樹遍歷的時間效率和空間效率二叉樹遍歷的時間效率和空間效率時間效率時間效率: : /每個結點只訪問一次每個結點只訪問一次空間效率空間效率: : /棧占用的最大輔助空間棧占用的最大輔助空間（精確值：樹深為（精確值：樹深為k k的遞歸遍歷需要的遞歸遍歷需要k+1k+1個輔助單元?。﹤€輔助單元?。?8例：例：【嚴題集【嚴題集6.42】編寫遞歸算法，計算二叉樹編寫遞歸算法，計算二叉樹中葉子結點的

9、數(shù)目。中葉子結點的數(shù)目。 思路：思路：輸出葉子結點比較簡單，用任何一種遍歷算法，凡輸出葉子結點比較簡單，用任何一種遍歷算法，凡是左右指針均空者，則為葉子，將其統(tǒng)計并打印出來。是左右指針均空者，則為葉子，將其統(tǒng)計并打印出來。 DLR(liuyu *root) /采用中序遍歷的遞歸算法采用中序遍歷的遞歸算法 if ( root!=NULL ) /非空二叉樹條件，還可寫成非空二叉樹條件，還可寫成if(root)if(root) if(!root-lchild&!root-rchild) /是葉子結點則統(tǒng)計并打印是葉子結點則統(tǒng)計并打印 sum+; printf(%dn,root-data);

10、DLR(root-lchild); /遞歸遍歷左子樹，直到葉子處；遞歸遍歷左子樹，直到葉子處； DLR(root-rchild); /遞歸遍歷右子樹，直到葉子處；遞歸遍歷右子樹，直到葉子處； return(0); 19注：要實現(xiàn)遍歷運算必須先把二叉樹存入機內(nèi)。注：要實現(xiàn)遍歷運算必須先把二叉樹存入機內(nèi)。思路：思路：利用利用前序前序遍歷來建樹遍歷來建樹 （結點值陸續(xù)從鍵盤輸入，用（結點值陸續(xù)從鍵盤輸入，用DLR為宜為宜）Bintree createBTpre( ) Bintree T; char ch;scanf(“%c”,&ch);if(ch=)T=NULL; elseT=( Bintr

11、ee )malloc(sizeof(BinTNode);T-data=ch;T-lchild=createBTpre();T-rchild=createBTpre(); return T;怎樣建樹？見教材怎樣建樹？見教材P131P131程序。程序。20習題討論：習題討論： 算法思路：算法思路：只查各結點后繼鏈表指針，若左只查各結點后繼鏈表指針，若左( (右右) )孩子的左孩子的左( (右右) )指針非空，則層次數(shù)加指針非空，則層次數(shù)加1 1；否則函數(shù)返回。；否則函數(shù)返回。技巧：技巧：遞歸時應當遞歸時應當從葉子開始向上計數(shù)，層深者保留。從葉子開始向上計數(shù)，層深者保留。否則否則不易確定層數(shù)。不易確

12、定層數(shù)。 算法思路：算法思路：既然要求從上到下，從左到右，則既然要求從上到下，從左到右，則利用隊列利用隊列存放存放各子樹結點的指針是個好辦法，而不必拘泥于遞歸算法。各子樹結點的指針是個好辦法，而不必拘泥于遞歸算法。技巧：技巧：當根結點入隊后，令其左、右孩子結點入隊，而左孩當根結點入隊后，令其左、右孩子結點入隊，而左孩子出隊時又令它的左右孩子結點入隊，子出隊時又令它的左右孩子結點入隊，由此便可產(chǎn)生按由此便可產(chǎn)生按層次輸出的效果。層次輸出的效果。 A B CD E21算法思路：算法思路：若不用遞歸，則要實現(xiàn)二叉樹遍歷的若不用遞歸，則要實現(xiàn)二叉樹遍歷的“嵌套嵌套”規(guī)規(guī)則，必用堆棧。可直接用則，必用堆

13、棧?？芍苯佑脀hilewhile語句和語句和push/poppush/pop操作。操作。參見教參見教材材P130-131P130-131程序。程序。 算法思路：算法思路：完全二叉樹的特點是：沒有左子樹空而右子樹單完全二叉樹的特點是：沒有左子樹空而右子樹單獨存在的情況獨存在的情況( (前前k-1k-1層都是滿的，且第層都是滿的，且第k k層左邊也滿）層左邊也滿）。技巧技巧: :按層序遍歷方式，先把所有結點按層序遍歷方式，先把所有結點（不管當前結點是否有（不管當前結點是否有左右孩子）左右孩子）都入隊列都入隊列. .若為完全二叉樹若為完全二叉樹, ,則層序遍歷時得到的則層序遍歷時得到的肯定是一個連續(xù)

14、的不包含空指針的序列肯定是一個連續(xù)的不包含空指針的序列. .如果序列中出現(xiàn)了空如果序列中出現(xiàn)了空指針，則說明不是完全二叉樹。指針，則說明不是完全二叉樹。22【嚴題集【嚴題集6.31】 證明：由一棵二叉樹的先序序列和中序證明：由一棵二叉樹的先序序列和中序序列可唯一確定這棵二叉樹。序列可唯一確定這棵二叉樹。 例：例：已知一棵二叉樹的已知一棵二叉樹的中序序列中序序列和和后序序列后序序列分別是分別是BDCEAFHG 和和 DECBHGFA，請畫出這棵二叉樹。，請畫出這棵二叉樹。分析：分析：由后序遍歷特征，根結點必在后序序列尾部由后序遍歷特征，根結點必在后序序列尾部（即（即A A）；由中序遍歷特征，根結

15、點必在其中間，而且其左部必全部是由中序遍歷特征，根結點必在其中間，而且其左部必全部是左子樹子孫左子樹子孫（即（即BDCEBDCE），其右部必全部是右子樹子孫，其右部必全部是右子樹子孫（即（即FHGFHG）；繼而，根據(jù)后序中的繼而，根據(jù)后序中的DECBDECB子樹可確定子樹可確定B B為為A A的左孩子，根據(jù)的左孩子，根據(jù)HGFHGF子串可確定子串可確定F F為為A A的右孩子；以此類推。的右孩子；以此類推。23中序遍歷：中序遍歷：B D C E A F H G后序遍歷：后序遍歷：D E C B H G F A（B D C E）（ F H G）ABF （D C E） （ H G）CD EGHAB

16、BFF24問：問：用二叉鏈表法（用二叉鏈表法（l_child, r_child）存儲包含）存儲包含n個結點的個結點的二叉樹，結點的指針區(qū)域中會有多少個空指針？二叉樹，結點的指針區(qū)域中會有多少個空指針？分析：分析：用二叉鏈表存儲包含用二叉鏈表存儲包含n n個結點的二叉樹，結點必有個結點的二叉樹，結點必有2n個鏈域個鏈域（見二叉鏈表數(shù)據(jù)類型說明）（見二叉鏈表數(shù)據(jù)類型說明）。除根結點外，二叉樹中每一個結點除根結點外，二叉樹中每一個結點有且僅有一個雙親有且僅有一個雙親（直接前驅），所以只會有（直接前驅），所以只會有n n1 1個結點的鏈域存放指針，指個結點的鏈域存放指針，指向非空子女結點（即直接后繼）

17、。向非空子女結點（即直接后繼）。思考：思考：二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？有用的信息或線索？我們可以用它來存放當前結點的直接前驅和后繼等線索，我們可以用它來存放當前結點的直接前驅和后繼等線索，以加快查找速度。以加快查找速度。所以，所以， 空指針數(shù)目空指針數(shù)目2n(n-1)=n+1個個。n+125二、線索二叉樹線索二叉樹（Threaded Binary Tree）普通二叉樹只能找到結點的左右孩子信息，普通二叉樹只能找到結點的左右孩子信息，而該結點的而該結點的直接前驅和直接后繼只能在遍歷過程中獲得。直接前驅和直接后繼只

18、能在遍歷過程中獲得。若將若將遍歷后對應的有關前驅和后繼預存遍歷后對應的有關前驅和后繼預存起來，則從起來，則從第一第一個結點個結點開始就能很快開始就能很快“順藤摸瓜順藤摸瓜”而遍歷整個樹了。而遍歷整個樹了。兩種解決方法兩種解決方法增加兩個域：增加兩個域：fwd和和bwd；利用空鏈域（利用空鏈域（n+1個空鏈域）個空鏈域）存放前驅指針存放前驅指針存放后繼指針存放后繼指針如何預存這類信息？如何預存這類信息？例如中序遍歷結果：例如中序遍歷結果：B D C E A F H GB D C E A F H G，實際上，實際上已將二叉已將二叉樹轉為線性排列，顯然具有唯一前驅和唯一后繼！樹轉為線性排列，顯然具有

19、唯一前驅和唯一后繼！可能是根、或最左（右）葉子可能是根、或最左（右）葉子26規(guī)規(guī) 定：定：1）若結點有左子樹，則）若結點有左子樹，則lchild指向其左孩子；指向其左孩子； 否則，否則， lchild指向其直接前驅指向其直接前驅(即線索即線索)；2）若結點有右子樹，則）若結點有右子樹，則rchild指向其右孩子；指向其右孩子； 否則，否則， rchild指向其直接后繼指向其直接后繼(即線索即線索) 。為了避免混淆，增加兩個標志域為了避免混淆，增加兩個標志域，如下圖所示：，如下圖所示：lchildLTagdataRTag rchild約定約定:當當Tag域為域為0時時,表示表示正常正常情況情況;

20、當當Tag域為域為1時時,表示表示線索線索情況情況.27有關線索二叉樹的幾個術語：有關線索二叉樹的幾個術語： 線索鏈表：線索鏈表：用前頁結點結構所構成的二叉鏈表用前頁結點結構所構成的二叉鏈表 線線 索：索：指向結點前驅和后繼的指針指向結點前驅和后繼的指針線索二叉樹：線索二叉樹：加上線索的二叉樹加上線索的二叉樹（圖形式樣）（圖形式樣） 線線 索索 化：化：對二叉樹以對二叉樹以某種次序遍歷某種次序遍歷使其變?yōu)榫€使其變?yōu)榫€索二叉樹的過程索二叉樹的過程注：注：在線索化二叉樹中，并不是每個結點都能直在線索化二叉樹中，并不是每個結點都能直接找到其后繼的，接找到其后繼的，當標志為當標志為0時，則需要通過一時

21、，則需要通過一定運算才能找到它的后繼定運算才能找到它的后繼。28dataAGEIDJHCFBltag0011110101rtag0001010111AGEIDJHCFB例例1：帶了帶了兩個標志兩個標志的某的某先序遍歷先序遍歷結果如表所示，請畫結果如表所示，請畫出對應二叉樹。出對應二叉樹。29ABCGEIDHFroot懸空？懸空？懸空？懸空？解：解：該二叉樹中序遍歷結果為該二叉樹中序遍歷結果為: : H, D, I, B, E, A, F, C, G所以添加線索應當按如下路徑進行：所以添加線索應當按如下路徑進行：例例2 2：畫出以下二叉樹對應的畫出以下二叉樹對應的中序中序線索二叉樹。線索二叉樹。

22、為避免懸空為避免懸空態(tài)，應增設態(tài)，應增設一個頭結點一個頭結點30對應的中序線索二叉樹存儲結構如圖所示：對應的中序線索二叉樹存儲結構如圖所示：00A00C00B11E11F11G00D11I11H注：此圖中序遍歷結果為注：此圖中序遍歷結果為: : H, D, I, B, E, A, F, C, G0-root0314.【 2000年計算機系考研題】年計算機系考研題】給定如圖所示二叉給定如圖所示二叉樹樹T T，請畫出與其對應的中序線索二叉樹。，請畫出與其對應的中序線索二叉樹。 2825405560330854解解: :因為中序遍歷序列是：因為中序遍歷序列是：5555 40 25 60 40 25 60 2828 08 33 08 33 5454對應線索樹應當按此規(guī)律連線，即對應線索樹應當按此規(guī)律連線，即在原二叉樹中添加虛線。在原二叉樹中添加虛線。NILNILNILNIL