數據結構ch6樹與二叉樹

1、1第第1章章 緒論緒論第第2章章 線性表線性表第第3章章 棧和隊列棧和隊列 第第4章章 串串第第5章章 數組和廣義表數組和廣義表第第6 6章章 樹和二叉樹樹和二叉樹 第第7章章 圖圖第第9章章 查找查找第第10章章 排序排序目目 錄錄2第第6 6章章 樹和二叉樹樹和二叉樹（tree & binary tree）6.1 樹的基本概念樹的基本概念6.2 二叉樹二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 樹和森林樹和森林6.5 赫夫曼樹及其應用赫夫曼樹及其應用特點：特點：非線性結構，一個直接前驅，但可能有多個非線性結構，一個直接前驅，但可能有多個直接后繼。直接后繼。（一

2、對多，或稱（一對多，或稱1:n1:n）36.16.1 樹的基本概念6.1.1 樹的定義樹的定義6.1.2 若干術語若干術語6.1.3 邏輯結構邏輯結構6.1.4 存儲結構存儲結構6.1.5 樹的運算樹的運算4注注1 1：過去許多書籍中都定義樹為過去許多書籍中都定義樹為n1，曾經有，曾經有“空樹不是空樹不是樹樹”的說法，但現(xiàn)在樹的定義已修改。的說法，但現(xiàn)在樹的定義已修改。注注2：樹的定義具有樹的定義具有遞歸性遞歸性，即，即“樹中還有樹樹中還有樹”。由一個或多個由一個或多個( (n0n0) )結點組成的有限集合結點組成的有限集合t t，有且僅有，有且僅有一一個結點稱為根個結點稱為根（rootroo

3、t），），當當n1n1時，其余的結點分為時，其余的結點分為m m(m0)(m0)個個互不相交的互不相交的有限集合有限集合t1,t2t1,t2，tmtm。每個集合本身又是棵樹，。每個集合本身又是棵樹，被稱作這個根的被稱作這個根的子樹子樹 。5即上層的那個結點即上層的那個結點(直接前驅直接前驅)即下層結點的子樹的根即下層結點的子樹的根(直接后繼直接后繼)同一雙親下的同層結點（孩子之間互稱兄弟）同一雙親下的同層結點（孩子之間互稱兄弟）即雙親位于同一層的結點（但并非同一雙親）即雙親位于同一層的結點（但并非同一雙親）即從根到該結點所經分支的所有結點即從根到該結點所經分支的所有結點即該結點下層子樹中的任一

4、結點即該結點下層子樹中的任一結點abcgeidhfjflk 根根 葉子葉子 森林森林有序樹有序樹無序樹無序樹即根結點即根結點(沒有前驅沒有前驅)即終端結點即終端結點(沒有后繼沒有后繼)指指m棵不相交的樹的集棵不相交的樹的集合合(例如刪除例如刪除a后的子樹個數后的子樹個數)雙親雙親孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孫子孫結點各子樹從左至右有序，不能互換（左為第一）結點各子樹從左至右有序，不能互換（左為第一）結點各子樹可互換位置。結點各子樹可互換位置。6即樹的數據元素即樹的數據元素結點掛接的子樹數結點掛接的子樹數結點結點結點的度結點的度結點的層次結點的層次終端結點終端結點分支結點分支結點樹的度

5、樹的度樹的深度樹的深度(或高度或高度)abcgeidhfjflk從根到該結點的層數（根結點算第一層）從根到該結點的層數（根結點算第一層）即度為即度為0的結點，即葉子的結點，即葉子即度不為即度不為0的結點（也稱為內部結點）的結點（也稱為內部結點）所有結點度中的最大值（所有結點度中的最大值（max各結點的度各結點的度）指所有結點中最大的層數（指所有結點中最大的層數（max各結點的層次各結點的層次）問：問：右上圖中的結點數右上圖中的結點數 ；樹的度；樹的度 ；樹的深度；樹的深度13133 34 4（有幾個直接后繼就是幾度，亦稱（有幾個直接后繼就是幾度，亦稱“次數次數”）7樹的抽象數據類型定義樹的抽象

6、數據類型定義（見教材（見教材p118-119p118-119）adt treeadt tree數據對象數據對象d:d:數據關系數據關系r:r:基本操作基本操作 p p：adt treeadt treed是具有相同特性的數據元素的集合。是具有相同特性的數據元素的集合。若若d為空集，則稱為空樹；為空集，則稱為空樹；/允許允許n=0若若d中僅含一個數據元素，則中僅含一個數據元素，則r為空集；為空集；其他情況下的其他情況下的r存在二元關系：存在二元關系： root 唯一唯一 /關于根的說明關于根的說明 djdk= /關于子樹不相交的說明關于子樹不相交的說明 /關于數據元素的說明關于數據元素的說明 /至

7、少有至少有15個，如求樹深，求某結點的雙親個，如求樹深，求某結點的雙親8一對多（一對多（1:n1:n），），有多個直接后繼（如家譜有多個直接后繼（如家譜樹、目錄樹等等），但只有一個根結點，樹、目錄樹等等），但只有一個根結點，且且子樹之間互不相交。子樹之間互不相交。 討論討論1：樹是非線性結構，該怎樣存儲？樹是非線性結構，該怎樣存儲？特點：特點：仍然有順序存儲、鏈式存儲等方式。仍然有順序存儲、鏈式存儲等方式。 9討論討論3：樹的鏈式存儲方案應該怎樣制定？樹的鏈式存儲方案應該怎樣制定？復原困難復原困難可用多重鏈表：可用多重鏈表：一個前趨指針，一個前趨指針，n n個后繼指針。個后繼指針。 細節(jié)問題：

