ch6 樹和二叉樹

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

2、定義樹為n1，曾經(jīng)有，曾經(jīng)有“空樹不是空樹不是 樹樹”的說法，但現(xiàn)在樹的定義已修改。的說法，但現(xiàn)在樹的定義已修改。注注2：樹的定義具有樹的定義具有遞歸性遞歸性，即樹中還有樹。，即樹中還有樹。由由0個(gè)或多個(gè)個(gè)或多個(gè)(n0)結(jié)點(diǎn)組成的有限集合結(jié)點(diǎn)組成的有限集合T T，有且僅，有且僅有有一個(gè)結(jié)點(diǎn)稱為根一個(gè)結(jié)點(diǎn)稱為根（root），），當(dāng)當(dāng)n1時(shí)，其余的結(jié)點(diǎn)分時(shí)，其余的結(jié)點(diǎn)分為為m(m0)個(gè)個(gè)互不相交互不相交的有限集合的有限集合T1,T2，Tm。每。每個(gè)集合本身又是棵樹，被稱作這個(gè)根的個(gè)集合本身又是棵樹，被稱作這個(gè)根的子樹子樹 。6.1 樹的基本概念4樹的表示法有幾種：樹的表示法有幾種：圖形表示法圖形表

3、示法嵌套集合表示法嵌套集合表示法廣義表表示法廣義表表示法目錄表示法目錄表示法左孩子右兄弟表示法左孩子右兄弟表示法這些表示法的示意圖這些表示法的示意圖參見教材參見教材P120樹的抽象數(shù)據(jù)類型定義樹的抽象數(shù)據(jù)類型定義參參見教材見教材P118-1196.1 樹的基本概念5圖形表示法：圖形表示法：教師教師學(xué)生學(xué)生其他人員其他人員20082008級級20092009級級 20102010級級20112011級級河南大學(xué)河南大學(xué)數(shù)學(xué)學(xué)院數(shù)學(xué)學(xué)院計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院物理學(xué)院物理學(xué)院葉子葉子根根子樹子樹6廣義表表示法廣義表表示法( A ( B ( E ( K, L ), F ), C ( G ), D ( H

4、 ( M ), I, J ) ) 根作為根作為由子樹森林組成的由子樹森林組成的表的名字寫在表的左邊表的名字寫在表的左邊datalink 1 link 2.link n麻煩問題：應(yīng)當(dāng)開設(shè)多少個(gè)鏈域麻煩問題：應(yīng)當(dāng)開設(shè)多少個(gè)鏈域?ABCGEIDHFJMLK6.1 樹的基本概念1. 樹的定義樹的定義7左孩子右兄弟表示法左孩子右兄弟表示法數(shù)據(jù)數(shù)據(jù)左孩子左孩子 右兄弟右兄弟ABCGEIDHFJMLK6.1 樹的基本概念1. 樹的定義樹的定義8數(shù)據(jù)對象數(shù)據(jù)對象 D：D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 若若D為空集，則稱為空樹；為空集，則稱為空樹； 否則否則: (1) 在在D中

5、存在唯一的稱為根的數(shù)據(jù)元素中存在唯一的稱為根的數(shù)據(jù)元素root, (2) 當(dāng)當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為時(shí)，其余結(jié)點(diǎn)可分為m (m0)個(gè)互不相交個(gè)互不相交 的有限集的有限集T1, T2, , Tm, 其中每一棵子集本身又其中每一棵子集本身又 是一棵符合本定義的樹，稱為根是一棵符合本定義的樹，稱為根root的子樹。的子樹。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R： 樹的抽象數(shù)據(jù)類型定義樹的抽象數(shù)據(jù)類型定義（見教材（見教材P118-119）6.1 樹的基本概念1. 樹的定義樹的定義9 基本操作：基本操作：查查 找找 類類 插插 入入 類類刪刪 除除 類類6.1 樹的基本概念10Root(T) / 求樹的根結(jié)點(diǎn)求樹的根結(jié)

6、點(diǎn) 查找類：查找類：Value(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的元素值求當(dāng)前結(jié)點(diǎn)的元素值 Parent(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)LeftChild(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的最左孩子求當(dāng)前結(jié)點(diǎn)的最左孩子 RightSibling(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的右兄弟求當(dāng)前結(jié)點(diǎn)的右兄弟TreeEmpty(T) / 判定樹是否為空樹判定樹是否為空樹 TreeDepth(T) / 求樹的深度求樹的深度TraverseTree( T, Visit() ) / 遍歷遍歷6.1 樹的基本概念11InitTree(&T) / 初始化置空樹初始化置空

7、樹 插入類：插入類：CreateTree(&T, definition) / 按定義構(gòu)造樹按定義構(gòu)造樹Assign(T, cur_e, value) / 給當(dāng)前結(jié)點(diǎn)賦值給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T, &p, i, c) / 將以將以c為根的樹插入為結(jié)點(diǎn)為根的樹插入為結(jié)點(diǎn)p的第的第i棵子樹棵子樹6.1 樹的基本概念12 ClearTree(&T) / 將樹清空將樹清空 刪除類：刪除類：DestroyTree(&T) / 銷毀樹的結(jié)構(gòu)銷毀樹的結(jié)構(gòu)DeleteChild(&T, &p, i) / 刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)p的第的第i棵子樹棵子樹6.1 樹的基本概念132. 若干術(shù)語若干術(shù)語即上

8、層的那個(gè)結(jié)點(diǎn)即上層的那個(gè)結(jié)點(diǎn)(直接前驅(qū)直接前驅(qū))即下層結(jié)點(diǎn)的子樹的根即下層結(jié)點(diǎn)的子樹的根(直接后繼直接后繼)同一雙親下的同層結(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)下層子樹中的任一結(jié)點(diǎn)即該結(jié)點(diǎn)下層子樹中的任一結(jié)點(diǎn)ABCGEIDHFJMLK 根根 葉子葉子 森林森林有序樹有序樹有向樹有向樹無序樹無序樹即根結(jié)點(diǎn)即根結(jié)點(diǎn)(沒有前驅(qū)沒有前驅(qū))即終端結(jié)點(diǎn)即終端結(jié)點(diǎn)(沒有后繼沒有后繼)指指m棵不相交的樹的集棵不相交的樹的集合合(例如

9、刪除例如刪除A后的子樹個(gè)數(shù)后的子樹個(gè)數(shù))雙親雙親孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孫子孫子樹從左至右有序，不能互換（左為第一）。子樹從左至右有序，不能互換（左為第一）。有確定的根，樹根和子樹根之間為有向關(guān)系。有確定的根，樹根和子樹根之間為有向關(guān)系。結(jié)點(diǎn)各子樹可互換位置。結(jié)點(diǎn)各子樹可互換位置。142. 若干術(shù)語（續(xù)）若干術(shù)語（續(xù)）即樹的數(shù)據(jù)元素即樹的數(shù)據(jù)元素結(jié)點(diǎn)掛接的子樹數(shù)結(jié)點(diǎn)掛接的子樹數(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)樹的度樹的度樹的深度樹的深度(或高度或高度)ABCGEI

10、DHFJMLK從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）即度為即度為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)的層次）問：問：右上圖中的結(jié)點(diǎn)數(shù)右上圖中的結(jié)點(diǎn)數(shù) ；樹的度；樹的度 ；樹的深度；樹的深度13133 34 4153. 樹的邏輯結(jié)構(gòu)樹的邏輯結(jié)構(gòu) ( (特點(diǎn)特點(diǎn)) )： 一對多（一對多（1:n1:n），有多個(gè)直接后繼（如家譜），有多個(gè)直接后繼（如家譜樹、目錄樹等等

11、），但只有一個(gè)根結(jié)點(diǎn)，樹、目錄樹等等），但只有一個(gè)根結(jié)點(diǎn)，且且子樹之間互不相交子樹之間互不相交。 4. 樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu) 討論討論1：樹是非線性結(jié)構(gòu)，該怎樣存儲？樹是非線性結(jié)構(gòu)，該怎樣存儲？仍然有順序存儲、鏈?zhǔn)酱鎯Φ确绞?。仍然有順序存儲、鏈?zhǔn)酱鎯Φ确绞健?16討論討論3：樹的樹的鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯Ψ桨笐?yīng)該怎樣制定？方案應(yīng)該怎樣制定？可規(guī)定為：可規(guī)定為：從上至下、從左至右從上至下、從左至右將樹的結(jié)點(diǎn)依次存入內(nèi)存。將樹的結(jié)點(diǎn)依次存入內(nèi)存。重大缺陷：重大缺陷：復(fù)原困難（不能唯一復(fù)原就沒有實(shí)用價(jià)值）。復(fù)原困難（不能唯一復(fù)原就沒有實(shí)用價(jià)值）。討論討論2：樹的樹的順序存儲順序存儲方案應(yīng)該怎樣制定？方

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

