1、目 錄1 教教 學學 內內 容容 1 1、樹和森林的概念、樹和森林的概念2 2、二叉樹的定義、性質及運算；、二叉樹的定義、性質及運算； 3 3、二叉樹的存儲結構、二叉樹的存儲結構 4 4、遍歷二叉樹、遍歷二叉樹5 5、線索二叉樹、線索二叉樹6 6、樹、森林、森林與二叉樹的轉換、樹、森林、森林與二叉樹的轉換7 7、哈夫曼樹、哈夫曼編碼、哈夫曼樹、哈夫曼編碼 26.4 二叉樹的遍歷二叉樹的遍歷3 遍歷概念遍歷概念 順著某一條搜索路徑順著某一條搜索路徑巡訪巡訪二叉樹中的結點，使二叉樹中的結點，使 得每個結點得每個結點均被訪問一次均被訪問一次，而且，而且僅被訪問一次僅被訪問一次?！啊钡暮x很廣，可以是

2、對結點作各種處的含義很廣，可以是對結點作各種處理，如：輸出結點的信息、修改結點的數據值理，如：輸出結點的信息、修改結點的數據值等，但要求這種訪問等，但要求這種訪問。 4 遍歷方法遍歷方法 依次遍歷二叉樹中的三依次遍歷二叉樹中的三個組成個組成 部分，便是遍歷部分，便是遍歷了整個二叉樹了整個二叉樹 假設：假設：L：遍歷左子樹：遍歷左子樹 v：訪問根結點：訪問根結點 R：遍：遍歷右子樹歷右子樹,則遍歷整個二叉樹方案共有：則遍歷整個二叉樹方案共有： 遍歷目的遍歷目的 得到樹中所有結點的一個得到樹中所有結點的一個線性線性排列。排列。 根結點根結點 左子樹左子樹 右子樹右子樹 vLR、LvR、LRv 、

3、vRL、RvL、RLv 六種。六種。 5 根結點根結點 左子樹左子樹 右子樹右子樹 67ADBCV L RAV L RV L RBDCV L R先序遍歷序列：先序遍歷序列：A B D CA B D C7遍歷遍歷 (VLR)(VLR)二叉樹的操作定義：二叉樹的操作定義： 若二叉樹為空，則空操作；否則若二叉樹為空，則空操作；否則 (1) 訪問根結點；訪問根結點； (2) 前序遍歷左子樹；前序遍歷左子樹； (3) 前序遍歷右子樹。前序遍歷右子樹。 遍歷二叉樹的操作定義：遍歷二叉樹的操作定義： 若二叉樹為空，則空操作；否則若二叉樹為空，則空操作；否則 (1) 訪問根結點；訪問根結點； (2) 前序遍歷

4、左子樹；前序遍歷左子樹； (3) 前序遍歷右子樹。前序遍歷右子樹。 先序遍歷結果：先序遍歷結果：A B E L D H M I J A B D E LH M I J 89ADBCL V RBL V RL V RADCL V R中序遍歷序列：中序遍歷序列：B D A CB D A C遍歷二叉樹的操作定義：遍歷二叉樹的操作定義： 若二叉樹為空，則空操作；否則若二叉樹為空，則空操作；否則 (1) 中序遍歷左子樹；中序遍歷左子樹； (2) 訪問根結點；訪問根結點； (3) 中序遍歷右子樹。中序遍歷右子樹。 遍歷二叉樹的操作定義：遍歷二叉樹的操作定義： 若二叉樹為空，則空操作；否則若二叉樹為空，則空操作

5、；否則 (1) 中序遍歷左子樹；中序遍歷左子樹； (2) 訪問根結點；訪問根結點； (3) 中序遍歷右子樹。中序遍歷右子樹。 E L B A M H I D J A B D E LH M I J 1011ADBC L R VL R VL R VADCL R V后序遍歷序列后序遍歷序列: : D B C AD B C AB遍歷二叉樹的操作定義：遍歷二叉樹的操作定義： 若二叉樹為空，則空操作；否則若二叉樹為空，則空操作；否則 (1) 后序遍歷左子樹；后序遍歷左子樹； (2) 后序遍歷右子樹；后序遍歷右子樹； (3) 訪問根結點。訪問根結點。 遍歷二叉樹的操作定義：遍歷二叉樹的操作定義： 若二叉樹為

