第6章樹和二叉樹C

1、1具體內容：先生成一棵二叉樹，再用中序遍歷方式打印每個具體內容：先生成一棵二叉樹，再用中序遍歷方式打印每個結點值，并統(tǒng)計其葉子結點的個數結點值，并統(tǒng)計其葉子結點的個數。具體內容：先生成一棵哈夫曼樹，再打印各字符對應的哈夫具體內容：先生成一棵哈夫曼樹，再打印各字符對應的哈夫曼編碼。曼編碼。具體內容：參見嚴題集具體內容：參見嚴題集P149 實習實習5.2要求，或參見自測卷要求，或參見自測卷（三個方案由易到難，可自選，參見自測題集（三個方案由易到難，可自選，參見自測題集實驗二實驗二資料）資料）2喻信課堂網址：喻信課堂網址：8:8000/海豚之家網址：海豚之家網址：

2、3第第6 6章章 樹和二叉樹樹和二叉樹（Tree & Binary Tree）6.1 樹的基本概念樹的基本概念6.2 二叉樹二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 樹和森林樹和森林6.5 赫夫曼樹及其應用赫夫曼樹及其應用二叉樹的運算二叉樹的運算46.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.3.1 遍歷二叉樹遍歷二叉樹遍歷遍歷指按某條搜索路線遍訪每個結點且不重復。指按某條搜索路線遍訪每個結點且不重復。常用的有常用的有先序、中序和后序遍歷先序、中序和后序遍歷，還有，還有層次層次遍歷。遍歷。Traversing Binary Tree6.3.2 線索二叉

3、樹線索二叉樹用二叉鏈表法存儲包含用二叉鏈表法存儲包含n n個結點的二叉樹，結點的指針區(qū)域中個結點的二叉樹，結點的指針區(qū)域中會有會有n+1n+1個空指針。個空指針?？梢杂盟鼇砜梢杂盟鼇泶娣女斍敖Y點的直接前驅和后繼存放當前結點的直接前驅和后繼等線索，以加快查等線索，以加快查找速度。找速度。Threaded Binary Tree5例：例：【 20002000年計算機系考研題】年計算機系考研題】給定如圖所示二叉給定如圖所示二叉樹樹T T，請畫出與其對應的中序線索二叉樹。，請畫出與其對應的中序線索二叉樹。 2825405560330854解解: :因為中序遍歷序列是：因為中序遍歷序列是：5555 40

4、 25 60 40 25 60 2828 08 33 08 33 5454對應線索樹應當按此規(guī)律連線，即對應線索樹應當按此規(guī)律連線，即在原二叉樹中添加虛線。在原二叉樹中添加虛線。NILNILNILNILNILNIL和和NULLNULL的值都是的值都是0,0,區(qū)別何在？區(qū)別何在？ 在在DelphiDelphi中中NILNIL用來標用來標記空指針記空指針，NullNull用來表用來表示空的示空的VariantVariant型變量型變量或是或是ASCIIASCII碼為碼為0 0的字符，的字符，比如用于標記字符串結比如用于標記字符串結束。束。在在C/C+C/C+中定義的宏中定義的宏NULLNULL不加

5、區(qū)別的包括了不加區(qū)別的包括了以上兩種含義。以上兩種含義?？梢娍梢奜bject PascalObject Pascal的的語法要比語法要比C/C+C/C+嚴謹得嚴謹得多多6線索二叉樹的生成線索二叉樹的生成（遞歸算法見教材（遞歸算法見教材P134-135P134-135）設計技巧：設計技巧：依某種順序依某種順序遍歷二叉樹，對每個結點遍歷二叉樹，對每個結點p，判斷其左指，判斷其左指針是否為空，以及其針是否為空，以及其前驅結點的前驅結點的右指針是否為空。右指針是否為空。每次只修改每次只修改前驅結點的右指針前驅結點的右指針（后繼）和（后繼）和本結點的左指針本結點的左指針（前（前驅）驅），參見算法，參見算

6、法6.6。線索二叉樹的遍歷線索二叉樹的遍歷（無需堆棧）（無需堆棧）難點：難點：在線索化二叉樹中，并不是每個結點都能在線索化二叉樹中，并不是每個結點都能直接找到其后繼的，直接找到其后繼的，當標志為當標志為0 0時，則需要通過一時，則需要通過一定運算才能找到它的后繼。定運算才能找到它的后繼。76.4 樹和森林6.4.1 樹和森林與二叉樹的轉換樹和森林與二叉樹的轉換6.4.2 樹和森林的存儲方式樹和森林的存儲方式6.4.3 樹和森林的遍歷樹和森林的遍歷86.4.1 6.4.1 樹和森林與二叉樹的轉換樹和森林與二叉樹的轉換轉換步驟：轉換步驟：step1: step1: 將樹中同一結點的兄弟相連將樹中同

