數(shù)據(jù)結(jié)構(gòu)銅陵學(xué)院課件

1、1數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容1數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容2第6章 樹和二叉樹（ Tree & Binary Tree ）6.1 樹的基本概念6.2 二叉樹6.3 遍歷二叉樹和線索二叉樹6.4 樹和森林6.5 赫夫曼樹及其應(yīng)用特點(diǎn)：非線性結(jié)構(gòu)，一個直接前驅(qū)，但可能有多個直接后繼（1：n）2第6章 樹和二叉樹（ Tree & Binary Tr36.1 樹的基本概念1. 樹的定義2 若干術(shù)語3. 邏輯結(jié)構(gòu)4.存儲結(jié)構(gòu)5. 樹的運(yùn)算36.1 樹的基本概念1. 樹的定義41. 樹的定義注1：過去許多書籍中都定義樹為n1，曾經(jīng)有“空樹不是樹”的說法，但現(xiàn)在樹的定義已修改。注2：樹的定義具有遞歸性，即樹中還有樹。由一個或

2、多個(n0)結(jié)點(diǎn)組成的有限集合T，有且僅有一個結(jié)點(diǎn)稱為根（root），當(dāng)n1時，其余的結(jié)點(diǎn)分為m(m0)個互不相交的有限集合T1,T2，Tm。每個集合本身又是棵樹，被稱作這個根的子樹 。41. 樹的定義注1：過去許多書籍中都定義樹為n1，5樹的表示法有幾種：圖形表示法嵌套集合表示法廣義表表示法目錄表示法左孩子右兄弟表示法這些表示法的示意圖參見教材P120樹的抽象數(shù)據(jù)類型定義參見教材P118-1195樹的表示法有幾種：圖形表示法這些表示法的示意圖參見教材P16圖形表示法：教師學(xué)生其他人員2011級2012級2013級2014級銅陵學(xué)院會計學(xué)院數(shù)計學(xué)院金融學(xué)院葉子根子樹6圖形表示法：教師學(xué)生其他人

3、員2011級2012級2013級7廣義表表示法( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 根作為由子樹森林組成的表的名字寫在表的左邊datalink 1link 2.link n麻煩問題：應(yīng)當(dāng)開設(shè)多少個鏈域?7廣義表表示法( A ( B ( E ( K, L ), F8左孩子右兄弟表示法ABCDEFGHIJKLM數(shù)據(jù)左孩子 右兄弟( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )8左孩子右兄弟表示法ABCDEFGHIJKLM數(shù)據(jù)左孩子 9 樹的抽象數(shù)據(jù)類型

4、定義（見教材P118-119）ADT Tree數(shù)據(jù)對象D:數(shù)據(jù)關(guān)系R:基本操作 P：ADT Tree若D為空集，則稱為空樹；/允許n=0若D中僅含一個數(shù)據(jù)元素，則R為空集；其他情況下的R存在二元關(guān)系： root 唯一 /關(guān)于根的說明 DjDk= /關(guān)于子樹不相交的說明 /關(guān)于數(shù)據(jù)元素的說明D是具有相同特性的數(shù)據(jù)元素的集合。/至少有15個9 樹的抽象數(shù)據(jù)類型定義（見教材P118-119）ADT T102. 若干術(shù)語即上層的那個結(jié)點(diǎn)(直接前驅(qū))即下層結(jié)點(diǎn)的子樹的根(直接后繼)同一雙親下的同層結(jié)點(diǎn)（孩子之間互稱兄弟）即雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親）即從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)即該結(jié)點(diǎn)下層

5、子樹中的任一結(jié)點(diǎn)ABCGEIDHFJMLK 根 葉子 森林有序樹無序樹即根結(jié)點(diǎn)(沒有前驅(qū))即終端結(jié)點(diǎn)(沒有后繼)指m棵不相交的樹的集合(例如刪除A后的子樹個數(shù))雙親孩子兄弟堂兄弟祖先子孫結(jié)點(diǎn)各子樹從左至右有序，不能互換（左為第一）結(jié)點(diǎn)各子樹可互換位置。102. 若干術(shù)語即上層的那個結(jié)點(diǎn)(直接前驅(qū))AB112. 若干術(shù)語（續(xù)）即樹的數(shù)據(jù)元素結(jié)點(diǎn)掛接的子樹數(shù)（有幾個直接后繼就是幾度，亦稱“次數(shù)”）結(jié)點(diǎn)結(jié)點(diǎn)的度結(jié)點(diǎn)的層次終端結(jié)點(diǎn)分支結(jié)點(diǎn)樹的度樹的深度(或高度)ABCGEIDHFJMLK從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）即度為0的結(jié)點(diǎn)，即葉子即度不為0的結(jié)點(diǎn)（也稱為內(nèi)部結(jié)點(diǎn)）所有結(jié)點(diǎn)度中的最大值（M

6、ax各結(jié)點(diǎn)的度）指所有結(jié)點(diǎn)中最大的層數(shù)（Max各結(jié)點(diǎn)的層次）問：右上圖中的結(jié)點(diǎn)數(shù) ；樹的度 ；樹的深度1334112. 若干術(shù)語（續(xù)）即樹的數(shù)據(jù)元素結(jié)點(diǎn)樹的度A123. 樹的邏輯結(jié)構(gòu) (特點(diǎn))： 一對多（1:n），有多個直接后繼（如家譜樹、目錄樹等等），但只有一個根結(jié)點(diǎn)，且子樹之間互不相交。 4. 樹的存儲結(jié)構(gòu) 討論1：樹是非線性結(jié)構(gòu)，該怎樣存儲？仍然有順序存儲、鏈?zhǔn)酱鎯Φ确绞健?123. 樹的邏輯結(jié)構(gòu) (特點(diǎn))： 一對多（1:n），有多個13討論3：樹的鏈?zhǔn)酱鎯Ψ桨笐?yīng)該怎樣制定？可規(guī)定為：從上至下、從左至右將樹的結(jié)點(diǎn)依次存入內(nèi)存。重大缺陷：復(fù)原困難（不能唯一復(fù)原就沒有實用價值）。討論2：樹的