8、細節(jié)問題： 樹中結點的結構類型樣式該如何設計？樹中結點的結構類型樣式該如何設計？ 即應該設計成即應該設計成“等長等長”還是還是“不等長不等長”？ 缺點：缺點： 等長結構太浪費（每個結點的度不一定相同）；等長結構太浪費（每個結點的度不一定相同）； 不等長結構太復雜（要定義好多種結構類型）。不等長結構太復雜（要定義好多種結構類型）?？煞褚?guī)定為：可否規(guī)定為： 從上至下、從左至右將樹的結點依次存入內存。從上至下、從左至右將樹的結點依次存入內存。有重大缺陷：有重大缺陷：不能唯一復原就沒有實用價值！不能唯一復原就沒有實用價值！討論討論2：樹的順序存儲方案應該怎樣制定？樹的順序存儲方案應該怎樣制定？data

9、link 1 link 2 .link n.困惑困惑：到底到底應當開多少個鏈域應當開多少個鏈域? ?補充：樹的補充：樹的5種表示法：種表示法：v 圖形表示法圖形表示法v 嵌套集合表示法嵌套集合表示法v 廣義表表示法廣義表表示法v 凹入表示法凹入表示法v 左孩子右兄弟表示法左孩子右兄弟表示法意義：把一般的樹轉化為最簡單、最有規(guī)律意義：把一般的樹轉化為最簡單、最有規(guī)律的二叉樹再研究，然后設法從二叉樹再轉回的二叉樹再研究，然后設法從二叉樹再轉回多叉樹。多叉樹。11教師教師學生學生其他人員其他人員20052005級級20062006級級20072007級級20082008級級湖北理工學院湖北理工學院計

10、算機系計算機系計算機系計算機系控制系控制系葉子葉子根根子樹子樹1213( a ( b ( e ( k, l ), f ), c ( g ), d ( h ( m ), i, j ) ) 約定：約定：根根作為由子樹森林組成的作為由子樹森林組成的表的名字寫在表的左邊表的名字寫在表的左邊14又稱目錄表示法又稱目錄表示法15data左孩子左孩子 右兄弟右兄弟意義：多叉樹轉為二叉樹！意義：多叉樹轉為二叉樹！16方法：方法：加線加線抹線抹線旋轉旋轉 abeidfhgc樹轉二叉樹舉例：樹轉二叉樹舉例：abeidfhgc兄弟相連兄弟相連長兄為父長兄為父孩子靠左孩子靠左17討論討論：二叉樹怎樣還原為樹？二叉樹怎

11、樣還原為樹？abeidfhgc要點：要點：逆操作，把逆操作，把所有右孩子變?yōu)樾值芩杏液⒆幼優(yōu)樾值埽?abdefhgic18要明確：要明確：1. 普通樹（即多叉樹）若不轉化為二叉樹，則運算很難實現(xiàn)。普通樹（即多叉樹）若不轉化為二叉樹，則運算很難實現(xiàn)。2. 二叉樹的運算仍然是插入、刪除、修改、查找、排序等，但二叉樹的運算仍然是插入、刪除、修改、查找、排序等，但這些操作必須建立在這些操作必須建立在對樹結點能夠對樹結點能夠“遍歷遍歷”的基礎上！的基礎上！本章重點：本章重點：二叉樹的表示和實現(xiàn)二叉樹的表示和實現(xiàn)196.2 二叉樹二叉樹為何要重點研究每結點最多只有兩個為何要重點研究每結點最多只有兩個 “

12、叉叉” 的樹？的樹？二叉樹的結構最簡單，規(guī)律性最強；二叉樹的結構最簡單，規(guī)律性最強；可以證明，所有樹都能轉為唯一對應的二叉樹，可以證明，所有樹都能轉為唯一對應的二叉樹，不失一般性。不失一般性。6.2.1 二叉樹的定義二叉樹的定義6.2.2 二叉樹的性質二叉樹的性質6.2.3 二叉樹的存儲結構二叉樹的存儲結構注：二叉樹最重要的運算是：遍歷！注：二叉樹最重要的運算是：遍歷！20定義：定義：是是n（n0）個結點的有限集合，由一個根結點以及兩）個結點的有限集合，由一個根結點以及兩棵互不相交的、分別稱為棵互不相交的、分別稱為左子樹和右子樹左子樹和右子樹的二叉樹組成的二叉樹組成 。邏輯結構：邏輯結構： 一

13、對二（一對二（1:2） 基本特征基本特征: 每個結點最多只有兩棵子樹（不存在度大于每個結點最多只有兩棵子樹（不存在度大于2 2的結點）；的結點）； 左子樹和右子樹左子樹和右子樹次序不能顛倒次序不能顛倒。 基本形態(tài)：基本形態(tài)：一般的樹一般的樹有幾種？有幾種？21二叉樹的抽象數據類型定義二叉樹的抽象數據類型定義（見教材（見教材p p121-122121-122）adt binarytree數據對象數據對象d:數據關系數據關系r:基本操作基本操作 p：adt binarytreed是具有相同特性的數據元素的集合。是具有相同特性的數據元素的集合。若若d=，則，則r= ；若若d，則，則r= h；存在二元

14、關系：；存在二元關系： root 唯一唯一 /關于根的說明關于根的說明 djdk= /關于子樹不相交的說明關于子樹不相交的說明 /關于數據元素的說明關于數據元素的說明 /關于左子樹和右子樹的說明關于左子樹和右子樹的說明 /至少有至少有20個，如返回某結點的左孩子，個，如返回某結點的左孩子，或中序遍歷，等等或中序遍歷，等等22討論討論1 1：第第i i層的結點數最多是多少？層的結點數最多是多少？ （利用二進制性質可輕松求出）（利用二進制性質可輕松求出） 性質性質1:1: 性質性質2:2: 再提問：再提問：第第i i層上至少有層上至少有 個結點？個結點？1 1討論討論2 2：深度為深度為k k的二

