數(shù)據(jù)結(jié)構(gòu)第六章數(shù)和二叉樹(shù)

1、1數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容2第第6章章 樹(shù)和二叉樹(shù)（樹(shù)和二叉樹(shù)（ tree & binary tree ）6.1 樹(shù)的基本概念樹(shù)的基本概念6.2 二叉樹(shù)二叉樹(shù)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)6.4 樹(shù)和森林樹(shù)和森林6.5 赫夫曼樹(shù)及其應(yīng)用赫夫曼樹(shù)及其應(yīng)用特點(diǎn)：特點(diǎn)：非線性結(jié)構(gòu)，一個(gè)直接前驅(qū)，但可能有多個(gè)非線性結(jié)構(gòu)，一個(gè)直接前驅(qū)，但可能有多個(gè)直接后繼（直接后繼（1 1：n n）36.1 樹(shù)的基本概念1. 樹(shù)的定義樹(shù)的定義2 若干術(shù)語(yǔ)若干術(shù)語(yǔ)3. 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)4.存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)5. 樹(shù)的運(yùn)算樹(shù)的運(yùn)算41. 樹(shù)的定義樹(shù)的定義注注1：過(guò)去許多書籍中都定義樹(shù)

2、為過(guò)去許多書籍中都定義樹(shù)為n1，曾經(jīng)有，曾經(jīng)有“空樹(shù)不是空樹(shù)不是樹(shù)樹(shù)”的說(shuō)法，但現(xiàn)在樹(shù)的定義已修改。的說(shuō)法，但現(xiàn)在樹(shù)的定義已修改。注注2：樹(shù)的定義具有樹(shù)的定義具有遞歸性遞歸性，即樹(shù)中還有樹(shù)。，即樹(shù)中還有樹(shù)。由一個(gè)或多個(gè)由一個(gè)或多個(gè)( (n0n0) )結(jié)點(diǎn)組成的有限集合結(jié)點(diǎn)組成的有限集合t t，有且，有且僅有僅有一個(gè)結(jié)點(diǎn)稱為根一個(gè)結(jié)點(diǎn)稱為根（rootroot），），當(dāng)當(dāng)n1n1時(shí)，其余的結(jié)點(diǎn)時(shí)，其余的結(jié)點(diǎn)分為分為m(m0)m(m0)個(gè)個(gè)互不相交互不相交的有限集合的有限集合t1,t2t1,t2，tmtm。每。每個(gè)集合本身又是棵樹(shù)，被稱作這個(gè)根的個(gè)集合本身又是棵樹(shù)，被稱作這個(gè)根的子樹(shù)子樹(shù) 。5樹(shù)的表

3、示法有幾種：樹(shù)的表示法有幾種：圖形表示法圖形表示法嵌套集合表示法嵌套集合表示法廣義表表示法廣義表表示法目錄表示法目錄表示法左孩子右兄弟表示法左孩子右兄弟表示法這些表示法的示意圖這些表示法的示意圖參見(jiàn)教材參見(jiàn)教材p120p120樹(shù)的抽象數(shù)據(jù)類型定義樹(shù)的抽象數(shù)據(jù)類型定義參參見(jiàn)教材見(jiàn)教材p118-119p118-1196圖形表示法：圖形表示法：教師教師學(xué)生學(xué)生其他人員其他人員20032003級(jí)級(jí) 20042004級(jí)級(jí) 20052005級(jí)級(jí)20062006級(jí)級(jí)河南大學(xué)河南大學(xué)物理系物理系計(jì)算機(jī)系計(jì)算機(jī)系化學(xué)系化學(xué)系葉子葉子根根子樹(shù)子樹(shù)7嵌套集合表示法嵌套集合表示法( a ( b ( e ( k, l

4、), f ), c ( g ), d ( h ( m ), i, j ) ) 根作為根作為由子樹(shù)森林組成的由子樹(shù)森林組成的表的名字寫在表的左邊表的名字寫在表的左邊(a(b(e(f),g),c,d(h(i),j,k(l) (c) 廣義表表示法a bdjcklhiefg(a) 嵌套集合表示法 a b e f g c d h i j k l( b) 凹入表示法8左孩子右兄弟表示法左孩子右兄弟表示法數(shù)據(jù)數(shù)據(jù)左孩子左孩子 右兄弟右兄弟( a ( b ( e ( k, l ), f ), c ( g ), d ( h ( m ), i, j ) ) )9 樹(shù)的抽象數(shù)據(jù)類型定義樹(shù)的抽象數(shù)據(jù)類型定義adt t

5、ree數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象d:數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系r:基本操作基本操作 p：adt tree若若d為空集，則稱為空樹(shù)；為空集，則稱為空樹(shù)；/允許允許n=0若若d中僅含一個(gè)數(shù)據(jù)元素，則中僅含一個(gè)數(shù)據(jù)元素，則r為空集；為空集；其他情況下的其他情況下的r存在二元關(guān)系：存在二元關(guān)系： root 唯一唯一 /關(guān)于根的說(shuō)明關(guān)于根的說(shuō)明 djdk= /關(guān)于子樹(shù)不相交的說(shuō)明關(guān)于子樹(shù)不相交的說(shuō)明 hj hk= 且且hi仍然是一棵樹(shù)仍然是一棵樹(shù) /關(guān)于數(shù)據(jù)元素的說(shuō)明關(guān)于數(shù)據(jù)元素的說(shuō)明d是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。/至少有至少有15個(gè)個(gè)abcgeidhfjmlk102. 若干術(shù)語(yǔ)若干術(shù)語(yǔ)

6、即上層的那個(gè)結(jié)點(diǎn)即上層的那個(gè)結(jié)點(diǎn)(直接前驅(qū)直接前驅(qū))即下層結(jié)點(diǎn)的子樹(shù)的根即下層結(jié)點(diǎn)的子樹(shù)的根(直接后繼直接后繼)同一雙親下的同層結(jié)點(diǎn)（孩子之間互稱兄弟）同一雙親下的同層結(jié)點(diǎn)（孩子之間互稱兄弟）即雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親）即雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親）即從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)即從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)即該結(jié)點(diǎn)下層子樹(shù)中的任一結(jié)點(diǎn)即該結(jié)點(diǎn)下層子樹(shù)中的任一結(jié)點(diǎn)abcgeidhfjmlk 根根 葉子葉子 森林森林有序樹(shù)有序樹(shù)無(wú)序樹(shù)無(wú)序樹(shù)即根結(jié)點(diǎn)即根結(jié)點(diǎn)(沒(méi)有前驅(qū)沒(méi)有前驅(qū))即終端結(jié)點(diǎn)即終端結(jié)點(diǎn)(沒(méi)有后繼沒(méi)有后繼)指指m棵不相交的樹(shù)的集棵不相交的樹(shù)的集合合(例如刪除例如

7、刪除a后的子樹(shù)個(gè)數(shù)后的子樹(shù)個(gè)數(shù))雙親雙親孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孫子孫結(jié)點(diǎn)各子樹(shù)從左至右有序，不能互換（左為第一）結(jié)點(diǎn)各子樹(shù)從左至右有序，不能互換（左為第一）結(jié)點(diǎn)各子樹(shù)可互換位置。結(jié)點(diǎn)各子樹(shù)可互換位置。112. 若干術(shù)語(yǔ)（續(xù)）若干術(shù)語(yǔ)（續(xù)）即樹(shù)的數(shù)據(jù)元素即樹(shù)的數(shù)據(jù)元素結(jié)點(diǎn)掛接的子樹(shù)數(shù)結(jié)點(diǎn)掛接的子樹(shù)數(shù)（有幾個(gè)直接后繼就是幾度（有幾個(gè)直接后繼就是幾度，亦稱，亦稱“次數(shù)次數(shù)”）結(jié)點(diǎn)結(jié)點(diǎn)結(jié)點(diǎn)的度結(jié)點(diǎn)的度結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次終端結(jié)點(diǎn)終端結(jié)點(diǎn)分支結(jié)點(diǎn)分支結(jié)點(diǎn)樹(shù)的度樹(shù)的度樹(shù)的深度樹(shù)的深度(或高度或高度)abcgeidhfjmlk從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第

8、一層）即度為即度為0的結(jié)點(diǎn)，即葉子的結(jié)點(diǎn)，即葉子即度不為即度不為0的結(jié)點(diǎn)（也稱為內(nèi)部結(jié)點(diǎn)）的結(jié)點(diǎn)（也稱為內(nèi)部結(jié)點(diǎn)）所有結(jié)點(diǎn)度中的最大值（所有結(jié)點(diǎn)度中的最大值（max各結(jié)點(diǎn)的度各結(jié)點(diǎn)的度）指所有結(jié)點(diǎn)中最大的層數(shù)（指所有結(jié)點(diǎn)中最大的層數(shù)（max各結(jié)點(diǎn)的層次各結(jié)點(diǎn)的層次）問(wèn)：?jiǎn)枺河疑蠄D中的結(jié)點(diǎn)數(shù)右上圖中的結(jié)點(diǎn)數(shù) ；樹(shù)的度；樹(shù)的度 ；樹(shù)的深度；樹(shù)的深度13133 34 4123. 樹(shù)的邏輯結(jié)構(gòu)樹(shù)的邏輯結(jié)構(gòu) ( (特點(diǎn)特點(diǎn)) )： 一對(duì)多（一對(duì)多（1:n1:n），有多個(gè)直接后繼（如家譜），有多個(gè)直接后繼（如家譜樹(shù)、目錄樹(shù)等等），但只有一個(gè)根結(jié)點(diǎn)，樹(shù)、目錄樹(shù)等等），但只有一個(gè)根結(jié)點(diǎn)，且且子樹(shù)之間互不相交子

9、樹(shù)之間互不相交。 4. 樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu) 討論討論1：樹(shù)是非線性結(jié)構(gòu)，該怎樣存儲(chǔ)？樹(shù)是非線性結(jié)構(gòu)，該怎樣存儲(chǔ)？仍然有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)等方式。仍然有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)等方式。 13討論討論3：樹(shù)的樹(shù)的鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)方案應(yīng)該怎樣制定？方案應(yīng)該怎樣制定？可規(guī)定為：可規(guī)定為：從上至下、從左至右從上至下、從左至右將樹(shù)的結(jié)點(diǎn)依次存入內(nèi)存。將樹(shù)的結(jié)點(diǎn)依次存入內(nèi)存。重大缺陷：復(fù)原困難（不能唯一復(fù)原就沒(méi)有實(shí)用價(jià)值）。重大缺陷：復(fù)原困難（不能唯一復(fù)原就沒(méi)有實(shí)用價(jià)值）。討論討論2：樹(shù)的樹(shù)的順序存儲(chǔ)順序存儲(chǔ)方案應(yīng)該怎樣制定？方案應(yīng)該怎樣制定？可用多重鏈表：可用多重鏈表：一個(gè)前趨指針，一個(gè)前趨指針，n n個(gè)