13、算 要明確：要明確：1. 普通樹（即多叉樹）若不轉(zhuǎn)化為二叉樹，則運(yùn)普通樹（即多叉樹）若不轉(zhuǎn)化為二叉樹，則運(yùn)算很難實(shí)現(xiàn)。算很難實(shí)現(xiàn)。2. 二叉樹的運(yùn)算仍然是插入、刪除、修改、查找、二叉樹的運(yùn)算仍然是插入、刪除、修改、查找、排序等，但這些操作必須建立在排序等，但這些操作必須建立在對樹結(jié)點(diǎn)能夠?qū)浣Y(jié)點(diǎn)能夠“遍歷遍歷”的基礎(chǔ)上！的基礎(chǔ)上?。ū闅v遍歷指每個(gè)結(jié)點(diǎn)都被訪問且僅訪問一次，指每個(gè)結(jié)點(diǎn)都被訪問且僅訪問一次，不遺漏不重復(fù)）。不遺漏不重復(fù)）。本章重點(diǎn)：二叉樹的表示和實(shí)現(xiàn)本章重點(diǎn)：二叉樹的表示和實(shí)現(xiàn)186.2 二叉樹二叉樹為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè) “叉叉” 的樹？

14、的樹？ 二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強(qiáng)；二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強(qiáng)； 可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹，不失一般性?？梢宰C明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹，不失一般性。1. 二叉樹的定義二叉樹的定義2. 二叉樹的性質(zhì)二叉樹的性質(zhì)3. 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)（二叉樹的運(yùn)算（二叉樹的運(yùn)算見見6.3節(jié)節(jié)）191. 二叉樹的定義二叉樹的定義定義：定義：是是n（n0）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為互不相交的、分別稱為左子樹和右子樹左子樹和右子樹的二叉樹組成的二叉樹組成 。邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)： 一對二（一對二（1：2

15、） 基本特征基本特征: : 每個(gè)結(jié)點(diǎn)最多只有兩棵子樹（不存在度大于每個(gè)結(jié)點(diǎn)最多只有兩棵子樹（不存在度大于2 2的結(jié)點(diǎn)）；的結(jié)點(diǎn)）； 左子樹和右子樹次序不能顛倒（有序樹）。左子樹和右子樹次序不能顛倒（有序樹）?；拘螒B(tài)：基本形態(tài)： 5種種/2種種20二叉樹的抽象數(shù)據(jù)類型定義二叉樹的抽象數(shù)據(jù)類型定義（見教材（見教材P121-122）ADT BinaryTree數(shù)據(jù)對象數(shù)據(jù)對象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)于根的說明關(guān)于根的說明 DlDr= /關(guān)于子樹不

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

17、：第提問：第i i層上至少有層上至少有 個(gè)結(jié)點(diǎn)？個(gè)結(jié)點(diǎn)？1 1討論討論2 2：深度為：深度為k k的二叉樹，至多有多少個(gè)結(jié)點(diǎn)？的二叉樹，至多有多少個(gè)結(jié)點(diǎn)？ （利用二進(jìn)制性質(zhì)可輕松求出）（利用二進(jìn)制性質(zhì)可輕松求出）2k-1提問：深度為提問：深度為k k時(shí)至少有時(shí)至少有 個(gè)結(jié)點(diǎn)？個(gè)結(jié)點(diǎn)？k k22討論討論3 3：二叉樹的葉子數(shù)和度為：二叉樹的葉子數(shù)和度為2 2的結(jié)點(diǎn)數(shù)之間有關(guān)系嗎？的結(jié)點(diǎn)數(shù)之間有關(guān)系嗎？性質(zhì)性質(zhì)3: 3: 對于任何一棵二叉樹，若對于任何一棵二叉樹，若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