7、順序存儲方案應(yīng)該怎樣制定？可用多重鏈表：一個前趨指針，n個后繼指針。細(xì)節(jié)問題：樹中結(jié)點(diǎn)的結(jié)構(gòu)類型樣式該如何設(shè)計？ 即應(yīng)該設(shè)計成“等長”還是“不等長”？缺點(diǎn)：等長結(jié)構(gòu)太浪費(fèi)（每個結(jié)點(diǎn)的度不一定相同）； 不等長結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類型）。解決思路：先研究最簡單、最有規(guī)律的樹，然后設(shè)法把一般的樹轉(zhuǎn)化為簡單樹。二叉樹13討論3：樹的鏈?zhǔn)酱鎯Ψ桨笐?yīng)該怎樣制定？可規(guī)定為：從上至下145. 樹的運(yùn)算 要明確：1. 普通樹（即多叉樹）若不轉(zhuǎn)化為二叉樹，則運(yùn)算很難實現(xiàn)。2. 二叉樹的運(yùn)算仍然是插入、刪除、修改、查找、排序等，但這些操作必須建立在對樹結(jié)點(diǎn)能夠“遍歷”的基礎(chǔ)上?。ū闅v指每個結(jié)點(diǎn)都被訪問且僅訪

8、問一次，不遺漏不重復(fù)）。本章重點(diǎn)：二叉樹的表示和實現(xiàn)145. 樹的運(yùn)算 要明確：本章重點(diǎn)：二叉樹的表示和實現(xiàn)156.2 二叉樹為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個 “叉” 的樹？二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強(qiáng)；可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹，不失一般性。1. 二叉樹的定義2. 二叉樹的性質(zhì)3. 二叉樹的存儲結(jié)構(gòu)（二叉樹的運(yùn)算見6.3節(jié)）156.2 二叉樹為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個 “叉161. 二叉樹的定義定義：是n（n0）個結(jié)點(diǎn)的有限集合，由一個根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成 。邏輯結(jié)構(gòu)： 一對二（1：2） 基本特征: 每個結(jié)點(diǎn)最多只有兩棵子樹（不存

9、在度大于2的結(jié)點(diǎn)）； 左子樹和右子樹次序不能顛倒（有序樹）?；拘螒B(tài)： 問：具有3個結(jié)點(diǎn)的二叉樹可能有幾種不同形態(tài)？普通樹呢？ 5種/2種161. 二叉樹的定義定義：是n（n0）個結(jié)點(diǎn)的有限集合，17二叉樹的抽象數(shù)據(jù)類型定義（見教材P121-122）ADT BinaryTree數(shù)據(jù)對象D:數(shù)據(jù)關(guān)系R:基本操作 P：ADT BinaryTree若D=，則R= ；若D，則R= H；存在二元關(guān)系： root 唯一 /關(guān)于根的說明 DjDk= /關(guān)于子樹不相交的說明 /關(guān)于數(shù)據(jù)元素的說明 /關(guān)于左子樹和右子樹的說明D是具有相同特性的數(shù)據(jù)元素的集合。/至少有20個17二叉樹的抽象數(shù)據(jù)類型定義（見教材P1