10、后繼指針。個(gè)后繼指針。細(xì)節(jié)問(wèn)題：細(xì)節(jié)問(wèn)題：樹(shù)中結(jié)點(diǎn)的結(jié)構(gòu)類型樣式該如何設(shè)計(jì)？樹(shù)中結(jié)點(diǎn)的結(jié)構(gòu)類型樣式該如何設(shè)計(jì)？ 即應(yīng)該設(shè)計(jì)成即應(yīng)該設(shè)計(jì)成“等長(zhǎng)等長(zhǎng)”還是還是“不等長(zhǎng)不等長(zhǎng)”？缺點(diǎn)：缺點(diǎn)：等長(zhǎng)結(jié)構(gòu)太浪費(fèi)（每個(gè)結(jié)點(diǎn)的度不一定相同）；等長(zhǎng)結(jié)構(gòu)太浪費(fèi)（每個(gè)結(jié)點(diǎn)的度不一定相同）； 不等長(zhǎng)結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類型）。不等長(zhǎng)結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類型）。解決思路：解決思路：先研究最簡(jiǎn)單、最有規(guī)律的樹(shù)，然后設(shè)法把先研究最簡(jiǎn)單、最有規(guī)律的樹(shù)，然后設(shè)法把一般的樹(shù)轉(zhuǎn)化為簡(jiǎn)單樹(shù)。一般的樹(shù)轉(zhuǎn)化為簡(jiǎn)單樹(shù)。145. 樹(shù)的運(yùn)算樹(shù)的運(yùn)算 要明確：要明確：1. 普通樹(shù)（即多叉樹(shù)）若不轉(zhuǎn)化為二叉樹(shù)，則運(yùn)普通樹(shù)（即多叉

11、樹(shù)）若不轉(zhuǎn)化為二叉樹(shù)，則運(yùn)算很難實(shí)現(xiàn)。算很難實(shí)現(xiàn)。2. 二叉樹(shù)的運(yùn)算仍然是插入、刪除、修改、查找、二叉樹(shù)的運(yùn)算仍然是插入、刪除、修改、查找、排序等，但這些操作必須建立在排序等，但這些操作必須建立在對(duì)樹(shù)結(jié)點(diǎn)能夠?qū)?shù)結(jié)點(diǎn)能夠“遍歷遍歷”的基礎(chǔ)上！的基礎(chǔ)上?。ū闅v遍歷指每個(gè)結(jié)點(diǎn)都被訪問(wèn)且僅訪問(wèn)一次，指每個(gè)結(jié)點(diǎn)都被訪問(wèn)且僅訪問(wèn)一次，不遺漏不重復(fù)）。不遺漏不重復(fù)）。本章重點(diǎn)：二叉樹(shù)的表示和實(shí)現(xiàn)本章重點(diǎn)：二叉樹(shù)的表示和實(shí)現(xiàn)156.2 6.2 二叉樹(shù)二叉樹(shù)為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè) “叉叉” 的樹(shù)？的樹(shù)？ 二叉樹(shù)的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)；二叉樹(shù)的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)；

12、 可以證明，所有樹(shù)都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹(shù)，不失一般性?？梢宰C明，所有樹(shù)都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹(shù)，不失一般性。1. 二叉樹(shù)的定義二叉樹(shù)的定義2. 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì)3. 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)（二叉樹(shù)的運(yùn)算（二叉樹(shù)的運(yùn)算見(jiàn)見(jiàn)6.3節(jié)節(jié)）16定義：定義：是是n（n0）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為棵互不相交的、分別稱為左子樹(shù)和右子樹(shù)左子樹(shù)和右子樹(shù)的二叉樹(shù)組成的二叉樹(shù)組成 。邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)： 一對(duì)二（一對(duì)二（1：2） 基本特征基本特征: 每個(gè)結(jié)點(diǎn)最多只有兩棵子樹(shù)（不存在度大于每個(gè)結(jié)點(diǎn)最多只有兩棵子樹(shù)（不存在度大于