18、+1）二叉樹中全部結(jié)點(diǎn)數(shù)二叉樹中全部結(jié)點(diǎn)數(shù)nn0+n1+n2( (葉子數(shù)葉子數(shù)1 1度結(jié)點(diǎn)數(shù)度結(jié)點(diǎn)數(shù)2 2度結(jié)點(diǎn)數(shù)度結(jié)點(diǎn)數(shù)) )二叉樹中全部結(jié)點(diǎn)數(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 1ABCGEIDHFJ

19、23對于兩種特殊形式的二叉樹（對于兩種特殊形式的二叉樹（滿二叉樹和完全二叉樹滿二叉樹和完全二叉樹），），還特別具備以下還特別具備以下2 2個(gè)性質(zhì)：個(gè)性質(zhì)：性質(zhì)性質(zhì)4: 4: 具有具有n n個(gè)結(jié)點(diǎn)的完全二叉樹的深度必為個(gè)結(jié)點(diǎn)的完全二叉樹的深度必為loglog2 2nn1 1性質(zhì)性質(zhì)5: 5: 對完全二叉樹，若從上至下、從左至右編號，對完全二叉樹，若從上至下、從左至右編號，則編號為則編號為i 的結(jié)點(diǎn)，其左孩子編號必為的結(jié)點(diǎn)，其左孩子編號必為2i，其右孩子編號，其右孩子編號必為必為2i1；其雙親的編號必為；其雙親的編號必為i/2（i1 時(shí)為根時(shí)為根, ,除外除外）。）。 證明：證明：根據(jù)性質(zhì)根據(jù)性質(zhì)

20、2 2，深度為，深度為k k的二叉樹最多只有的二叉樹最多只有2 2k k-1-1個(gè)結(jié)點(diǎn)，且完全二叉樹個(gè)結(jié)點(diǎn)，且完全二叉樹的定義是與同深度的滿二叉樹前面編號相同，即它的總結(jié)點(diǎn)數(shù)的定義是與同深度的滿二叉樹前面編號相同，即它的總結(jié)點(diǎn)數(shù)n n位于位于k k層和層和k-1k-1層滿二叉樹容量之間，即層滿二叉樹容量之間，即 2 2k-1k-1-1n2-1n2k k-1 -1 或或2 2k-1k-1n n 2 2k k三邊同時(shí)取對數(shù)，于是有：三邊同時(shí)取對數(shù)，于是有：k-1logk-1log2 2nk ndata); /訪問訪問D DLR(root-lchild); /遞歸遍歷左子樹遞歸遍歷左子樹 DLR(r

21、oot-rchild); /遞歸遍歷右子樹遞歸遍歷右子樹 return(0); 二叉樹結(jié)點(diǎn)數(shù)據(jù)類型定義：二叉樹結(jié)點(diǎn)數(shù)據(jù)類型定義：typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree;則三種遍歷算法可寫出則三種遍歷算法可寫出: :2. 二叉樹二叉樹遍歷算法的遞歸實(shí)現(xiàn)遍歷算法的遞歸實(shí)現(xiàn) 43中序遍歷算法中序遍歷算法 LDR (BiTNode *root) if (root !=NULL) LDR(root-lchild); printf (“%d”,root-data); L

22、DR(root-rchild); return(0); 后序遍歷算法后序遍歷算法 LRD (BiTNode *root) if (root !=NULL) LRD(root-lchild); LRD(root-rchild); printf (“%d”,root-data); return(0); 2. 二叉樹二叉樹遍歷算法的遞歸實(shí)現(xiàn)遍歷算法的遞歸實(shí)現(xiàn) 44對遍歷的分析：對遍歷的分析：1. 從前面的三種遍歷算法可以知道：從前面的三種遍歷算法可以知道：如果將如果將print語句抹去，語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種從遞歸的角度看，這三種算法是完全相同的，或者說這三種

23、遍歷算法的遍歷算法的訪問路徑是相同的，只是訪問結(jié)點(diǎn)的時(shí)機(jī)不同訪問路徑是相同的，只是訪問結(jié)點(diǎn)的時(shí)機(jī)不同。從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑上，每個(gè)結(jié)點(diǎn)經(jīng)過上，每個(gè)結(jié)點(diǎn)經(jīng)過3次次。AFEDCBG第第1次經(jīng)過時(shí)訪問先序遍歷次經(jīng)過時(shí)訪問先序遍歷第第2次經(jīng)過時(shí)訪問中序遍歷次經(jīng)過時(shí)訪問中序遍歷第第3次經(jīng)過時(shí)訪問后序遍歷次經(jīng)過時(shí)訪問后序遍歷2. 二叉樹遍歷的時(shí)間效率和空間效率二叉樹遍歷的時(shí)間效率和空間效率時(shí)間效率時(shí)間效率: : /每個(gè)結(jié)點(diǎn)只訪問一次每個(gè)結(jié)點(diǎn)只訪問一次空間效率空間效率: : /棧占用的最大輔助空間棧占用的最大輔助空間（精確值：樹深為（精確值：樹深為k k的遞歸遍歷需要的遞歸遍

24、歷需要k+1k+1個(gè)輔助單元！）個(gè)輔助單元?。?5算法思路：算法思路：若不用遞歸，則要實(shí)現(xiàn)二叉樹遍歷的若不用遞歸，則要實(shí)現(xiàn)二叉樹遍歷的“嵌套嵌套”規(guī)則，規(guī)則， 必用堆棧。必用堆棧。參見教材參見教材P130-131程序。程序。Status InOrderTraverse ( Bitree T, Status (* Visit) (TElemType e) ) InitStack( S ); Push( S, T ); / 根指針進(jìn)棧根指針進(jìn)棧 while ( !StackEmpty(S) ) while( GetTop(S, p) & p) Push( S, p-lchild ); / 向左走到

25、盡頭向左走到盡頭 Pop( S, p ); / 空指針退棧空指針退棧 if ( !StackEmpty(S) ) / 訪問結(jié)點(diǎn)訪問結(jié)點(diǎn), ,向右一步向右一步 Pop( S, p ); if (!Visit ( p-data ) ) return ERROR; Push ( S, p-rchild ); / 將右兒子入棧，則下次循環(huán)時(shí)打印右兒子將右兒子入棧，則下次循環(huán)時(shí)打印右兒子 / if /while return OK; / InOrderTraverse 3. 二叉樹二叉樹遍歷算法的非遞歸實(shí)現(xiàn)遍歷算法的非遞歸實(shí)現(xiàn) 46Status InorderTraverse ( BiTree T, S

26、tatus( *Visit) (TElemType e) InitStack( S ); p=T; while ( p | !StackEmpty(S) ) / 棧不空或樹不空棧不空或樹不空 if ( p ) Push(S,p); p= p-lchild; / 根指針進(jìn)棧根指針進(jìn)棧, ,遍歷左子樹遍歷左子樹 else / 根指針退棧根指針退棧, ,訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn), ,遍歷右子樹遍歷右子樹 Pop( S,p); if ( !Visit( p-data) ) return ERROR; p = p-rchild; / else / while return OK; / InorderTrav