15、叉樹，最多有多少個結點？的二叉樹，最多有多少個結點？ （利用二進制性質可輕松求出）（利用二進制性質可輕松求出）233. 3. 深度為深度為9 9的二叉樹中至少有的二叉樹中至少有 個結點。個結點。 ) )9 9 ) )8 8 ) ) ) )9 91 12.2.深度為的二叉樹的結點總數，最多為深度為的二叉樹的結點總數，最多為 個。個。 ) )k-1k-1 ) log) log2 2k k ) ) k k ) )k k1. 1. 樹中各結點的度的最大值稱為樹的樹中各結點的度的最大值稱為樹的 。 ) ) 高度高度 ) ) 層次層次 ) ) 深度深度 ) ) 度度dcc課堂練習：課堂練習：24性質性質3

16、: 3: 對于任何一棵二叉樹，若對于任何一棵二叉樹，若2 2度的結點數有度的結點數有n n2 2個，個，則葉子數（則葉子數（n n0 0）必定為必定為n n2 21 1 （即（即n0=n2+1）二叉樹中全部結點數二叉樹中全部結點數nn0+n1+n2( (葉子數葉子數1 1度結點數度結點數2 2度結點數度結點數) )二叉樹中全部結點數二叉樹中全部結點數nb+1 ( ( 總分支數根結點總分支數根結點 ) ) （除根結點外，每個結點必有一個直接前趨，即一個分支）（除根結點外，每個結點必有一個直接前趨，即一個分支）總分支數總分支數b= n1+2n2 (1(1度結點必有度結點必有1 1個直接后繼，個直接

17、后繼，2 2度結點必有度結點必有2 2個個) )n0+n1+n2= n1+2n2 +1, 即即n0=n2+1討論：二叉樹的葉子數和度為討論：二叉樹的葉子數和度為2 2的結點數之間有關系嗎？的結點數之間有關系嗎？25完全二叉樹：完全二叉樹：深度為深度為k 的的、有有n個結點個結點的二叉樹，當且僅當其每一個結點都與的二叉樹，當且僅當其每一個結點都與深度為深度為k 的滿二叉樹中編號從的滿二叉樹中編號從1至至n的結的結點一一對應。點一一對應。aobcgekdjfihnml深度為深度為4 4的滿二叉樹的滿二叉樹完全二叉樹完全二叉樹abcgeidhfj為何要研究為何要研究這兩種特殊這兩種特殊形式？形式？討

18、論：滿二叉樹：討論：滿二叉樹：一棵深度為一棵深度為k 且有且有2k -1個結點的二叉樹。個結點的二叉樹。 （特點：每層都（特點：每層都“充滿充滿”了結點）了結點）解釋：完全二叉樹的特點是只有最后一層葉子不滿，且解釋：完全二叉樹的特點是只有最后一層葉子不滿，且全部集中在左邊。但這其實是全部集中在左邊。但這其實是順序二叉樹順序二叉樹的含義。而的含義。而圖圖論論中的中的“完全二叉樹完全二叉樹”是指是指n1=0的情況。的情況。滿二叉樹和完全二叉樹有什么區(qū)別？滿二叉樹和完全二叉樹有什么區(qū)別？答：滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前答：滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前k-k-1

19、 1層是滿的，但最底層卻允許在右邊缺少連續(xù)若干個結點。滿層是滿的，但最底層卻允許在右邊缺少連續(xù)若干個結點。滿二叉樹是完全二叉樹的一個特例。二叉樹是完全二叉樹的一個特例。26證明：證明：根據性質根據性質2 2，深度為深度為k k的二叉樹最多只有的二叉樹最多只有2 2k k-1-1個結點，且個結點，且完全二叉樹的定義是與同深度的滿二叉樹前面編號相同，即它完全二叉樹的定義是與同深度的滿二叉樹前面編號相同，即它的總結點數的總結點數n n位于位于k k層和層和k-1k-1層滿二叉樹容量之間，層滿二叉樹容量之間，即即 2 2k-1k-1-1n2-1n2k k-1 -1 或或2 2k-1k-1n2n2k k

20、三邊同時取對數，于是有：三邊同時取對數，于是有：k-1logk-1log2 2nk nbdcd l r先序遍歷序列：a b d c先序遍歷:adbcl d rbl d rl d radcl d r中序遍歷序列：b d a c中序遍歷:adbc l r dl r dl r dadcl r d后序遍歷序列： d b c a后序遍歷:b38+*a*/edcb先序遍歷結果先序遍歷結果+ * * / a b c d e前綴表示法前綴表示法中序遍歷結果中序遍歷結果a / b * c * d + e中綴表示法中綴表示法后序遍歷結果后序遍歷結果a b / c * d * e +后綴表示法后綴表示法層次遍歷結果