13、2 2的結(jié)點(diǎn)）；的結(jié)點(diǎn)）； 左子樹(shù)和右子樹(shù)次序不能顛倒（有序樹(shù)）。左子樹(shù)和右子樹(shù)次序不能顛倒（有序樹(shù)）?；拘螒B(tài)：基本形態(tài)： 5種種/2種種17二叉樹(shù)的抽象數(shù)據(jù)類型定義二叉樹(shù)的抽象數(shù)據(jù)類型定義（見(jiàn)教材（見(jiàn)教材p p121-122121-122）adt binarytree數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象d:數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系r:基本操作基本操作 p：adt binarytree若若d=，則，則r= ；若若d，則，則r= h；存在二元關(guān)系：；存在二元關(guān)系： root 唯一唯一 /關(guān)于根的說(shuō)明關(guān)于根的說(shuō)明 djdk= /關(guān)于子樹(shù)不相交的說(shuō)明關(guān)于子樹(shù)不相交的說(shuō)明 /關(guān)于數(shù)據(jù)元素的說(shuō)明關(guān)于數(shù)據(jù)元素的說(shuō)明 /關(guān)于左子樹(shù)和

14、右子樹(shù)的說(shuō)明關(guān)于左子樹(shù)和右子樹(shù)的說(shuō)明d是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。/至少有至少有20個(gè)個(gè)18討論討論1 1：第：第i i層的結(jié)點(diǎn)數(shù)至多是多少？層的結(jié)點(diǎn)數(shù)至多是多少？ （利用二進(jìn)制性質(zhì)可輕松求出）（利用二進(jìn)制性質(zhì)可輕松求出） 性質(zhì)性質(zhì)1: 1: 在二叉樹(shù)的第在二叉樹(shù)的第i i層上至多有層上至多有個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（i i00）。）。性質(zhì)性質(zhì)2: 2: 深度為深度為k k的二叉樹(shù)至多有的二叉樹(shù)至多有個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（k0k0）。）。2 2i-1i-1個(gè)個(gè)提問(wèn)：第提問(wèn)：第i i層上至少有層上至少有 個(gè)結(jié)點(diǎn)？個(gè)結(jié)點(diǎn)？1 1討論討論2 2：深度為：深度為k k的二叉樹(shù)，至多

15、有多少個(gè)結(jié)點(diǎn)？的二叉樹(shù)，至多有多少個(gè)結(jié)點(diǎn)？ （利用二進(jìn)制性質(zhì)可輕松求出）（利用二進(jìn)制性質(zhì)可輕松求出）2 2k k-1-1提問(wèn)：深度為提問(wèn)：深度為k k時(shí)至少有時(shí)至少有 個(gè)結(jié)點(diǎn)？個(gè)結(jié)點(diǎn)？k k19討論討論3 3：二叉樹(shù)的葉子數(shù)和度為：二叉樹(shù)的葉子數(shù)和度為2 2的結(jié)點(diǎn)數(shù)之間有關(guān)系嗎？的結(jié)點(diǎn)數(shù)之間有關(guān)系嗎？性質(zhì)性質(zhì)3: 3: 對(duì)于任何一棵二叉樹(shù)，若對(duì)于任何一棵二叉樹(shù)，若2 2度的結(jié)點(diǎn)數(shù)有度的結(jié)點(diǎn)數(shù)有n n2 2個(gè)，個(gè)，則葉子數(shù)（則葉子數(shù)（n n0 0）必定為必定為n n2 21 1 （即（即n0=n2+1）二叉樹(shù)中全部結(jié)點(diǎn)數(shù)二叉樹(shù)中全部結(jié)點(diǎn)數(shù)nn0+n1+n2( (葉子數(shù)葉子數(shù)1 1度結(jié)點(diǎn)數(shù)度結(jié)點(diǎn)數(shù)

16、2 2度結(jié)點(diǎn)數(shù)度結(jié)點(diǎn)數(shù)) )二叉樹(shù)中全部結(jié)點(diǎn)數(shù)二叉樹(shù)中全部結(jié)點(diǎn)數(shù)nb+1 ( ( 總分支數(shù)根結(jié)點(diǎn)總分支數(shù)根結(jié)點(diǎn) ) ) （除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)必有一個(gè)直接前趨，即一個(gè)分支）（除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)必有一個(gè)直接前趨，即一個(gè)分支）總分支數(shù)總分支數(shù)b= n1+2n2 (1(1度結(jié)點(diǎn)必有度結(jié)點(diǎn)必有1 1個(gè)直接后繼，個(gè)直接后繼，2 2度結(jié)點(diǎn)必有度結(jié)點(diǎn)必有2 2個(gè)個(gè)) )n0+n1+n2= n1+2n2 +1, 即即n0=n2+1實(shí)際意義：實(shí)際意義：葉子數(shù)葉子數(shù)2 2度結(jié)點(diǎn)數(shù)度結(jié)點(diǎn)數(shù)1 1abcgeidhfj20滿二叉樹(shù)：滿二叉樹(shù)：一棵深度為一棵深度為k 且有且有2k -1個(gè)結(jié)點(diǎn)的二叉樹(shù)。個(gè)結(jié)點(diǎn)的二叉樹(shù)。

17、（特點(diǎn)：每層都（特點(diǎn)：每層都“充滿充滿”了結(jié)點(diǎn)）了結(jié)點(diǎn)）完全二叉樹(shù)：完全二叉樹(shù)：深度為深度為k 的的，有有n個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為深度為k 的滿二叉樹(shù)中編號(hào)從的滿二叉樹(shù)中編號(hào)從1至至n的結(jié)的結(jié)點(diǎn)一一對(duì)應(yīng)。點(diǎn)一一對(duì)應(yīng)。aobcgekdjfihnml深度為深度為4 4的滿二叉樹(shù)的滿二叉樹(shù)深度為深度為4 4的的完全二叉樹(shù)完全二叉樹(shù)abcgeidhfj為何要研究這兩種特殊形式？為何要研究這兩種特殊形式？因?yàn)樗鼈冊(cè)陧樞虼鎯?chǔ)方式下可以復(fù)原！因?yàn)樗鼈冊(cè)陧樞虼鎯?chǔ)方式下可以復(fù)原！ 完全二叉樹(shù)的特點(diǎn)就是，只有最后一層完全二叉樹(shù)的特點(diǎn)就是，只有最后一層

18、葉子不滿，且全部集中在左邊。葉子不滿，且全部集中在左邊。 這其實(shí)是這其實(shí)是的含義。在的含義。在的的“完全二叉樹(shù)完全二叉樹(shù)”是指是指n1=0的情況。的情況。21對(duì)于兩種特殊形式的二叉樹(shù)（對(duì)于兩種特殊形式的二叉樹(shù)（滿二叉樹(shù)和完全二叉樹(shù)滿二叉樹(shù)和完全二叉樹(shù)），還特別具備以下），還特別具備以下2 2個(gè)性質(zhì)：個(gè)性質(zhì)：2log1n 性質(zhì)性質(zhì)4: 4: 具有具有n n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度必為個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度必為性質(zhì)性質(zhì)5: 5: 對(duì)完全二叉樹(shù)，若從上至下、從左至右編號(hào)，則對(duì)完全二叉樹(shù)，若從上至下、從左至右編號(hào)，則編號(hào)為編號(hào)為i 的結(jié)點(diǎn)，其左孩子編號(hào)必為的結(jié)點(diǎn)，其左孩子編號(hào)必為2i，其右孩子編號(hào)必

19、，其右孩子編號(hào)必為為2i1；其雙親的編號(hào)必為；其雙親的編號(hào)必為i/2（i1 時(shí)為根時(shí)為根, ,除外除外）。）。 證明：當(dāng)證明：當(dāng)i=1i=1時(shí)，由完全二叉樹(shù)的定義，其左孩子是結(jié)點(diǎn)時(shí)，由完全二叉樹(shù)的定義，其左孩子是結(jié)點(diǎn)2 2，右孩子是，右孩子是結(jié)點(diǎn)結(jié)點(diǎn)3 3，成立。，成立。當(dāng)當(dāng)i1i1時(shí)，分兩種情況，此時(shí)只證最簡(jiǎn)單的一種情況，即設(shè)第時(shí)，分兩種情況，此時(shí)只證最簡(jiǎn)單的一種情況，即設(shè)第j j層的第層的第一個(gè)結(jié)點(diǎn)的編號(hào)為一個(gè)結(jié)點(diǎn)的編號(hào)為i i，（由性質(zhì)，（由性質(zhì)2 2知，前知，前j-1j-1層共有層共有2 2j-1j-1-1-1個(gè)結(jié)點(diǎn)，所以個(gè)結(jié)點(diǎn)，所以第第j j層的第一個(gè)結(jié)點(diǎn)的編號(hào)為層的第一個(gè)結(jié)點(diǎn)的編號(hào)

