課程：樹和二叉樹

1、教學(xué)要求：教學(xué)要求： 掌握樹的定義及基本術(shù)語，掌握二叉樹的定義、掌握樹的定義及基本術(shù)語，掌握二叉樹的定義、 性質(zhì)和存儲結(jié)構(gòu)，熟練掌握二叉樹的遍歷方法及其性質(zhì)和存儲結(jié)構(gòu)，熟練掌握二叉樹的遍歷方法及其 實現(xiàn)和線索二叉樹的構(gòu)造，掌握樹，森林和二叉樹實現(xiàn)和線索二叉樹的構(gòu)造，掌握樹，森林和二叉樹 之間相互轉(zhuǎn)換的方法，掌握哈夫曼樹的定義和哈夫之間相互轉(zhuǎn)換的方法，掌握哈夫曼樹的定義和哈夫 曼算法，了解哈夫曼編碼的方法。曼算法，了解哈夫曼編碼的方法。 教學(xué)重點與難點：教學(xué)重點與難點： 二叉樹的存儲結(jié)構(gòu)，二叉樹的遍歷及線索二叉二叉樹的存儲結(jié)構(gòu)，二叉樹的遍歷及線索二叉 樹的構(gòu)造，樹、森林和二叉樹之間的相互轉(zhuǎn)換，哈

2、樹的構(gòu)造，樹、森林和二叉樹之間的相互轉(zhuǎn)換，哈 夫曼樹的定義和哈夫曼算法。夫曼樹的定義和哈夫曼算法。 6.1 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語 6.2 6.2 二叉樹二叉樹 6.3 6.3 二叉樹的遍歷與線索化二叉樹的遍歷與線索化 6.4 6.4 樹、森林和二叉樹的關(guān)系樹、森林和二叉樹的關(guān)系 6.5 6.5 哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用 6.6 6.6 總結(jié)與提高總結(jié)與提高 第 六 章 樹 和 二 叉 樹 第3頁 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語 1樹的基本概念樹的基本概念 2樹的圖解表示法樹的圖解表示法 3樹的相關(guān)術(shù)語樹的相關(guān)術(shù)語 4樹的抽象數(shù)據(jù)類型樹的抽象數(shù)據(jù)類型

3、 第4頁 6.1 樹的定義與基本術(shù)語樹的定義與基本術(shù)語 樹定義：樹定義：是是n（n0）個結(jié)點的有限集合）個結(jié)點的有限集合T。當(dāng)。當(dāng)n=0時，時， 稱為空樹；當(dāng)稱為空樹；當(dāng)n0時，該集合滿足如下條件：時，該集合滿足如下條件： (1) 其中必有一個稱為其中必有一個稱為根（根（root）的特定結(jié)點，它沒的特定結(jié)點，它沒 有直接前驅(qū)，但有零個或多個直接后繼。有直接前驅(qū)，但有零個或多個直接后繼。 (2) 其余其余n-1個結(jié)點可以劃分成個結(jié)點可以劃分成m（m0）個互不相交）個互不相交 的有限集的有限集T1，T2，T3，Tm，其中，其中Ti又是一棵樹，又是一棵樹， 稱為稱為根根root的的子樹子樹。每棵子樹

4、的根結(jié)點有且僅有一。每棵子樹的根結(jié)點有且僅有一 個直接前驅(qū)，可有零個或多個直接后繼。個直接前驅(qū)，可有零個或多個直接后繼。 1樹的基本概念樹的基本概念 第5頁 例如：一棵樹的邏輯結(jié)構(gòu)圖（例如：一棵樹的邏輯結(jié)構(gòu)圖（6.1）為：）為： A BCD GFEHIJ KLM 從圖中可以看出它好象一棵倒栽的樹。從圖中可以看出它好象一棵倒栽的樹。 2樹的圖解表示法樹的圖解表示法 1 1）倒置樹結(jié)構(gòu)（樹形表示法）倒置樹結(jié)構(gòu)（樹形表示法） 2 2）文氏圖表示法（嵌套集合形式）文氏圖表示法（嵌套集合形式） 圖圖6.2 3 3）廣義表形式（嵌套擴(kuò)號表示法）廣義表形式（嵌套擴(kuò)號表示法） 4 4）凹入表示法）凹入表示法

5、圖圖6.3 圖圖6.2 文氏圖表示法文氏圖表示法 (A(B(D),C) 廣義表表示法廣義表表示法 3.樹的相關(guān)術(shù)語：樹的相關(guān)術(shù)語： 結(jié)點結(jié)點：包含一個數(shù)據(jù)元素及若干指向其它結(jié)點的分：包含一個數(shù)據(jù)元素及若干指向其它結(jié)點的分 支信息。支信息。 結(jié)點的度：結(jié)點的度：一個結(jié)點的子樹個數(shù)稱為此結(jié)點的度。一個結(jié)點的子樹個數(shù)稱為此結(jié)點的度。 葉結(jié)點：葉結(jié)點：度度為為0的結(jié)點，即無后繼的結(jié)點，也稱為終端結(jié)點。的結(jié)點，即無后繼的結(jié)點，也稱為終端結(jié)點。 分支結(jié)點分支結(jié)點：度：度不為不為0的結(jié)點，也稱為非終端結(jié)點。的結(jié)點，也稱為非終端結(jié)點。 結(jié)點的層次結(jié)點的層次：從根結(jié)點開始定義，根結(jié)點的層次為從根結(jié)點開始定義，根

6、結(jié)點的層次為1，根的，根的 直接后繼的層次為直接后繼的層次為2，依此類推。，依此類推。 結(jié)點的層次編號結(jié)點的層次編號：將樹中的結(jié)點按從上層到下層、同層從左將樹中的結(jié)點按從上層到下層、同層從左 到右的次序排成一個線性序列，依次給它們編以連續(xù)的自然到右的次序排成一個線性序列，依次給它們編以連續(xù)的自然 數(shù)。數(shù)。 第8頁 樹的度：樹的度：樹中所有結(jié)點的度的最大值。樹中所有結(jié)點的度的最大值。 樹的高度（深度）：樹的高度（深度）：樹中所有結(jié)點的層次的最大值。樹中所有結(jié)點的層次的最大值。 有序樹有序樹：在樹：在樹T中，如果各子樹中，如果各子樹Ti之間是有先后次序的，之間是有先后次序的， 則稱為有序樹。則稱為

7、有序樹。 森林森林：m（m0）棵互不相交的樹的集合。將一棵非空樹）棵互不相交的樹的集合。將一棵非空樹 的根結(jié)點刪去，樹就變成一個森林；反之，給森林增加的根結(jié)點刪去，樹就變成一個森林；反之，給森林增加 一個統(tǒng)一的根結(jié)點，森林就變成一棵樹。一個統(tǒng)一的根結(jié)點，森林就變成一棵樹。 同構(gòu)同構(gòu)：對兩棵樹，通過對結(jié)點適當(dāng)?shù)刂孛涂梢允箤煽脴?，通過對結(jié)點適當(dāng)?shù)刂孛涂梢允?兩棵樹完全相等（結(jié)點對應(yīng)相等，對應(yīng)結(jié)點的相關(guān)關(guān)系兩棵樹完全相等（結(jié)點對應(yīng)相等，對應(yīng)結(jié)點的相關(guān)關(guān)系 也像等），則稱這兩棵樹同構(gòu)。也像等），則稱這兩棵樹同構(gòu)。 第9頁 雙親結(jié)點：雙親結(jié)點：一個結(jié)點的直接前驅(qū)稱為該結(jié)點的雙親結(jié)點。上圖一