10、21-122）ADT182. 二叉樹的性質(zhì) (3+2)討論1：第i層的結(jié)點(diǎn)數(shù)至多是多少？ （利用二進(jìn)制性質(zhì)可輕松求出） 性質(zhì)1: 在二叉樹的第i層上至多有2i-1個結(jié)點(diǎn)（i0）。性質(zhì)2: 深度為k的二叉樹至多有2k-1個結(jié)點(diǎn)（k0）。2i-1個提問：第i層上至少有 個結(jié)點(diǎn)？1討論2：深度為k的二叉樹，至多有多少個結(jié)點(diǎn)？ （利用二進(jìn)制性質(zhì)可輕松求出）2k-1提問：深度為k時至少有 個結(jié)點(diǎn)？k182. 二叉樹的性質(zhì) (3+2)討論1：第i層的結(jié)點(diǎn)19討論3：二叉樹的葉子數(shù)和度為2的結(jié)點(diǎn)數(shù)之間有關(guān)系嗎？性質(zhì)3: 對于任何一棵二叉樹，若2度的結(jié)點(diǎn)數(shù)有n2個，則葉子數(shù)（n0）必定為n21 （即n0=n2

11、+1）證明： 二叉樹中全部結(jié)點(diǎn)數(shù)nn0+n1+n2(葉子數(shù)1度結(jié)點(diǎn)數(shù)2度結(jié)點(diǎn)數(shù))又二叉樹中全部結(jié)點(diǎn)數(shù)nB+1 ( 總分支數(shù)根結(jié)點(diǎn) ) （除根結(jié)點(diǎn)外，每個結(jié)點(diǎn)必有一個直接前趨，即一個分支）而 總分支數(shù)B= n1+2n2 (1度結(jié)點(diǎn)必有1個直接后繼，2度結(jié)點(diǎn)必有2個)三式聯(lián)立可得： n0+n1+n2= n1+2n2 +1, 即n0=n2+1實際意義：葉子數(shù)2度結(jié)點(diǎn)數(shù)1ABCGEIDHFJ19討論3：二叉樹的葉子數(shù)和度為2的結(jié)點(diǎn)數(shù)之間有關(guān)系嗎？性質(zhì)20對于兩種特殊形式的二叉樹（滿二叉樹和完全二叉樹），還特別具備以下2個性質(zhì)：性質(zhì)4: 具有n個結(jié)點(diǎn)的完全二叉樹的深度必為log2n1性質(zhì)5: 對完全二叉

12、樹，若從上至下、從左至右編號，則編號為i 的結(jié)點(diǎn)，其左孩子編號必為2i，其右孩子編號必為2i1；其雙親的編號必為i/2（i1 時為根,除外）。 證明：根據(jù)性質(zhì)2，深度為k的二叉樹最多只有2k-1個結(jié)點(diǎn)，且完全二叉樹的定義是與同深度的滿二叉樹前面編號相同，即它的總結(jié)點(diǎn)數(shù)n位于k層和k-1層滿二叉樹容量之間，即 2k-1-1n2k-1 或2k-1n2k三邊同時取對數(shù)，于是有：k-1log2n1)f=n*fact(n-1); else f=1; return(f); 33遍歷的算法實現(xiàn)：用遞歸形式格外簡單！回憶1：二叉樹結(jié)點(diǎn)的34先序遍歷算法DLR( liuyu *root )if (root !=

13、NULL) /非空二叉樹 printf(“%d”,root-data); /訪問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)

14、; return(0);結(jié)點(diǎn)數(shù)據(jù)類型自定義typedef struct liuyuint data; struct liuyu *lchild,*rchild； liuyu;liuyu *root; 34先序遍歷算法中序遍歷算法后序遍歷算法結(jié)點(diǎn)數(shù)據(jù)類型自定義35對遍歷的分析：1. 從前面的三種遍歷算法可以知道：如果將print語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的訪問路徑是相同的，只是訪問結(jié)點(diǎn)的時機(jī)不同。從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑上，每個結(jié)點(diǎn)經(jīng)過3次。AFEDCBG第1次經(jīng)過時訪問先序遍歷第2次經(jīng)過時訪問中序遍歷第3次經(jīng)過時訪問后序遍歷2. 二叉樹遍歷的時間效

15、率和空間效率時間效率:O(n) /每個結(jié)點(diǎn)只訪問一次空間效率:O(n) /棧占用的最大輔助空間（精確值：樹深為k的遞歸遍歷需要k+1個輔助單元?。?5對遍歷的分析：1. 從前面的三種遍歷算法可以知道：如果將36例：【嚴(yán)題集6.42】編寫遞歸算法，計算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。 思路：輸出葉子結(jié)點(diǎn)比較簡單，用任何一種遍歷算法，凡是左右指針均空者，則為葉子，將其統(tǒng)計并打印出來。 DLR(liuyu *root) /采用中序遍歷的遞歸算法 if ( root!=NULL ) /非空二叉樹條件，還可寫成if(root) if(!root-lchild&!root-rchild) /是葉子結(jié)點(diǎn)則統(tǒng)計并打印