20、為2 2j-1j-1，即，即i= i= 2 2j-1j-1），則其左孩子必為第），則其左孩子必為第j+1j+1層上的第一個(gè)結(jié)點(diǎn)，其編號(hào)為層上的第一個(gè)結(jié)點(diǎn)，其編號(hào)為2 2j j。( (因?yàn)榈谝驗(yàn)榈趈 j層上有層上有2 2j j-1-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)) )，而，而2 2j j=2(2=2(2j-1j-1)=2i)=2i，所以，編號(hào)為，所以，編號(hào)為i i的結(jié)點(diǎn)的左孩子的編號(hào)為的結(jié)點(diǎn)的左孩子的編號(hào)為2i2i。證明：根據(jù)性質(zhì)證明：根據(jù)性質(zhì)2 2，深度為，深度為k k的二叉樹(shù)最多只有的二叉樹(shù)最多只有2 2k k-1-1個(gè)結(jié)點(diǎn)，且完全二叉樹(shù)個(gè)結(jié)點(diǎn)，且完全二叉樹(shù)的定義是與同深度的滿二叉樹(shù)前面編號(hào)相同，即它的總結(jié)

21、點(diǎn)數(shù)的定義是與同深度的滿二叉樹(shù)前面編號(hào)相同，即它的總結(jié)點(diǎn)數(shù)n n位于位于k k層和層和k-1k-1層滿二叉樹(shù)容量之間，即層滿二叉樹(shù)容量之間，即 2 2k-1k-1-1n2-1n2k k-1 -1 或或2 2k-1k-1n n 2 2k k三邊同時(shí)取對(duì)數(shù)，于是有：三邊同時(shí)取對(duì)數(shù)，于是有：k-1logk-1log2 2nk n-lchildlchild) ; ) ; preorder ( preorder (btbt-rchildrchild) ; ) ; bcdefghji 二叉樹(shù)的遍歷二叉樹(shù)的遍歷1 1）中序遍歷二叉樹(shù)）中序遍歷二叉樹(shù)算法思想算法思想: : 若二叉樹(shù)非空，則：若二叉樹(shù)非空，則：

22、1 1）中序遍歷左子樹(shù)）中序遍歷左子樹(shù)2 2）訪問(wèn)根結(jié)點(diǎn)）訪問(wèn)根結(jié)點(diǎn)3 3）中序遍歷右子樹(shù)）中序遍歷右子樹(shù)算法描述算法描述:void inorder (bitree bt) /bt為根結(jié)點(diǎn)指針為根結(jié)點(diǎn)指針 if( bt) /根非空根非空 inorder (bt-lchild) ; inorder (bt-rchild) ; 362 2）后序遍歷二叉樹(shù)）后序遍歷二叉樹(shù)算法思想算法思想: : 若二叉樹(shù)非空，則：若二叉樹(shù)非空，則：1 1）后序遍歷左子樹(shù)）后序遍歷左子樹(shù)2 2）后序遍歷右子樹(shù)）后序遍歷右子樹(shù)3 3）訪問(wèn)根結(jié)點(diǎn)）訪問(wèn)根結(jié)點(diǎn)算法描述算法描述:void postorder (bitree b

23、t) /bt為根結(jié)點(diǎn)指針為根結(jié)點(diǎn)指針 if( bt) /根非空根非空 postorder (bt-lchild) ; postorder (bt-rchild) ; 37對(duì)遍歷的分析：對(duì)遍歷的分析：1. 從前面的三種遍歷算法可以知道：如果將從前面的三種遍歷算法可以知道：如果將print語(yǔ)句抹去，語(yǔ)句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說(shuō)這三種從遞歸的角度看，這三種算法是完全相同的，或者說(shuō)這三種遍歷算法的遍歷算法的訪問(wèn)路徑是相同的，只是訪問(wèn)結(jié)點(diǎn)的時(shí)機(jī)不同訪問(wèn)路徑是相同的，只是訪問(wèn)結(jié)點(diǎn)的時(shí)機(jī)不同。從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑上，每個(gè)結(jié)點(diǎn)經(jīng)過(guò)上，每個(gè)結(jié)點(diǎn)經(jīng)過(guò)3次

24、次。afedcbg第第1次經(jīng)過(guò)時(shí)訪問(wèn)先序遍歷次經(jīng)過(guò)時(shí)訪問(wèn)先序遍歷第第2次經(jīng)過(guò)時(shí)訪問(wèn)中序遍歷次經(jīng)過(guò)時(shí)訪問(wèn)中序遍歷第第3次經(jīng)過(guò)時(shí)訪問(wèn)后序遍歷次經(jīng)過(guò)時(shí)訪問(wèn)后序遍歷2. 2. 二叉樹(shù)遍歷的時(shí)間效率和空間效率二叉樹(shù)遍歷的時(shí)間效率和空間效率時(shí)間效率時(shí)間效率: : /每個(gè)結(jié)點(diǎn)只訪問(wèn)一次每個(gè)結(jié)點(diǎn)只訪問(wèn)一次空間效率空間效率: : /棧占用的最大輔助空間棧占用的最大輔助空間（精確值：樹(shù)深為（精確值：樹(shù)深為k k的遞歸遍歷需要的遞歸遍歷需要k+1k+1個(gè)輔助單元！）個(gè)輔助單元?。?8注：要實(shí)現(xiàn)遍歷運(yùn)算必須先把二叉樹(shù)存入機(jī)內(nèi)。注：要實(shí)現(xiàn)遍歷運(yùn)算必須先把二叉樹(shù)存入機(jī)內(nèi)。思路：思路：利用利用前序前序遍歷來(lái)建樹(shù)遍歷來(lái)建樹(shù)

25、（結(jié)點(diǎn)值陸續(xù)從鍵盤輸入，用（結(jié)點(diǎn)值陸續(xù)從鍵盤輸入，用dlr為宜為宜）bintree createbtpre( ) bintree t; char ch;scanf(“%c”,&ch);if(ch=)t=null; elset=( bintree )malloc(sizeof(bintnode);t-data=ch;t-lchild=createbtpre();t-rchild=createbtpre(); return t;怎樣建樹(shù)？見(jiàn)教材怎樣建樹(shù)？見(jiàn)教材p131p131程序。程序。39知識(shí)回顧：知識(shí)回顧：（1 1）二叉樹(shù)的存儲(chǔ)：二叉樹(shù)的存儲(chǔ)： 順序存儲(chǔ)方式順序存儲(chǔ)方式： 完全二叉樹(shù)完

26、全二叉樹(shù) 滿二叉樹(shù)滿二叉樹(shù) 一般樹(shù)補(bǔ)充成的完全二叉樹(shù)或滿二叉樹(shù)一般樹(shù)補(bǔ)充成的完全二叉樹(shù)或滿二叉樹(shù) 鏈?zhǔn)酱鎯?chǔ)方式鏈?zhǔn)酱鎯?chǔ)方式：適用于各種樹(shù)：適用于各種樹(shù)（2 2）二叉樹(shù)的遍歷二叉樹(shù)的遍歷： 先序遍歷、中序遍歷、后序遍歷、層序遍歷先序遍歷、中序遍歷、后序遍歷、層序遍歷40a ab bj ji id dc cg gf fe eh h1 1、先序遍歷的結(jié)果為：、先序遍歷的結(jié)果為：2 2、中序遍歷的結(jié)果為：、中序遍歷的結(jié)果為：3 3、后序遍歷的結(jié)果為：、后序遍歷的結(jié)果為：a b d h e c f i g ja b d h e c f i g jd h b e a f i c j gd h b e a