8、個結(jié)點的直接前驅(qū)稱為該結(jié)點的雙親結(jié)點。上圖 中中A是是B、C的雙親。的雙親。 兄弟結(jié)點：兄弟結(jié)點：同一雙親結(jié)點的孩子結(jié)點之間互稱兄弟結(jié)點。上同一雙親結(jié)點的孩子結(jié)點之間互稱兄弟結(jié)點。上 圖中的結(jié)點圖中的結(jié)點H、I、J互為兄弟結(jié)點?；樾值芙Y(jié)點。 孩子結(jié)點：孩子結(jié)點：一個結(jié)點的直接后繼稱為該結(jié)點的孩子結(jié)點。如上一個結(jié)點的直接后繼稱為該結(jié)點的孩子結(jié)點。如上 圖的圖的B、C是是A的孩子。的孩子。 我們常常借助人類家族樹的術(shù)語，以便于直觀理解結(jié)點我們常常借助人類家族樹的術(shù)語，以便于直觀理解結(jié)點 間的層次關(guān)系。間的層次關(guān)系。 堂兄弟堂兄弟：父親是兄弟關(guān)系或堂兄關(guān)系的結(jié)點稱為堂兄弟結(jié)點。父親是兄弟關(guān)系或堂兄

9、關(guān)系的結(jié)點稱為堂兄弟結(jié)點。 在圖在圖6.1中，結(jié)點中，結(jié)點E、G、H互為堂兄弟?；樘眯值?。 第10頁 祖先結(jié)點祖先結(jié)點：一個結(jié)點的祖先結(jié)點是指從根結(jié)點到該結(jié)點的路徑：一個結(jié)點的祖先結(jié)點是指從根結(jié)點到該結(jié)點的路徑 上的所有結(jié)點。如結(jié)點上的所有結(jié)點。如結(jié)點K的祖先結(jié)點是的祖先結(jié)點是A、B、E。 子孫結(jié)點子孫結(jié)點：一個結(jié)點的直接后繼和間接后繼稱為該結(jié)點的子孫：一個結(jié)點的直接后繼和間接后繼稱為該結(jié)點的子孫 結(jié)點。如結(jié)點結(jié)點。如結(jié)點D的子孫是的子孫是H、I、J、M。 前輩前輩：層號比該結(jié)點小的結(jié)點，都稱為該結(jié)點的前輩。層號比該結(jié)點小的結(jié)點，都稱為該結(jié)點的前輩。 后輩后輩：層號比該結(jié)點大的結(jié)點，都稱為該

10、結(jié)點的后輩。層號比該結(jié)點大的結(jié)點，都稱為該結(jié)點的后輩。 第11頁 A BCD EFGHIJ KLM 結(jié)點結(jié)點A的度：的度：3 結(jié)點結(jié)點B的度：的度：2 結(jié)點結(jié)點M的度：的度：0 葉子：葉子：K，L，F(xiàn)，G，M，I，J 結(jié)點結(jié)點A的孩子：的孩子：B，C，D 結(jié)點結(jié)點B的孩子：的孩子：E，F(xiàn) 結(jié)點結(jié)點I的雙親：的雙親：D 結(jié)點結(jié)點L的雙親：的雙親：E 結(jié)點結(jié)點B，C，D為兄弟為兄弟 結(jié)點結(jié)點K，L為兄弟為兄弟 樹的度：樹的度：3 結(jié)點結(jié)點A的層次：的層次：1 結(jié)點結(jié)點M的層次：的層次：4 樹的深度：樹的深度：4 結(jié)點結(jié)點F，G為堂兄弟為堂兄弟 結(jié)點結(jié)點A是結(jié)點是結(jié)點F，G的祖先的祖先 第12頁 任

11、何一棵非空樹是一個二元組任何一棵非空樹是一個二元組 Tree = （root，F(xiàn)） 其中：其中：root 被稱為根結(jié)點被稱為根結(jié)點 F 被稱為子樹森林被稱為子樹森林 森林森林(forest)： 是是m（m0）棵互）棵互 不相交的樹的集合不相交的樹的集合 A root BCD EFGHIJ MKL F 第13頁 4.樹的抽象數(shù)據(jù)類型樹的抽象數(shù)據(jù)類型 數(shù)據(jù)對象數(shù)據(jù)對象D：一個集合，該集合中的所有元素具有相：一個集合，該集合中的所有元素具有相 同的特性。同的特性。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R：若：若D為空集，則為空樹。若為空集，則為空樹。若D中僅含有中僅含有 一個數(shù)據(jù)元素，則一個數(shù)據(jù)元素，則R為空集，否則為

12、空集，否則R=H，H是如下是如下 的二元關(guān)系：的二元關(guān)系： (1) 在在D中存在唯一的稱為根的數(shù)據(jù)元素中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)，它在關(guān) 系系H下沒有前驅(qū)。下沒有前驅(qū)。 (2) 除除root以外，以外，D中每個結(jié)點在關(guān)系中每個結(jié)點在關(guān)系H下都有且僅有下都有且僅有 一個前驅(qū)。一個前驅(qū)。 第14頁 基本操作基本操作： (1)InitTree（Tree）：）： 將將Tree初始化為一棵空樹。初始化為一棵空樹。 (2) DestoryTree（Tree）：）： 銷毀樹銷毀樹Tree。 (3) CreateTree（Tree）：）： 創(chuàng)建樹創(chuàng)建樹Tree。 (4) TreeEmpty（

13、Tree）：）： 若若Tree為空，則返回為空，則返回TRUE，否則返，否則返 回回FALSE。 (5) Root（Tree）：）： 返回樹返回樹Tree的根。的根。 第15頁 (6) Parent（Tree，x）：）： 樹樹Tree存在，存在，x是是Tree中的某個結(jié)點。中的某個結(jié)點。 若若x為非根結(jié)點，則返回它的雙親，否則返回為非根結(jié)點，則返回它的雙親，否則返回“空空”。 (7) FirstChild（Tree，x）：）： 樹樹Tree存在，存在，x是是Tree中的某個中的某個 結(jié)點。若結(jié)點。若x為非葉子結(jié)點，則返回它的第一個孩子結(jié)點，否為非葉子結(jié)點，則返回它的第一個孩子結(jié)點，否 則返回則