27、erse 47例例5 判斷二叉樹是否為完全二叉樹判斷二叉樹是否為完全二叉樹4. 二叉樹二叉樹遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例例例1 統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)例例3 求二叉樹的深度求二叉樹的深度例例4 按層次輸出二叉樹中的所有結(jié)點(diǎn)按層次輸出二叉樹中的所有結(jié)點(diǎn)例例2 創(chuàng)建一棵二叉樹創(chuàng)建一棵二叉樹48思路：思路：輸出葉子結(jié)點(diǎn)比較簡單，用任何一種遍歷算法，凡輸出葉子結(jié)點(diǎn)比較簡單，用任何一種遍歷算法，凡是左右指針均空者，則為葉子，將其統(tǒng)計(jì)并打印出來。是左右指針均空者，則為葉子，將其統(tǒng)計(jì)并打印出來。 DLR (BiTNode *root) /采用先序遍歷的遞歸算法采用先序遍

28、歷的遞歸算法 if ( root!=NULL ) /非空二叉樹條件，還可寫成非空二叉樹條件，還可寫成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); /遞歸遍歷左子樹，直到葉子處；遞歸遍歷左子樹，直到葉子處； DLR (root-rchild); /遞歸遍歷右子樹，直到葉子處；遞歸遍歷右子樹，直到葉子處； return(0); 例例1 統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)49注：注：要實(shí)現(xiàn)遍歷運(yùn)算

29、必須先把二叉樹存入機(jī)內(nèi)。要實(shí)現(xiàn)遍歷運(yùn)算必須先把二叉樹存入機(jī)內(nèi)。思路：思路：利用利用前序前序遍歷來建樹遍歷來建樹（結(jié)點(diǎn)值陸續(xù)從鍵盤輸入，用（結(jié)點(diǎn)值陸續(xù)從鍵盤輸入，用DLR為宜）為宜）BiTNode createBTpre( ) BiTNode T; char ch; scanf (“%c”, &ch); if (ch=) T=NULL; else T=( Bintree ) malloc (sizeof (BinTNode); T-data=ch; T-lchild=createBTpre(); T-rchild=createBTpre(); return T;例例2 創(chuàng)建一棵二叉樹創(chuàng)建一棵二叉

30、樹50算法思路：算法思路：只查各結(jié)點(diǎn)后繼鏈表指針，若左只查各結(jié)點(diǎn)后繼鏈表指針，若左( (右右) )孩子孩子 的左的左( (右右) )指針非空，則層次數(shù)加指針非空，則層次數(shù)加1 1；否則；否則 函數(shù)返回。函數(shù)返回。當(dāng)當(dāng)T= NULLT= NULL時(shí)時(shí), ,深度為深度為0;0;否則否則, T, T的深度的深度= MAX= MAX左子樹深度左子樹深度, ,右子樹深度右子樹深度+1;+1; 例例3 求二叉樹的深度求二叉樹的深度51算法思路：算法思路：既然要求從上到下，從左到右，則既然要求從上到下，從左到右，則利用利用 隊(duì)列隊(duì)列存放各子樹結(jié)點(diǎn)的指針是個(gè)好辦法，存放各子樹結(jié)點(diǎn)的指針是個(gè)好辦法， 而不必拘泥

31、于遞歸算法。而不必拘泥于遞歸算法。技巧：技巧：當(dāng)根結(jié)點(diǎn)入隊(duì)后，令其左、右孩子結(jié)點(diǎn)入隊(duì)，當(dāng)根結(jié)點(diǎn)入隊(duì)后，令其左、右孩子結(jié)點(diǎn)入隊(duì)， 而根結(jié)點(diǎn)以外的結(jié)點(diǎn)出隊(duì)時(shí)又令它的左右孩子而根結(jié)點(diǎn)以外的結(jié)點(diǎn)出隊(duì)時(shí)又令它的左右孩子 結(jié)點(diǎn)入隊(duì)，結(jié)點(diǎn)入隊(duì)，由此便可產(chǎn)生按層次輸出的效果。由此便可產(chǎn)生按層次輸出的效果。 A B CD E例例4 按層次輸出二叉樹中的所有結(jié)點(diǎn)按層次輸出二叉樹中的所有結(jié)點(diǎn)52算法思路：算法思路：完全二叉樹的特點(diǎn)是：沒有左子樹空而右完全二叉樹的特點(diǎn)是：沒有左子樹空而右 子樹單獨(dú)存在的情況子樹單獨(dú)存在的情況( (前前k-1k-1層都是滿的，層都是滿的， 且第且第k k層左邊也滿）層左邊也滿）。技巧技

32、巧: : 按層序遍歷方式，先把所有結(jié)點(diǎn)按層序遍歷方式，先把所有結(jié)點(diǎn)（不管當(dāng)前結(jié)（不管當(dāng)前結(jié) 點(diǎn)是否有左右孩子）點(diǎn)是否有左右孩子）都入隊(duì)列都入隊(duì)列. .若為完全二叉樹若為完全二叉樹, , 則層序遍歷時(shí)得到的肯定是一個(gè)則層序遍歷時(shí)得到的肯定是一個(gè)連續(xù)的不包含連續(xù)的不包含 空指針的序列空指針的序列. .如果序列中出現(xiàn)了空指針，則說如果序列中出現(xiàn)了空指針，則說 明不是完全二叉樹。明不是完全二叉樹。例例5 判斷二叉樹是否為完全二叉樹判斷二叉樹是否為完全二叉樹53問：問：用二叉鏈表法用二叉鏈表法（l_child, r_child）存儲包含存儲包含n個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的 二叉樹，結(jié)點(diǎn)的指針區(qū)域中會有多少個(gè)空指針

33、？二叉樹，結(jié)點(diǎn)的指針區(qū)域中會有多少個(gè)空指針？分析：分析：用二叉鏈表存儲包含用二叉鏈表存儲包含n n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)必有個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)必有2n 個(gè)鏈域個(gè)鏈域（見二叉鏈表數(shù)據(jù)類型說明）（見二叉鏈表數(shù)據(jù)類型說明）。思考：思考：二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放 有用的信息或線索？有用的信息或線索？我們可以用它來存放當(dāng)前結(jié)點(diǎn)的直接前驅(qū)和后繼等線索，我們可以用它來存放當(dāng)前結(jié)點(diǎn)的直接前驅(qū)和后繼等線索， 以加快查找速度。以加快查找速度。所以，所以， 空指針數(shù)目空指針數(shù)目2n(n-1)=n+1個(gè)個(gè)。n+1 除根結(jié)點(diǎn)外，二叉樹中每一個(gè)結(jié)點(diǎn)除根結(jié)

34、點(diǎn)外，二叉樹中每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親有且僅有一個(gè)雙親（直接（直接前驅(qū)），所以只會有前驅(qū)），所以只會有n1個(gè)結(jié)點(diǎn)的鏈域存放指針，指向非空子個(gè)結(jié)點(diǎn)的鏈域存放指針，指向非空子女結(jié)點(diǎn)（即直接后繼）。女結(jié)點(diǎn)（即直接后繼）。54二.線索二叉樹線索二叉樹（Threaded Binary Tree）普通二叉樹只能找到結(jié)點(diǎn)的左右孩子信息，普通二叉樹只能找到結(jié)點(diǎn)的左右孩子信息，而該結(jié)點(diǎn)而該結(jié)點(diǎn)的直接前驅(qū)和直接后繼只能在遍歷過程中獲得。的直接前驅(qū)和直接后繼只能在遍歷過程中獲得。若將若將遍歷后遍歷后對應(yīng)的有關(guān)前驅(qū)和后繼對應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存預(yù)存起來，則從起來，則從第第一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)開始就能很快開始就能很快“順