16、 sum+; printf(%dn,root-data); DLR(root-lchild); /遞歸遍歷左子樹，直到葉子處； DLR(root-rchild); /遞歸遍歷右子樹，直到葉子處； return(0); 36例：【嚴(yán)題集6.42】編寫遞歸算法，計算二叉樹中葉子結(jié)37注：要實現(xiàn)遍歷運(yùn)算必須先把二叉樹存入機(jī)內(nèi)。思路：利用前序遍歷來建樹 （結(jié)點(diǎn)值陸續(xù)從鍵盤輸入，用DLR為宜）Bintree createBTpre( ) Bintree T; char ch;scanf(“%c”,&ch);if(ch=)T=NULL; elseT=( Bintree )malloc(sizeof(Bin

17、TNode);T-data=ch;T-lchild=createBTpre();T-rchild=createBTpre(); return T;怎樣建樹？見教材P131程序。37注：要實現(xiàn)遍歷運(yùn)算必須先把二叉樹存入機(jī)內(nèi)。思路：利用前序38習(xí)題討論：1. 求二叉樹深度，或從x結(jié)點(diǎn)開始的子樹深度。 算法思路：只查各結(jié)點(diǎn)后繼鏈表指針，若左(右)孩子的左(右)指針非空，則層次數(shù)加1；否則函數(shù)返回。技巧：遞歸時應(yīng)當(dāng)從葉子開始向上計數(shù)，層深者保留。否則不易確定層數(shù)。 2. 按層次輸出二叉樹中所有結(jié)點(diǎn)。 算法思路：既然要求從上到下，從左到右，則利用隊列存放各子樹結(jié)點(diǎn)的指針是個好辦法，而不必拘泥于遞歸算法。

18、技巧：當(dāng)根結(jié)點(diǎn)入隊后，令其左、右孩子結(jié)點(diǎn)入隊，而左孩子出隊時又令它的左右孩子結(jié)點(diǎn)入隊，由此便可產(chǎn)生按層次輸出的效果。 A B CD E38習(xí)題討論：1. 求二叉樹深度，或從x結(jié)點(diǎn)開始的子樹深度。393 中序遍歷的非遞歸(迭代)算法算法思路：若不用遞歸，則要實現(xiàn)二叉樹遍歷的“嵌套”規(guī)則，必用堆棧。可直接用while語句和push/pop操作。參見教材P130-131程序。4.判別給定二叉樹是否為完全二叉樹（即順序二叉樹）。 算法思路：完全二叉樹的特點(diǎn)是：沒有左子樹空而右子樹單獨(dú)存在的情況(前k-1層都是滿的，且第k層左邊也滿）。技巧:按層序遍歷方式，先把所有結(jié)點(diǎn)（不管當(dāng)前結(jié)點(diǎn)是否有左右孩子）都入

19、隊列.若為完全二叉樹,則層序遍歷時得到的肯定是一個連續(xù)的不包含空指針的序列.如果序列中出現(xiàn)了空指針，則說明不是完全二叉樹。393 中序遍歷的非遞歸(迭代)算法算法思路：若不用遞歸，則40特別討論：若已知先序/后序遍歷結(jié)果和中序遍歷結(jié)果，能否“恢復(fù)”出二叉樹？【嚴(yán)題集6.31】 證明：由一棵二叉樹的先序序列和中序序列可唯一確定這棵二叉樹。 例：已知一棵二叉樹的中序序列和后序序列分別是BDCEAFHG 和 DECBHGFA，請畫出這棵二叉樹。分析：由后序遍歷特征，根結(jié)點(diǎn)必在后序序列尾部（即A）；由中序遍歷特征，根結(jié)點(diǎn)必在其中間，而且其左部必全部是左子樹子孫（即BDCE），其右部必全部是右子樹子孫（

20、即FHG）；繼而，根據(jù)后序中的DECB子樹可確定B為A的左孩子，根據(jù)HGF子串可確定F為A的右孩子；以此類推。40特別討論：若已知先序/后序遍歷結(jié)果和中序遍歷結(jié)果，能否“41中序遍歷：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 EGHABBFF41中序遍歷：B D C E A F H G后序遍歷：D42問：用二叉鏈表法（l_child, r_child）存儲包含n個結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的指針區(qū)域中會有多少個空指針？分析：用二叉鏈表存儲包含n個結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)必有2n個鏈域（見二叉鏈表數(shù)據(jù)類型說

21、明）。除根結(jié)點(diǎn)外，二叉樹中每一個結(jié)點(diǎn)有且僅有一個雙親（直接前驅(qū)），所以只會有n1個結(jié)點(diǎn)的鏈域存放指針，指向非空子女結(jié)點(diǎn)（即直接后繼）。思考：二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？我們可以用它來存放當(dāng)前結(jié)點(diǎn)的直接前驅(qū)和后繼等線索，以加快查找速度。所以， 空指針數(shù)目2n(n-1)=n+1個。n+142問：用二叉鏈表法（l_child, r_child）存儲43二、線索二叉樹（Threaded Binary Tree）普通二叉樹只能找到結(jié)點(diǎn)的左右孩子信息，而該結(jié)點(diǎn)的直接前驅(qū)和直接后繼只能在遍歷過程中獲得。若將遍歷后對應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存起來，則從第一個結(jié)點(diǎn)開始就能很快“順

22、藤摸瓜”而遍歷整個樹了。兩種解決方法：增加兩個域：fwd和bwd；存放前驅(qū)指針存放后繼指針如何預(yù)存這類信息？例如中序遍歷結(jié)果：B D C E A F H G，實際上已將二叉樹轉(zhuǎn)為線性排列，顯然具有唯一前驅(qū)和唯一后繼。1. 定義 2. 生成 3. 遍歷利用空鏈域（n+1個空鏈域）43二、線索二叉樹（Threaded Binary Tree44規(guī)定：1）若結(jié)點(diǎn)有左子樹，則lchild指向其左孩子； 否則， lchild指向其直接前驅(qū)(即線索)；2）若結(jié)點(diǎn)有右子樹，則rchild指向其右孩子； 否則， rchild指向其直接后繼(即線索) 。為區(qū)別兩種不同情況，特增加兩個標(biāo)志域（各1bit)lchi