14、返回“空空”。 (8) NextSibling（Tree，x）：）： 樹樹Tree存在，存在，x是是Tree中的某中的某 個結(jié)點。若個結(jié)點。若x不是其雙親的最后一個孩子結(jié)點，則返回不是其雙親的最后一個孩子結(jié)點，則返回x后面后面 的下一個兄弟結(jié)點，否則返回的下一個兄弟結(jié)點，否則返回“空空”。 第16頁 基本操作基本操作: (9) InsertChild（Tree，p，Child）：）： 樹樹Tree存在，存在，p指向指向Tree 中某個結(jié)點，非空樹中某個結(jié)點，非空樹Child與與Tree不相交。將不相交。將Child插入插入Tree中，中， 做做p所指向結(jié)點的子樹。所指向結(jié)點的子樹。 (10)

15、DeleteChild（Tree，p，i）：）： 樹樹Tree存在，存在，p指向指向Tree中中 某個結(jié)點，某個結(jié)點，1id，d為為p所指向結(jié)點的度。刪除所指向結(jié)點的度。刪除Tree中中p所指所指 向結(jié)點的第向結(jié)點的第i棵子樹?？米訕?。 (11) TraverseTree（Tree，Visit（）：（）： 樹樹Tree存在，存在，Visit（）（） 是對結(jié)點進(jìn)行訪問的函數(shù)。按照某種次序?qū)涫菍Y(jié)點進(jìn)行訪問的函數(shù)。按照某種次序?qū)銽ree的每個結(jié)的每個結(jié) 點調(diào)用點調(diào)用Visit（）函數(shù)（）函數(shù)訪問一次且最多一次訪問一次且最多一次。若。若Visit（）失敗，（）失敗， 則操作失敗。則操作失敗。 返

16、回返回 第17頁 6.2 二叉樹二叉樹 6.2.1 二叉樹的定義與基本操作二叉樹的定義與基本操作 6.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì) 6.2.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu) 第18頁 6.2.1 二叉樹的定義與基本操作二叉樹的定義與基本操作 定義定義：我們把滿足以下兩個條件的樹型結(jié)構(gòu)叫做二：我們把滿足以下兩個條件的樹型結(jié)構(gòu)叫做二 叉樹（叉樹（Binary Tree）：）： （1）每個結(jié)點的度都不大于）每個結(jié)點的度都不大于2； （2）每個結(jié)點的孩子結(jié)點次序不能任意顛倒。）每個結(jié)點的孩子結(jié)點次序不能任意顛倒。 下面給出二叉樹的五種基本形態(tài)：下面給出二叉樹的五種基本形態(tài)： (a)(a)空二叉

17、數(shù)空二叉數(shù)(c)(c)只有左子只有左子 樹的二叉樹樹的二叉樹 (b)(b)只有根結(jié)只有根結(jié) 點的二叉樹點的二叉樹 (d)(d)左右子樹均左右子樹均 非空的二叉樹非空的二叉樹 (e)(e)只有右子樹只有右子樹 的二叉樹的二叉樹 二叉樹或為空樹，或是由一個根結(jié)點加上兩棵分別稱為二叉樹或為空樹，或是由一個根結(jié)點加上兩棵分別稱為左子左子 樹樹和和右子樹右子樹的、的、互不交的互不交的二叉樹組成。二叉樹組成。 A B C D E F G HK 根結(jié)點根結(jié)點 左子樹左子樹 右子樹右子樹 第20頁 二叉樹的基本操作：二叉樹的基本操作： Initiate（bt）：將：將bt初始化為空二叉樹。初始化為空二叉樹。

18、(2) Create(bt)：創(chuàng)建一棵非空二叉樹：創(chuàng)建一棵非空二叉樹bt。 (3) Destory（bt）：）： 銷毀二叉樹銷毀二叉樹bt。 (4) Empty（bt）：）： 若若bt為空，則返回為空，則返回TRUE，否，否 則返回則返回FALSE。 (5) Root(bt)： 求二叉樹求二叉樹bt的根結(jié)點。若的根結(jié)點。若bt為空二為空二 叉樹，則函數(shù)返回叉樹，則函數(shù)返回“空空”。 (6) Parent（bt，x）：求雙親函數(shù)。求二叉樹）：求雙親函數(shù)。求二叉樹bt中中 結(jié)點結(jié)點x的雙親結(jié)點。若結(jié)點的雙親結(jié)點。若結(jié)點x是二叉樹的根結(jié)點或是二叉樹的根結(jié)點或 二叉樹二叉樹bt中無結(jié)點中無結(jié)點x，則返

19、回，則返回“空空”。 第21頁 基本操作：基本操作： (7) LeftChild（bt，x）：求左孩子。若結(jié)點）：求左孩子。若結(jié)點x為葉子為葉子 結(jié)點或結(jié)點或x不在不在bt中，則返回中，則返回“空空”。 (8) RightChild（bt，x）：求右孩子。若結(jié)點）：求右孩子。若結(jié)點x為葉子為葉子 結(jié)點或結(jié)點或x不在不在bt中，則返回中，則返回“空空”。 (9) Traverse（bt）: 遍歷操作。按某個次序依次訪問遍歷操作。按某個次序依次訪問 二叉樹中每個結(jié)點一次且僅一次。二叉樹中每個結(jié)點一次且僅一次。 (10) Clear（bt）：清除操作。將二叉樹）：清除操作。將二叉樹bt置為空樹。置為

20、空樹。 第22頁 6.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì) 性質(zhì)性質(zhì)1：在二叉樹的第在二叉樹的第i層上至多有層上至多有2i-1個結(jié)點個結(jié)點(i1)。 當(dāng)當(dāng)i=1時，整個二叉樹只有一根結(jié)點，此時時，整個二叉樹只有一根結(jié)點，此時2i-1=20=1，結(jié)，結(jié) 論成立。論成立。 證明：證明： 假設(shè)假設(shè)i=k時結(jié)論成立，即第時結(jié)論成立，即第k層上結(jié)點總數(shù)最多為層上結(jié)點總數(shù)最多為2k-1個。個。 現(xiàn)證明當(dāng)現(xiàn)證明當(dāng)i=k+1時，結(jié)論成立：時，結(jié)論成立： 因為二叉樹中每個結(jié)點的度最大為因為二叉樹中每個結(jié)點的度最大為2，則第，則第k+1層的結(jié)點總層的結(jié)點總 數(shù)最多為第數(shù)最多為第k層上結(jié)點最大數(shù)的層上結(jié)點最大數(shù)的2倍，

21、即倍，即22k-1=2(k+1)-1，故，故 結(jié)論成立。結(jié)論成立。 第23頁 性質(zhì)性質(zhì)2：深度為：深度為k的二叉樹至多有的二叉樹至多有2k-1個結(jié)點（個結(jié)點（k1）。）。 證明：證明： 因為深度為因為深度為k的二叉樹，其結(jié)點總數(shù)的最大值是將二的二叉樹，其結(jié)點總數(shù)的最大值是將二 叉樹每層上結(jié)點的最大值相加，所以深度為叉樹每層上結(jié)點的最大值相加，所以深度為k的二叉的二叉 樹的結(jié)點總數(shù)至多為：樹的結(jié)點總數(shù)至多為： 第第i層上的最大結(jié)點個數(shù)層上的最大結(jié)點個數(shù)= 2i-1= 2k-1 i=1 k i=1 k 故結(jié)論成立。故結(jié)論成立。 性質(zhì)性質(zhì)3：對任意一棵二叉樹：對任意一棵二叉樹T，若終端結(jié)點數(shù)為，若終