7、一結點的兄弟相連; ;加線加線抹線抹線旋轉旋轉討論討論1 1：樹如何轉為二叉樹？：樹如何轉為二叉樹？孩子孩子兄弟兄弟表示法表示法step2: step2: 保留結點的最左孩子連線，保留結點的最左孩子連線，刪除其它孩子連線；刪除其它孩子連線；step3: step3: 將同一孩子的連線繞左孩子將同一孩子的連線繞左孩子旋轉旋轉4545度角。度角。9方法：方法：加加線線抹線抹線旋轉旋轉 abeidfhgc樹轉二叉樹舉樹轉二叉樹舉例例：abeidfhgc兄弟相連兄弟相連長兄為父長兄為父孩子靠左孩子靠左10討論討論2 2：二叉樹怎樣還原為樹？：二叉樹怎樣還原為樹？abeidfhgc要點：要點：逆操作，把

8、逆操作，把所有右孩子變?yōu)樾值芩杏液⒆幼優(yōu)樾值埽?abdefhgic11法一：法一： 各森林先各自轉為二叉樹；各森林先各自轉為二叉樹； 依次連到前一個二叉樹的右子樹上。依次連到前一個二叉樹的右子樹上。討論討論3 3：森林如何轉為二叉樹？：森林如何轉為二叉樹？即即F=TF=T1 1, T, T2 2, , ,T,Tm m B=root, LB, RB B=root, LB, RB法二：法二：森林直接變兄弟，再轉為二叉樹森林直接變兄弟，再轉為二叉樹（參見教材（參見教材P138P138圖圖6.176.17，兩種方法都有轉換示意圖），兩種方法都有轉換示意圖）法一和法二得到的二叉樹是完法一和法二得到的二

9、叉樹是完全相同的、惟一的。全相同的、惟一的。12ABCDEFGHJIABCDEFGHJIBCDEFGHJI森林轉二叉樹舉例：森林轉二叉樹舉例：（用法二，森林直接變兄弟，再轉為二叉樹）（用法二，森林直接變兄弟，再轉為二叉樹）兄弟相連兄弟相連 長兄為父長兄為父頭樹為根頭樹為根 孩子靠左孩子靠左13BCDEFGHJI討論討論4 4：二叉樹如何還原為森林？：二叉樹如何還原為森林？要點：要點：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值馨炎钣疫叺淖訕渥優(yōu)樯郑溆嘤易訕渥優(yōu)樾值?即即B=root, LB, RB F=TB=root, LB, RB F=T1 1, T, T2 2, , ,T,Tm m AB

10、CDEFGHJIEFABCDGHJI146.4.2 6.4.2 樹和森林的存儲方式樹和森林的存儲方式樹有三種常用存儲方式：樹有三種常用存儲方式：雙親表示法雙親表示法 孩子表示法孩子表示法 孩子孩子兄弟表示法兄弟表示法 nextsiblingdatafirstchild指向左孩子指向左孩子指向右兄弟指向右兄弟問：問：樹樹二叉樹的二叉樹的“連線連線抹線抹線旋轉旋轉” ” 如何由計算機自動實如何由計算機自動實現？現？答：答：用用“左孩子右兄弟左孩子右兄弟”表示法來存儲即可。表示法來存儲即可。 15abecdfhgbacedfgh例如例如：166.4.3 6.4.3 樹和森林的遍歷樹和森林的遍歷例如：

11、例如：abdec先根序列：先根序列：后根序列：后根序列：a b c d eb d c e a深度優(yōu)先遍歷深度優(yōu)先遍歷（先根、后根）（先根、后根）廣度優(yōu)先遍歷廣度優(yōu)先遍歷（層次）（層次）先根遍歷先根遍歷訪問根結點；訪問根結點；依次先根遍歷根結點依次先根遍歷根結點的每棵子樹。的每棵子樹。后根遍歷后根遍歷 依次后根遍歷根結點的每依次后根遍歷根結點的每棵子樹；棵子樹； 訪問根結點。訪問根結點。樹沒有中序遍歷（因樹沒有中序遍歷（因子樹不分左右）子樹不分左右）17討論：樹若采用討論：樹若采用“先轉換，后遍歷先轉換，后遍歷”方式，結果是否一樣？方式，結果是否一樣？abdec先序遍歷：先序遍歷：后序遍歷：后序