35、藤摸瓜順藤摸瓜”而遍歷整個(gè)樹了。而遍歷整個(gè)樹了。兩種解決方法：兩種解決方法：增加兩個(gè)域：增加兩個(gè)域：fwd和和bwd；存放前驅(qū)指針存放前驅(qū)指針存放后繼指針存放后繼指針如何預(yù)存這類信息？如何預(yù)存這類信息？例如中序遍歷結(jié)果：例如中序遍歷結(jié)果：B D C E A F H G，實(shí)際上，實(shí)際上已將二叉已將二叉樹轉(zhuǎn)為樹轉(zhuǎn)為線性排列線性排列，顯然具有唯一前驅(qū)和唯一后繼。，顯然具有唯一前驅(qū)和唯一后繼。利用空鏈域（利用空鏈域（n+1個(gè)空鏈域）個(gè)空鏈域）55規(guī)定：規(guī)定：1）若結(jié)點(diǎn)有左子樹，則）若結(jié)點(diǎn)有左子樹，則lchild指向其左孩子；指向其左孩子； 否則，否則， lchild指向其直接前驅(qū)指向其直接前驅(qū)(即線索

36、即線索)；2）若結(jié)點(diǎn)有右子樹，則）若結(jié)點(diǎn)有右子樹，則rchild指向其右孩子；指向其右孩子； 否則，否則， rchild指向其直接后繼指向其直接后繼(即線索即線索) 。為區(qū)別兩種不同情況，特增加兩個(gè)標(biāo)志域（各為區(qū)別兩種不同情況，特增加兩個(gè)標(biāo)志域（各1bit)lchilddatarchild約定約定:當(dāng)當(dāng)Tag域?yàn)橛驗(yàn)?時(shí)時(shí),表示表示正常正常情況情況;當(dāng)當(dāng)Tag域?yàn)橛驗(yàn)?時(shí)時(shí),表示表示線索線索情況情況.右孩子或后繼右孩子或后繼左孩子或前驅(qū)左孩子或前驅(qū)LTagRTag1. 線索二叉樹的定義線索二叉樹的定義56附：有關(guān)線索二叉樹的幾個(gè)術(shù)語：附：有關(guān)線索二叉樹的幾個(gè)術(shù)語： 線索鏈表：線索鏈表：用用含含

37、Tag的結(jié)點(diǎn)樣式所構(gòu)成的二叉鏈表的結(jié)點(diǎn)樣式所構(gòu)成的二叉鏈表 線線 索：索：指向結(jié)點(diǎn)前驅(qū)和后繼的指針指向結(jié)點(diǎn)前驅(qū)和后繼的指針線索二叉樹：線索二叉樹：加上線索的二叉樹加上線索的二叉樹 線線 索索 化：化：對二叉樹以對二叉樹以某種次序遍歷某種次序遍歷使其變?yōu)榫€索二使其變?yōu)榫€索二叉樹的過程叉樹的過程討論：討論：增加了前驅(qū)和后繼等線索有什么好處？增加了前驅(qū)和后繼等線索有什么好處？能方便找出當(dāng)前結(jié)點(diǎn)的前驅(qū)和后繼，不用能方便找出當(dāng)前結(jié)點(diǎn)的前驅(qū)和后繼，不用堆棧也能遍歷整個(gè)樹。堆棧也能遍歷整個(gè)樹。1. 線索二叉樹的定義線索二叉樹的定義57data AGEIDJHCFBltag0011110101rtag0001

38、010111AGEIDJHCFB例：例：某某先序遍歷先序遍歷結(jié)果如下表所示，請畫出對應(yīng)的結(jié)果如下表所示，請畫出對應(yīng)的二叉樹。二叉樹。 （多帶了兩個(gè)標(biāo)志?。ǘ鄮Я藘蓚€(gè)標(biāo)志?。?82. 線索二叉樹的生成線索二叉樹的生成線索化過程就是線索化過程就是在遍歷過程中修改空指針在遍歷過程中修改空指針的過程：的過程：將空的將空的lchild改為結(jié)點(diǎn)的直接前驅(qū)；改為結(jié)點(diǎn)的直接前驅(qū)；將空的將空的rchild改為結(jié)點(diǎn)的直接后繼。改為結(jié)點(diǎn)的直接后繼。非空指針呢？仍然指向孩子結(jié)點(diǎn)（稱為非空指針呢？仍然指向孩子結(jié)點(diǎn)（稱為“正常情況正常情況”）59ABCGEIDHFroot懸空？懸空？懸空？懸空？解：解：該二叉樹中序遍歷

39、結(jié)果為該二叉樹中序遍歷結(jié)果為: : H, D, I, B, E, A, F, C, G所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：為避免懸空為避免懸空態(tài)，應(yīng)增設(shè)態(tài)，應(yīng)增設(shè)一個(gè)頭結(jié)點(diǎn)一個(gè)頭結(jié)點(diǎn)例例1 1：畫出以下二叉樹對應(yīng)的畫出以下二叉樹對應(yīng)的中序中序線索二叉樹。線索二叉樹。6000A00C00B11E11F11G00D11I11H注：注：此圖中序遍歷結(jié)果為此圖中序遍歷結(jié)果為: : H, D, I, B, E, A, F, C, G0-root0對應(yīng)的中序線索二叉樹存儲結(jié)構(gòu)如圖所示：對應(yīng)的中序線索二叉樹存儲結(jié)構(gòu)如圖所示：61例例2：給定如圖所示二叉樹給定如圖所示二叉樹T T，

40、請畫出與其對應(yīng)的，請畫出與其對應(yīng)的中序線索二叉樹。中序線索二叉樹。 2825405560330854解解: :因?yàn)橹行虮闅v序列是：因?yàn)橹行虮闅v序列是：55 40 25 60 28 08 33 54對應(yīng)線索樹應(yīng)當(dāng)按此規(guī)律連線，即對應(yīng)線索樹應(yīng)當(dāng)按此規(guī)律連線，即在原二叉樹中添加虛線。在原二叉樹中添加虛線。NILNILNILNIL62線索二叉樹的生成算法線索二叉樹的生成算法（算法算法6.6, 見教材見教材P134）目的：目的：在依某種順序遍歷二叉樹時(shí)修改空指針，添加前驅(qū)或后繼。在依某種順序遍歷二叉樹時(shí)修改空指針，添加前驅(qū)或后繼。注解：注解：為方便添加結(jié)點(diǎn)的前驅(qū)或后繼，需要設(shè)置兩個(gè)指針：為方便添加結(jié)點(diǎn)的