22、端結(jié)點數(shù)為n0， 而其度數(shù)為而其度數(shù)為2的結(jié)點數(shù)為的結(jié)點數(shù)為n2，則，則n0= n2+1 。 證明：設(shè)二叉樹中結(jié)點總數(shù)為證明：設(shè)二叉樹中結(jié)點總數(shù)為n，n1為二叉樹中度為為二叉樹中度為1的結(jié)點總的結(jié)點總 數(shù)。因為二叉樹中所有結(jié)點的度小于等于數(shù)。因為二叉樹中所有結(jié)點的度小于等于2，所以有，所以有 n= n0+ n1+n2 設(shè)二叉樹中分支數(shù)目為設(shè)二叉樹中分支數(shù)目為B，因為除根結(jié)點外，每個結(jié)點均對應(yīng)，因為除根結(jié)點外，每個結(jié)點均對應(yīng) 一個進(jìn)入它的分支，所以有：一個進(jìn)入它的分支，所以有：n=B+1。 又因為二叉樹中的分支都是由度為又因為二叉樹中的分支都是由度為1和度為和度為2的結(jié)點發(fā)出，所以的結(jié)點發(fā)出，所

23、以 分支數(shù)目為：分支數(shù)目為：B=n1+2n2 整理上述兩式可得到：整理上述兩式可得到：n=B+1=n1+2n2+1 將將n= n0+ n1+n2代入上式得出代入上式得出n0+ n1+n2=n1+2n2+1，整理后得，整理后得 n0= n2+1，故結(jié)論成立。，故結(jié)論成立。 第25頁 兩種特殊的二叉樹：兩種特殊的二叉樹： 滿二叉樹滿二叉樹：深度為：深度為k且有且有2k-1個結(jié)點的二叉樹。在滿個結(jié)點的二叉樹。在滿 二叉樹中，每層結(jié)點都是滿的，即每層結(jié)點都具有二叉樹中，每層結(jié)點都是滿的，即每層結(jié)點都具有 最大結(jié)點數(shù)。最大結(jié)點數(shù)。 1 2 3 4567 8910111213 1415 滿二叉樹滿二叉樹

24、第26頁 完全二叉樹完全二叉樹： 1 2 3 4567 8910111213 14 關(guān)系關(guān)系：滿二叉樹：滿二叉樹必為必為完全二叉樹，而完全二叉樹完全二叉樹，而完全二叉樹不一不一 定定是滿二叉樹。是滿二叉樹。 深度為深度為k k，結(jié)點數(shù)為，結(jié)點數(shù)為n n的二叉樹，如果其結(jié)點的二叉樹，如果其結(jié)點1n1n的位置序的位置序 號分別與滿二叉樹的結(jié)點號分別與滿二叉樹的結(jié)點1n1n的位置序號一一對應(yīng)，則為的位置序號一一對應(yīng)，則為 完全二叉樹完全二叉樹 第27頁 性質(zhì)性質(zhì)4：具有：具有n個結(jié)點的個結(jié)點的完全二叉樹完全二叉樹的深度為的深度為 2n +1。 證明：設(shè)證明：設(shè)n個結(jié)點的完全二叉樹的深度為個結(jié)點的完全

25、二叉樹的深度為k，根據(jù)性，根據(jù)性 質(zhì)質(zhì)2可知，可知，k-1層滿二叉樹的結(jié)點總數(shù)為：層滿二叉樹的結(jié)點總數(shù)為： 2k-1-1 k層滿二叉樹的結(jié)點總數(shù)為：層滿二叉樹的結(jié)點總數(shù)為： 2k-1 顯然有：顯然有： 2k-1 - 1 n 2k- 1 2k- 1 n 2k 取對數(shù)有：取對數(shù)有：k -1 log2n 1, 1, 則則 i i 的雙親結(jié)點為的雙親結(jié)點為 i i /2/2 (2)(2)若若2 2* *i i n n, , 則則 i i 無左孩子無左孩子 若若2 2* *i in n, , 則則 i i 結(jié)點的左孩子結(jié)點為結(jié)點的左孩子結(jié)點為2 2* *i i (3)(3)若若 2 2* *i+1i+1

26、 n n , ,則則i i 無右孩子無右孩子 若若 2 2* *i+1i+1n n, , 則則i i的右孩子結(jié)點為的右孩子結(jié)點為2 2* * i i+1+1 用歸納法證明其中的用歸納法證明其中的(2)和和(3)。 第29頁 課堂練習(xí)課堂練習(xí) 1、若一個二叉樹共有、若一個二叉樹共有n個結(jié)點，試問其最小個結(jié)點，試問其最小 高度為多少高度為多少?最大高度為多少？最大高度為多少？ 解：最小高度為解：最小高度為 log log2 2n n + 1 + 1 最大高度為最大高度為n(當(dāng)此二叉樹是歪斜樹時，最大當(dāng)此二叉樹是歪斜樹時，最大 高度為高度為n)。 2、若二叉樹有、若二叉樹有10個樹葉結(jié)點，試問其度為

27、個樹葉結(jié)點，試問其度為2的結(jié)的結(jié) 點有幾個？點有幾個？ n0=n2+1 n2=9 第30頁 3.對于一棵具有對于一棵具有n個結(jié)點的完全二叉樹，一個結(jié)點的編號為個結(jié)點的完全二叉樹，一個結(jié)點的編號為 i(1in)，若它有左孩子則左孩子結(jié)點的編號為，若它有左孩子則左孩子結(jié)點的編號為_，若，若 它有右孩子，則右孩子結(jié)點的編號為它有右孩子，則右孩子結(jié)點的編號為_，若它有雙親，若它有雙親， 則雙親結(jié)點的編號為則雙親結(jié)點的編號為_。 4. 深度為深度為k的二叉樹的結(jié)點總數(shù)最多為的二叉樹的結(jié)點總數(shù)最多為( ). A2k-1 B.2K+1 C.2K-1 D. 2k-1 5.假定一棵樹的廣義表表示為假定一棵樹的廣

28、義表表示為A（D（E，G），），H（I，J），）， 則 樹 中 所 含 的 結(jié) 點 數(shù) 為則 樹 中 所 含 的 結(jié) 點 數(shù) 為 _ _ _ _ _ _ _ _ _ 個 ， 樹 的 深 度 為個 ， 樹 的 深 度 為 _，樹的度為，樹的度為_。 6.在樹中，一個結(jié)點的直接后繼結(jié)點稱為該結(jié)點的在樹中，一個結(jié)點的直接后繼結(jié)點稱為該結(jié)點的_。 一個結(jié)點的直接前趨結(jié)點稱為該結(jié)點的一個結(jié)點的直接前趨結(jié)點稱為該結(jié)點的_。 第31頁 6.2.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu) 二叉樹的結(jié)構(gòu)是非線性的，每一結(jié)點最多可有兩二叉樹的結(jié)構(gòu)是非線性的，每一結(jié)點最多可有兩 個后繼。個后繼。 二叉樹的存儲結(jié)構(gòu)有兩種：