27、f i c j gh d e b i f j g ch d e b i f j g c特點(diǎn)：先訪問(wèn)根，特點(diǎn)：先訪問(wèn)根， 再遍歷左子樹(shù)，再遍歷左子樹(shù)， 再遍歷右子樹(shù)再遍歷右子樹(shù)特點(diǎn)：先遍歷左子樹(shù)，特點(diǎn)：先遍歷左子樹(shù)， 再訪問(wèn)根，再訪問(wèn)根， 再遍歷右子樹(shù)再遍歷右子樹(shù)特點(diǎn)：特點(diǎn)： 先遍歷左子樹(shù)，先遍歷左子樹(shù)， 再遍歷右子樹(shù)再遍歷右子樹(shù) 最后訪問(wèn)根，最后訪問(wèn)根，41（3 3）二叉樹(shù)的生成二叉樹(shù)的生成按先序遍歷方式生成按先序遍歷方式生成注意注意：空節(jié)點(diǎn)的輸入：空節(jié)點(diǎn)的輸入42例：例：編寫遞歸算法，計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。編寫遞歸算法，計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。 思路：思路：輸出葉子結(jié)點(diǎn)比較簡(jiǎn)單，用

28、任何一種遍歷算法，凡輸出葉子結(jié)點(diǎn)比較簡(jiǎn)單，用任何一種遍歷算法，凡是左右指針均空者，則為葉子，將其統(tǒng)計(jì)并打印出來(lái)。是左右指針均空者，則為葉子，將其統(tǒng)計(jì)并打印出來(lái)。 dlr(bitreebitree *root) /采用中序遍歷的遞歸算法采用中序遍歷的遞歸算法 if ( root!=null ) /非空二叉樹(shù)條件，還可寫成非空二叉樹(shù)條件，還可寫成if(root)if(root) if(!root-lchild&!root-rchild) /是葉子結(jié)點(diǎn)則統(tǒng)計(jì)并打印是葉子結(jié)點(diǎn)則統(tǒng)計(jì)并打印 sum+; printf(%dn,root-data); dlr(root-lchild); /遞歸遍歷左

29、子樹(shù)，直到葉子處；遞歸遍歷左子樹(shù)，直到葉子處； dlr(root-rchild); /遞歸遍歷右子樹(shù)，直到葉子處；遞歸遍歷右子樹(shù)，直到葉子處； return(0); 43習(xí)題討論：習(xí)題討論： 算法思路：算法思路：只查各結(jié)點(diǎn)后繼鏈表指針，若左只查各結(jié)點(diǎn)后繼鏈表指針，若左( (右右) )孩子的左孩子的左( (右右) )指針?lè)强?，則層次數(shù)加指針?lè)强?，則層次數(shù)加1 1；否則函數(shù)返回。；否則函數(shù)返回。左左子子樹(shù)樹(shù)右右子子樹(shù)樹(shù)根根hlhlhrhrheight=max(hl,hr)+1height=max(hl,hr)+1afedcbg44后序遍歷求二叉樹(shù)的高度遞歸算法：后序遍歷求二叉樹(shù)的高度遞歸算法：in

30、t posttreedepth(bitree bt)int posttreedepth(bitree bt) int hl,hr,max; int hl,hr,max; if(bt!=null) if(bt!=null) hl=posttreedepth hl=posttreedepth（bt-lchild); /bt-lchild); /求左子樹(shù)的深度求左子樹(shù)的深度 hr=posttreedepth(bt-rchild); /hr=posttreedepth(bt-rchild); /求右子樹(shù)的深度求右子樹(shù)的深度 max=hlhr?hl:hr; /max=hlhr?hl:hr; /* *得到

31、左、右子樹(shù)深度較大者得到左、右子樹(shù)深度較大者* */ / return (max+1); / return (max+1); /* *返回樹(shù)的深度返回樹(shù)的深度* */ / else return 0; else return 0; 45 算法思路：算法思路：既然要求從上到下，從左到右，則既然要求從上到下，從左到右，則利用隊(duì)列利用隊(duì)列存放各存放各子樹(shù)結(jié)點(diǎn)的指針是個(gè)好辦法，而不必拘泥于遞歸算法。子樹(shù)結(jié)點(diǎn)的指針是個(gè)好辦法，而不必拘泥于遞歸算法。技巧：技巧：當(dāng)根結(jié)點(diǎn)出隊(duì)后，令其左、右孩子結(jié)點(diǎn)入隊(duì)，而左孩子當(dāng)根結(jié)點(diǎn)出隊(duì)后，令其左、右孩子結(jié)點(diǎn)入隊(duì)，而左孩子出隊(duì)時(shí)又令它的左右孩子結(jié)點(diǎn)入隊(duì)，出隊(duì)時(shí)又令它的左右