41、前驅(qū)或后繼，需要設(shè)置兩個(gè)指針： p指針指針當(dāng)前結(jié)點(diǎn)之指針；當(dāng)前結(jié)點(diǎn)之指針； pre指針指針前驅(qū)結(jié)點(diǎn)之指針。前驅(qū)結(jié)點(diǎn)之指針。技巧：技巧：當(dāng)結(jié)點(diǎn)當(dāng)結(jié)點(diǎn)p的左的左/右域?yàn)榭沼矣驗(yàn)榭諘r(shí)，只改寫它的左域（裝入前驅(qū)時(shí)，只改寫它的左域（裝入前驅(qū)pre），而其右域（后繼）留給下一結(jié)點(diǎn)來填寫。，而其右域（后繼）留給下一結(jié)點(diǎn)來填寫。 或者說，當(dāng)前結(jié)點(diǎn)的指針或者說，當(dāng)前結(jié)點(diǎn)的指針p應(yīng)當(dāng)送到前驅(qū)結(jié)點(diǎn)的空右域中。應(yīng)當(dāng)送到前驅(qū)結(jié)點(diǎn)的空右域中。若若p-lchildNULL, ,則則p-p-LtagLtag=1;=1;p-p-l lchildchildpre; ; /p/p的前驅(qū)結(jié)點(diǎn)指針的前驅(qū)結(jié)點(diǎn)指針pre存入左空域存入左空

42、域若若pre-rchildNULL, 則則pre-pre-RtagRtag1;pre-rchild=p; /p存入其前驅(qū)結(jié)點(diǎn)存入其前驅(qū)結(jié)點(diǎn)pre的右的右空域空域63Status InorderThreading(BiThrTree & Thrt, BiThrTree T) /中序遍歷二叉樹中序遍歷二叉樹T,并將其中序線索化并將其中序線索化, Thrt 指向頭結(jié)點(diǎn)指向頭結(jié)點(diǎn). if ( ! (Thrt = (BiThrTree) malloc ( sizeof (BiThrnode) ) ) exit ( OVERFLOW ) ; Thrt -LTag = Link; Thrt -RTag =

43、Thead; / 建頭結(jié)點(diǎn)建頭結(jié)點(diǎn) Thrt -rchild = Thrt ; /右指針回指右指針回指 if ( !T ) Thrt -lchild = Thrt ; / 若二叉樹空若二叉樹空,則左指針回指則左指針回指 else Thrt -lchild = T; pre = Thrt; /將頭結(jié)點(diǎn)與樹相連將頭結(jié)點(diǎn)與樹相連 InThreading(T); / 中序遍歷進(jìn)行中序線索化中序遍歷進(jìn)行中序線索化 pre -rchild = Thrt; pre -RTag = Thread; /最后一個(gè)結(jié)點(diǎn)線索化最后一個(gè)結(jié)點(diǎn)線索化 Thrt -rchild = pre; return OK; / InO

44、rderThreading64void InThreading (BiThrTree p) if (p) InThreading( p-lchild ); / 左子樹線索化左子樹線索化 if ( !p-lchild ) p-LTag=Thread; p-lchild=pre; / 前驅(qū)線索前驅(qū)線索 if ( !pre-rchild ) pre-RTag=Thread; pre-rchild=p; /后繼線索后繼線索 pre = p; / 保持保持pre指向指向p的前驅(qū)的前驅(qū) InThreading(p-rchild); /右子樹線索化右子樹線索化 / InThreading653. 線索二叉樹

45、的遍歷線索二叉樹的遍歷理論上，只要找到序列中的理論上，只要找到序列中的第一個(gè)結(jié)點(diǎn)第一個(gè)結(jié)點(diǎn)，然后，然后依次訪依次訪問結(jié)點(diǎn)的后繼問結(jié)點(diǎn)的后繼直到后繼為空時(shí)結(jié)束。直到后繼為空時(shí)結(jié)束。在線索化二叉樹中，并不是每個(gè)結(jié)點(diǎn)都能直接找到其在線索化二叉樹中，并不是每個(gè)結(jié)點(diǎn)都能直接找到其后繼的，后繼的，當(dāng)標(biāo)志為當(dāng)標(biāo)志為0時(shí)，時(shí)，R_child= =右孩子地址指針，并非后繼！右孩子地址指針，并非后繼！需要通過一定運(yùn)算才能找到它的后繼。需要通過一定運(yùn)算才能找到它的后繼。以以中序線索二叉樹中序線索二叉樹為例：為例：對葉子結(jié)點(diǎn)（對葉子結(jié)點(diǎn)（RTag=1），直接后繼指針就在其），直接后繼指針就在其rchild域內(nèi)；域內(nèi)；

46、對其他結(jié)點(diǎn)（對其他結(jié)點(diǎn)（RTag=0），直接后繼是其），直接后繼是其右子樹最左下的結(jié)點(diǎn)右子樹最左下的結(jié)點(diǎn)；（因?yàn)橹行虮闅v規(guī)則是（因?yàn)橹行虮闅v規(guī)則是LDR，）66 Status InorderTraverse_Thr(BiThrTree T) P=T-lchild; /p指向根結(jié)點(diǎn)；指向根結(jié)點(diǎn)； while( p!=T) / 空樹或遍歷結(jié)束時(shí)，空樹或遍歷結(jié)束時(shí)，p=T while (p-LTag=link) p=p-lchild; /先找到中序遍歷起點(diǎn)先找到中序遍歷起點(diǎn) if (!visit(p-data) return ERROR; /訪問最左結(jié)點(diǎn)訪問最左結(jié)點(diǎn) while(p-RTag=Thr

47、ead & p-rchild!=T) /p-rchild=T即為最后一個(gè)結(jié)點(diǎn)即為最后一個(gè)結(jié)點(diǎn) p=p-rchild; Visit(p-data); /若有后繼標(biāo)志，則直接提取若有后繼標(biāo)志，則直接提取p-rchild中線索并訪問后繼結(jié)點(diǎn)；中線索并訪問后繼結(jié)點(diǎn)； p=p-rchild; /當(dāng)前結(jié)點(diǎn)右域不空當(dāng)前結(jié)點(diǎn)右域不空或或已經(jīng)找好了后繼已經(jīng)找好了后繼，則一律從結(jié)點(diǎn)，則一律從結(jié)點(diǎn)的右子樹開始重復(fù)的右子樹開始重復(fù) 的全部過程。的全部過程。 return OK; / InOrderTraverse_Thr線索二叉樹的線索二叉樹的中序中序遍歷算法遍歷算法（算法算法6.5, 參見教材參見教材P134）67

48、算法流程：算法流程：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演演示示程程序序686.4 樹和森林樹和森林一一. 樹和森林與二叉樹的轉(zhuǎn)換樹和森林與二叉樹的轉(zhuǎn)換二二. 樹和森林的存儲方式樹和森林的存儲方式三三. 樹和森林的遍歷樹和森林的遍歷69一一. .樹和森林與二叉樹的轉(zhuǎn)換樹和森林與二叉樹的轉(zhuǎn)換轉(zhuǎn)換步驟：轉(zhuǎn)換步驟：step1: 將樹中同一結(jié)點(diǎn)的兄弟相連將樹中同一結(jié)點(diǎn)的兄弟相連; ;step2: 保留結(jié)

49、點(diǎn)的最左孩子連線，刪除其它孩保留結(jié)點(diǎn)的最左孩子連線，刪除其它孩子連線；子連線；step3: 將同一孩子的連線繞左孩子旋轉(zhuǎn)將同一孩子的連線繞左孩子旋轉(zhuǎn)4545度角。度角。加線加線抹線抹線旋轉(zhuǎn)旋轉(zhuǎn)討論討論1：樹如何轉(zhuǎn)為二叉樹？樹如何轉(zhuǎn)為二叉樹？70方法：方法：加加線線抹線抹線旋轉(zhuǎn)旋轉(zhuǎn) abeidfhgc樹轉(zhuǎn)二叉樹舉例：樹轉(zhuǎn)二叉樹舉例：abeidfhgc兄弟相連兄弟相連長兄為父長兄為父孩子靠左孩子靠左71討論討論2：二叉樹怎樣還原為樹？二叉樹怎樣還原為樹？abeidfhgc要點(diǎn)：把所有右孩子變?yōu)樾值?！要點(diǎn)：把所有右孩子變?yōu)樾值埽?abeidfhgc72法一：法一： 各森林先各自轉(zhuǎn)為二叉樹；各森林先各