29、二叉樹的存儲結(jié)構(gòu)有兩種：順序存儲順序存儲結(jié)構(gòu)和結(jié)構(gòu)和鏈?zhǔn)芥準(zhǔn)?存儲存儲結(jié)構(gòu)。結(jié)構(gòu)。 第32頁 1.順序存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)：是用一組連續(xù)的存儲單元來存放是用一組連續(xù)的存儲單元來存放 二叉樹的數(shù)據(jù)元素二叉樹的數(shù)據(jù)元素 。 A B C DEFG HIJKL A B C D E F G H IJ K L 二叉樹的順序存儲結(jié)構(gòu)二叉樹的順序存儲結(jié)構(gòu) 第33頁 對于一般的二叉樹，我們必須按照完全二叉樹的對于一般的二叉樹，我們必須按照完全二叉樹的 形式來存儲，就會造成空間的浪費。單支樹就是一形式來存儲，就會造成空間的浪費。單支樹就是一 個極端情況。個極端情況。 A B C D A B C D 單支樹單支樹

30、 第34頁 2. 鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu) 對于任意的二叉樹來說，每個結(jié)點只有兩個孩子，對于任意的二叉樹來說，每個結(jié)點只有兩個孩子， 一個雙親結(jié)點。我們可以設(shè)計每個結(jié)點至少包括三個一個雙親結(jié)點。我們可以設(shè)計每個結(jié)點至少包括三個 域：數(shù)據(jù)域、左孩子域和右孩子域：域：數(shù)據(jù)域、左孩子域和右孩子域： LChildDataRChild二叉鏈表二叉鏈表 D A BC EF G A BC D E F G 二叉樹二叉樹T 二叉鏈表二叉鏈表 第35頁 typedef struct Node DataType data; strct Node * LChild; struct Node * RChild; BiT

31、Node, *BiTree; 用用C語言描述定義二叉樹的二叉鏈表結(jié)構(gòu)如下語言描述定義二叉樹的二叉鏈表結(jié)構(gòu)如下 ： 結(jié)論：若一個二叉樹含有結(jié)論：若一個二叉樹含有n個結(jié)點個結(jié)點，則它的二叉鏈表，則它的二叉鏈表 中必含有中必含有2n個指針域個指針域，其中必有，其中必有n1個空的鏈域個空的鏈域。 第36頁 證明：證明： 分支數(shù)目分支數(shù)目B=n-1，即非空的鏈域有，即非空的鏈域有n-1個，故空鏈域個，故空鏈域 有有2n-(n-1)=n+1個。個。 為了便于找到雙親結(jié)點，可以增加一個為了便于找到雙親結(jié)點，可以增加一個Parent域，域， 以指向該結(jié)點的雙親結(jié)點。采用這種結(jié)點結(jié)構(gòu)存放以指向該結(jié)點的雙親結(jié)點。

32、采用這種結(jié)點結(jié)構(gòu)存放 稱做二叉樹的三叉鏈表存儲結(jié)構(gòu)。稱做二叉樹的三叉鏈表存儲結(jié)構(gòu)。 RChildParentDataLChild三叉鏈表三叉鏈表 第37頁 三叉鏈表的結(jié)點結(jié)構(gòu)三叉鏈表的結(jié)點結(jié)構(gòu) lchild data parent rchild 二叉樹二叉樹 D C E B A A CB DE 三叉鏈表三叉鏈表 返回返回 第38頁 6.3 二叉樹的遍歷與線索化二叉樹的遍歷與線索化 6.3.1 二叉樹的遍歷二叉樹的遍歷 6.3.2 遍歷算法應(yīng)用遍歷算法應(yīng)用 6.3.3 基于棧的遞歸消除基于棧的遞歸消除 6.3.4 線索二叉樹線索二叉樹 6.3.5 由遍歷序列確定二叉樹由遍歷序列確定二叉樹 第39

33、頁 6.3 二叉樹的遍歷與線索化二叉樹的遍歷與線索化 二叉樹的遍歷：指按一定規(guī)律對二叉樹中的每個結(jié)點進(jìn)二叉樹的遍歷：指按一定規(guī)律對二叉樹中的每個結(jié)點進(jìn) 行訪問且僅訪問一次。行訪問且僅訪問一次。 二叉樹的基本結(jié)構(gòu)由二叉樹的基本結(jié)構(gòu)由根結(jié)點、左子樹和右子樹組成根結(jié)點、左子樹和右子樹組成 RChildDataLChild Data LChildLChildRChild 如圖示如圖示 6.3.1 二叉樹的遍歷二叉樹的遍歷 第40頁 用用L、D、R分別表示分別表示遍歷左子樹、訪問根結(jié)點、遍遍歷左子樹、訪問根結(jié)點、遍 歷右子樹歷右子樹，那么對二叉樹的遍歷順序就可以有：，那么對二叉樹的遍歷順序就可以有： 訪

34、問根，遍歷左子樹，遍歷右子樹訪問根，遍歷左子樹，遍歷右子樹(記做記做DLR)。 訪問根，遍歷右子樹，遍歷左子樹訪問根，遍歷右子樹，遍歷左子樹(記做記做DRL)。 遍歷左子樹，訪問根，遍歷右子樹遍歷左子樹，訪問根，遍歷右子樹(記做記做LDR)。 遍歷左子樹，遍歷右子樹，訪問根遍歷左子樹，遍歷右子樹，訪問根 (記做記做LRD)。 遍歷右子樹，訪問根，遍歷左子樹遍歷右子樹，訪問根，遍歷左子樹 (記做記做RDL)。 遍歷右子樹，遍歷左子樹，訪問根遍歷右子樹，遍歷左子樹，訪問根 (記做記做RLD)。 第41頁 在以上六種遍歷方式中，如果我們規(guī)定按在以上六種遍歷方式中，如果我們規(guī)定按先左后右先左后右 的順

35、序，那么就只剩有的順序，那么就只剩有 DLR 、LDR 和和LRD三種。三種。 根據(jù)對根據(jù)對根根的訪問的訪問先后順序不同先后順序不同，分別稱，分別稱DLR為先序為先序 遍歷或先根遍歷；遍歷或先根遍歷；LDR為中序遍歷（對稱遍歷）；為中序遍歷（對稱遍歷）； LRD為后序遍歷。為后序遍歷。 注意：先序、中序、后序遍歷是遞歸定義的，即在注意：先序、中序、后序遍歷是遞歸定義的，即在 其子樹中亦按上述規(guī)律進(jìn)行遍歷。其子樹中亦按上述規(guī)律進(jìn)行遍歷。 第42頁 三種遍歷方法的遞歸定義：三種遍歷方法的遞歸定義： （1）先序遍歷（）先序遍歷（DLR）操作過程：）操作過程： 若二叉樹為空，則空操作，否則依次執(zhí)行如下