23、lddatarchild約定:當(dāng)Tag域為0時,表示正常情況;當(dāng)Tag域為1時,表示線索情況.右孩子或后繼左孩子或前驅(qū)LTagRTag44規(guī)定：1）若結(jié)點(diǎn)有左子樹，則lchild指向其左孩子；245附：有關(guān)線索二叉樹的幾個術(shù)語： 線索鏈表：用含Tag的結(jié)點(diǎn)樣式所構(gòu)成的二叉鏈表 線 索：指向結(jié)點(diǎn)前驅(qū)和后繼的指針線索二叉樹：加上線索的二叉樹 線 索 化：對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程討論：增加了前驅(qū)和后繼等線索有什么好處？能方便找出當(dāng)前結(jié)點(diǎn)的前驅(qū)和后繼，不用堆棧也能遍歷整個樹。45附：有關(guān)線索二叉樹的幾個術(shù)語： 線索鏈表：用含Tag46dataAGEIDJHCFBltag00111

24、10101rtag0001010111AGEIDJHCFB例：某先序遍歷結(jié)果如下表所示，請畫出對應(yīng)的二叉樹。（多帶了兩個標(biāo)志?。?6dataAGEIDJHCFBltag0011110101472. 線索二叉樹的生成線索化過程就是在遍歷過程中修改空指針的過程：將空的lchild改為結(jié)點(diǎn)的直接前驅(qū)；將空的rchild改為結(jié)點(diǎn)的直接后繼。非空指針呢？仍然指向孩子結(jié)點(diǎn)（稱為“正常情況”）472. 線索二叉樹的生成線索化過程就是在遍歷過程中修改空指48ABCGEIDHFroot懸空？懸空？解：該二叉樹中序遍歷結(jié)果為: H, D, I, B, E, A, F, C, G所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：為避

25、免懸空態(tài)，應(yīng)增設(shè)一個頭結(jié)點(diǎn)例1：畫出以下二叉樹對應(yīng)的中序線索二叉樹。48ABCGEIDHFroot懸空？懸空？解：該二叉樹中序遍4900A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為: H, D, I, B, E, A, F, C, G0-root0對應(yīng)的中序線索二叉樹存儲結(jié)構(gòu)如圖所示：4900A00C00B11E11F11G00D11I11H注50例2：【 2000年計算機(jī)系考研題】給定如圖所示二叉樹T，請畫出與其對應(yīng)的中序線索二叉樹。 2825405560330854解:因為中序遍歷序列是：55 40 25 60 28 08 33 54對應(yīng)線索樹應(yīng)當(dāng)按此規(guī)律連線，

26、即在原二叉樹中添加虛線。NILNIL50例2：【 2000年計算機(jī)系考研題】給定如圖所示二叉樹T51線索二叉樹的生成算法（算法6.6, 見教材P134）目的：在依某種順序遍歷二叉樹時修改空指針，添加前驅(qū)或后 繼。注解：為方便添加結(jié)點(diǎn)的前驅(qū)或后繼，需要設(shè)置兩個指針： p指針當(dāng)前結(jié)點(diǎn)之指針； pre指針前驅(qū)結(jié)點(diǎn)之指針。技巧：當(dāng)結(jié)點(diǎn)p的左/右域為空時，只改寫它的左域（裝入前驅(qū)pre），而其右域（后繼）留給下一結(jié)點(diǎn)來填寫。 或者說，當(dāng)前結(jié)點(diǎn)的指針p應(yīng)當(dāng)送到前驅(qū)結(jié)點(diǎn)的空右域中。若p-lchildNULL,則p-Ltag=1;p-lchildpre; /p的前驅(qū)結(jié)點(diǎn)指針pre存入左空域若pre-rchil