50、自轉(zhuǎn)為二叉樹； 依次連到前一個(gè)二叉樹的右子樹上。依次連到前一個(gè)二叉樹的右子樹上。討論討論3：森林如何轉(zhuǎn)為二叉樹？森林如何轉(zhuǎn)為二叉樹？法二：法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹森林直接變兄弟，再轉(zhuǎn)為二叉樹（參見教材（參見教材P138圖圖6.17，兩種方法都有轉(zhuǎn)換示意圖），兩種方法都有轉(zhuǎn)換示意圖）即即F=T1, T2, ,Tm B=root, LB, RB73ABCDEFGHJIABCDEFGHJIBCDEFGHJI森林轉(zhuǎn)二叉樹舉例：森林轉(zhuǎn)二叉樹舉例：（法二）（法二）兄弟相連兄弟相連 長兄為父長兄為父孩子靠左孩子靠左 頭根為根頭根為根 74討論討論4 4：二叉樹如何還原為森林？：二叉樹如何還原為森林

51、？要點(diǎn)：要點(diǎn)：把最右邊的子樹變?yōu)樯郑溆嘤易訕渥優(yōu)樾值馨炎钣疫叺淖訕渥優(yōu)樯?，其余右子樹變?yōu)樾值?ABCDEFGHJIABCDEFGHJIEFABCDGHJI即即B=root, LB, RB F=TB=root, LB, RB F=T1 1, T, T2 2, , ,T,Tm m 75二二. .樹和森林的存儲方式樹和森林的存儲方式樹有三種常用存儲方式：樹有三種常用存儲方式：雙親表示法雙親表示法 孩子表示法孩子表示法 孩子兄弟表示法孩子兄弟表示法 (1)(1)用雙親表示法來存儲用雙親表示法來存儲思路：思路：用一組用一組連續(xù)空間連續(xù)空間來存儲樹的結(jié)點(diǎn)，同時(shí)在每個(gè)來存儲樹的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中結(jié)

52、點(diǎn)中附設(shè)一個(gè)指示器附設(shè)一個(gè)指示器，指示其雙親結(jié)點(diǎn)在鏈表中的，指示其雙親結(jié)點(diǎn)在鏈表中的位置。位置。parentsdata結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)dataparents1樹結(jié)構(gòu)樹結(jié)構(gòu) 23n76缺點(diǎn)：求結(jié)點(diǎn)的孩子時(shí)需要遍歷整個(gè)結(jié)構(gòu)。缺點(diǎn)：求結(jié)點(diǎn)的孩子時(shí)需要遍歷整個(gè)結(jié)構(gòu)。01234567812233ABCDEFGHI-1001例例1: 雙親表示法雙親表示法77思路：思路：將每個(gè)結(jié)點(diǎn)的孩子排列起來，形成一個(gè)帶表頭將每個(gè)結(jié)點(diǎn)的孩子排列起來，形成一個(gè)帶表頭（裝父結(jié)點(diǎn)）的線性表（裝父結(jié)點(diǎn)）的線性表（n n個(gè)結(jié)點(diǎn)要設(shè)立個(gè)結(jié)點(diǎn)要設(shè)立n n個(gè)鏈表）；個(gè)鏈表）；再將再將n n個(gè)表頭用數(shù)組存放起來，這樣就形成一個(gè)混合個(gè)表頭用

53、數(shù)組存放起來，這樣就形成一個(gè)混合結(jié)構(gòu)。結(jié)構(gòu)。例如例如：abecdfhgdefghgfedcbah12345678(2)(2)用孩子表示法來存儲用孩子表示法來存儲bc78思路：思路：用二叉鏈表來表示樹，但鏈表中的兩個(gè)用二叉鏈表來表示樹，但鏈表中的兩個(gè)指針域含義不同。指針域含義不同。左指針指向該結(jié)點(diǎn)的第一個(gè)孩子；左指針指向該結(jié)點(diǎn)的第一個(gè)孩子；右指針指向該結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn)。右指針指向該結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn)。nextsiblingdatafirstchild(3)(3)用孩子兄弟表示法來存儲用孩子兄弟表示法來存儲指向左孩子指向左孩子指向右兄弟指向右兄弟79abecdfhgbacedfgh問：問：樹