21、層次遍歷結果+ * e * d / c a b例例2 2：用二叉樹表示算術表達式用二叉樹表示算術表達式39ldr(node *root)if(root !=null) ldr(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 *lc

22、hild,*rchild； node;node *root; a b cd edlr( node *root )if (root !=null) /非空二叉樹非空二叉樹 printf(“%d”,root-data); /訪問訪問d ddlr(root-lchild); /遞歸遍歷左子樹遞歸遍歷左子樹dlr(root-rchild); /遞歸遍歷右子樹遞歸遍歷右子樹 return(0); 40對遍歷的分析：對遍歷的分析：1. 從前面的三種遍歷算法可以知道：如果將從前面的三種遍歷算法可以知道：如果將print語句抹去，語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種從遞歸的角度看，這

23、三種算法是完全相同的，或者說這三種遍歷算法的遍歷算法的訪問路徑是相同的，只是訪問結點的時機不同。訪問路徑是相同的，只是訪問結點的時機不同。從虛線的出發(fā)點到終點的路徑從虛線的出發(fā)點到終點的路徑上，每個結點經過上，每個結點經過3次次。afedcbg第第1次次經過時訪問，是經過時訪問，是先序先序遍歷遍歷第第2次次經過時訪問，是經過時訪問，是中序中序遍歷遍歷第第3次次經過時訪問，是經過時訪問，是后序后序遍歷遍歷2. 2. 二叉樹遍歷的時間效率和空間效率二叉樹遍歷的時間效率和空間效率時間效率時間效率: : /每個結點只訪問一次每個結點只訪問一次空間效率空間效率: : /棧占用的最大輔助空間棧占用的最大輔

24、助空間精確值：樹深為精確值：樹深為k k的遞歸遍歷需要的遞歸遍歷需要k+1k+1個輔助單元個輔助單元41例：例：【嚴題集嚴題集6.426.42】編寫遞歸算法，計算二叉樹編寫遞歸算法，計算二叉樹中葉子結點的數目。中葉子結點的數目。 思路：思路：葉子的特點？左右指針均空！葉子的特點？左右指針均空！ 可選用任何一種遍歷算法查找葉子，將其統(tǒng)計并打印出來。可選用任何一種遍歷算法查找葉子，將其統(tǒng)計并打印出來。 dlr(node *root) /采用先序遍歷的遞歸算法采用先序遍歷的遞歸算法 if ( root!=null ) /非空二叉樹條件，等效于非空二叉樹條件，等效于 if(rootif(root) )

25、 if(!root-lchild&!root-rchild) /是葉子結點則統(tǒng)計并打印是葉子結點則統(tǒng)計并打印 sum+; printf(%dn,root-data); dlr(root-lchild); /遞歸遍歷左子樹，直到葉子處；遞歸遍歷左子樹，直到葉子處； dlr(root-rchild); / /遞歸遍歷右子樹，直到葉子處；遞歸遍歷右子樹，直到葉子處； return(0); 42用空格字符表示用空格字符表示無孩子無孩子或指針或指針為空為空如何如何把二叉樹存入電腦內？把二叉樹存入電腦內？怎樣建樹？見教材怎樣建樹？見教材p131p131例例例：將下面的二叉樹以二叉鏈表形式存入計算機

26、內。例：將下面的二叉樹以二叉鏈表形式存入計算機內?？紤]考慮1 1：輸入結點時怎樣表示：輸入結點時怎樣表示“無孩子無孩子”？考慮考慮2 2：以何種遍歷方式來輸入和建樹？：以何種遍歷方式來輸入和建樹？將二叉樹將二叉樹按先序遍歷按先序遍歷次序輸入：次序輸入：a b c d e g f (/n)以先序遍歷最為合以先序遍歷最為合適，讓每個結點都適，讓每個結點都能及時被連接到位。能及時被連接到位。字符串輸完后字符串輸完后應當再應當再加一特殊的結束符號加一特殊的結束符號(如如$)，因為，因為 無無法惟一表示結束。法惟一表示結束。43建樹算法：建樹算法：status createbitree( bitree

27、&t ) /構造二叉樹構造二叉樹t t scanf(“%c”,&ch); if(ch= )t=null; /立即結束立即結束 else if(!(t=( bitnode*)malloc(sizeof(bitnode)exit(overflow); t-data=ch; /生成根結點生成根結點 createbitree(t-lchild); /構造左子樹構造左子樹 createbitree(t-rchild); /構造右子樹構造右子樹 return ok; /createbitreecreatebitree輸入序列：輸入序列： a b c d e g f 44例：例：已知一棵二叉

28、樹的已知一棵二叉樹的中序序列中序序列和和后序序列后序序列分別是分別是bdceafhg 和和 decbhgfa，請畫出這棵二叉樹。，請畫出這棵二叉樹。分析：分析：由后序遍歷特征，根結點必在后序序列尾部由后序遍歷特征，根結點必在后序序列尾部（即（即a a）；由中序遍歷特征，根結點必在其中間，而且其左部必全部是由中序遍歷特征，根結點必在其中間，而且其左部必全部是左子樹的子孫左子樹的子孫（即（即bdcebdce），），其右部必全部是右子樹的子孫其右部必全部是右子樹的子孫（即（即fhgfhg）；）；繼而，根據后序中的繼而，根據后序中的decbdecb子樹可確定子樹可確定b b為為a a的左孩子，根據的左

29、孩子，根據hgfhgf子串可確定子串可確定f f為為a a的右孩子；以此類推。的右孩子；以此類推?！緡李}集嚴題集6.31】 請證明：由一棵二叉樹的先序序列和中序序請證明：由一棵二叉樹的先序序列和中序序列可唯一確定這棵二叉樹。列可唯一確定這棵二叉樹。 45已知中序遍歷：已知中序遍歷：b d c e a f h g已知后序遍歷：已知后序遍歷：d e c b h g f a（b d c e）（ f h g）a （d c e）bfghcd eabbaccd c e詳細說明：詳細說明：6.3.2 線索二叉樹線索二叉樹所以，所以， 空指針數目空指針數目2n(n-1)=n+1個個。證明：證明：因為用二叉鏈表

30、存儲包含因為用二叉鏈表存儲包含n n個結點的二叉樹，結點必有個結點的二叉樹，結點必有2n個個鏈域鏈域（見二叉鏈表數據類型說明）（見二叉鏈表數據類型說明）。又因為除根結點外，二叉樹中每一個結點又因為除根結點外，二叉樹中每一個結點有且僅有一個雙親有且僅有一個雙親，意即每個結點地址占用了雙親的一個直接后繼，意即每個結點地址占用了雙親的一個直接后繼，n n個結點地址個結點地址共占用了共占用了n-1n-1個雙親的指針域個雙親的指針域。也就是說，只會有。也就是說，只會有n n1 1個結點個結點的鏈域存放指針。的鏈域存放指針。threaded binary tree討論：討論：用二叉鏈表法（用二叉鏈表法（l

31、_child, r_child）存儲包含存儲包含n個結點個結點的二叉樹，結點的指針區(qū)域中會有多少個的二叉樹，結點的指針區(qū)域中會有多少個空空指針？指針？結論：結論：用二叉鏈表法存儲包含用二叉鏈表法存儲包含n n個結點的二叉樹，結點的指針區(qū)個結點的二叉樹，結點的指針區(qū)域中會有域中會有n+1n+1個空指針。個空指針?？梢杂盟鼇砜梢杂盟鼇泶娣女斍敖Y點的直接前驅和后繼存放當前結點的直接前驅和后繼等線索，以加快查等線索，以加快查找速度。找速度。這就是這就是的意義和用途。的意義和用途。疑問疑問1：二叉樹是二叉樹是1:2的非線性結構，如何定義其惟一的直接后繼？的非線性結構，如何定義其惟一的直接后繼？答：答：要

32、遍歷之后才能得到，且不同遍歷算法得到的后繼也不同。要遍歷之后才能得到，且不同遍歷算法得到的后繼也不同。先依遍歷規(guī)則先依遍歷規(guī)則把每個結點對應的把每個結點對應的前驅前驅或或后繼線索后繼線索預存預存起來，這叫做起來，這叫做“線索化線索化”。疑問疑問2：獲得這種：獲得這種“直接前驅直接前驅”或或“直接后繼直接后繼”有何意義？有何意義？答：答：從從任一結點任一結點出發(fā)都能快速找到其前驅和后繼，且出發(fā)都能快速找到其前驅和后繼，且不必借助堆棧不必借助堆棧疑問疑問3：如何經濟的：如何經濟的(預先預先)存放這類信息？存放這類信息？答：答：左孩子左孩子/前驅前驅復用，復用，右孩子右孩子/后繼后繼復用，后者稱之為

33、復用，后者稱之為線索線索lchildltagdatartag rchild約定約定:當當tag域為域為0時時,表示表示正常正常情況情況;當當tag域為域為1時時,表示表示線索線索情況情況.前驅前驅(后繼后繼)左左(右右)孩子孩子為識別復用的兩種不同信息，特增加兩個標志域：為識別復用的兩種不同信息，特增加兩個標志域：問：問：增加了前驅和后繼等線索有什么好處？增加了前驅和后繼等線索有什么好處？能方便找出當前結點的前驅和后繼，不用能方便找出當前結點的前驅和后繼，不用堆棧（遞歸）也能遍歷整個樹。堆棧（遞歸）也能遍歷整個樹。各各1bit 1bit 疑問疑問4：計算機如何識別是孩子指針還是線索指針？：計算

34、機如何識別是孩子指針還是線索指針？1. 1. 有關線索二叉樹的幾個術語：有關線索二叉樹的幾個術語： 線索鏈表：線索鏈表： 線線 索：索：線索二叉樹：線索二叉樹： 線線 索索 化：化：用用含含tag的結點樣式所構成的二叉鏈表的結點樣式所構成的二叉鏈表指向結點前驅和后繼的指針指向結點前驅和后繼的指針加上線索的二叉樹加上線索的二叉樹對二叉樹以對二叉樹以某種次序遍歷某種次序遍歷使其變?yōu)榫€索使其變?yōu)榫€索二叉樹的過程二叉樹的過程線索化過程就是在遍歷過程中修改空指針的過程：線索化過程就是在遍歷過程中修改空指針的過程：將空的將空的l lchildchild改為結點的直接前驅；改為結點的直接前驅；將空的將空的r