27、dNULL, 則pre-Rtag1;pre-rchild=p; /p存入其前驅(qū)結(jié)點(diǎn)pre的右空域51線索二叉樹的生成算法（算法6.6, 見教材P134）目的523. 線索二叉樹的遍歷理論上，只要找到序列中的第一個結(jié)點(diǎn)，然后依次訪問結(jié)點(diǎn)的后繼直到后繼為空時結(jié)束。但是，在線索化二叉樹中，并不是每個結(jié)點(diǎn)都能直接找到其后繼的，當(dāng)標(biāo)志為0時，R_child=右孩子地址指針，并非后繼！需要通過一定運(yùn)算才能找到它的后繼。以中序線索二叉樹為例：對葉子結(jié)點(diǎn)（RTag=1），直接后繼指針就在其rchild域內(nèi)；對其他結(jié)點(diǎn)（RTag=0），直接后繼是其右子樹最左下的結(jié)點(diǎn)；（因為中序遍歷規(guī)則是LDR，先左再根再右）5

28、23. 線索二叉樹的遍歷理論上，只要找到序列中的第一個結(jié)點(diǎn)53程序注解 (非遞歸，且不用棧）：P=T-lchild; /從頭結(jié)點(diǎn)進(jìn)入到根結(jié)點(diǎn)；while( p!=T) while(p-LTag=link)p=p-lchild; /先找到中序遍歷起點(diǎn) if(!visit(p-data) return ERROR; /若起點(diǎn)值為空則出錯告警 while(p-RTag=Thread ) p=p-rchild; Visit(p-data); /若有后繼標(biāo)志，則直接提取p-rchild中線索并訪問后繼結(jié)點(diǎn)；p=p-rchild; /當(dāng)前結(jié)點(diǎn)右域不空或已經(jīng)找好了后繼，則一律從結(jié)點(diǎn)的右子樹開始重復(fù) 的全部過

29、程。Return OK;線索二叉樹的中序遍歷算法（算法6.5, 參見教材P134）LTag=0RTag=153程序注解 (非遞歸，且不用棧）：線索二叉樹的中序遍歷算54算法流程：return OK;p=T-lchild;p!=Tp-LTag=0p=p-lchild;vist(p-data);p-LTag=1&p-rchild!=Tp=p-rchild;visit(p-data);p=p-rchild;YNYNYN演示程序54算法流程：return OK;p=T-lchild;p55提前介紹：二叉樹的應(yīng)用平衡樹排序樹字典樹判定樹帶權(quán)樹最優(yōu)樹特點(diǎn)：左右子樹深度差 1特點(diǎn)：“左小右大”（見實驗二的方

30、案1）由字符串構(gòu)成的二叉樹排序樹例如，12個球只稱3次分出輕重特點(diǎn)：路徑長度帶權(quán)值 帶權(quán)路徑長度最短的樹，又稱 Huffman樹，用途之一是通信中的壓縮編碼。55提前介紹：二叉樹的應(yīng)用平衡樹特點(diǎn)：左右子樹深度差 566.4 樹和森林1. 樹和森林與二叉樹的轉(zhuǎn)換2. 樹和森林的存儲方式3. 樹和森林的遍歷566.4 樹和森林1. 樹和森林與二叉樹的轉(zhuǎn)換571. 樹和森林與二叉樹的轉(zhuǎn)換轉(zhuǎn)換步驟：step1: 將樹中同一結(jié)點(diǎn)的兄弟相連;step2: 保留結(jié)點(diǎn)的最左孩子連線，刪除其它孩子連線；step3: 將同一孩子的連線繞左孩子旋轉(zhuǎn)45度角。加線抹線旋轉(zhuǎn)討論1：樹如何轉(zhuǎn)為二叉樹？571. 樹和森林與

31、二叉樹的轉(zhuǎn)換轉(zhuǎn)換步驟：加線抹線旋轉(zhuǎn)討58方法：加線抹線旋轉(zhuǎn) abeidfhgc樹轉(zhuǎn)二叉樹舉例：abeidfhgc兄弟相連長兄為父孩子靠左根結(jié)點(diǎn)肯定沒有右孩子！58方法：加線抹線旋轉(zhuǎn) abeidfhgc樹轉(zhuǎn)二叉樹舉例59討論2：二叉樹怎樣還原為樹？abeidfhgc要點(diǎn)：把所有右孩子變?yōu)樾值埽?abeidfhgc59討論2：二叉樹怎樣還原為樹？abeidfhgc要點(diǎn)：把所60法一： 各森林先各自轉(zhuǎn)為二叉樹； 依次連到前一個二叉樹的右子樹上。討論3：森林如何轉(zhuǎn)為二叉樹？法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹（參見教材P138圖6.17，兩種方法都有轉(zhuǎn)換示意圖）即F=T1, T2, ,Tm B=root

32、, LB, RB60法一：討論3：森林如何轉(zhuǎn)為二叉樹？法二：森林直接變兄弟，61ABCDEFGHJIABCDEFGHJIABCDEFGHJI森林轉(zhuǎn)二叉樹舉例：（法二）兄弟相連 長兄為父孩子靠左 頭根為根 A61ABCDEFGHJIABCDEFGHJIABCDEFGH62討論4：二叉樹如何還原為森林？要點(diǎn)：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值?ABCDEFGHJIABCDEFGHJIEFABCDGHJI即B=root, LB, RB F=T1, T2, ,Tm62討論4：二叉樹如何還原為森林？要點(diǎn)：把最右邊的子樹變?yōu)樯?32. 樹和森林的存儲方式樹有三種常用存儲方式：雙親表示法 孩子表示法

33、 孩子兄弟表示法 1、用雙親表示法來存儲思路：用一組連續(xù)空間來存儲樹的結(jié)點(diǎn)，同時在每個結(jié)點(diǎn)中附設(shè)一個指示器，指示其雙親結(jié)點(diǎn)在鏈表中的位置。parentsdata結(jié)點(diǎn)結(jié)構(gòu)dataparents1樹結(jié)構(gòu) 23n632. 樹和森林的存儲方式樹有三種常用存儲方式：1、用雙親64ABCGEIDHF缺點(diǎn)：求結(jié)點(diǎn)的孩子時需要遍歷整個結(jié)構(gòu)。01234567812233ABCDEFGHI-1001例1: 雙親表示法64ABCGEIDHF缺點(diǎn)：求結(jié)點(diǎn)的孩子時需要遍歷整個結(jié)構(gòu)。65思路：將每個結(jié)點(diǎn)的孩子排列起來，形成一個帶表頭（裝父結(jié)點(diǎn)）的線性表（n個結(jié)點(diǎn)要設(shè)立n個鏈表）；再將n個表頭用數(shù)組存放起來，這樣就形成一個

34、混合結(jié)構(gòu)。例如：abecdfhgdefghgfedcbah123456782、用孩子表示法來存儲bc65思路：將每個結(jié)點(diǎn)的孩子排列起來，形成一個帶表頭（裝父結(jié)點(diǎn)66思路：用二叉鏈表來表示樹，但鏈表中的兩個指針域含義不同。左指針指向該結(jié)點(diǎn)的第一個孩子；右指針指向該結(jié)點(diǎn)的下一個兄弟結(jié)點(diǎn)。nextsiblingdatafirstchild3、用孩子兄弟表示法來存儲指向左孩子指向右兄弟66思路：用二叉鏈表來表示樹，但鏈表中的兩個指針域含義不同。67abecdfhgbacedfgh問：樹轉(zhuǎn)二叉樹的“連線抹線旋轉(zhuǎn)” 如何由計算機(jī)自動實現(xiàn)？答：用“左孩子右兄弟”表示法來存儲即可。 存儲的過程就是轉(zhuǎn)換的過程！

35、例如：67abecdfhgbacedfgh問：樹轉(zhuǎn)二叉樹的“連線68先序遍歷若森林為空，返回；訪問森林中第一棵樹的根結(jié)點(diǎn)；先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林；先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。中序遍歷若森林為空，返回；中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林；訪問第一棵樹的根結(jié)點(diǎn)；中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。森林的遍歷ABCDEFGHJI68先序遍歷森林的遍歷ABCDEFGHJI69路 徑：路徑長度：樹的路徑長度：帶權(quán)路徑長度：樹的帶權(quán)路徑長度：霍 夫 曼 樹：6.5 Huffman樹及其應(yīng)用一、最優(yōu)二叉樹（霍夫曼樹）由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成路徑上的分支數(shù)目從

36、樹根到每一結(jié)點(diǎn)的路徑長度之和。結(jié)點(diǎn)到根的路徑長度與結(jié)點(diǎn)上權(quán)的乘積預(yù)備知識：若干術(shù)語debacf g樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和帶權(quán)路徑長度最小的樹。ae的路徑長度樹長度21069路 徑：6.5 Huffman樹及其應(yīng)用一、最優(yōu)70Huffman樹簡介：樹的帶權(quán)路徑長度如何計算？WPL = wklk k=1nabdc7524(a)cdab2457(b)bdac7524(c)經(jīng)典之例：WPL=36WPL=46WPL= 35哈夫曼樹則是：WPL 最小的樹。Huffman樹Weighted Path Length70Huffman樹簡介：樹的帶權(quán)路徑長度如何計算？WPL 71(1) 由給定的 n

37、 個權(quán)值w0, w1, w2, , wn-1，構(gòu)造具有 n 棵擴(kuò)充二叉樹的森林F = T0, T1, T2, , Tn-1 ，其中每一棵擴(kuò)充二叉樹 Ti 只有一個帶有權(quán)值 wi 的根結(jié)點(diǎn)，其左、右子樹均為空。 (2) 重復(fù)以下步驟, 直到 F 中僅剩下一棵樹為止： 在 F 中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的擴(kuò)充二叉樹, 做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。 在 F 中刪去這兩棵二叉樹。 把新的二叉樹加入 F。構(gòu)造霍夫曼樹的基本思想：構(gòu)造Huffman樹的步驟（即Huffman算法）：權(quán)值大的結(jié)點(diǎn)用短路徑，權(quán)值小的結(jié)點(diǎn)用長路徑。先舉例！71(1

38、) 由給定的 n 個權(quán)值w0, w1, w2, 72例1：設(shè)有4個字符d,i,a,n，出現(xiàn)的頻度分別為7,5,2, 4，怎樣編碼才能使它們組成的報文在網(wǎng)絡(luò)中傳得最快？法1：等長編碼。例如用二進(jìn)制編碼來實現(xiàn)。 取 d=00，i=01，a=10，n=11怎樣實現(xiàn)Huffman編碼？法2：不等長編碼，例如用哈夫曼編碼來實現(xiàn)。 取 d=0; i=10, a=110, n=111最快的編碼是哪個？是非等長的Huffman碼！先要構(gòu)造Huffman樹！72例1：設(shè)有4個字符d,i,a,n，出現(xiàn)的頻度分別為7,573操作要點(diǎn)1：對權(quán)值的合并、刪除與替換在權(quán)值集合7,5,2,4中，總是合并當(dāng)前值最小的兩個權(quán)構(gòu)

39、造Huffman樹的步驟：注：方框表示外結(jié)點(diǎn)（葉子，字符對應(yīng)的權(quán)值）， 圓框表示內(nèi)結(jié)點(diǎn)（合并后的權(quán)值）。73操作要點(diǎn)1：對權(quán)值的合并、刪除與替換構(gòu)造Huffman樹74操作要點(diǎn)2：按左0右1對Huffman樹的所有分支編號！dain111000Huffman編碼結(jié)果：d=0, i=10, a=110, n=111WPL=1bit72bit5+3bit(2+4)=35特點(diǎn)：每一碼都不是另一碼的前綴，絕不會錯譯! 稱為前綴碼將 Huffman樹 與 Huffman編碼 掛鉤74操作要點(diǎn)2：按左0右1對Huffman樹的所有分支編號！75例2（嚴(yán)題集6.26）：假設(shè)用于通信的電文僅由8個字母 a,

40、b, c, d, e, f, g, h 構(gòu)成，它們在電文中出現(xiàn)的概率分別為 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10，試為這8個字母設(shè)計哈夫曼編碼。如果用07的二進(jìn)制編碼方案又如何？霍夫曼編碼的基本思想是：概率大的字符用短碼，概率小的用長碼。由于霍夫曼樹的WPL最小，說明編碼所需要的比特數(shù)最少。這種編碼已廣泛應(yīng)用于網(wǎng)絡(luò)通信中。解：先將概率放大100倍，以方便構(gòu)造哈夫曼樹。權(quán)值集合 w=7, 19, 2, 6, 32, 3, 21, 10，按哈夫曼樹構(gòu)造規(guī)則（合并、刪除、替換），可得到哈夫曼樹。75例2（嚴(yán)題集6.26）：假設(shè)用于通信的電文僅由

41、8個字母76w4=19, 21, 28, 32為清晰起見，重新排序為:w=2, 3, 6, 7, 10, 19, 21, 322356w1=5, 6, 7, 10, 19, 21, 32w2=7, 10, 11, 19, 21, 32w3=11, 17, 19, 21, 32111071728211940w5=28,32,403260w6=40,60w7=100100bcadegfh哈夫曼樹76w4=19, 21, 28, 32為清晰起見，重新排77對應(yīng)的哈夫曼編碼（左0右1）：23561110732172821194060100bcadegfh00000111111100符編碼頻率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符編碼頻率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10Huffman碼的WPL2(0.19+0.32+0.21) + 4(0.07+0.06+0.10) +5(0.02+0.03) =1.44+0.92+0.25=2.61 WPL3(0.19+0.32+0.21