32、孩子結(jié)點(diǎn)入隊(duì)，由此便可產(chǎn)生按層次由此便可產(chǎn)生按層次輸出的效果。輸出的效果。adfcgehbvoid layout(bitree root)void layout(bitree root) enqueue(s,root); enqueue(s,root); while(!queueempty(s) while(!queueempty(s) dequeue(s,p); dequeue(s,p); printf( printf(“%c%c”,root-data);,root-data); enqueue(s,p-lchild); enqueue(s,p-lchild); enqueue(s,p-rc

33、hild); enqueue(s,p-rchild); 46算法思路：算法思路：若不用遞歸，則要實(shí)現(xiàn)二叉樹(shù)遍歷的若不用遞歸，則要實(shí)現(xiàn)二叉樹(shù)遍歷的“嵌套嵌套”規(guī)規(guī)則，必用堆棧?？芍苯佑脛t，必用堆棧?？芍苯佑脀hilewhile語(yǔ)句和語(yǔ)句和push/poppush/pop操作。操作。參見(jiàn)教材參見(jiàn)教材p130-131p130-131程序。程序。在中序遍歷中，我們是通過(guò)順著左子樹(shù)的在中序遍歷中，我們是通過(guò)順著左子樹(shù)的根直走到最左端，然后訪問(wèn)最左端元素，根直走到最左端，然后訪問(wèn)最左端元素，遍歷右，再返回上一層，訪問(wèn)結(jié)點(diǎn)，遍歷遍歷右，再返回上一層，訪問(wèn)結(jié)點(diǎn)，遍歷右，然后再訪問(wèn)上一層，這樣又順著左子右，然后

34、再訪問(wèn)上一層，這樣又順著左子樹(shù)的根回到樹(shù)的根回到a a。在遞歸調(diào)用中，返回上一層的操作是通過(guò)在遞歸調(diào)用中，返回上一層的操作是通過(guò)調(diào)用函數(shù)執(zhí)行結(jié)束自然返回上一層的。如調(diào)用函數(shù)執(zhí)行結(jié)束自然返回上一層的。如果不用遞歸，如何返回上一層。果不用遞歸，如何返回上一層。先從先從a a走到走到f f，在從，在從f f返回到返回到a a，最后走到的，最后走到的先訪問(wèn)，所以可以用棧。先訪問(wèn)，所以可以用棧。把根和左子樹(shù)的根全部入棧把根和左子樹(shù)的根全部入棧然后判斷是否有右子樹(shù)，如果有，則遍歷然后判斷是否有右子樹(shù)，如果有，則遍歷右子樹(shù)，右子樹(shù)，hiafedcbg4748證明：由一棵二叉樹(shù)的先序序列和中序序列可唯一確定這

35、棵證明：由一棵二叉樹(shù)的先序序列和中序序列可唯一確定這棵二叉樹(shù)。二叉樹(shù)。 例：例：已知一棵二叉樹(shù)的已知一棵二叉樹(shù)的中序序列中序序列和和后序序列后序序列分別是分別是bdceafhg 和和 decbhgfa，請(qǐng)畫出這棵二叉樹(shù)。，請(qǐng)畫出這棵二叉樹(shù)。分析：分析：由后序遍歷特征，根結(jié)點(diǎn)必在后序序列尾部由后序遍歷特征，根結(jié)點(diǎn)必在后序序列尾部（即（即a a）；由中序遍歷特征，根結(jié)點(diǎn)必在其中間，而且其左部必全部是由中序遍歷特征，根結(jié)點(diǎn)必在其中間，而且其左部必全部是左子樹(shù)子孫左子樹(shù)子孫（即（即bdcebdce），其右部必全部是右子樹(shù)子孫，其右部必全部是右子樹(shù)子孫（即（即fhgfhg）；繼而，根據(jù)后序中的繼而，根據(jù)

36、后序中的decbdecb子樹(shù)可確定子樹(shù)可確定b b為為a a的左孩子，根據(jù)的左孩子，根據(jù)hgfhgf子串可確定子串可確定f f為為a a的右孩子；以此類推。的右孩子；以此類推。49中序遍歷：中序遍歷：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 eghabbff506.4 樹(shù)和森林1. 樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換2. 樹(shù)和森林的存儲(chǔ)方式樹(shù)和森林的存儲(chǔ)方式3. 樹(shù)和森林的遍歷樹(shù)和森林的遍歷511234587961852 利用除根結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)只有唯一的雙利用除根結(jié)點(diǎn)外每

37、個(gè)結(jié)點(diǎn)只有唯一的雙親的性質(zhì)，以一組連續(xù)的空間存儲(chǔ)樹(shù)的結(jié)點(diǎn)，親的性質(zhì)，以一組連續(xù)的空間存儲(chǔ)樹(shù)的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示域指示其雙同時(shí)在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示域指示其雙親結(jié)點(diǎn)在存儲(chǔ)空間中的位置。親結(jié)點(diǎn)在存儲(chǔ)空間中的位置。6.4 樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu)一、一、雙親表示法雙親表示法#define max_tree_size 100#define max_tree_size 100結(jié)點(diǎn)結(jié)構(gòu)：結(jié)點(diǎn)結(jié)構(gòu)：typedef struct ptnode elem data; int parent; ptnode;data parentdata parenttypedef struct ptnode n

38、odesmax_tree_size; int r,n;536 .4 樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu)e ed da ab br rc cf fg gh hk k6h6g3f1e1d0c0b0a-1rk60 01 12 23 34 45 56 67 78 89 9r=0r=0n=10n=1054特點(diǎn)：特點(diǎn)：1 1）求結(jié)點(diǎn)的雙親操作可以在常量時(shí)間內(nèi)實(shí)）求結(jié)點(diǎn)的雙親操作可以在常量時(shí)間內(nèi)實(shí)現(xiàn)；現(xiàn)；2 2）求結(jié)點(diǎn)的孩子時(shí)需要遍歷整個(gè)向量。）求結(jié)點(diǎn)的孩子時(shí)需要遍歷整個(gè)向量。55二、孩子表示法二、孩子表示法孩子結(jié)點(diǎn)：孩子結(jié)點(diǎn)： typedef struct ctnode int child; struct ctno

39、de *next; *childptr;雙親結(jié)點(diǎn)雙親結(jié)點(diǎn): typedef struct elem data; childptr firstchild; ctbox;56樹(shù)結(jié)構(gòu)：樹(shù)結(jié)構(gòu)： typedef structtypedef struct ctbox nodesmax_tree_size; ctbox nodesmax_tree_size; int n,r; int n,r; ctree; ctree; 57f fe eb bc ca ad dg gr=0r=0n=7n=70 01 12 23 34 45 56 6a ab bc cd de ef fg g1 12 23 34 45 56

40、 6-1-10 00 00 02 22 25 558三、樹(shù)的二叉鏈表三、樹(shù)的二叉鏈表 （孩子（孩子- -兄弟）存儲(chǔ)表示法兄弟）存儲(chǔ)表示法 typedef structtypedef struct csnode csnode elem data; elem data; struct csnode struct csnode * *firstchild,firstchild,* *nextsibling;nextsibling; csnode, csnode,* *cstree;cstree;59f fe eb bc ca ad dg ga ab bc ce ed df fg ga ab bc c

41、e ed df fg g601. 樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換轉(zhuǎn)換步驟：轉(zhuǎn)換步驟：step1: step1: 將樹(shù)中同一結(jié)點(diǎn)的兄弟相連將樹(shù)中同一結(jié)點(diǎn)的兄弟相連; ;step2: step2: 保留結(jié)點(diǎn)的最左孩子連線，刪除其它孩保留結(jié)點(diǎn)的最左孩子連線，刪除其它孩子連線；子連線；step3: step3: 將同一孩子的連線繞左孩子旋轉(zhuǎn)將同一孩子的連線繞左孩子旋轉(zhuǎn)4545度角。度角。加線加線抹線抹線旋轉(zhuǎn)旋轉(zhuǎn)討論討論1 1：樹(shù)如何轉(zhuǎn)為二叉樹(shù)？：樹(shù)如何轉(zhuǎn)為二叉樹(shù)？61方法：方法：加加線線抹線抹線旋轉(zhuǎn)旋轉(zhuǎn) abeidfhgc樹(shù)轉(zhuǎn)二叉樹(shù)舉例：樹(shù)轉(zhuǎn)二叉樹(shù)舉例：abeidfhgc兄弟相連兄弟相連

42、長(zhǎng)兄為父長(zhǎng)兄為父孩子靠左孩子靠左62討論討論2 2：二叉樹(shù)怎樣還原為樹(shù)？：二叉樹(shù)怎樣還原為樹(shù)？abeidfhgc要點(diǎn)：把所有右孩子變?yōu)樾值?！要點(diǎn)：把所有右孩子變?yōu)樾值埽?abeidfhgc63法一：法一： 各森林先各自轉(zhuǎn)為二叉樹(shù)；各森林先各自轉(zhuǎn)為二叉樹(shù)； 依次連到前一個(gè)二叉樹(shù)的右子樹(shù)上。依次連到前一個(gè)二叉樹(shù)的右子樹(shù)上。討論討論3 3：森林如何轉(zhuǎn)為二叉樹(shù)？：森林如何轉(zhuǎn)為二叉樹(shù)？法二：法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹(shù)森林直接變兄弟，再轉(zhuǎn)為二叉樹(shù)（參見(jiàn)教材（參見(jiàn)教材p138p138圖圖6.176.17，兩種方法都有轉(zhuǎn)換示意圖），兩種方法都有轉(zhuǎn)換示意圖）即即f=tf=t1 1, t, t2 2, ,