6、空，則空操作；否則若二叉樹為空，則空操作；否則 (1) 后序遍歷左子樹；后序遍歷左子樹； (2) 后序遍歷右子樹；后序遍歷右子樹； (3) 訪問根結點。訪問根結點。 L E B M I H J D A A B D E LH M I J 12分析表達式和二叉樹的關系分析表達式和二叉樹的關系13以二叉樹表示表達式的遞歸定義如下：若表達式為一個數（或簡單變量），則對應的二叉樹中僅有一個根結點，其數據域存放該表達式的信息；若表達式形如“（第一操作數）（運算符）（第二操作數）”，則對應的二叉樹以左子樹表示第一操作數，右子樹表示第二操作數，根結點的數據域存放運算符（若為一元運算符，則左子樹為空）。操作數本

7、身又為表達式。a+bab+abc+(a+b)c(a+b)c d/e d/ea+bc 分析表達式和二叉樹的關系分析表達式和二叉樹的關系abc+abcde- -+/14遍歷結果：遍歷結果： 前序：前序： - - + ab - - c d / e f 中序：中序： a + bc - - d - - e / f 后序：后序： a b c d - -+ e f / - - 表達式的表達式的前綴表示前綴表示表達式的表達式的中綴表示中綴表示 表達式的表達式的后綴表示后綴表示15層次遍歷層次遍歷(Levelorder Traversal)16LDR(node *root)if(root !=NULL) LDR

8、(root-lchild); printf(“%d”,root-data); LDR(root-rchild); return(0);LRD (node *root)if(root !=NULL) LRD(root-lchild); LRD(root-rchild); printf(“%d”,root-data); return(0);typedef struct nodeint data; struct node *lchild,*rchild； node;node *root; A B CD EDLR( node *root )if (root !=NULL) /非空二叉樹 printf(

9、“%d”,root-data); /訪問DDLR(root-lchild); /遞歸遍歷左子樹DLR(root-rchild); /遞歸遍歷右子樹 return(0); 17對于非遞歸算法，引入棧模擬遞歸過程，初始時棧為空。問題是如何利用棧來保存信息，使得在前序遍歷節點t的左子樹后，能利用棧頂信息獲取節點t的右子樹的根指針？方法是訪問tdata后，將t入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為t，出棧，再先序遍歷t的右子樹。1）建立棧stack, 初始時棧為空2）t指向根3）當 t不為空時，或棧stack不空時，重復：若t不空，訪問tdata后，將t入棧；t指向其左子女；否則：棧頂元素

10、出棧；t指向其右子女4）結束18A B C D EF H I G J 訪問A, A進棧，t指向B 棧A訪問B, B進棧，t指向D 棧AB訪問D, D進棧，t為空棧ABDD出棧，t為空棧ABB出棧，t指向E 棧A訪問E, E進棧，t指向H 棧AE訪問H，H進棧，t為空棧AEHH出棧，t指向J棧AE訪問J， J進棧， t為空棧AEJJ出棧， t為空棧AEE出棧，t為空棧AA出棧，t指向C 棧為空訪問C，C進棧，t指向F 棧C訪問F，F進棧，t為空棧CFF出棧，t指向I棧C訪問I， I進棧，t為空棧CII出棧，t為空棧CC出棧，t指向G 棧為空訪問G，G進棧，t為空棧GG出棧，t為空棧為空191）建

11、立棧stack, 初始時棧為空2）t指向根3）當 t不為空時，或棧stack不空時，重復： 若t不空，訪問tdata后，將t入棧； t指向其左子女； 否則：棧頂元素出棧； t指向其右子女4）結束/ 二叉樹節點定義二叉樹節點定義typedef struct node datatype data; struct node *lchild, *rchild bintnode;typedef bintnode *bintree;/ 棧結構定義棧結構定義typedef struct stack bintree data100; int top; /棧頂指針seqstack;/ 進棧函數進棧函數void

12、push(seqstack *s, bintree t) sdata+stop=t;/ 出棧函數出棧函數bintree pop(seqstack *s) if (stop !=-1) stop-; return (sdatastop+1); else return NULL;20/ 非遞歸實現二叉樹的前序遍歷非遞歸實現二叉樹的前序遍歷void preorder1(bintree t) seqstack s; s.top = -1; / 當前處理的子樹不為空或棧不為空則循環 while ( (t) | (s.top !=-1) ) while (t) printf(“%f”, tdata); s