35、 rchildchild改為結點的直接后繼。改為結點的直接后繼。非空指針呢？仍然指向孩子結點非空指針呢？仍然指向孩子結點（稱為（稱為“正常情況正常情況”）dataageidjhcfbltag0011110101rtag0001010111ageidjhcfb例：例：帶了帶了兩個標志兩個標志的某的某先序先序遍歷結果如下表所示，遍歷結果如下表所示，請畫出對應的二叉樹。請畫出對應的二叉樹。altag=1表示表示前驅線索前驅線索rtag=1表示表示后繼線索后繼線索abcgeidhfroot懸空？懸空？ nilnil懸空？懸空？ nilnil解：解：對該二叉樹對該二叉樹中序中序遍歷的結果為遍歷的結果為:

36、 : h, d, i, b, e, a, f, c, g所以添加線索應當按如下路徑進行：所以添加線索應當按如下路徑進行：為為避免懸空避免懸空態(tài)，應增設態(tài)，應增設一個頭結點一個頭結點例例1 1：畫出以下二叉樹對應的畫出以下二叉樹對應的中序中序線索二叉樹。線索二叉樹。2. 2. 線索二叉樹的生成線索二叉樹的生成線索化線索化線索化過程就是在遍歷過線索化過程就是在遍歷過程中修改空指針的過程程中修改空指針的過程00a00c00b11e11f11g00d11i11h注：此圖中序遍歷結果為注：此圖中序遍歷結果為: : h, d, i, b, e, a, f, c, g0root0對應的中序線索二叉樹存儲結構

37、如圖所示：對應的中序線索二叉樹存儲結構如圖所示：例例2 2：【 2000 2000年計算機系考研題年計算機系考研題】給定如圖所示給定如圖所示二叉樹二叉樹t t，請畫出與其對應的中序線索二叉樹。請畫出與其對應的中序線索二叉樹。 2825405560330854解解: :因為中序遍歷序列是：因為中序遍歷序列是：5555 40 25 60 40 25 60 28 28 08 33 08 33 5454對應線索樹應當按此規(guī)律連線，即對應線索樹應當按此規(guī)律連線，即在原二叉樹中添加虛線。在原二叉樹中添加虛線。nilnilnilnilnilnil和和nullnull的值都是的值都是0,0,區(qū)區(qū)別何在？別何在