54、樹二叉樹的二叉樹的“連線連線抹線抹線旋轉(zhuǎn)旋轉(zhuǎn)” 如如何由計(jì)算機(jī)自動實(shí)現(xiàn)？何由計(jì)算機(jī)自動實(shí)現(xiàn)？答：答：用用“左孩子右兄弟左孩子右兄弟”表示法來存儲即可。表示法來存儲即可。 例如例如：801. 樹的遍歷樹的遍歷:按層次遍歷按層次遍歷:先根先根(次序次序)遍歷遍歷:后根后根(次序次序)遍歷遍歷:若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹?？米訕?。若樹不空，則先依次后根遍歷各棵子樹，然后訪問根若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)。結(jié)點(diǎn)。若樹不空，則自上而下自左至右訪問樹中每個(gè)結(jié)點(diǎn)。若樹不空，則自上而下自左至右訪問樹中每個(gè)結(jié)點(diǎn)。三三. .

55、樹和森林的遍歷樹和森林的遍歷81 A B C DE F G H I J K層次遍歷時(shí)頂點(diǎn)的訪問次序：層次遍歷時(shí)頂點(diǎn)的訪問次序： 先根遍歷時(shí)頂點(diǎn)的訪問次序：先根遍歷時(shí)頂點(diǎn)的訪問次序：A B E F C D G H I J K后根遍歷時(shí)頂點(diǎn)的訪問次序：后根遍歷時(shí)頂點(diǎn)的訪問次序：E F B C I J K H G D AA B C D E F G H I J K82層次遍歷時(shí)頂點(diǎn)的訪問次序：層次遍歷時(shí)頂點(diǎn)的訪問次序： A B C DE F G H I J K先根遍歷時(shí)頂點(diǎn)的訪問次序：先根遍歷時(shí)頂點(diǎn)的訪問次序：A B E F C D G H I J K后根遍歷時(shí)頂點(diǎn)的訪問次序：后根遍歷時(shí)頂點(diǎn)的訪問次序

56、：E F B C I J K H G D AA B C D E F G H I J K83 B C DE F G H I J K1. .森林中第一棵樹的根結(jié)點(diǎn)；森林中第一棵樹的根結(jié)點(diǎn)；2. .森林中第一棵樹的子樹森林中第一棵樹的子樹 森林；森林；3. .森林中其它樹構(gòu)成的森林。森林中其它樹構(gòu)成的森林?？梢苑纸獬扇糠郑嚎梢苑纸獬扇糠郑?. 森林的遍歷森林的遍歷84若森林不空，則若森林不空，則訪問森林中第一棵樹的根結(jié)點(diǎn)訪問森林中第一棵樹的根結(jié)點(diǎn);先序遍歷先序遍歷森林中第一棵樹的子樹森林森林中第一棵樹的子樹森林;先序遍歷先序遍歷森林中森林中(除第一棵樹之外除第一棵樹之外)其余樹構(gòu)成的森林。其余樹

57、構(gòu)成的森林。先序遍歷先序遍歷2. 森林的遍歷森林的遍歷即：依次從左至右對森林中的每一棵即：依次從左至右對森林中的每一棵樹樹進(jìn)行進(jìn)行先根遍歷先根遍歷。85 中序遍歷中序遍歷若森林不空，則若森林不空，則中序遍歷中序遍歷森林中第一棵樹的子樹森林森林中第一棵樹的子樹森林;訪問森林中第一棵樹的根結(jié)點(diǎn)訪問森林中第一棵樹的根結(jié)點(diǎn);中序遍歷中序遍歷森林中森林中(除第一棵樹之外除第一棵樹之外)其余樹構(gòu)成的森林。其余樹構(gòu)成的森林。即：依次從左至右對森林中的每一棵即：依次從左至右對森林中的每一棵樹樹進(jìn)行進(jìn)行后根遍歷后根遍歷。2. 森林的遍歷森林的遍歷86 樹的遍歷和二叉樹遍歷樹的遍歷和二叉樹遍歷的對應(yīng)關(guān)系的對應(yīng)關(guān)系

58、 ？先根遍歷先根遍歷后根遍歷后根遍歷樹樹二叉樹二叉樹森林森林先序遍歷先序遍歷先序遍歷先序遍歷中序遍歷中序遍歷中序遍歷中序遍歷876.5 Huffman樹及其應(yīng)用樹及其應(yīng)用一、最優(yōu)二叉樹（一、最優(yōu)二叉樹（赫夫曼赫夫曼樹）樹）二、二、Huffman樹的構(gòu)造樹的構(gòu)造三、三、Huffman編碼編碼88路路 徑徑：路徑長度路徑長度：樹的路徑長度樹的路徑長度：帶權(quán)路徑長度帶權(quán)路徑長度：樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度：赫赫 夫夫 曼曼 樹：樹：一一. .最優(yōu)二叉樹（最優(yōu)二叉樹（赫夫曼赫夫曼樹）樹）由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成。由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成。路徑上的分支數(shù)目。路徑上的分支數(shù)目。從樹根

59、到從樹根到每一結(jié)點(diǎn)每一結(jié)點(diǎn)的路徑長度之和。的路徑長度之和。結(jié)點(diǎn)到根的路徑長度與結(jié)點(diǎn)上權(quán)的乘積。結(jié)點(diǎn)到根的路徑長度與結(jié)點(diǎn)上權(quán)的乘積。debacf g樹中所有樹中所有葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和。的帶權(quán)路徑長度之和。帶權(quán)路徑長度最小的樹。帶權(quán)路徑長度最小的樹。ae的路徑長度的路徑長度樹長度樹長度2106.5 Huffman樹及其應(yīng)用樹及其應(yīng)用89Huffman樹簡介：樹簡介：樹的帶權(quán)路徑長度如何計(jì)算？樹的帶權(quán)路徑長度如何計(jì)算？WPLWPL = = w wk kl lk k k=1k=1n nabdc7524(a)cdab2457(b)bdac7524(c)WPL=36WPL=46WPL= 3

60、5哈夫曼樹則是：哈夫曼樹則是：WPL WPL 最小的樹。最小的樹。Huffman樹樹Weighted Path Length90構(gòu)造赫夫曼樹的基本思想：構(gòu)造赫夫曼樹的基本思想：二二. .Huffman樹的構(gòu)造樹的構(gòu)造構(gòu)造構(gòu)造Huffman樹的步驟（即樹的步驟（即Huffman算法）：算法）：91二二. .Huffman樹的構(gòu)造樹的構(gòu)造構(gòu)造構(gòu)造Huffman樹的步驟（即樹的步驟（即Huffman算法）：算法）：92設(shè)有設(shè)有4個(gè)字符個(gè)字符d,i,a,n，出現(xiàn)的頻度分別為，出現(xiàn)的頻度分別為7,5,2,4， 怎樣編碼才能使它們組成的報(bào)文在網(wǎng)絡(luò)中傳得最快？怎樣編碼才能使它們組成的報(bào)文在網(wǎng)絡(luò)中傳得最快？法