36、操作：若二叉樹為空，則空操作，否則依次執(zhí)行如下操作： 訪問根結(jié)點；訪問根結(jié)點； 按先序遍歷左子樹；按先序遍歷左子樹； 按先序遍歷右子樹。按先序遍歷右子樹。 第43頁 A D B C D L R A D L R D L R B D C D L R 先序遍歷序列：先序遍歷序列：A B D C 先序遍歷先序遍歷: 演示演示 第44頁 若二叉樹為空，則空操作，否則依次執(zhí)行如下操作：若二叉樹為空，則空操作，否則依次執(zhí)行如下操作： 按中序遍歷左子樹；按中序遍歷左子樹； 訪問根結(jié)點；訪問根結(jié)點； 按中序遍歷右子樹。按中序遍歷右子樹。 （2）中序遍歷（）中序遍歷（LDR）操作過程）操作過程 第45頁 A D

37、B C L D R B L D R L D R A D C L D R 中序遍歷序列：中序遍歷序列：B D A C 中序遍歷中序遍歷: 演示演示 第46頁 二叉樹中序遍歷的直觀方法：投影法二叉樹中序遍歷的直觀方法：投影法 對于一棵二叉樹，從根結(jié)點所在的層開始，將對于一棵二叉樹，從根結(jié)點所在的層開始，將 所有非空左子樹完全位于當(dāng)前根結(jié)點的左方，將所所有非空左子樹完全位于當(dāng)前根結(jié)點的左方，將所 有非空右子樹完全位于當(dāng)前根結(jié)點的右方，其于各有非空右子樹完全位于當(dāng)前根結(jié)點的右方，其于各 層均按該方法處理。這樣就構(gòu)造好了一棵符合要求層均按該方法處理。這樣就構(gòu)造好了一棵符合要求 的二叉樹，如下圖所示：的二

38、叉樹，如下圖所示： 補充補充 第47頁 A B C DE FG D B E A F C G 在上述二叉樹的正下方畫一條水平直線，將樹中各結(jié)在上述二叉樹的正下方畫一條水平直線，將樹中各結(jié) 點依次垂直投影到這條水平直線上，此時該水平直線點依次垂直投影到這條水平直線上，此時該水平直線 上得到的結(jié)點序列即為該二叉樹的中序遍歷序列上得到的結(jié)點序列即為該二叉樹的中序遍歷序列 (DBEAFCG) 第48頁 （3）后序遍歷（）后序遍歷（LRD）操作過程：）操作過程： 若二叉樹為空，則空操作，否則依次執(zhí)行如下操作：若二叉樹為空，則空操作，否則依次執(zhí)行如下操作： 按后序遍歷左子樹；按后序遍歷左子樹； 按后序遍歷右

39、子樹；按后序遍歷右子樹； 訪問根結(jié)點。訪問根結(jié)點。 第49頁 A D B C L R D L R D L R D A D C L R D 后序遍歷序列：后序遍歷序列： D B C A 后序遍歷后序遍歷: B 演示演示 第50頁 對于如下圖的二叉樹，其先序、中序、后序遍歷的序?qū)τ谌缦聢D的二叉樹，其先序、中序、后序遍歷的序 列為：列為： 先序遍歷：先序遍歷： A、B、D、F、G、C、E、H 。 中序遍歷：中序遍歷： B、F、D、G、A、C、E、H 。 后序遍歷：后序遍歷： F、G、D、B、H、E、C、A 。 A BC D FG E H 第51頁 - + / a* b- ef cd 先序遍歷：先序遍

40、歷： 中序遍歷：中序遍歷： 后序遍歷：后序遍歷： 層次遍歷：層次遍歷： - + a * b - c d / e f -+a*b-cd/ef - +a *b - c d/e f -+a*b-c d/e f 第52頁 以二叉鏈表作為存儲結(jié)構(gòu)，討論二叉樹的遍歷算法以二叉鏈表作為存儲結(jié)構(gòu)，討論二叉樹的遍歷算法 1) 先序遍歷先序遍歷 void PreOrder(BiTree BiTree root) /*先序遍歷二叉樹先序遍歷二叉樹, root為指向二叉樹為指向二叉樹(或某一子樹或某一子樹)根結(jié)點的指針根結(jié)點的指針*/ if (root!=NULL) Visit(root -data); /*訪問根結(jié)

41、點訪問根結(jié)點*/ PreOrder(root -LChild); /*先序遍歷左子樹先序遍歷左子樹*/ PreOrder(root -RChild); /*先序遍歷右子樹先序遍歷右子樹*/ 第53頁 2) 中序遍歷中序遍歷 void InOrder(BiTree root) /*中序遍歷二叉樹中序遍歷二叉樹, root為指向二叉樹為指向二叉樹(或某一子樹或某一子樹)根結(jié)點的指針根結(jié)點的指針*/ if (root!=NULL) InOrder(root -LChild); /*中序遍歷左子樹中序遍歷左子樹*/ Visit(root -data); /*訪問根結(jié)點訪問根結(jié)點*/ InOrder(r

42、oot -RChild); /*中序遍歷右子樹中序遍歷右子樹*/ 第54頁 3) 后序遍歷后序遍歷 void PostOrder(BiTree root) /* 后序遍歷二叉樹，后序遍歷二叉樹，root為指向二叉樹為指向二叉樹(或某一子樹或某一子樹)根結(jié)點的指針根結(jié)點的指針*/ if(root!=NULL) PostOrder(root -LChild); /*后序遍歷左子樹后序遍歷左子樹*/ PostOrder(root -RChild); /*后序遍歷右子樹后序遍歷右子樹* Visit(root -data); /*訪問根結(jié)點訪問根結(jié)點*/ 第55頁 以中序遍歷為例來說明中序遍歷二叉樹的遞

43、歸過程以中序遍歷為例來說明中序遍歷二叉樹的遞歸過程 B D 第一次經(jīng)過第一次經(jīng)過 第二次經(jīng)過第二次經(jīng)過 第三次經(jīng)過第三次經(jīng)過 A B D C E 主程序主程序 Pre( T ) 返回 返回 pre(T R); 返回 返回 pre(T R); A CB D T B printf(B); pre(T L); B T A printf(A); pre(T L); A T D printf(D); pre(T L); D T C printf(C); pre(T L); C 返回 T 左是空返回 pre(T R); T 左是空返回 T 右是空返回 T 左是空返回 T 右是空返回 pre(T R); 先