12、遍歷：中序遍歷：中序遍歷：d e c b aabdeca b c d eb d c e a1. 樹的先根遍歷與二叉樹的樹的先根遍歷與二叉樹的先序先序遍歷相同；遍歷相同； 2. 樹的樹的后根后根遍歷相當于二叉樹的遍歷相當于二叉樹的中序中序遍歷；遍歷；3. 樹沒有中序遍歷，因為子樹無左右之分。樹沒有中序遍歷，因為子樹無左右之分。結論：結論：樹的先根序列：樹的先根序列：a b c d e樹的后根序列：樹的后根序列：b d c e a18先根遍歷先根遍歷若森林為空，返回；若森林為空，返回；訪問森林中第一棵樹的根結點；訪問森林中第一棵樹的根結點；先根遍歷第一棵樹的根結點的子樹森林；先根遍歷第一棵樹的根結

13、點的子樹森林；先根遍歷除去第一棵樹之后剩余的樹構成的森林。先根遍歷除去第一棵樹之后剩余的樹構成的森林。森林的遍歷森林的遍歷ABCDEFGHJI為何有中為何有中序？序？深度優(yōu)先遍歷深度優(yōu)先遍歷（先根、中根、（先根、中根、后根后根）廣度優(yōu)先遍歷廣度優(yōu)先遍歷（層次）（層次）中根遍歷中根遍歷若森林為空，返回；若森林為空，返回；中根遍歷森林中第一棵樹的根結點的子樹森林；中根遍歷森林中第一棵樹的根結點的子樹森林；訪問第一棵樹的根結點；訪問第一棵樹的根結點；中根遍歷除去第一棵樹之后剩余的樹構成的森林。中根遍歷除去第一棵樹之后剩余的樹構成的森林。19討論：討論：若采用若采用“先轉換，后遍歷先轉換，后遍歷”方式

14、，結果是否相同？方式，結果是否相同？例如：例如：先根序列：先根序列：中根序列：中根序列：A B C D E F G H I JB C D A F E H J I G先序序列：先序序列：中序序列：中序序列：A B C D E F G H I JB C D A F E H J I G結論：結論：森林的先根和中根遍歷在森林的先根和中根遍歷在兩種方式下的結果相同。兩種方式下的結果相同。但森林的后根遍歷則不一定，因而少用但森林的后根遍歷則不一定，因而少用20 算法思路：算法思路：既然要求從上到下，從左到右，則既然要求從上到下，從左到右，則存放各子存放各子樹結點的指針是個好辦法，此時樹結點的指針是個好辦法

15、，此時絕不能用遞歸絕不能用遞歸算法。算法。技巧：技巧：當根結點入隊后，令其左、右孩子結點入隊，而左孩子出當根結點入隊后，令其左、右孩子結點入隊，而左孩子出隊時又令它的左右孩子結點入隊，隊時又令它的左右孩子結點入隊，由此便可產生按層次輸出由此便可產生按層次輸出的效果。的效果。 算法思路：算法思路：只查各結點后繼鏈表指針，若左只查各結點后繼鏈表指針，若左( (右右) )孩子的左孩子的左( (右右) )指針非空，則層次數加指針非空，則層次數加1 1；否則函數返回。；否則函數返回。 A B CD E算法見附算法見附1算法見附算法見附221算法思路：算法思路：若不用遞歸，則要實現二叉樹遍歷的若不用遞歸，