38、？ 在在delphidelphi中中nilnil用來標記用來標記空指針空指針，nullnull用來表示用來表示空的空的variantvariant型變量或是型變量或是asciiascii碼為碼為0 0的字符，比的字符，比如用于標記字符串結束。如用于標記字符串結束。在在c/c+c/c+中定義的宏中定義的宏nullnull不加區(qū)別的包括了以上不加區(qū)別的包括了以上兩種含義。兩種含義。可見可見object pascalobject pascal的語的語法要比法要比c/c+c/c+嚴謹得多。嚴謹得多。線索二叉樹的線索二叉樹的生成生成算法算法（遞歸算法見教材遞歸算法見教材p134-135p134-135）

39、目的：目的：在遍歷二叉樹的過程中修改空指針，添加前驅或后繼在遍歷二叉樹的過程中修改空指針，添加前驅或后繼的線索，使之成為線索二叉樹。的線索，使之成為線索二叉樹。為了記下遍歷過程中訪問結點的先后次序，需要設置兩個指針：為了記下遍歷過程中訪問結點的先后次序，需要設置兩個指針：p指針指針當前結點之指針；當前結點之指針；pre指針指針當前結點的前趨結點指針。當前結點的前趨結點指針。設計技巧：設計技巧：依某種順序依某種順序遍歷二叉樹，對每個結點遍歷二叉樹，對每個結點p，判斷其左指判斷其左指針是否為空，以及其針是否為空，以及其前驅結點的前驅結點的右指針是否為空。右指針是否為空。每次只修改每次只修改前驅結點

40、的右指針前驅結點的右指針（后繼）和（后繼）和本結點的左指針本結點的左指針（前（前驅）驅），參見算法，參見算法6.6。若若p-lchildnull, ,則則p-p-ltagltag=1;=1;p-p-lchildlchildpre;pre; /p/p的前驅線索應存的前驅線索應存p p結點的左邊結點的左邊若若pre-rchildnull, 則則pre-pre-rtagrtag1;1;pre-pre-rchildrchild=p=p; /pre/pre的后繼線索應存的后繼線索應存prepre結點的右邊結點的右邊3. 3. 線索二叉樹的遍歷線索二叉樹的遍歷（無需堆棧）（無需堆棧）對于線索二叉樹的遍歷，

41、只要找到序列中的對于線索二叉樹的遍歷，只要找到序列中的第一個第一個結結點，然后點，然后依次訪問結點的后繼依次訪問結點的后繼直到后繼為空為止。直到后繼為空為止。（因為建立線索時已遍歷一次，相當于線性化了！）（因為建立線索時已遍歷一次，相當于線性化了?。╇y點：難點：在線索化二叉樹中，并不是每個結點都能直接在線索化二叉樹中，并不是每個結點都能直接找到其后繼的，找到其后繼的，當標志為當標志為0 0時，則需要通過一定運算時，則需要通過一定運算才能找到它的后繼。才能找到它的后繼。以以中序線索二叉樹中序線索二叉樹為例：為例：當當rtag=1時，直接后繼指針就在其時，直接后繼指針就在其rchild域內；域內；

42、當當rtag=0時，直接后繼是當前結點時，直接后繼是當前結點的結點的結點；請注意中序遍歷規(guī)則是請注意中序遍歷規(guī)則是ldr，5 5）當）當rtagrtag=0=0時時（表示有右孩子）（表示有右孩子） ，此時應當從該結點的，此時應當從該結點的右孩子開始右孩子開始(p=p-(p=p-rchildrchild）查找左下角的子孫結點；即查找左下角的子孫結點；即重復重復2）附：附：中序中序線索二叉樹遍歷步驟線索二叉樹遍歷步驟 （算法（算法6.56.5）：1）設置一個搜索指針）設置一個搜索指針p；2）先尋找中序遍歷之）先尋找中序遍歷之首結點首結點（即最左下角結點），（即最左下角結點），方法是：方法是：當當l

43、tagltag=0=0時時（表示有左孩子），（表示有左孩子），p=p-p=p-lchildlchild; ; 直到直到ltagltag=1=1（無左孩子，已到最左下角）無左孩子，已到最左下角）；首先訪問首先訪問p-datap-data；3）接著進入該結點的右子樹，檢查）接著進入該結點的右子樹，檢查rtagrtag 和和p-p-rchildrchild ；4 4） 若該結點的若該結點的rtagrtag=1=1(表示有后繼線索表示有后繼線索)，則則p=p-p=p-rchildrchild ；訪問訪問p-datap-data ;并重復并重復4） ，直到后繼結點的，直到后繼結點的rtagrtag=0=

44、0；有有后繼找后繼，后繼找后繼，無后繼找無后繼找右子樹右子樹的最左子孫的最左子孫有后繼找后繼有后繼找后繼算法流程：算法流程：return ok;return ok;p=t-p=t-lchildlchild; ;p!=tp!=tp-p-ltagltag=0=0p=p-p=p-lchildlchild; ;visit(p-data);visit(p-data);p-p-rtagrtag=1=1&p-&p-rchildrchild!=t!=tp=p-p=p-rchild;visit(prchild;visit(p-data);-data);p=p-p=p-rchildrchild;

45、;y yn ny yn ny yn n先找最左子孫先找最左子孫找到最左子孫找到最左子孫無后繼找右子樹無后繼找右子樹的最左子孫的最左子孫6.4 樹和森林6.4.1 樹和森林與二叉樹的轉換樹和森林與二叉樹的轉換6.4.2 樹和森林的存儲方式樹和森林的存儲方式6.4.3 樹和森林的遍歷樹和森林的遍歷58方法：方法：加線加線抹線抹線旋轉旋轉 abeidfhgcabeidfhgc兄弟相連兄弟相連長兄為父長兄為父孩子靠左孩子靠左6.4.1 6.4.1 樹和森林與二叉樹的轉換樹和森林與二叉樹的轉換回顧回顧1 1：樹如何轉為二叉樹？樹如何轉為二叉樹？左孩子左孩子右右兄弟表示法兄弟表示法59回顧回顧2 2：二叉

46、樹怎樣還原為樹？二叉樹怎樣還原為樹？abeidfhgc要點：要點：逆操作，把逆操作，把所有右孩子變?yōu)樾值芩杏液⒆幼優(yōu)樾值埽?abdefhgic60法一：法一： 各森林先各自轉為二叉樹；各森林先各自轉為二叉樹； 依次連到前一個二叉樹的右子樹上。依次連到前一個二叉樹的右子樹上。討論討論1 1：森林如何轉為二叉樹？森林如何轉為二叉樹？即即f=tf=t1 1, t, t2 2, , ,t,tm m b=root, lb, rb b=root, lb, rb法二：法二：森林直接變兄弟，再轉為二叉樹森林直接變兄弟，再轉為二叉樹（參見教材（參見教材p138p138圖圖6.176.17，兩種方法都有轉換示意

47、圖），兩種方法都有轉換示意圖）法一和法二得到的二叉樹是完法一和法二得到的二叉樹是完全相同的、惟一的。全相同的、惟一的。61abcdefghjiabcdefghjibcdefghji森林轉二叉樹舉例：森林轉二叉樹舉例：（用法二，森林直接變兄弟，再轉為二叉樹）（用法二，森林直接變兄弟，再轉為二叉樹）兄弟相連兄弟相連 長兄為父長兄為父頭樹為根頭樹為根 孩子靠左孩子靠左62bcdefghji討論討論2 2：二叉樹如何還原為森林？二叉樹如何還原為森林？要點：要點：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值馨炎钣疫叺淖訕渥優(yōu)樯?，其余右子樹變?yōu)樾值?即即b=root, lb, rb f=tb=root,