43、 ,t,tm m b=root, lb, rb b=root, lb, rb64abcdefghjiabcdefghjibcdefghji森林轉(zhuǎn)二叉樹(shù)舉例：森林轉(zhuǎn)二叉樹(shù)舉例：（法二）（法二）兄弟相連兄弟相連 長(zhǎng)兄為父長(zhǎng)兄為父孩子靠左孩子靠左 頭根為根頭根為根 65討論討論4 4：二叉樹(shù)如何還原為森林？：二叉樹(shù)如何還原為森林？要點(diǎn)：要點(diǎn)：把最右邊的子樹(shù)變?yōu)樯?，其余右子?shù)變?yōu)樾值馨炎钣疫叺淖訕?shù)變?yōu)樯郑溆嘤易訕?shù)變?yōu)樾值?abcdefghjiabcdefghjiefabcdghji即即b=root, lb, rb f=tb=root, lb, rb f=t1 1, t, t2 2, , ,t,t

44、m m 66樹(shù)的遍歷可有三條搜索路徑：樹(shù)的遍歷可有三條搜索路徑：先根序（次序）遍歷先根序（次序）遍歷 若樹(shù)不空，則先訪問(wèn)根結(jié)點(diǎn)，然后依次先根遍若樹(shù)不空，則先訪問(wèn)根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹(shù)。歷各棵子樹(shù)。后根（次序）遍歷后根（次序）遍歷 若樹(shù)不空，則先依次后根遍歷各棵子樹(shù)，然后若樹(shù)不空，則先依次后根遍歷各棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)。訪問(wèn)根結(jié)點(diǎn)。按層次遍歷按層次遍歷 若樹(shù)不空，則自上而下自左至右訪問(wèn)樹(shù)中每個(gè)若樹(shù)不空，則自上而下自左至右訪問(wèn)樹(shù)中每個(gè)結(jié)點(diǎn)。結(jié)點(diǎn)。67c cf fe eb ba ad dg gh hi ij jk k先根遍歷時(shí)頂點(diǎn)的訪問(wèn)先根遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：次序：a b e f c

45、d g h i j ka b e f c d g h i j k后根遍歷時(shí)頂點(diǎn)的訪問(wèn)后根遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：次序：e f b c i j k h g d ae f b c i j k h g d a層序遍歷時(shí)頂點(diǎn)的訪問(wèn)層序遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：次序：a b c d e f g h i j ka b c d e f g h i j k68 先序遍歷先序遍歷f若森林為空，返回；若森林為空，返回；f訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；f先序遍歷第一棵樹(shù)中根結(jié)點(diǎn)的子樹(shù)森林；先序遍歷第一棵樹(shù)中根結(jié)點(diǎn)的子樹(shù)森林；f先序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。先序遍歷除去第一棵樹(shù)之后剩

46、余的樹(shù)構(gòu)成的森林。 中序遍歷中序遍歷f若森林為空，返回；若森林為空，返回；f中序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林；中序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林；f訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)；訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)；f中序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。中序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。森林的遍歷森林的遍歷abcdefghji69abcdefghkiabcdefglj70路路 徑徑：路徑長(zhǎng)度路徑長(zhǎng)度：樹(shù)的路徑長(zhǎng)度樹(shù)的路徑長(zhǎng)度：帶權(quán)路徑長(zhǎng)度帶權(quán)路徑長(zhǎng)度：樹(shù)的帶權(quán)路徑長(zhǎng)度樹(shù)的帶權(quán)路徑長(zhǎng)度：霍霍 夫夫 曼曼 樹(shù)樹(shù)：6.5 huffman6.5 huffman樹(shù)及其應(yīng)用樹(shù)及其應(yīng)用一、最優(yōu)二叉樹(shù)

47、（一、最優(yōu)二叉樹(shù)（霍夫曼霍夫曼樹(shù)）樹(shù)）由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成路徑上的分支數(shù)目路徑上的分支數(shù)目從樹(shù)根到從樹(shù)根到每一結(jié)點(diǎn)每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。的路徑長(zhǎng)度之和。結(jié)點(diǎn)到根的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積結(jié)點(diǎn)到根的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積預(yù)備知識(shí)：若干術(shù)語(yǔ)預(yù)備知識(shí)：若干術(shù)語(yǔ)debacf g樹(shù)中所有樹(shù)中所有葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和的帶權(quán)路徑長(zhǎng)度之和帶權(quán)路徑長(zhǎng)度最小的樹(shù)。帶權(quán)路徑長(zhǎng)度最小的樹(shù)。aeae的路徑長(zhǎng)度的路徑長(zhǎng)度樹(shù)長(zhǎng)度樹(shù)長(zhǎng)度2 2101071huffmanhuffman樹(shù)簡(jiǎn)介：樹(shù)簡(jiǎn)介：樹(shù)的帶權(quán)路徑長(zhǎng)度如何計(jì)算？樹(shù)的帶權(quán)路徑長(zhǎng)度如何計(jì)算？wplwpl =

48、 = w wk kl lk k k=1k=1n nabdc7524(a)cdab2457(b)bdac7524(c)wpl=36wpl=46wpl= 35哈夫曼樹(shù)則是：哈夫曼樹(shù)則是：wpl wpl 最小的樹(shù)。最小的樹(shù)。huffman樹(shù)樹(shù)weighted path lengthweighted path length72構(gòu)造霍夫曼樹(shù)的基本思想：構(gòu)造霍夫曼樹(shù)的基本思想：構(gòu)造構(gòu)造huffmanhuffman樹(shù)的步驟（即樹(shù)的步驟（即huffmanhuffman算法）：算法）：73操作要點(diǎn)：操作要點(diǎn)：對(duì)權(quán)值的合并、刪除與替換對(duì)權(quán)值的合并、刪除與替換在權(quán)值集合在權(quán)值集合7,5,2,47,5,2,4中，總是

49、合并中，總是合并當(dāng)前值最小當(dāng)前值最小的兩個(gè)權(quán)的兩個(gè)權(quán)構(gòu)造構(gòu)造huffmanhuffman樹(shù)的步驟：樹(shù)的步驟：注：方框表示外結(jié)點(diǎn)（葉子，字符對(duì)應(yīng)的權(quán)值），注：方框表示外結(jié)點(diǎn)（葉子，字符對(duì)應(yīng)的權(quán)值）， 圓框表示內(nèi)結(jié)點(diǎn)（合并后的權(quán)值）。圓框表示內(nèi)結(jié)點(diǎn)（合并后的權(quán)值）。6.2.2 6.2.2 赫夫曼編碼赫夫曼編碼74設(shè)有設(shè)有4 4個(gè)字符個(gè)字符d,i,a,nd,i,a,n，出現(xiàn)的頻度分別為，出現(xiàn)的頻度分別為7,5,2, 7,5,2, 4 4，怎樣編碼才能使它們組成的報(bào)文在網(wǎng)絡(luò)中傳得最快？，怎樣編碼才能使它們組成的報(bào)文在網(wǎng)絡(luò)中傳得最快？法法1 1：等長(zhǎng)編碼等長(zhǎng)編碼。例如用二進(jìn)制編碼來(lái)實(shí)現(xiàn)。例如用二進(jìn)制編碼

50、來(lái)實(shí)現(xiàn)。 取取 d=d=0000，i=i=0101，a=a=1010，n=n=1111法法2 2：不等長(zhǎng)編碼不等長(zhǎng)編碼，例如用前綴編碼來(lái)實(shí)現(xiàn)。，例如用前綴編碼來(lái)實(shí)現(xiàn)。 取取 d=d=0 0; i=; i=1010, a=, a=110110, n=, n=111111adin000111用用二二叉叉樹(shù)樹(shù)來(lái)來(lái)設(shè)設(shè)計(jì)計(jì)前前綴綴編編碼碼最快的編碼是哪個(gè)？最快的編碼是哪個(gè)？ 是非等長(zhǎng)的前綴編碼！是非等長(zhǎng)的前綴編碼！任一個(gè)字符的編任一個(gè)字符的編碼都不是另一個(gè)碼都不是另一個(gè)字符編碼的前綴字符編碼的前綴約定：約定：左分支表示左分支表示0 0右分支表示右分支表示1 1則從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的則從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)