13、.top+; s.datas.top = t; t = tlchild; /endwhile if (s.top-1) t = pop(&s); t = trchild; /endif /endwhile/end preorder121二叉樹的重建二叉樹的重建由二叉樹的由二叉樹的前序前序序列和序列和中序中序序列序列可以可以唯唯一地確定一棵二叉樹一地確定一棵二叉樹由二叉樹的由二叉樹的后序后序序列和序列和中序中序序列序列可以可以唯唯一地確定一棵二叉樹一地確定一棵二叉樹由二叉樹的由二叉樹的前序前序序列和序列和后序后序序列序列不可不可唯唯一地確定一棵二叉樹一地確定一棵二叉樹22僅知二叉樹的前序

14、序列僅知二叉樹的前序序列“abcdefg” 不不能唯一確定一棵二叉樹，能唯一確定一棵二叉樹， 如果同時已知如果同時已知二叉樹的中序序列二叉樹的中序序列“cbdaegf”，則會如，則會如何？何？ 由二叉樹的前序和中序序列建樹由二叉樹的前序和中序序列建樹二叉樹的前序序列二叉樹的前序序列二叉樹的中序序列二叉樹的中序序列左子樹左子樹左子樹左子樹 右子樹右子樹右子樹右子樹根根根根23a b c d e f gc b d a e g faab bccddeeffggabcdefg前序序列前序序列中序序列中序序列24前序序列前序序列 A B H F D E C K G 中序序列中序序列 H B D F A

15、E K C G 256.5 線索二叉樹線索二叉樹26所以， 空指針數目2n(n-1)=n+1個。證明：用二叉鏈表存儲包含n個結點的二叉樹，結點必有2n個鏈域（見二叉鏈表數據類型說明）。除根結點外，二叉樹中每一個結點有且僅有一個雙親，意即每個結點地址占用了雙親的一個直接后繼，n個結點地址共占用了n-1個雙親的指針域。也就是說，只會有n1個結點的鏈域存放指針。Threaded Binary Tree討論：用二叉鏈表法（l_child, r_child）存儲包含n個結點的二叉樹，結點的指針區域中會有多少個空指針？6.5 線索二叉樹線索二叉樹27結論：結論：用二叉鏈表法存儲包含用二叉鏈表法存儲包含n

16、n個結點的二叉樹，結點的指針個結點的二叉樹，結點的指針區域中會有區域中會有n+1n+1個空指針。個空指針?？梢杂盟鼇砜梢杂盟鼇泶娣女斍敖Y點的直接前驅和后繼存放當前結點的直接前驅和后繼等線索，以加快查等線索，以加快查找速度。找速度。這就是這就是的意義和用途。的意義和用途。疑問疑問1：二叉樹是二叉樹是1:2的非線性結構，如何定義其惟一的直接后繼？的非線性結構，如何定義其惟一的直接后繼？答：答：要遍歷之后才能得到，且不同遍歷算法得到的后繼也不同。要遍歷之后才能得到，且不同遍歷算法得到的后繼也不同。先依遍歷規則先依遍歷規則把每個結點對應的把每個結點對應的前驅前驅或或后繼線索后繼線索預存預存起來，這叫做

17、起來，這叫做“線索化線索化”。疑問疑問2：獲得這種：獲得這種“直接前驅直接前驅”或或“直接后繼直接后繼”有何意義？有何意義？答：答：從從任一結點任一結點出發都能快速找到其前驅和后繼，且出發都能快速找到其前驅和后繼，且不必借助堆棧不必借助堆棧疑問疑問3：如何經濟的：如何經濟的(預先預先)存放這類信息？存放這類信息？答：答：左孩子左孩子/前驅前驅復用，復用，右孩子右孩子/后繼后繼復用，后者稱之為復用，后者稱之為線索線索28lchildLTagdataRTag rchild約定:當Tag域為0時,表示正常情況;當Tag域為1時,表示線索情況.前驅(后繼)左(右)孩子為識別復用的兩種不同信息，特增加兩

18、個標志域：為識別復用的兩種不同信息，特增加兩個標志域：問：增加了前驅和后繼等線索有什么好處？能方便找出當前結點的前驅和后繼，不用堆棧（遞歸）也能遍歷整個樹。各1bit疑問4：計算機如何識別是孩子指針還是線索指針？291. 有關線索二叉樹的幾個術語：有關線索二叉樹的幾個術語： 線索鏈表： 線 索：線索二叉樹： 線 索 化：用含Tag的結點樣式所構成的二叉鏈表指向結點前驅和后繼的指針加上線索的二叉樹對二叉樹以某種次序遍歷使其變為線索二叉樹的過程線索化過程就是在遍歷過程中修改空指針的過程：線索化過程就是在遍歷過程中修改空指針的過程：將將空的空的l lchildchild改為結點的直接改為結點的直接前