16、則要實現二叉樹遍歷的“嵌套嵌套”規(guī)規(guī)則，必用堆棧則，必用堆棧 ?？芍苯佑?。可直接用whilewhile語句和語句和push/poppush/pop操作。操作。參見教材參見教材P130-131P130-131程序。程序。算法思路：算法思路：完全二叉樹的特點是：沒有左子樹空而右子樹單獨完全二叉樹的特點是：沒有左子樹空而右子樹單獨存在的情況存在的情況( (前前k-1k-1層都是滿的，且第層都是滿的，且第k k層左邊也滿）層左邊也滿）。技巧技巧: :按按層次遍歷層次遍歷方式，先把方式，先把所有所有結點（不管當前結點是否有左結點（不管當前結點是否有左右孩子）右孩子）都入隊列都入隊列. .若為完全二叉樹若

17、為完全二叉樹, ,則層次遍歷時得到的肯定則層次遍歷時得到的肯定是一個連續(xù)的不包含空指針的序列是一個連續(xù)的不包含空指針的序列. .如果序列中出現了空指針，如果序列中出現了空指針，則說明不是完全二叉樹。則說明不是完全二叉樹。算法見附算法見附3算法見附算法見附422Void ABC(Bitree p, int l, int &h) if pNIL then l=l+1; if lh then h=l; ABC(p-Lchild, l, h); ABC(p-Rchild, l, h); 法法1 1：從根開始向下計算層次：從根開始向下計算層次( (比從葉子往上計算更簡單比從葉子往上計算更簡單) )l、h

18、分別表示二叉樹的層次分別表示二叉樹的層次數和深度。數和深度。想一想，想一想，l和和h的初始值應設的初始值應設為多少？為多少？開始調用時，應當用開始調用時，應當用ABC（p, 0, 0）若去掉若去掉h形參中的形參中的“&”號，則號，則h不不變化，算出的更深層數不能正確變化，算出的更深層數不能正確返回返回, h將永遠為將永遠為 0。23int BTreeDepth(Btree *BT) /*BT為二叉樹某結點的指針為二叉樹某結點的指針 int leftdep, rightdep; /設左右兩個深度設左右兩個深度/層次計數器層次計數器if(BT=NULL) return(0); /當前結點指針為空則

19、立即返回當前結點指針為空則立即返回else leftdep= BTreeDepth(BT-left); /遍歷當前結點左子樹遍歷當前結點左子樹 rightdep=BTreeDepth(BT-right); /遍歷當前結點右子樹遍歷當前結點右子樹 if( leftdeprightdep)return(leftdep+1); /從葉子起計數從葉子起計數 else return(rightdep+1); /BTreeDepth法法2 2：遞歸時從葉子開始向上計數，層深者保留。：遞歸時從葉子開始向上計數，層深者保留。24void void LayerOrderLayerOrder(Bitree(Bit

20、ree T) T) /層序遍歷二叉樹層序遍歷二叉樹 InitQueueInitQueue(Q); (Q); /建一個空隊（初始化隊列）建一個空隊（初始化隊列） EnQueueEnQueue(Q,T); (Q,T); /將一個結點插入隊尾的函數將一個結點插入隊尾的函數 whilewhile( ( !QueueEmpty!QueueEmpty(Q)(Q) ) ) DeQueue DeQueue(Q, &p); (Q, &p); /隊首結點出隊隊首結點出隊( (送入送入p)p) visit(p); visit(p); if(p-lchild) EnQueue(Q,p-lchild if(p-lchi

21、ld) EnQueue(Q,p-lchild); ); /p/p的左孩子入隊的左孩子入隊 if(p-rchild) EnQueue(Q,p-rchildif(p-rchild) EnQueue(Q,p-rchild); ); /p/p的右孩子入隊的右孩子入隊 /LayerOrder/LayerOrder 當孩子為空時不要當孩子為空時不要將空指針入隊將空指針入隊25int int IsFull_BitreeIsFull_Bitree(Bitree(Bitree T) T)/是完全二叉樹返回是完全二叉樹返回1 1, ,否則返否則返0 0 InitQueueInitQueue(Q); (Q); /建

22、隊（初始化隊列）建隊（初始化隊列） flag=flag=0 0; ; /標志初始化標志初始化 EnQueueEnQueue(Q,T); (Q,T); /結點結點T T入隊（入隊（空指針也要入隊空指針也要入隊） whilewhile(!QueueEmpty(!QueueEmpty(Q)(Q) DeQueueDeQueue(Q,&p); (Q,&p); /隊首結點出隊隊首結點出隊( (送入送入p)p) if(!p) if(!p) flag=1flag=1; ; /隊首結點為空則標志變，但也許是隊尾隊首結點為空則標志變，但也許是隊尾 else if(flag)return else if(flag)return 0 0; ; /下一輪才能確定是不是完全二叉樹下一輪才能確定是不是完全二叉樹 elseelse EnQueue(Q,p-lchild EnQueue(Q,p-lchild); ); /不管孩子是否為空不管孩子是否為空, ,都入隊列都入隊列 EnQ