48、lb, rb f=t1 1, t, t2 2, , ,t,tm m abcdefghjiefabcdghji636.4.2 6.4.2 樹和森林的存儲方式樹和森林的存儲方式樹有三種常用存儲方式：樹有三種常用存儲方式：雙親表示法雙親表示法 孩子表示法孩子表示法 孩子孩子兄弟表示法兄弟表示法 nextsiblingdatafirstchild指向左孩子指向左孩子指向右兄弟指向右兄弟問：問：樹樹二叉樹的二叉樹的“連線連線抹線抹線旋轉旋轉” 如何由計算機自動實現(xiàn)如何由計算機自動實現(xiàn)？答：答：用用“左孩子右兄弟左孩子右兄弟”表示法來存儲即可。表示法來存儲即可。 64abecdfhgbacedfgh例如例

49、如：6566因課時有限，因課時有限， “樹和森林樹和森林的遍歷的遍歷”請自學請自學6.4.3 6.4.3 樹和森林的遍歷樹和森林的遍歷例如：例如：abdec先根序列：先根序列：后根序列：后根序列：a b c d eb d c e a深度優(yōu)先遍歷深度優(yōu)先遍歷（先根、后根）（先根、后根）廣度優(yōu)先遍歷廣度優(yōu)先遍歷（層次）（層次）先根遍歷先根遍歷訪問根結點；訪問根結點；依次先根遍歷根結點依次先根遍歷根結點的每棵子樹。的每棵子樹。后根遍歷后根遍歷 依次后根遍歷根結點的每依次后根遍歷根結點的每棵子樹；棵子樹； 訪問根結點。訪問根結點。樹沒有中序遍歷（因樹沒有中序遍歷（因子樹不分左右）子樹不分左右）67討論

50、：樹若采用討論：樹若采用“先轉換，后遍歷先轉換，后遍歷”方式，結果是否一樣？方式，結果是否一樣？abdec先序遍歷：先序遍歷：后序遍歷：后序遍歷：中序遍歷：中序遍歷：d e c b aabdeca b c d eb d c e a1. 樹的先根遍歷與二叉樹的樹的先根遍歷與二叉樹的先序先序遍歷相同；遍歷相同； 2. 樹的樹的后根后根遍歷相當于二叉樹的遍歷相當于二叉樹的中序中序遍歷；遍歷；3. 樹沒有中序遍歷，因為子樹無左右之分。樹沒有中序遍歷，因為子樹無左右之分。結論：結論：樹的先根序列：樹的先根序列：a b c d e樹的后根序列：樹的后根序列：b d c e a68先序遍歷先序遍歷若森林為空

51、，返回；若森林為空，返回；訪問森林中第一棵樹的根結點；訪問森林中第一棵樹的根結點；先根遍歷第一棵樹的根結點的子樹森林；先根遍歷第一棵樹的根結點的子樹森林；先根遍歷除去第一棵樹之后剩余的樹構成的森林。先根遍歷除去第一棵樹之后剩余的樹構成的森林。森林的遍歷森林的遍歷abcdefghji為何有中序？為何有中序？深度優(yōu)先遍歷深度優(yōu)先遍歷（先序、中序）（先序、中序）廣度優(yōu)先遍歷廣度優(yōu)先遍歷（層次）（層次）中序遍歷中序遍歷若森林為空，返回；若森林為空，返回；中根遍歷森林中第一棵樹的根結點的子樹森林；中根遍歷森林中第一棵樹的根結點的子樹森林；訪問第一棵樹的根結點；訪問第一棵樹的根結點；中根遍歷除去第一棵樹之

52、后剩余的樹構成的森林。中根遍歷除去第一棵樹之后剩余的樹構成的森林。69討論：討論：若采用若采用“先轉換，后遍歷先轉換，后遍歷”方式，結果是否相同？方式，結果是否相同？例如：例如：先序序列：先序序列：中序序列：中序序列：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結論：結論：森林的先序和中序遍歷在森林的先序和中序遍歷在兩種方式下的結果相同。兩種方式下的結果相同。706.5 6.5 二叉樹的典型應用二叉樹的典型應用平衡樹平衡樹排序樹排序樹字典樹字典樹判