51、的路徑上分支字符組成的字路徑上分支字符組成的字符串作為該葉子的編碼。符串作為該葉子的編碼。75a ac cb bd de ek kf fg gh hi ij j76如何得到電文長(zhǎng)度最短的二進(jìn)制前綴編碼？如何得到電文長(zhǎng)度最短的二進(jìn)制前綴編碼？ 若按各個(gè)字符出現(xiàn)的概率不同而給予不等長(zhǎng)編碼，可望減若按各個(gè)字符出現(xiàn)的概率不同而給予不等長(zhǎng)編碼，可望減少總編碼長(zhǎng)度。少總編碼長(zhǎng)度。d,i,a,nd,i,a,n，出現(xiàn)的頻度分別為，出現(xiàn)的頻度分別為7,5,2,47,5,2,4 假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為w wi,i,，其編碼長(zhǎng)度為，其編碼長(zhǎng)度為l li i, ,電文中只有電

52、文中只有n n種字符，則電文總長(zhǎng)度為種字符，則電文總長(zhǎng)度為=niiliw1=niiliw1 由此可見(jiàn)，設(shè)計(jì)電文總長(zhǎng)最短的二進(jìn)制前綴編碼即為以由此可見(jiàn)，設(shè)計(jì)電文總長(zhǎng)最短的二進(jìn)制前綴編碼即為以n n種字符出現(xiàn)的頻率作權(quán)，設(shè)計(jì)一顆赫夫曼樹(shù)的問(wèn)題，由此得到種字符出現(xiàn)的頻率作權(quán)，設(shè)計(jì)一顆赫夫曼樹(shù)的問(wèn)題，由此得到的二進(jìn)制前綴編碼便稱為赫夫曼編碼。的二進(jìn)制前綴編碼便稱為赫夫曼編碼。 對(duì)應(yīng)到二叉樹(shù)上，若置對(duì)應(yīng)到二叉樹(shù)上，若置wiwi為葉子結(jié)點(diǎn)的權(quán)，為葉子結(jié)點(diǎn)的權(quán)， lili恰為從根恰為從根到葉子的路徑長(zhǎng)度。則：到葉子的路徑長(zhǎng)度。則： 恰為二叉樹(shù)上帶權(quán)路徑長(zhǎng)度。恰為二叉樹(shù)上帶權(quán)路徑長(zhǎng)度。77操作要點(diǎn)：操作要點(diǎn)：

53、按左按左0 0右右1 1對(duì)對(duì)huffmanhuffman樹(shù)的所有分支編號(hào)！樹(shù)的所有分支編號(hào)！d da ai in n1 11 11 10 00 00 0huffmanhuffman編碼結(jié)果：編碼結(jié)果：d=d=0 0, i=, i=1010, a=, a=110110, n=, n=111111wpl=1bitwpl=1bit7 72bit2bit5+3bit(2+4)=5+3bit(2+4)=3535特點(diǎn)：每一碼都不是另一碼的前綴，絕不會(huì)錯(cuò)譯特點(diǎn)：每一碼都不是另一碼的前綴，絕不會(huì)錯(cuò)譯! ! 稱為前綴碼稱為前綴碼huffmanhuffman樹(shù)樹(shù) 與與 huffmanhuffman編碼編碼 掛鉤掛

54、鉤78例例2 2（嚴(yán)題集（嚴(yán)題集6.266.26）：假設(shè)用于通信的電文僅由假設(shè)用于通信的電文僅由8 8個(gè)字母?jìng)€(gè)字母 a, a, b, c, d, e, f, g, hb, c, d, e, f, g, h 構(gòu)成，它們?cè)陔娢闹谐霈F(xiàn)的概率分別構(gòu)成，它們?cè)陔娢闹谐霈F(xiàn)的概率分別為為 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10，試為這試為這8 8個(gè)字母設(shè)計(jì)哈夫曼個(gè)字母設(shè)計(jì)哈夫曼編碼。編碼。如果用如果用0 07 7的二進(jìn)制編碼方案的二進(jìn)制編碼方案又如何？又如何？霍

55、夫曼霍夫曼編碼的基本思想是：概率大的字符用短碼，概率小的用編碼的基本思想是：概率大的字符用短碼，概率小的用長(zhǎng)碼。由于長(zhǎng)碼。由于霍夫曼樹(shù)的霍夫曼樹(shù)的wplwpl最小，說(shuō)明編碼所需要的比特?cái)?shù)最最小，說(shuō)明編碼所需要的比特?cái)?shù)最少。這種編碼已廣泛應(yīng)用于網(wǎng)絡(luò)通信中。少。這種編碼已廣泛應(yīng)用于網(wǎng)絡(luò)通信中。解：解：先將概率放大先將概率放大100100倍，以方便構(gòu)造哈夫曼樹(shù)。倍，以方便構(gòu)造哈夫曼樹(shù)。權(quán)值集合權(quán)值集合 w=7, 19, 2, 6, 32, 3, 21, 10w=7, 19, 2, 6, 32, 3, 21, 10，按哈夫曼樹(shù)構(gòu)造規(guī)則（合并、刪除、替換），可得到哈夫曼樹(shù)。按哈夫曼樹(shù)構(gòu)造規(guī)則（合并、刪除

56、、替換），可得到哈夫曼樹(shù)。79w4=19, 21, w4=19, 21, 28,28, 32 32為清晰起見(jiàn)，重新排序?yàn)闉榍逦鹨?jiàn)，重新排序?yàn)? :w=2, 3, 6, 7, 10, 19, 21, 32w=2, 3, 6, 7, 10, 19, 21, 322 23 35 56 6w1=w1=5,5, 6, 7, 10, 19, 21, 32 6, 7, 10, 19, 21, 32w2=7, 10, w2=7, 10, 11,11, 19, 21, 32 19, 21, 32w3=w3=11, 17,11, 17, 19, 21, 32 19, 21, 32111110107 717172

57、828212119194040w5=w5=28,28,32,32,4040 32326060w6=w6=40,6040,60 w7=w7=100100 100100b bc ca ad de eg gf fh h哈夫曼樹(shù)哈夫曼樹(shù)80對(duì)應(yīng)的哈夫曼編碼（左對(duì)應(yīng)的哈夫曼編碼（左0右右1）：）：2 23 35 56 6111110107 73232171728282121191940406060100100b bc ca ad de eg gf fh h0 00 00 00 00 01 11 11 11 11 11 11 10 00 0符符編碼編碼頻率頻率a0.07b0.19c0.02d0.06e0.

58、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 00000101001110010111011181另一種結(jié)果表示：另一種結(jié)果表示：82voidvoid huffmancoding(huffmantree &ht,huffmancode &hc, huffmancoding(huffmantree &ht,huff

59、mancode &hc,intint * *w,w,intint n) n) if(n=1) if(n=1) returnreturn; ;n n個(gè)權(quán)值構(gòu)造一顆赫夫曼樹(shù)需要的結(jié)點(diǎn)個(gè)數(shù)是：個(gè)權(quán)值構(gòu)造一顆赫夫曼樹(shù)需要的結(jié)點(diǎn)個(gè)數(shù)是：2n-12n-1這這 2n-1 2n-1 個(gè)結(jié)點(diǎn)的存儲(chǔ)方式：個(gè)結(jié)點(diǎn)的存儲(chǔ)方式：鏈?zhǔn)?，鏈?zhǔn)剑樞蝽樞騛wawp pl lr r1 12 23 34 45 56 67 7m mawaw0 00 00 0bwbw0 00 00 0cwcw0 00 00 0dwdw0 00 00 0ewew0 00 00 0fwfw0 00 00 01 12 23 34 45 56 67 7m m0