44、序序列：A B D C void Preorder (BiTree T, void( *visit)(TElemType Preorder(T-lchild, visit); Preorder(T-rchild, visit); 第57頁 1.若二叉樹有若二叉樹有12個結(jié)點而且度為個結(jié)點而且度為1的個數(shù)有的個數(shù)有5 個，試問該樹中葉子結(jié)點有幾個？個，試問該樹中葉子結(jié)點有幾個？ 2. A Tree is represented as A(B(CD)E(F(G)H(I(JK)L(MNO) Please draw the tree 練習(xí)：練習(xí)： 3 3. .下面的二叉樹中，下面的二叉樹中，( )不是

45、完全二叉樹。不是完全二叉樹。 4 4. .先根序列和中根序列相同的非空二叉樹是先根序列和中根序列相同的非空二叉樹是（ ）。 A.A.任一結(jié)點均無右子樹的非空二叉樹任一結(jié)點均無右子樹的非空二叉樹 B.B.根結(jié)點無右子樹的非空二叉樹根結(jié)點無右子樹的非空二叉樹 C.C.任一結(jié)點均無左子樹的非空二叉樹任一結(jié)點均無左子樹的非空二叉樹 D.D.根結(jié)點無左子樹的非空二叉樹根結(jié)點無左子樹的非空二叉樹 6.3.2 遍歷算法應(yīng)用遍歷算法應(yīng)用 1.輸出二叉樹中的結(jié)點輸出二叉樹中的結(jié)點 【算法描述】【算法描述】 void PreOrder(BiTree BiTree root) /* 先序遍歷輸出二叉樹結(jié)點先序遍歷輸

46、出二叉樹結(jié)點, root為指向二叉樹根結(jié)點的指針為指向二叉樹根結(jié)點的指針 */ if (root!=NULL) printf (root -data); /* 輸出根結(jié)點輸出根結(jié)點 */ PreOrder(root -LChild); /* 先序遍歷左子樹先序遍歷左子樹 */ PreOrder(root -RChild); /* 先序遍歷右子樹先序遍歷右子樹 */ 【算法思想】【算法思想】輸出二叉樹中的結(jié)點并無次序要求，因此可用輸出二叉樹中的結(jié)點并無次序要求，因此可用 三種遍歷算法中的任何一種完成，只需將訪問操作具體變?yōu)槿N遍歷算法中的任何一種完成，只需將訪問操作具體變?yōu)?打印操作即可。下面給

47、出采用前序遍歷實現(xiàn)的算法。打印操作即可。下面給出采用前序遍歷實現(xiàn)的算法。 2.輸出二叉樹中的葉子結(jié)點輸出二叉樹中的葉子結(jié)點 【算法思想】【算法思想】輸出二叉樹中的葉子結(jié)點與輸出輸出二叉樹中的葉子結(jié)點與輸出 二叉樹中的結(jié)點相比，它是一個有條件的輸出二叉樹中的結(jié)點相比，它是一個有條件的輸出 問題，即在遍歷過程中走到每一個結(jié)點時需進(jìn)問題，即在遍歷過程中走到每一個結(jié)點時需進(jìn) 行測試，看是否滿足葉子結(jié)點的條件。行測試，看是否滿足葉子結(jié)點的條件。 第61頁 【算法描述】【算法描述】 void PreOrder(BiTree BiTree root) /* 先序遍歷輸出二叉樹中的葉子結(jié)點先序遍歷輸出二叉樹中

48、的葉子結(jié)點 , root為指向二叉樹根結(jié)點為指向二叉樹根結(jié)點 的指針的指針 */ if (root!=NULL) if (root -LChild=NULL /* 輸出葉子結(jié)點輸出葉子結(jié)點 */ PreOrder(root -LChild); /* 先序遍歷左子樹先序遍歷左子樹 */ PreOrder(root -RChild); /* 先序遍歷右子樹先序遍歷右子樹 */ 第62頁 3.統(tǒng)計葉子結(jié)點數(shù)目統(tǒng)計葉子結(jié)點數(shù)目 【算法思想】【算法思想】統(tǒng)計二叉樹中的葉子結(jié)點數(shù)目并統(tǒng)計二叉樹中的葉子結(jié)點數(shù)目并 無次序要求，因此可用三種遍歷算法中的任何無次序要求，因此可用三種遍歷算法中的任何 一種完成，只

49、需將訪問操作具體變?yōu)榕袛嗍欠褚环N完成，只需將訪問操作具體變?yōu)榕袛嗍欠?為葉子結(jié)點及統(tǒng)計操作即可。為葉子結(jié)點及統(tǒng)計操作即可。 方法一：方法一： 第63頁 【算法描述】【算法描述】 / /* * LeafCount LeafCount為保存葉子結(jié)點數(shù)目的全局變量為保存葉子結(jié)點數(shù)目的全局變量, ,調(diào)用之前初始調(diào)用之前初始 化值為化值為0 0 * */ / void leaf(BiTree root) void leaf(BiTree root) if(root!=NULL) if(root!=NULL) leaf(root-LChild);leaf(root-RChild); leaf(root-L

50、Child);leaf(root-RChild); if (root -LChild=NULL LeafCount+; 【算法思想】【算法思想】采用遞歸算法，如果是空樹，返采用遞歸算法，如果是空樹，返 回回0 0；如果只有一個結(jié)點，返回；如果只有一個結(jié)點，返回1 1；否則為左右；否則為左右 子樹的葉子結(jié)點數(shù)之和。子樹的葉子結(jié)點數(shù)之和。 方法二：方法二： 3.統(tǒng)計葉子結(jié)點數(shù)目統(tǒng)計葉子結(jié)點數(shù)目 第65頁 【算法描述】【算法描述】 int leaf(BiTree root) int LeafCount; if(root=NULL) LeafCount =0; else if (root-LChild

51、=NULL) else /* 葉子數(shù)為左右子樹的葉子數(shù)目之和葉子數(shù)為左右子樹的葉子數(shù)目之和 */ LeafCount =leaf(root-LChild)+leaf(root-RChild); return LeafCount; 4.建立二叉鏈表方式存儲的二叉樹建立二叉鏈表方式存儲的二叉樹 【算法思想】【算法思想】采用類似先序遍歷的遞歸算法，采用類似先序遍歷的遞歸算法， 首先讀入當(dāng)前根結(jié)點的數(shù)據(jù)，如果是首先讀入當(dāng)前根結(jié)點的數(shù)據(jù)，如果是.則將則將 當(dāng)前樹根置為空，否則申請一個新結(jié)點，存入當(dāng)前樹根置為空，否則申請一個新結(jié)點，存入 當(dāng)前根結(jié)點的數(shù)據(jù)，分別用當(dāng)前根結(jié)點的左子當(dāng)前根結(jié)點的數(shù)據(jù)，分別用當(dāng)前

52、根結(jié)點的左子 域和右子域進(jìn)行遞歸調(diào)用，創(chuàng)建左右子樹。域和右子域進(jìn)行遞歸調(diào)用，創(chuàng)建左右子樹。 第67頁 【算法描述】【算法描述】 void CreateBiTree(BiTree *bt) char ch; ch=getchar(); if(ch=.) *bt=NULL; else *bt=(BiTree)malloc(sizeof(BiTNode); (*bt)-data=ch; CreateBiTree( CreateBiTree( 第68頁 5.求二叉樹的高度求二叉樹的高度 設(shè)函數(shù)表示二叉樹設(shè)函數(shù)表示二叉樹bt的高度，則遞歸定義如下的高度，則遞歸定義如下: 若若bt為空，則高度為為空，則高

53、度為0 若若bt非空，其高度應(yīng)為其左右子樹高度的最大值加非空，其高度應(yīng)為其左右子樹高度的最大值加1 左左 子子 樹樹 右右 子子 樹樹 bt hlhr High=max(hl+hr)+1 第69頁 【算法思想】【算法思想】二叉樹二叉樹bt的高度可以遞歸定義的高度可以遞歸定義 如下：如下： l l 若若bt為空，則高度為為空，則高度為0 l l 若若bt非空，其高度應(yīng)為其左右子樹高度的非空，其高度應(yīng)為其左右子樹高度的 最大值加最大值加1 第70頁 【算法描述】【算法描述】 int PostTreeDepth(BiTree bt) /* 后序遍歷求二叉樹后序遍歷求二叉樹bt高度的高度的 遞歸算法遞

54、歸算法 */ int hl, hr, max; if(bt!=NULL) hl=PostTreeDepth(bt-LChild); /* 求左子樹的深度求左子樹的深度 */ hr=PostTreeDepth(bt-RChild); /* 求右子樹的深度求右子樹的深度 */ max=hlhr?hl:hr; /* 得到左、右子樹深度較大者得到左、右子樹深度較大者*/ return(max+1); /* 返回樹的深度返回樹的深度 */ else return(0); /* 如果是空樹，則返回如果是空樹，則返回0 */ 求二叉樹的高度是也可用前序遍歷的方式實現(xiàn)。求二叉樹的高度是也可用前序遍歷的方式實現(xiàn)

55、。 【算法思想】【算法思想】二叉樹的高度（深度）為二叉樹中二叉樹的高度（深度）為二叉樹中 結(jié)點層次的最大值。設(shè)根結(jié)點為第結(jié)點層次的最大值。設(shè)根結(jié)點為第1層的結(jié)點，層的結(jié)點， 所有所有h層的結(jié)點的左右孩子結(jié)點在層的結(jié)點的左右孩子結(jié)點在h+1層。故可以層。故可以 通過遍歷計算二叉樹中的每個結(jié)點的層次，其中通過遍歷計算二叉樹中的每個結(jié)點的層次，其中 最大值即為二叉樹的高度。最大值即為二叉樹的高度。 第72頁 【算法描述】【算法描述】 void PreTreeDepth(BiTeee bt, int h) /* 先序遍歷求二叉樹先序遍歷求二叉樹bt高度的遞歸算法，高度的遞歸算法，h為為bt指向結(jié)點指向

56、結(jié)點 所在層次，初值為所在層次，初值為1*/ /*depth為當(dāng)前求得的最大層次，為全局變量，調(diào)用前初為當(dāng)前求得的最大層次，為全局變量，調(diào)用前初 值為值為0 */ if(bt!=NULL) if(hdepth) depth = h; /*如果該結(jié)點層次值大于如果該結(jié)點層次值大于depth， 更新更新depth的值的值*/ PreTreeDepth(bt-Lchild, h+1); /* 遍歷左子樹遍歷左子樹 */ PreTreeDepth(bt-Rchild, h+1); /* 遍歷右子樹遍歷右子樹 */ 第73頁 6. 按樹狀打印的二叉樹按樹狀打印的二叉樹 假設(shè)以二叉鏈表存儲的二叉樹中，每個

57、結(jié)點所含數(shù)假設(shè)以二叉鏈表存儲的二叉樹中，每個結(jié)點所含數(shù) 據(jù)元素均為單字母，要求實現(xiàn)如下圖的打印結(jié)果。據(jù)元素均為單字母，要求實現(xiàn)如下圖的打印結(jié)果。 A BC DE F 輸出輸出 C F AE D B 分析：這是二叉樹的橫向顯示問題，橫向顯示應(yīng)是豎向顯示分析：這是二叉樹的橫向顯示問題，橫向顯示應(yīng)是豎向顯示 的的900旋轉(zhuǎn)，又由于二叉樹的橫向顯示算法一定是中序遍歷旋轉(zhuǎn)，又由于二叉樹的橫向顯示算法一定是中序遍歷 算法，所以把橫向顯示的二叉樹算法改為算法，所以把橫向顯示的二叉樹算法改為RDL結(jié)構(gòu)，實現(xiàn)算結(jié)構(gòu)，實現(xiàn)算 法為：法為： 【算法思想】【算法思想】 （1）二叉樹的橫向顯示應(yīng)是二叉樹豎向顯示的）二叉

58、樹的橫向顯示應(yīng)是二叉樹豎向顯示的90。 。旋轉(zhuǎn)。分 旋轉(zhuǎn)。分 析圖析圖6.15圖示可知，這種樹形打印格式要求先打印右子樹，圖示可知，這種樹形打印格式要求先打印右子樹， 再打印根，最后打印左子樹，按由上而下順序看，其輸出的再打印根，最后打印左子樹，按由上而下順序看，其輸出的 結(jié)點序列為：結(jié)點序列為：CFEADB，這恰為逆中序順序。解決二叉樹的，這恰為逆中序順序。解決二叉樹的 橫向顯示問題采用橫向顯示問題采用“逆中序逆中序”遍歷框架，所以橫向顯示二叉遍歷框架，所以橫向顯示二叉 樹算法為先右子樹、再根結(jié)點、再左子樹的樹算法為先右子樹、再根結(jié)點、再左子樹的RDL結(jié)構(gòu)。結(jié)構(gòu)。 （2）在這種輸出格式中，結(jié)

59、點的左右位置與結(jié)點的層深有）在這種輸出格式中，結(jié)點的左右位置與結(jié)點的層深有 關(guān)，故算法中設(shè)置了一個表示當(dāng)前根結(jié)點層深的參數(shù)，以控關(guān)，故算法中設(shè)置了一個表示當(dāng)前根結(jié)點層深的參數(shù)，以控 制輸出結(jié)點的左右位置，每當(dāng)遞歸進(jìn)層時層深參數(shù)加制輸出結(jié)點的左右位置，每當(dāng)遞歸進(jìn)層時層深參數(shù)加1。這些。這些 操作應(yīng)在訪問根結(jié)點時實現(xiàn)。操作應(yīng)在訪問根結(jié)點時實現(xiàn)。 第75頁 【算法描述】【算法描述】 void PrintTree(BiTree bt, int nLayer) /* 按豎向樹狀打印的二叉樹按豎向樹狀打印的二叉樹 */ if(bt = =NULL) return; PrintTree(bt -RChild

60、, nLayer+1); PrintTree(bt -LChild , nLayer+1); for(int i=0; idata); /*按逆中序輸出結(jié)點，用層深決定的左右位置按逆中序輸出結(jié)點，用層深決定的左右位置*/ 第76頁 6.3.3 基于棧的遞歸消除基于棧的遞歸消除 1. 中序遍歷二叉樹的非遞歸算法中序遍歷二叉樹的非遞歸算法 在大量復(fù)雜的情況下，遞歸的問題無法直接轉(zhuǎn)換成循環(huán)，需在大量復(fù)雜的情況下，遞歸的問題無法直接轉(zhuǎn)換成循環(huán)，需 要采用工作棧消除遞歸。工作棧提供一種控制結(jié)構(gòu)，要采用工作棧消除遞歸。工作棧提供一種控制結(jié)構(gòu)，當(dāng)遞歸當(dāng)遞歸 算法進(jìn)層時需要將信息保留；當(dāng)遞歸算法出層時需要從棧