53、定樹判定樹帶權樹帶權樹最優(yōu)樹最優(yōu)樹由字符串構成的二叉排序樹由字符串構成的二叉排序樹特點特點：分支查找樹（例如：分支查找樹（例如1212個球如何只稱個球如何只稱3 3次次便分出輕重）便分出輕重）特點特點：路徑帶權值（例如長度）：路徑帶權值（例如長度）是帶權路徑長度最短的樹，又稱是帶權路徑長度最短的樹，又稱 huffmanhuffman樹，樹，用途之一是通信中的壓縮編碼。用途之一是通信中的壓縮編碼。特點特點：所有結點左右子樹深度差：所有結點左右子樹深度差1 1特點特點：所有結點：所有結點“左小右大左小右大”71lhuffman樹概念的引入樹概念的引入l最佳判定樹最佳判定樹等級分數段比例abcde0

54、5960697079 8089 901000.050.150.400.300.10a60a90a80a70eyndyncynbyna70a80a60cynbyndyneyna80a9060a70eadeca80a70a60a90eyndyncynbyna什么是帶權樹？什么是帶權樹？abdc7524即葉子帶有權值。例如：即葉子帶有權值。例如：最優(yōu)二叉樹最優(yōu)二叉樹( (哈夫曼樹哈夫曼樹) )如果是帶權路徑長如果是帶權路徑長度最短的樹度最短的樹736.6 huffman6.6 huffman樹及其應用樹及其應用一、一、huffmanhuffman樹樹二、二、huffmanhuffman編碼編碼最優(yōu)二

55、叉樹最優(yōu)二叉樹huffmanhuffman樹樹huffmanhuffman編碼編碼帶權路徑帶權路徑長度最短長度最短的樹的樹不等長編碼不等長編碼是通信中是通信中最經典的最經典的壓縮編碼壓縮編碼74樹的帶權路徑長樹的帶權路徑長度如何計算？度如何計算？wplwpl = = w wk kl lk k k=1k=1n nabdc7524(a)cdab2457(b)bdac7524(c)經典之例：經典之例：wpl=wpl=wpl=huffman樹是樹是wpl wpl 最小的樹最小的樹樹中所有葉子結樹中所有葉子結點的帶權路徑長點的帶權路徑長度之和度之和36463575一、一、 huffmanhuffman樹

56、樹（最優(yōu)二叉樹）（最優(yōu)二叉樹）路路 徑徑：路徑長度路徑長度：樹的路徑長度樹的路徑長度：帶權路徑長度帶權路徑長度：樹的帶權路徑長度樹的帶權路徑長度：huffmanhuffman樹樹：由一結點到另一結點間的分支所構成。由一結點到另一結點間的分支所構成。路徑上的分支數目。路徑上的分支數目。從樹根到從樹根到每一結點每一結點的路徑長度之和。的路徑長度之和。結點到根的路徑長度與結點上權的乘積（結點到根的路徑長度與結點上權的乘積（wplwpl）若干術語：若干術語：debacf g即樹中所有即樹中所有葉子結點葉子結點的帶權路徑長度之和的帶權路徑長度之和帶權路徑長度最小的樹。帶權路徑長度最小的樹。例如：例如：a

57、eae的路徑長度的路徑長度樹長度樹長度2 21010huffmanhuffman常譯為常譯為赫夫曼、霍夫曼、哈夫曼、胡夫曼等赫夫曼、霍夫曼、哈夫曼、胡夫曼等weighted path lengthweighted path length761. 1. 構造構造huffmanhuffman樹的基本思想：樹的基本思想：設有設有4 4個字符個字符d,i,a,nd,i,a,n，出現(xiàn)的頻度分別為，出現(xiàn)的頻度分別為7,5,2,47,5,2,4， 怎樣編碼才能使它們組成的報文在網絡中傳得最快？怎樣編碼才能使它們組成的報文在網絡中傳得最快？法法1 1：等長編碼：等長編碼（如二進制編碼）（如二進制編碼）令令d=

58、d=0000，i=i=0101，a=a=1010，n=n=1111，則：，則：wplwpl1 12bit2bit(7(75 52 24 4）3636法法2 2：不等長編碼：不等長編碼（如（如huffmanhuffman編碼）編碼）令令d=d=0 0;i=;i=1010,a=,a=110110,n=,n=111111，則：，則：討論：討論：huffmanhuffman樹有什么用？樹有什么用？權值大的結點用短路徑，權值小的結點用長路徑。權值大的結點用短路徑，權值小的結點用長路徑。wplwpl最小的樹最小的樹頻度高的信息頻度高的信息用短碼，低的用短碼，低的用長碼，傳輸用長碼，傳輸效率肯定高！效率肯定

59、高！wplwpl2 2= =1 1bitbit7 72 2bitbit5+35+3bitbit(2+4)=(2+4)=3535最小冗余編碼、信息高效傳輸最小冗余編碼、信息高效傳輸77step1step1：在權值集合在權值集合7,5,2,47,5,2,4中，總是合并中，總是合并當前值最小當前值最小的兩個權的兩個權先介紹先介紹huffmanhuffman樹的具體構造步驟：樹的具體構造步驟：a. 初始初始方框表示外結點（葉子，字符）方框表示外結點（葉子，字符）圓框表示內結點圓框表示內結點（合并后的權值）（合并后的權值）b. 合并合并2 4c. 合并合并5 6d. 合并合并7 11誰左誰右？若不誰左誰

60、右？若不規(guī)定就會不惟一規(guī)定就會不惟一78step2step2：d da ai in n1 11 11 10 00 00 0huffmanhuffman編碼結果：編碼結果：d=d=0 0, i=, i=1010, a=, a=110110, n=, n=111111wpl=1wpl=1bitbit7 72 2bitbit5+35+3bitbit(2+4)=(2+4)=3535（小于等長碼的（小于等長碼的wpl=36wpl=36）huffmanhuffman編碼也稱為編碼也稱為huffmanhuffman樹樹 與與 huffmanhuffman編碼編碼 掛鉤掛鉤792. 2. 構造構造huffmanhuffman樹的步驟樹的步驟（即（即hu