19、驅前驅；將將空的空的r rchildchild改為結點的直接改為結點的直接后繼后繼。非空指針呢？仍然指向孩子結點（稱為非空指針呢？仍然指向孩子結點（稱為“正常情況正常情況”）30dataAGEIDJHCFBLtag0011110101Rtag0001010111AGEIDJHCFB例：例：帶了帶了兩個標志兩個標志的某的某先序先序遍歷結果如下表所示，遍歷結果如下表所示，請畫出對應的二叉樹。請畫出對應的二叉樹。ALtag=1表示前驅線索Rtag=1表示后繼線索31ABCGEIDHFroot懸空？ NIL懸空？ NIL解：對該二叉樹中序遍歷的結果為: H, D, I, B, E, A, F, C,

20、G所以添加線索應當按如下路徑進行：為避免懸空態，應增設一個頭結點例例1 1：畫出以下二叉樹對應的畫出以下二叉樹對應的中序中序線索二叉樹。線索二叉樹。2. 線索二叉樹的生成線索化線索化過程就是在遍歷過程中修改空指針的過程3200A00C00B11E11F11G00D11I11H注：此圖中序遍歷結果為: H, D, I, B, E, A, F, C, G0root0對應的中序線索二叉樹存儲結構如圖所示：對應的中序線索二叉樹存儲結構如圖所示：33【例例】 (2000年計算機系考研題) 給定如圖所示二叉樹給定如圖所示二叉樹T T，請畫出與其對應的中序線索二叉樹。請畫出與其對應的中序線索二叉樹。 282

21、5405560330854解解: :因為中序遍歷序列是：因為中序遍歷序列是：5555 40 25 60 40 25 60 2828 08 33 08 33 5454對應線索樹應當按此規律連線，即對應線索樹應當按此規律連線，即在原二叉樹中添加虛線。在原二叉樹中添加虛線。NILNIL34線索二叉樹的線索二叉樹的生成生成算法算法（遞歸算法見教材遞歸算法見教材P134-135）目的：目的：在遍歷二叉樹的過程中修改空指針，添加前驅或后繼在遍歷二叉樹的過程中修改空指針，添加前驅或后繼的線索，使之成為線索二叉樹。的線索，使之成為線索二叉樹。為了記下遍歷過程中訪問結點的先后次序，需要設置兩個指針：為了記下遍歷

22、過程中訪問結點的先后次序，需要設置兩個指針：p指針指針當前結點之指針；當前結點之指針；pre指針指針當前結點的前趨結點指針。當前結點的前趨結點指針。設計技巧：設計技巧：依某種順序依某種順序遍歷二叉樹，對每個結點遍歷二叉樹，對每個結點p，判斷其左指，判斷其左指針是否為空，以及其針是否為空，以及其前驅結點的前驅結點的右指針是否為空。右指針是否為空。每次只修改每次只修改前驅結點的右指針前驅結點的右指針（后繼）和（后繼）和本結點的左指針本結點的左指針（前（前驅）驅），參見算法，參見算法6.6。若若p-lchildNULL, ,則則p-Ltag=1;p-Ltag=1;p-lchildp-lchildpr

23、e;pre; /p/p的前驅線索應存的前驅線索應存p p結點的左邊結點的左邊若若pre-rchildNULL, 則則pre-Rtagpre-Rtag1;1;pre-rchild=ppre-rchild=p; /pre/pre的后繼線索應存的后繼線索應存prepre結點的右邊結點的右邊353. 3. 線索二叉樹的遍歷線索二叉樹的遍歷（無需堆棧）（無需堆棧）對于線索二叉樹的遍歷，只要找到序列中的對于線索二叉樹的遍歷，只要找到序列中的第一個第一個結結點，然后點，然后依次訪問結點的后繼依次訪問結點的后繼直到后繼為空為止。直到后繼為空為止。（因為建立線索時已遍歷一次，相當于線性化了！）（因為建立線索時已遍歷一次，相當于線性化了?。╇y點：難點：在線索化二叉樹中，并不是每個結點都能直接在線索化二叉樹中，并不是每個結點都能直接找到其后繼的，找到其后繼的，當標志為當標志為0 0時，則需要通過一定運算時，則需要通過一定運算才能找到它的后繼。才能找到它的后繼。以以中序線索二叉樹中序線索二叉樹為例：為例：當當RTag=1時，直接后繼指針就在其時，直接后繼指針就在其rchild域內；域內；當當RTag=0時，直接后繼是當前結點時