[ppt模板]Ch_6 樹(shù)和二叉樹(shù)

1、1知識(shí)回顧知識(shí)回顧線性表 一般的線性表 特殊的線性表：棧、隊(duì)列線性表的擴(kuò)展：數(shù)組、廣義表特點(diǎn)：有序前趨、后繼2第六章第六章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)樹(shù)是以分支關(guān)系定義的層次結(jié)構(gòu)。樹(shù)是以分支關(guān)系定義的層次結(jié)構(gòu)。樹(shù)結(jié)構(gòu)在客觀世界廣泛存在樹(shù)結(jié)構(gòu)在客觀世界廣泛存在: : 在自然科學(xué)，如地理學(xué)領(lǐng)域，水系、地貌（等高線）、行政區(qū)劃等都具有樹(shù)結(jié)構(gòu)關(guān)系； 在社會(huì)人文領(lǐng)域，人類社會(huì)構(gòu)成、組織機(jī)構(gòu)等也具有樹(shù)結(jié)構(gòu)關(guān)系。樹(shù)型結(jié)構(gòu)：樹(shù)型結(jié)構(gòu)：非線性數(shù)據(jù)結(jié)構(gòu)非線性數(shù)據(jù)結(jié)構(gòu)4要求要求1. 熟練掌握二叉樹(shù)的結(jié)構(gòu)特性。熟練掌握二叉樹(shù)的結(jié)構(gòu)特性。2. 熟悉二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍。熟悉二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍

2、。3. 掌握各種遍歷策略的遞歸算法，靈活運(yùn)用遍歷算法實(shí)掌握各種遍歷策略的遞歸算法，靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹(shù)的其它操作。現(xiàn)二叉樹(shù)的其它操作。4. 熟練掌握二叉樹(shù)的線索化過(guò)程以及在中序線索化樹(shù)上熟練掌握二叉樹(shù)的線索化過(guò)程以及在中序線索化樹(shù)上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。5. 熟悉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹(shù)和森林與二熟悉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換方法。叉樹(shù)的轉(zhuǎn)換方法。6. 了解最優(yōu)樹(shù)的特性，掌握建立最優(yōu)樹(shù)和哈夫曼編碼的了解最優(yōu)樹(shù)的特性，掌握建立最優(yōu)樹(shù)和哈夫曼編碼的方法。方法。6.1 6.1 樹(shù)的定義和基本術(shù)語(yǔ)樹(shù)的定義和基本術(shù)語(yǔ)6.2 6

3、.2 二叉樹(shù)二叉樹(shù)6.3 6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)6.4 6.4 樹(shù)和森林樹(shù)和森林6.5 6.5 赫夫曼樹(shù)與其應(yīng)用赫夫曼樹(shù)與其應(yīng)用主要內(nèi)容66.1.1 6.1.1 樹(shù)的定義樹(shù)的定義樹(shù)（樹(shù)（tree）是）是n (n0)個(gè)結(jié)點(diǎn)的有限集。在任意一棵個(gè)結(jié)點(diǎn)的有限集。在任意一棵非非空樹(shù)空樹(shù)中：中：（1）有且僅有一個(gè)特定的稱為）有且僅有一個(gè)特定的稱為根根的結(jié)點(diǎn)；的結(jié)點(diǎn)；（2）當(dāng)）當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為時(shí)，其余結(jié)點(diǎn)可分為m (m0)個(gè)互不相交個(gè)互不相交的有限集的有限集t1,t2,tm，其中每一個(gè)集合本身又是一棵，其中每一個(gè)集合本身又是一棵樹(shù)，并且稱為根的樹(shù)，并且稱為根的子樹(shù)子樹(shù)

4、。a只有根結(jié)點(diǎn)的樹(shù)abcdefghijklm有子樹(shù)的樹(shù)根子樹(shù)樹(shù)的表示法樹(shù)的表示法v 圖形表示法圖形表示法v 嵌套集合表示法嵌套集合表示法v 廣義表表示法廣義表表示法v 凹入表示法凹入表示法v 左孩子右兄弟表示法左孩子右兄弟表示法教師教師學(xué)生學(xué)生其他人員其他人員20012001級(jí)級(jí) 20022002級(jí)級(jí) 20032003級(jí)級(jí)20042004級(jí)級(jí)西安石油大學(xué)西安石油大學(xué)計(jì)算機(jī)系計(jì)算機(jī)系電信系電信系自控系自控系葉子葉子根根子樹(shù)子樹(shù)( a ( b ( e ( k, l ), f ), c ( g ), d ( h ( m ), i, j ) ) 約定：約定：根根作為由子樹(shù)森林組成的作為由子樹(shù)森林組成的

5、表的名字寫(xiě)在表的左邊表的名字寫(xiě)在表的左邊又稱目錄表示法又稱目錄表示法data左孩子左孩子 右兄弟右兄弟多叉樹(shù)轉(zhuǎn)為多叉樹(shù)轉(zhuǎn)為了二叉樹(shù)了二叉樹(shù)15數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 d：d是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 若若d為空集，則稱為空樹(shù)為空集，則稱為空樹(shù) 。 否則否則: (1) 在在d中存在唯一的稱為根的數(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，其中每一，其中每一 棵子集本身又是一棵符合本定義的樹(shù)，棵子集本身又是一棵符合本定義的樹(shù)， 稱為根稱為

6、根root的子樹(shù)。的子樹(shù)。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 r：adt tree16 基本操作：基本操作：查查 找找 類類 插插 入入 類類刪刪 除除 類類17 root(t) / 求樹(shù)的根結(jié)點(diǎn)求樹(shù)的根結(jié)點(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) / 判定樹(shù)是否為空樹(shù)判定樹(shù)是否為空樹(shù) t

7、reedepth(t) / 求樹(shù)的深度求樹(shù)的深度traversetree( t, visit() ) / 遍歷遍歷18inittree(&t) / 初始化置空樹(shù)初始化置空樹(shù) 插入類：插入類：createtree(&t, definition) / 按定義構(gòu)造樹(shù)按定義構(gòu)造樹(shù)assign(t, cur_e, value) / 給當(dāng)前結(jié)點(diǎn)賦值給當(dāng)前結(jié)點(diǎn)賦值insertchild(&t, &p, i, c) / 將以將以c為根的樹(shù)插入為結(jié)點(diǎn)為根的樹(shù)插入為結(jié)點(diǎn)p的第的第i棵子樹(shù)棵子樹(shù)19 cleartree(&t) / 將樹(shù)清空將樹(shù)清空 刪除類：刪除類：destr

8、oytree(&t) / 銷毀樹(shù)的結(jié)構(gòu)銷毀樹(shù)的結(jié)構(gòu)deletechild(&t, &p, i) / 刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)p的第的第i棵子樹(shù)棵子樹(shù)20abcdefghijmkla( b(e, f(k, l), c(g), d(h, i, j(m) )t1t3t2樹(shù)根例如例如: :21() 有確定的根；() 樹(shù)根和子樹(shù)根之間為有向關(guān)系。有向樹(shù)：有向樹(shù)：有序樹(shù)：有序樹(shù)：子樹(shù)之間存在確定的次序關(guān)系。無(wú)序樹(shù)：無(wú)序樹(shù)：子樹(shù)之間不存在確定的次序關(guān)系。22對(duì)比對(duì)比樹(shù)型結(jié)構(gòu)樹(shù)型結(jié)構(gòu)和和線性結(jié)構(gòu)線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)的結(jié)構(gòu)特點(diǎn)線性結(jié)構(gòu)線性結(jié)構(gòu)樹(shù)型結(jié)構(gòu)樹(shù)型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素第一個(gè)數(shù)據(jù)元素 ( (無(wú)前

9、驅(qū)無(wú)前驅(qū)) ) 根結(jié)點(diǎn)根結(jié)點(diǎn) ( (無(wú)前驅(qū)無(wú)前驅(qū)) )最后一個(gè)數(shù)據(jù)元素最后一個(gè)數(shù)據(jù)元素 (無(wú)后繼無(wú)后繼)多個(gè)葉子結(jié)點(diǎn)多個(gè)葉子結(jié)點(diǎn) ( (無(wú)后繼無(wú)后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 一個(gè)后繼一個(gè)后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 多個(gè)后繼多個(gè)后繼) )對(duì)比對(duì)比樹(shù)型結(jié)構(gòu)樹(shù)型結(jié)構(gòu)和和線性結(jié)構(gòu)線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)的結(jié)構(gòu)特點(diǎn)6.1.2 6.1.2 基本術(shù)語(yǔ)基本術(shù)語(yǔ)25結(jié)點(diǎn)結(jié)點(diǎn): :結(jié)點(diǎn)的度結(jié)點(diǎn)的度: :樹(shù)的度樹(shù)的度: :葉子結(jié)點(diǎn)葉子結(jié)點(diǎn): :分支結(jié)點(diǎn)分支結(jié)點(diǎn): :數(shù)據(jù)元素+ +若干指向子樹(shù)的分支分支的個(gè)數(shù)樹(shù)中所有結(jié)點(diǎn)的度的最大值度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)

10、dhijm26子孫子孫: :以某結(jié)點(diǎn)為根的子樹(shù)中的任一結(jié)點(diǎn)。以某結(jié)點(diǎn)為根的子樹(shù)中的任一結(jié)點(diǎn)。abcdefghijmkl孩子孩子: :結(jié)點(diǎn)的子樹(shù)的根。結(jié)點(diǎn)的子樹(shù)的根。雙親雙親: :該結(jié)點(diǎn)稱為孩子的雙親。該結(jié)點(diǎn)稱為孩子的雙親。兄弟兄弟: :同一個(gè)雙親的孩子之間互稱兄弟。同一個(gè)雙親的孩子之間互稱兄弟。祖先祖先: :從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)27有序樹(shù)：有序樹(shù)：子樹(shù)之間存在確定的次序關(guān)系子樹(shù)之間存在確定的次序關(guān)系無(wú)序樹(shù)：無(wú)序樹(shù)：子樹(shù)之間不存在確定的次序關(guān)系子樹(shù)之間不存在確定的次序關(guān)系樹(shù)的深度：樹(shù)的深度：樹(shù)中結(jié)點(diǎn)的最大層次樹(shù)中結(jié)點(diǎn)的最大層次堂兄弟堂兄弟: :其雙親在

11、同一層的結(jié)點(diǎn)其雙親在同一層的結(jié)點(diǎn)結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次:假設(shè)根結(jié)點(diǎn)的層次為假設(shè)根結(jié)點(diǎn)的層次為1，第，第l 層的結(jié)點(diǎn)的子樹(shù)根結(jié)點(diǎn)的層次為層的結(jié)點(diǎn)的子樹(shù)根結(jié)點(diǎn)的層次為l+128a ab bc cd de ef fg gh hi ij jk kl lm m結(jié)點(diǎn)結(jié)點(diǎn)a的度：的度：3結(jié)點(diǎn)結(jié)點(diǎn)b的度：的度：2結(jié)點(diǎn)結(jié)點(diǎn)m的度：的度：0葉子：葉子：k，l，f，g，m，i，j結(jié)點(diǎn)結(jié)點(diǎn)a的孩子：的孩子：b，c，d結(jié)點(diǎn)結(jié)點(diǎn)b的孩子：的孩子：e，f結(jié)點(diǎn)結(jié)點(diǎn)i的雙親：的雙親：d結(jié)點(diǎn)結(jié)點(diǎn)l的雙親：的雙親：e結(jié)點(diǎn)結(jié)點(diǎn)b，c，d為兄弟為兄弟結(jié)點(diǎn)結(jié)點(diǎn)k，l為兄弟為兄弟樹(shù)的度：樹(shù)的度：3結(jié)點(diǎn)結(jié)點(diǎn)a的層次：的層次：1結(jié)點(diǎn)結(jié)點(diǎn)m的層次

12、：的層次：4樹(shù)的深度：樹(shù)的深度：4結(jié)點(diǎn)結(jié)點(diǎn)f，g為堂兄弟為堂兄弟29任何一棵非空樹(shù)是一個(gè)二元組 tree = （root，f）其中：root 被稱為根結(jié)點(diǎn) f 被稱為子樹(shù)森林森林：森林：是m（m0）棵互不相交的樹(shù)的集合arootbcdefghijmklf先研究最簡(jiǎn)單、最有規(guī)律的樹(shù)，然先研究最簡(jiǎn)單、最有規(guī)律的樹(shù)，然后設(shè)法把一般的樹(shù)轉(zhuǎn)化為簡(jiǎn)單樹(shù)。后設(shè)法把一般的樹(shù)轉(zhuǎn)化為簡(jiǎn)單樹(shù)。解決思路：解決思路： 樹(shù)的操作實(shí)現(xiàn)比較復(fù)雜。樹(shù)的操作實(shí)現(xiàn)比較復(fù)雜。為何要重點(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)

13、； 可以證明，所有樹(shù)都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹(shù)，可以證明，所有樹(shù)都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹(shù)，不失一般性。不失一般性。 二叉樹(shù)二叉樹(shù):或?yàn)榭諛?shù)，或是由一個(gè)或?yàn)榭諛?shù)，或是由一個(gè)根根結(jié)點(diǎn)結(jié)點(diǎn)加上兩棵分別稱為加上兩棵分別稱為左子樹(shù)左子樹(shù)和和右子右子樹(shù)樹(shù)的、的、互不相交互不相交的二叉樹(shù)組成。的二叉樹(shù)組成。abcdefghk根結(jié)點(diǎn)根結(jié)點(diǎn)左子樹(shù)左子樹(shù)右子樹(shù)右子樹(shù)二叉樹(shù)的特點(diǎn)二叉樹(shù)的特點(diǎn)（1 1）每個(gè)結(jié)點(diǎn)至多有二棵子樹(shù)）每個(gè)結(jié)點(diǎn)至多有二棵子樹(shù)( (即不存在度大于即不存在度大于2 2的結(jié)點(diǎn)的結(jié)點(diǎn)) )；（2 2）二叉樹(shù)的子樹(shù)有左、右之）二叉樹(shù)的子樹(shù)有左、右之分，且其次序不能任意顛倒。分，且其次序不能任意顛倒。二叉樹(shù)

14、的五種基本形態(tài)：二叉樹(shù)的五種基本形態(tài)：空樹(shù)空樹(shù)只含根結(jié)點(diǎn)只含根結(jié)點(diǎn)lrr右子樹(shù)為空樹(shù)右子樹(shù)為空樹(shù)l左子樹(shù)為空樹(shù)左子樹(shù)為空樹(shù)左右子左右子樹(shù)均不樹(shù)均不為空樹(shù)為空樹(shù)34 二叉樹(shù)的主要基本操作二叉樹(shù)的主要基本操作：查查 找找 類類插插 入入 類類刪刪 除除 類類35 root(t); value(t, e); parent(t, e); leftchild(t, e); rightchild(t, e); leftsibling(t, e); rightsibling(t, e); bitreeempty(t); bitreedepth(t); preordertraverse(t, visit();

15、 inordertraverse(t, visit(); postordertraverse(t, visit(); levelordertraverse(t, visit();36 initbitree(&t); assign(t, &e, value); createbitree(&t, definition); insertchild(t, p, lr, c);37clearbitree(&t); destroybitree(&t);deletechild(t, p, lr);38二叉樹(shù)二叉樹(shù)的重要特性的重要特性39 性質(zhì)性質(zhì) 1 ： 在二叉樹(shù)的第

16、 i 層上至多有2i-1 個(gè)結(jié)點(diǎn)。 (i1)用歸納法證明用歸納法證明： 歸納基歸納基： 歸納假設(shè)：歸納假設(shè)： 歸納證明：歸納證明：i = 1 層時(shí)，只有一個(gè)根結(jié)點(diǎn)： 2i-1 = 20 = 1；假設(shè)對(duì)所有的 j，1 j i，命題成立；二叉樹(shù)上每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)，則第 i 層的結(jié)點(diǎn)數(shù) = 2i-2 2 = 2i-1 。40 性質(zhì)性質(zhì) 2 ： 深度為 k 的二叉樹(shù)上至多含 2k-1 個(gè)結(jié)點(diǎn)（k1）。證明：證明： 基于性質(zhì)1，深度為 k 的二叉樹(shù)上的結(jié)點(diǎn)數(shù)至多為 20+21+ +2k-1 = 2k-1 。41 性質(zhì)性質(zhì) 3 ： 對(duì)任何一棵二叉樹(shù)，若它含有對(duì)任何一棵二叉樹(shù)，若它含有n0 個(gè)葉個(gè)葉子

17、結(jié)點(diǎn)、子結(jié)點(diǎn)、n2 個(gè)度為個(gè)度為 2 的結(jié)點(diǎn)，則必存在的結(jié)點(diǎn)，則必存在關(guān)系式：關(guān)系式：n0 = n2+1。二叉樹(shù)中全部結(jié)點(diǎn)數(shù)二叉樹(shù)中全部結(jié)點(diǎn)數(shù)nn0+n1+n2(葉子數(shù)葉子數(shù)1度結(jié)度結(jié)點(diǎn)數(shù)點(diǎn)數(shù)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è)直接前趨，即一（除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)必有一個(gè)直接前趨，即一個(gè)分支）個(gè)分支）總分支數(shù)總分支數(shù)b= n1+2n2 (1度結(jié)點(diǎn)必有度結(jié)點(diǎn)必有1個(gè)直接后繼，個(gè)直接后繼，2度結(jié)點(diǎn)必有度結(jié)點(diǎn)必有2個(gè)個(gè))n0+n1+n2= n1+2n2 +1, 即即n0=n2+142兩類兩類特殊特殊的二

18、叉樹(shù)：的二叉樹(shù)：滿二叉樹(shù)滿二叉樹(shù)：深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。完全二叉樹(shù)完全二叉樹(shù)：樹(shù)中所含的 n 個(gè)結(jié)點(diǎn)和滿二叉樹(shù)中編號(hào)編號(hào)為為 1 至至 n 的結(jié)點(diǎn)的結(jié)點(diǎn)一一對(duì)應(yīng)。123456789 10 11 12 13 14 15abcdefghij43123114589121367101415123114589126710123456712345644完全二叉樹(shù)特點(diǎn)：完全二叉樹(shù)特點(diǎn)：（1 1）葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)）葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn); ;（2 2）對(duì)任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為）對(duì)任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為i i，則其左分支下子孫的最

19、大層次必為則其左分支下子孫的最大層次必為i i或或i+1i+1。滿二叉樹(shù)與完全二叉樹(shù)的區(qū)別滿二叉樹(shù)與完全二叉樹(shù)的區(qū)別滿二叉樹(shù)是葉子一個(gè)也不少的樹(shù)，而完全二叉樹(shù)雖滿二叉樹(shù)是葉子一個(gè)也不少的樹(shù)，而完全二叉樹(shù)雖然前然前k-1k-1層是滿的，但最底層卻允許在右邊缺少連續(xù)若干層是滿的，但最底層卻允許在右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)。滿二叉樹(shù)是完全二叉樹(shù)的一個(gè)特例。個(gè)結(jié)點(diǎn)。滿二叉樹(shù)是完全二叉樹(shù)的一個(gè)特例。為何要研究這兩種特殊形式？為何要研究這兩種特殊形式？45性質(zhì)性質(zhì) 4 ：具有具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 log2n +1 。 x 表示表示= x的最大整數(shù)。的最大整數(shù)。證明：設(shè)

20、完全二叉樹(shù)的深度為證明：設(shè)完全二叉樹(shù)的深度為 k 則根據(jù)第二條性質(zhì)得則根據(jù)第二條性質(zhì)得 2k-1 (第第k層第一個(gè)結(jié)點(diǎn)的編號(hào)）層第一個(gè)結(jié)點(diǎn)的編號(hào)） n 2k（第（第k1層第一個(gè)結(jié)點(diǎn)的編號(hào)）層第一個(gè)結(jié)點(diǎn)的編號(hào)） 即即 k-1 log2 n = (2k-1-1)+1，根據(jù)第二條性質(zhì)得 n 2k -1，因此：2k-1 n 2k 即 k-1 log2 n n，則該結(jié)點(diǎn)無(wú)左孩子， 否則，編號(hào)為 2i 的結(jié)點(diǎn)為其左孩子左孩子結(jié)點(diǎn)；(3) 若 2i+1n，則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)， 否則，編號(hào)為2i+1 的結(jié)點(diǎn)為其右孩子右孩子結(jié)點(diǎn)。123114589126710第第k層上最后一個(gè)結(jié)點(diǎn)的編號(hào)是層上最后一個(gè)結(jié)點(diǎn)的編

21、號(hào)是2k-1,它的右孩它的右孩子是第子是第k+1層上最后一個(gè)結(jié)點(diǎn)層上最后一個(gè)結(jié)點(diǎn),編號(hào)是編號(hào)是2k+1-1,右右孩子編號(hào)是它的雙親結(jié)點(diǎn)編號(hào)的孩子編號(hào)是它的雙親結(jié)點(diǎn)編號(hào)的(2k-1)*2+1,左左孩子的編號(hào)是孩子的編號(hào)是(2k-1)*2所以，編號(hào)為所以，編號(hào)為 i 的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)編號(hào)是的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)編號(hào)是2i，右孩子結(jié)點(diǎn)編號(hào)是右孩子結(jié)點(diǎn)編號(hào)是2i+1,雙親結(jié)點(diǎn)編號(hào)雙親結(jié)點(diǎn)編號(hào) i/2 49問(wèn)問(wèn) 題題 具有具有n n個(gè)結(jié)點(diǎn)的非空二叉樹(shù)的最小深度個(gè)結(jié)點(diǎn)的非空二叉樹(shù)的最小深度是多少？最大深度是多少？是多少？最大深度是多少？ 答1： 當(dāng)是滿二叉樹(shù)時(shí)深度最小。最小深度： log2n +1 當(dāng)每個(gè)節(jié)

22、點(diǎn)都只有左（右）子樹(shù)時(shí)深度最大最大深度： n 50思考題1.具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中有多少個(gè)葉子結(jié)點(diǎn)？有多少個(gè)度為2的結(jié)點(diǎn)？2.具有n0個(gè)葉子結(jié)點(diǎn)的完全二叉樹(shù)中共有多少個(gè)結(jié)點(diǎn)？51二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二、二叉樹(shù)的鏈?zhǔn)蕉⒍鏄?shù)的鏈?zhǔn)?存儲(chǔ)表示存儲(chǔ)表示一、一、 二叉樹(shù)的順序二叉樹(shù)的順序 存儲(chǔ)表示存儲(chǔ)表示存儲(chǔ)方式：用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)方式：用一組地址連續(xù)的存儲(chǔ)單元依次自上而下、自左至右自上而下、自左至右存儲(chǔ)存儲(chǔ)完全二叉樹(shù)完全二叉樹(shù)上的結(jié)上的結(jié)點(diǎn)元素，即將完全二叉樹(shù)上編號(hào)為點(diǎn)元素，即將完全二叉樹(shù)上編號(hào)為i的結(jié)點(diǎn)元的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組中下標(biāo)為素存儲(chǔ)在一維數(shù)組中下標(biāo)為i-1

23、的分量中。的分量中。一、一、 二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)/-二叉樹(shù)的順序存儲(chǔ)表示二叉樹(shù)的順序存儲(chǔ)表示-#define max_tree_size 100/ 二叉樹(shù)的最大結(jié)點(diǎn)數(shù)二叉樹(shù)的最大結(jié)點(diǎn)數(shù)typedef telemtype sqbitreemax_ tree_size; / 0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)號(hào)單元存儲(chǔ)根結(jié)點(diǎn)sqbitree bt;例如例如: :abcdef a b d 0 c 0 e 0 0 0 0 0 0 f 0 1 2 3 4 5 6 7 8 9 10 11 12 1314013260表示不存在此結(jié)點(diǎn)完全二叉樹(shù)的數(shù)組表示完全二叉樹(shù)的數(shù)組表示 一般二叉樹(shù)的數(shù)組表示一般二叉

24、樹(shù)的數(shù)組表示55特點(diǎn)：特點(diǎn)： 結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中，浪費(fèi)空間，適于結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中，浪費(fèi)空間，適于存滿二叉樹(shù)和完全二叉樹(shù)（在最壞情況下，深度為存滿二叉樹(shù)和完全二叉樹(shù)（在最壞情況下，深度為k且只有且只有k個(gè)結(jié)點(diǎn)的單支樹(shù)需要長(zhǎng)度為個(gè)結(jié)點(diǎn)的單支樹(shù)需要長(zhǎng)度為2k-1的一維數(shù)組）的一維數(shù)組）。 由于一般二叉樹(shù)必須仿照完全二叉樹(shù)那樣存儲(chǔ)，可由于一般二叉樹(shù)必須仿照完全二叉樹(shù)那樣存儲(chǔ)，可能會(huì)浪費(fèi)很多存儲(chǔ)空間，單支樹(shù)就是一個(gè)極端情況。能會(huì)浪費(fèi)很多存儲(chǔ)空間，單支樹(shù)就是一個(gè)極端情況。二、二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二、二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（1 1）二叉鏈表）二叉鏈表（2）三叉鏈表三叉鏈表adebcf r

25、ootlchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):1. 1. 二叉鏈表二叉鏈表fabcde在在n n個(gè)結(jié)點(diǎn)的二叉鏈表中，有個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1n+1個(gè)空指針域個(gè)空指針域typedef struct bitnode /結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) telemtype data; struct bitnode *lchild, *rchild; / 左右孩子指針 bitnode, *bitree;lchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):c 語(yǔ)言的類型描述如下語(yǔ)言的類型描述如下: :adebcf root 2三叉鏈表三叉鏈表parent lchild data rchild結(jié)點(diǎn)結(jié)

26、構(gòu)結(jié)點(diǎn)結(jié)構(gòu):abcdef typedef struct tritnode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) telemtype data; struct tritnode *lchild, *rchild; / 左右孩子指針 struct tritnode *parent; /雙親指針 tritnode, *tritree;parent lchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):c 語(yǔ)言的類型描述如下語(yǔ)言的類型描述如下: :二叉鏈存儲(chǔ)結(jié)構(gòu)的二叉樹(shù)操作實(shí)現(xiàn)二叉鏈存儲(chǔ)結(jié)構(gòu)的二叉樹(shù)操作實(shí)現(xiàn) 在二叉鏈存儲(chǔ)結(jié)構(gòu)下，針對(duì)一棵二叉樹(shù)，主要涉及如下幾在二叉鏈存儲(chǔ)結(jié)構(gòu)下，針對(duì)一棵二叉樹(shù)，主要涉及如下幾個(gè)功能模塊

27、：個(gè)功能模塊：v 二叉樹(shù)的初始化操作；二叉樹(shù)的初始化操作；v 二叉樹(shù)中給某結(jié)點(diǎn)插入一個(gè)左結(jié)點(diǎn)的操作；二叉樹(shù)中給某結(jié)點(diǎn)插入一個(gè)左結(jié)點(diǎn)的操作；v 二叉樹(shù)中給某結(jié)點(diǎn)插入一個(gè)右結(jié)點(diǎn)的操作；二叉樹(shù)中給某結(jié)點(diǎn)插入一個(gè)右結(jié)點(diǎn)的操作；v 刪除二叉樹(shù)中某結(jié)點(diǎn)的左子樹(shù)操作；刪除二叉樹(shù)中某結(jié)點(diǎn)的左子樹(shù)操作；v 刪除二叉樹(shù)中某結(jié)點(diǎn)的右子樹(shù)操作。刪除二叉樹(shù)中某結(jié)點(diǎn)的右子樹(shù)操作。 各算法的基本思想及程序?qū)崿F(xiàn)如下：各算法的基本思想及程序?qū)崿F(xiàn)如下： typedef structtypedef struct node node datatypedatatype data; data;struct node struct nod

28、e * *leftchildleftchild; ; struct node struct node * *rightchildrightchild; ; bitreenode bitreenode; /; /* *結(jié)點(diǎn)的結(jié)構(gòu)體定義結(jié)點(diǎn)的結(jié)構(gòu)體定義* */ /1.1.二叉樹(shù)的初始化二叉樹(shù)的初始化 算法的基本思想算法的基本思想: :創(chuàng)建二叉樹(shù)的頭結(jié)點(diǎn)。創(chuàng)建二叉樹(shù)的頭結(jié)點(diǎn)。 程序?qū)崿F(xiàn)：程序?qū)崿F(xiàn)： void initiate(bitreenodevoid initiate(bitreenode * * *root)root) * *root = (bitreenode root = (bitreen

29、ode * *)malloc(sizeof(bitreenode)malloc(sizeof(bitreenode););( (* *root)-leftchildroot)-leftchild=null;=null;( (* *root)-rightchildroot)-rightchild=null;=null; 2.2.二叉樹(shù)中給某結(jié)點(diǎn)插入一個(gè)左結(jié)點(diǎn)的操作二叉樹(shù)中給某結(jié)點(diǎn)插入一個(gè)左結(jié)點(diǎn)的操作 算法的基本思想算法的基本思想: : 若當(dāng)前結(jié)點(diǎn)若當(dāng)前結(jié)點(diǎn)( (假設(shè)為假設(shè)為currcurr）非空，在非空，在currcurr的左子的左子樹(shù)插入元素值為樹(shù)插入元素值為x x的新結(jié)點(diǎn)的新結(jié)點(diǎn) ，原，原c

30、urrcurr所指結(jié)點(diǎn)的左所指結(jié)點(diǎn)的左子樹(shù)成為新插入結(jié)點(diǎn)的左子樹(shù)。若插入成功返回新子樹(shù)成為新插入結(jié)點(diǎn)的左子樹(shù)。若插入成功返回新插入結(jié)點(diǎn)的指針，否則返回空指針。插入結(jié)點(diǎn)的指針，否則返回空指針。程序?qū)崿F(xiàn)：程序?qū)崿F(xiàn)： bitreenode bitreenode * *insertleftnode(bitreenode insertleftnode(bitreenode * *curr,datatype x) curr,datatype x) bitreenode bitreenode * *s, s, * *t;t; if(curr if(curr=null) return null;=null)

31、return null;t=curr-leftchildt=curr-leftchild; ;s=(bitreenode s=(bitreenode * *)malloc(sizeof(bitreenode)malloc(sizeof(bitreenode);); s-data=x; s-data=x;s-leftchilds-leftchild=t;=t; s-rightchild s-rightchild=null;=null;curr-leftchildcurr-leftchild=s;=s;return curr-leftchildreturn curr-leftchild; ; 3.

32、3.刪除二叉樹(shù)中某結(jié)點(diǎn)的左子樹(shù)操作刪除二叉樹(shù)中某結(jié)點(diǎn)的左子樹(shù)操作算法的基本思想算法的基本思想: :若若currcurr非空，刪除非空，刪除currcurr所指結(jié)點(diǎn)的左子樹(shù)。若所指結(jié)點(diǎn)的左子樹(shù)。若刪除成功，返回刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)指針，否則返回空指針。刪除成功，返回刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)指針，否則返回空指針。程序?qū)崿F(xiàn)程序?qū)崿F(xiàn)：bitreenode bitreenode * *deletelefttree(bitreenode deletelefttree(bitreenode * *currcurr) ) if(curr=null|curr-leftchildif(curr=null|curr-lef

33、tchild=null)=null) return null; return null;destroy(&curr-leftchilddestroy(&curr-leftchild););curr-leftchildcurr-leftchild=null;=null;return currreturn curr; ; 66知識(shí)回顧 樹(shù)和二叉樹(shù)的定義 二叉樹(shù)的特點(diǎn) 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)676.3.1二叉樹(shù)的遍歷二叉樹(shù)的遍歷68一、問(wèn)題的提出一、問(wèn)題的提出二、先左后右的遍歷算法二、先左后右的遍歷算法三、算法的遞歸描述三、算法的遞歸描述四、中序遍歷算法的非遞歸描述四、中序遍歷算法的非遞歸

34、描述五五、遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例69 順著某一條搜索路徑巡訪巡訪二叉樹(shù)中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一均被訪問(wèn)一次次，而且僅被訪問(wèn)一次僅被訪問(wèn)一次。一、問(wèn)題的提出一、問(wèn)題的提出“訪問(wèn)訪問(wèn)”的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。70 “遍歷遍歷”是任何類型均有的操作，對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，故不需要另加討論。而二叉樹(shù)是非線性結(jié)構(gòu)， 每個(gè)結(jié)點(diǎn)有兩個(gè)后繼每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷存在如何遍歷即按什么樣的搜索搜索路徑路徑遍歷的問(wèn)題。71 對(duì)對(duì)“二叉樹(shù)二叉樹(shù)”而言，可以有而言，可以有三條搜索路徑：三條搜索路徑：1先上后下先上后下的按層次遍歷；

35、2先左先左（子樹(shù)）后右后右（子樹(shù)）的遍歷；3先右先右（子樹(shù)）后左后左（子樹(shù)）的遍歷。72二、先左后右的遍歷算法二、先左后右的遍歷算法先先（根）序的遍歷算法中中（根）序的遍歷算法后后（根）序的遍歷算法73 若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）訪問(wèn)根結(jié)點(diǎn)；（2）先序遍歷左子樹(shù)；（3）先序遍歷右子樹(shù)。先（根）序的遍歷算法：先（根）序的遍歷算法：74 若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）中序遍歷左子樹(shù)；（2）訪問(wèn)根結(jié)點(diǎn)；（3）中序遍歷右子樹(shù)。中（根）序的遍歷算法：中（根）序的遍歷算法：75 若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）后序遍歷左子樹(shù)；（2）后序遍歷右子樹(shù)；（3）訪問(wèn)根結(jié)點(diǎn)。后（根）序的遍

36、歷算法：后（根）序的遍歷算法：76adbct l rat l rt l rbdct l r先序遍歷序列：先序遍歷序列：a b d c先序遍歷:77adbcl t rbl t rl t radcl t r中序遍歷序列：中序遍歷序列：b d a c中序遍歷:78adbc l r tl r tl r tadcl r t后序遍歷序列：后序遍歷序列： d b c a后序遍歷:b79-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：- + a * b - c d / e f-+a*b-cd/ef-+a*b-c d/e f80三、算法的遞歸描述三、算法的遞歸描述void inordertraverse (

37、bitree t, status(*visit)(telemtype e) / 中中序遍歷二叉樹(shù)序遍歷二叉樹(shù) if (t) inordertraverse (t-lchild, visit) ;/中中序遍歷左子樹(shù)序遍歷左子樹(shù) visit(t-data) / 訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn) inordertraverse (t-rchild, visit);/中序遍歷右子樹(shù)中序遍歷右子樹(shù) 見(jiàn)演示見(jiàn)演示81status inordertraverse(bitree t,status(*visit)(telemtype e)initstack(s); push(s,t); /根指針進(jìn)棧根指針進(jìn)棧while(!

38、stackempty(s) while(gettop(s,p)&p) push(s,p-lchild); /向左走到盡頭向左走到盡頭 pop(s,p); /空指針退?？罩羔樛藯?if(!stackempty(s) /訪問(wèn)結(jié)點(diǎn)訪問(wèn)結(jié)點(diǎn),向右一步向右一步 pop(s,p); visit(p-data); push(s,p-rchild); /if /whilereturn ok;/inordertraverse算法算法1四、中序遍歷算法的非遞歸描述四、中序遍歷算法的非遞歸描述82-b*ca-*anullnullbnullnullcnullnull中序遍歷序列:a*b-cwhile(!sta

39、ckempty(s) while(gettop(s,p)&p)push(s,p-lchild); /向左走到盡頭向左走到盡頭 pop(s,p); /空指針退?？罩羔樛藯?if(!stackempty(s)/訪問(wèn)結(jié)點(diǎn)訪問(wèn)結(jié)點(diǎn),向右一步向右一步 pop(s,p); if(!visit(p-data) return error; push(s,p-rchild); /if83status inordertraverse(bitree t, status (*visit)(telemtype e) initstack(s); p=t; while(p|!stackempty(s) if (p)

40、 push(s,p); p=p-lchild; /根指針進(jìn)棧根指針進(jìn)棧, ,遍歷左子樹(shù)遍歷左子樹(shù) else/根指針退棧根指針退棧,訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn),遍歷右子樹(shù)遍歷右子樹(shù) pop(s,p); visit(p-data); p=p-rchild; / else / while return ok;/inordertraverse算法算法2中序遍歷算法的非遞歸描述中序遍歷算法的非遞歸描述84p=t; while(p|!stackempty(s) if (p) push(s,p); p=p-lchild;/根指針進(jìn)棧根指針進(jìn)棧,遍歷左子樹(shù)遍歷左子樹(shù) else/根指針退棧根指針退棧,訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根

41、結(jié)點(diǎn),遍歷遍歷右子樹(shù)右子樹(shù) pop(s,p);if(!visit(p-data)return error; p=p-rchild; / else / while-b*ca-*abc85+*a*/edcb先序遍歷結(jié)果先序遍歷結(jié)果+ * * / a b c d e前綴表示法前綴表示法中序遍歷結(jié)果中序遍歷結(jié)果a / b * c * d + e中綴表示法中綴表示法后序遍歷結(jié)果后序遍歷結(jié)果a b / c * d * e +后綴表示法后綴表示法層次遍歷結(jié)果層次遍歷結(jié)果+ * e * d / c a b用二叉樹(shù)表示算術(shù)表達(dá)式用二叉樹(shù)表示算術(shù)表達(dá)式void layerorder(bitreevoid laye

42、rorder(bitree t) t) /層序遍歷二叉樹(shù)層序遍歷二叉樹(shù) if (t) if (t) initqueue(q initqueue(q); ); /建一個(gè)空隊(duì)（初始化隊(duì)列）建一個(gè)空隊(duì)（初始化隊(duì)列） enqueue(q,tenqueue(q,t); ); /將一個(gè)結(jié)點(diǎn)插入隊(duì)尾的函數(shù)將一個(gè)結(jié)點(diǎn)插入隊(duì)尾的函數(shù) while(while( !queueempty(q!queueempty(q) ) ) ) dequeue(q dequeue(q, &p); , &p); /隊(duì)首結(jié)點(diǎn)出隊(duì)隊(duì)首結(jié)點(diǎn)出隊(duì)( (送入送入p)p) visit(p); visit(p); if(p-lch

43、ild) enqueue(q,p-lchild if(p-lchild) enqueue(q,p-lchild); ); /p/p的左孩子入隊(duì)的左孩子入隊(duì) if(p-rchild) enqueue(q,p-rchildif(p-rchild) enqueue(q,p-rchild); ); /p/p的右孩子入隊(duì)的右孩子入隊(duì) /layerorder/layerorder 當(dāng)孩子為空時(shí)不要當(dāng)孩子為空時(shí)不要將空指針入隊(duì)將空指針入隊(duì)遍歷算法思想的應(yīng)用-步驟 要明確所要編寫(xiě)的算法的功能描述（包括所涉及的各參數(shù)或要明確所要編寫(xiě)的算法的功能描述（包括所涉及的各參數(shù)或變量的含義）變量的含義）這在遞歸算法中尤其

44、要注意。在此基礎(chǔ)上這在遞歸算法中尤其要注意。在此基礎(chǔ)上按如下步驟討論算法的實(shí)現(xiàn)：按如下步驟討論算法的實(shí)現(xiàn)：v如果如果t為空，則按預(yù)定功能實(shí)現(xiàn)對(duì)空樹(shù)的操作，以滿足功為空，則按預(yù)定功能實(shí)現(xiàn)對(duì)空樹(shù)的操作，以滿足功能要求（包括對(duì)相應(yīng)參數(shù)，變量的操作）。能要求（包括對(duì)相應(yīng)參數(shù)，變量的操作）。v否則，假設(shè)算法對(duì)否則，假設(shè)算法對(duì)t的左右子樹(shù)都能分別實(shí)現(xiàn)預(yù)定功能，的左右子樹(shù)都能分別實(shí)現(xiàn)預(yù)定功能，在此基礎(chǔ)上，通過(guò)按預(yù)定要求適當(dāng)調(diào)用對(duì)左右子樹(shù)的算在此基礎(chǔ)上，通過(guò)按預(yù)定要求適當(dāng)調(diào)用對(duì)左右子樹(shù)的算法的功能，及對(duì)當(dāng)前結(jié)點(diǎn)的操作實(shí)現(xiàn)對(duì)整個(gè)二叉樹(shù)的功法的功能，及對(duì)當(dāng)前結(jié)點(diǎn)的操作實(shí)現(xiàn)對(duì)整個(gè)二叉樹(shù)的功能（包括對(duì)各變量、參數(shù)的操

45、作）。能（包括對(duì)各變量、參數(shù)的操作）。89例例1 1：統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的：統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)個(gè)數(shù).(.(先序遍歷先序遍歷) )90算法基本思想算法基本思想: : 先序(或中序或后序)遍歷二叉樹(shù)，在遍歷過(guò)程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。由此，需在遍歷算法中增添一個(gè)需在遍歷算法中增添一個(gè)“計(jì)數(shù)計(jì)數(shù)”的參數(shù)的參數(shù)，并將算法中“訪問(wèn)結(jié)點(diǎn)”的操作改為：若是葉子，則計(jì)數(shù)器增若是葉子，則計(jì)數(shù)器增1 1。91void countleaf (bitree t, int& count) if ( t ) if (!t-lchild)& (!t-rchild) count+; / 對(duì)葉子結(jié)點(diǎn)計(jì)

46、數(shù) countleaf( t-lchild, count); countleaf( t-rchild, count); / if / countleaf92例例2 2：求二叉樹(shù)的深度：求二叉樹(shù)的深度 ( (后序遍歷后序遍歷) )93算法基本思想算法基本思想: : 從二叉樹(shù)深度的定義可知，二叉樹(shù)的二叉樹(shù)的深度應(yīng)為其左、右子樹(shù)深度的最大值加深度應(yīng)為其左、右子樹(shù)深度的最大值加1 1。由此，需先分別求得左、右子樹(shù)的深度需先分別求得左、右子樹(shù)的深度，算法中“訪問(wèn)結(jié)點(diǎn)”的操作為：求得左、求得左、右子樹(shù)深度的最大值，然后加右子樹(shù)深度的最大值，然后加 1 1 。 首先分析二叉樹(shù)的深度二叉樹(shù)的深度和它的左左、右

47、子右子樹(shù)深度樹(shù)深度之間的關(guān)系。94int depth (bitree t ) / 返回二叉樹(shù)的深度 if ( !t ) depthval = 0; else depthleft = depth( t-lchild ); depthright= depth( t-rchild ); depthval = 1 + (depthleft depthright ? depthleft : depthright); return depthval;95例例3 3：建立二叉樹(shù)的存：建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)儲(chǔ)結(jié)構(gòu)96 以字符串的形式以字符串的形式 根根 左子樹(shù)左子樹(shù) 右子樹(shù)右子樹(shù)定義一棵二叉樹(shù)定義一棵二叉樹(shù)例如

48、:abcd以空白字符“ ”表示a(b( ,c( , ),d( , )空樹(shù)空樹(shù)只含一個(gè)根結(jié)點(diǎn)只含一個(gè)根結(jié)點(diǎn)的二叉樹(shù)的二叉樹(shù)a以字符串“a ”表示以下列字符串表示97status createbitree(bitree &t) scanf(&ch); if (ch= ) t = null; else if (!(t = (bitnode *)malloc(sizeof(bitnode) exit(overflow); t-data = ch; / 生成根結(jié)點(diǎn) createbitree(t-lchild); / 構(gòu)造左子樹(shù) createbitree(t-rchild); / 構(gòu)造右子

49、樹(shù) return ok; / createbitree98a b c d a bcd上頁(yè)算法執(zhí)行過(guò)程舉例如下：atbcdstatus createbitree(bitree &t) scanf(&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; 99問(wèn)題 已知一棵二叉樹(shù)的先序遍歷序列，能否已知一棵二叉樹(shù)的先序

50、遍歷序列，能否得到這棵樹(shù)？得到這棵樹(shù)？100例：一棵樹(shù)的先序序列為：1，2，3。請(qǐng)畫(huà)出這棵樹(shù)。101 9可以證明：可以證明：一棵二叉樹(shù)的先序序列和中一棵二叉樹(shù)的先序序列和中序序列可以唯一的確定這棵二叉樹(shù)。序序列可以唯一的確定這棵二叉樹(shù)。結(jié)論結(jié)論 僅已知一棵二叉樹(shù)的先序遍歷序列，僅已知一棵二叉樹(shù)的先序遍歷序列，不不能能唯一確定這棵樹(shù)。唯一確定這棵樹(shù)。已知一棵二叉樹(shù)的中序序列和已知一棵二叉樹(shù)的中序序列和后序序列后序序列分別是分別是bdceafhg bdceafhg 和和 decbhgfadecbhgfa，請(qǐng)畫(huà)出這棵二叉樹(shù)。，請(qǐng)畫(huà)出這棵二叉樹(shù)。分析：分析：由后序遍歷特征，根結(jié)點(diǎn)必在后序序列尾部由后序

51、遍歷特征，根結(jié)點(diǎn)必在后序序列尾部（即（即a a）；由中序遍歷特征，根結(jié)點(diǎn)必在其中間，而且其左部必由中序遍歷特征，根結(jié)點(diǎn)必在其中間，而且其左部必全部是左子樹(shù)的子孫全部是左子樹(shù)的子孫（即（即bdcebdce），其右部必全部是右，其右部必全部是右子樹(shù)的子孫子樹(shù)的子孫（即（即fhgfhg）；繼而，根據(jù)后序中的繼而，根據(jù)后序中的decbdecb子樹(shù)可確定子樹(shù)可確定b b為為a a的左孩子，的左孩子，根據(jù)根據(jù)hgfhgf子串可確定子串可確定f f為為a a的右孩子；以此類推。的右孩子；以此類推。105106 二叉樹(shù)的遍歷：以一定的次序排列二叉樹(shù)的結(jié)點(diǎn)。-非線性結(jié)構(gòu)的線性化。 傳統(tǒng)的二叉鏈表存儲(chǔ)結(jié)構(gòu)只存儲(chǔ)了

52、結(jié)點(diǎn)的左右孩子的信息，沒(méi)有存儲(chǔ)其前趨和后繼信息。 這些信息只有在遍歷過(guò)程中才能得到。 傳統(tǒng)的二叉樹(shù)遍歷方法：-利用堆棧 效率低知識(shí)回顧知識(shí)回顧107-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：- + a * b - c d / e f-+a*b-cd/ef-+a*b-c d/e f108問(wèn)題：?jiǎn)栴}：能否在遍歷過(guò)程中把結(jié)點(diǎn)的能否在遍歷過(guò)程中把結(jié)點(diǎn)的前趨和后繼信息保存下來(lái)，并且提前趨和后繼信息保存下來(lái)，并且提高算法的效率呢？高算法的效率呢？1096.3.2線索二叉樹(shù)線索二叉樹(shù)threaded binary treethreaded binary tree110主要內(nèi)容（1）什么是線索二叉樹(shù)

53、（2）基于線索二叉樹(shù)的遍歷方法（3）如何建立線索二叉樹(shù)111線索二叉樹(shù)的引入和定義線索二叉樹(shù)的引入和定義所以，所以， 空指針數(shù)目空指針數(shù)目2n(n-1)=n+1個(gè)個(gè)。證明：證明：用二叉鏈表存儲(chǔ)包含用二叉鏈表存儲(chǔ)包含n n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)必有個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)必有2n個(gè)鏈域。個(gè)鏈域。除根結(jié)點(diǎn)外，二叉樹(shù)中每一個(gè)結(jié)點(diǎn)除根結(jié)點(diǎn)外，二叉樹(shù)中每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親有且僅有一個(gè)雙親，即每個(gè)結(jié)點(diǎn)地址占用了雙親的一個(gè)直接后繼，即每個(gè)結(jié)點(diǎn)地址占用了雙親的一個(gè)直接后繼，n n個(gè)結(jié)點(diǎn)地址共個(gè)結(jié)點(diǎn)地址共占用了占用了n-1n-1個(gè)雙親的指針域個(gè)雙親的指針域。也就是說(shuō)，只會(huì)有。也就是說(shuō)，只會(huì)有n n1 1個(gè)結(jié)點(diǎn)的

54、個(gè)結(jié)點(diǎn)的鏈域存放指針。鏈域存放指針。用二叉鏈表法存儲(chǔ)包含用二叉鏈表法存儲(chǔ)包含n n個(gè)結(jié)點(diǎn)的二叉?zhèn)€結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)的指針區(qū)域中會(huì)有樹(shù)，結(jié)點(diǎn)的指針區(qū)域中會(huì)有n+1n+1個(gè)空指?jìng)€(gè)空指針。針。112adebcf rootlchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):fabcde113思考：思考：二叉鏈表空間效率這么低，能否利用二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？這些空閑區(qū)存放有用的信息或線索？可以用它來(lái)存放當(dāng)前結(jié)點(diǎn)的可以用它來(lái)存放當(dāng)前結(jié)點(diǎn)的直接前驅(qū)和后直接前驅(qū)和后繼繼等線索，以加快查找速度。等線索，以加快查找速度。這就是這就是（threaded binary tr

55、ee） 對(duì)二叉樹(shù)進(jìn)行某種遍歷之后，將得到一個(gè)對(duì)二叉樹(shù)進(jìn)行某種遍歷之后，將得到一個(gè)線性有序的序列。線性有序的序列。例如對(duì)某二叉樹(shù)的例如對(duì)某二叉樹(shù)的中序遍歷中序遍歷結(jié)果是結(jié)果是b d c e a f h gb d c e a f h g，意味著，意味著已將該樹(shù)轉(zhuǎn)已將該樹(shù)轉(zhuǎn)為線性排列，顯然其中結(jié)點(diǎn)為線性排列，顯然其中結(jié)點(diǎn)具有唯一前驅(qū)和唯具有唯一前驅(qū)和唯一后繼。一后繼。討論討論1 1：二叉樹(shù)是二叉樹(shù)是1:21:2的非線性結(jié)構(gòu)，如的非線性結(jié)構(gòu)，如何定義其直接后繼？何定義其直接后繼？先定義遍歷規(guī)則，然后才能定義先定義遍歷規(guī)則，然后才能定義直接前驅(qū)和后繼。直接前驅(qū)和后繼。115討論討論2 2：如何獲得這種如

56、何獲得這種“直接前驅(qū)直接前驅(qū)”或或“直接后繼直接后繼”？有何意義？有何意義？二叉樹(shù)中容易找到結(jié)點(diǎn)的二叉樹(shù)中容易找到結(jié)點(diǎn)的左右孩子左右孩子信息，信息，但該結(jié)點(diǎn)的直接前驅(qū)和直接后繼只能在某種但該結(jié)點(diǎn)的直接前驅(qū)和直接后繼只能在某種遍歷過(guò)程中遍歷過(guò)程中動(dòng)態(tài)動(dòng)態(tài)獲得。獲得。先依先依遍歷規(guī)則遍歷規(guī)則把每個(gè)結(jié)點(diǎn)對(duì)應(yīng)的把每個(gè)結(jié)點(diǎn)對(duì)應(yīng)的前驅(qū)前驅(qū)和和后繼線索后繼線索預(yù)存預(yù)存起來(lái)，這叫做起來(lái)，這叫做“線索化線索化”。意義：意義：從從任一結(jié)點(diǎn)任一結(jié)點(diǎn)出發(fā)都能快速找到其出發(fā)都能快速找到其前驅(qū)和后繼，且前驅(qū)和后繼，且不必借助堆棧。不必借助堆棧。 每個(gè)結(jié)點(diǎn)增加兩個(gè)域：每個(gè)結(jié)點(diǎn)增加兩個(gè)域：fwd和和bwd；存放前驅(qū)指針存放前

57、驅(qū)指針存放后繼指針存放后繼指針如何預(yù)存這類信息？如何預(yù)存這類信息？ 與原有的左右孩子指針域與原有的左右孩子指針域“復(fù)用復(fù)用”，充分利用那，充分利用那n+1個(gè)空鏈域。個(gè)空鏈域。規(guī)規(guī) 定：定：1）若結(jié)點(diǎn)有左子樹(shù)，則）若結(jié)點(diǎn)有左子樹(shù)，則lchild指向其指向其左孩子；否則，左孩子；否則， lchild指向其直接前驅(qū)指向其直接前驅(qū)(即線索即線索)；2）若結(jié)點(diǎn)有右子樹(shù)，則）若結(jié)點(diǎn)有右子樹(shù)，則rchild指向其右指向其右孩子；否則，孩子；否則，rchild指向其直接后繼指向其直接后繼(即即線索線索) 。datalchildrchildfwdbwddatalchildrchild缺點(diǎn)：空間效率太低！缺點(diǎn)：空

58、間效率太低！問(wèn)題：計(jì)算機(jī)如何問(wèn)題：計(jì)算機(jī)如何判斷是孩子指針還判斷是孩子指針還是線索指針？是線索指針？如何區(qū)別？如何區(qū)別？lchildltagdatartag rchild約定約定:當(dāng)當(dāng)tag域?yàn)橛驗(yàn)?時(shí)時(shí),表示表示正常正常情況情況;當(dāng)當(dāng)tag域?yàn)橛驗(yàn)?時(shí)時(shí),表示表示線索線索情況情況.前驅(qū)前驅(qū)(后繼后繼)左左(右右)孩子孩子為區(qū)別兩種不同情況，特增加兩個(gè)標(biāo)志域：為區(qū)別兩種不同情況，特增加兩個(gè)標(biāo)志域：各各1bit1bit1. 有關(guān)線索二叉樹(shù)的幾個(gè)術(shù)語(yǔ)有關(guān)線索二叉樹(shù)的幾個(gè)術(shù)語(yǔ) 線索鏈表：線索鏈表： 線線 索：索：線索二叉樹(shù)：線索二叉樹(shù)： 線線 索索 化：化：用用含含tag的結(jié)點(diǎn)樣式所構(gòu)成的二叉鏈表。

59、的結(jié)點(diǎn)樣式所構(gòu)成的二叉鏈表。指向結(jié)點(diǎn)前驅(qū)和后繼的指針。指向結(jié)點(diǎn)前驅(qū)和后繼的指針。在二叉樹(shù)的結(jié)點(diǎn)上加上線索的二叉樹(shù)。在二叉樹(shù)的結(jié)點(diǎn)上加上線索的二叉樹(shù)。對(duì)二叉樹(shù)以對(duì)二叉樹(shù)以某種次序遍歷某種次序遍歷使其變?yōu)榫€索二使其變?yōu)榫€索二叉樹(shù)的過(guò)程。叉樹(shù)的過(guò)程。線索化過(guò)程就是在遍歷過(guò)程中修改空指針的過(guò)程：線索化過(guò)程就是在遍歷過(guò)程中修改空指針的過(guò)程：將空的將空的lchildlchild改為結(jié)點(diǎn)的直接前驅(qū)；改為結(jié)點(diǎn)的直接前驅(qū)；將空的將空的rchildrchild改為結(jié)點(diǎn)的直接后繼。改為結(jié)點(diǎn)的直接后繼。非空指針仍然指向孩子結(jié)點(diǎn)（稱為非空指針仍然指向孩子結(jié)點(diǎn)（稱為“正常情況正常情況”）119typedef struct

60、 bithrnod telemtype data; struct bithrnode *lchild, *rchild; / 左右指針 pointerthr ltag, rtag; / 左右標(biāo)志 bithrnode, *bithrtree; typedef enum link, thread pointerthr; / link=0:指針，thread=1:線索二叉樹(shù)的二叉線索存儲(chǔ)表示二叉樹(shù)的二叉線索存儲(chǔ)表示在二叉樹(shù)的線索鏈表上添加一個(gè)頭結(jié)點(diǎn)，并在二叉樹(shù)的線索鏈表上添加一個(gè)頭結(jié)點(diǎn)，并令其令其lchild域域的指針指向二叉樹(shù)的的指針指向二叉樹(shù)的根結(jié)點(diǎn)根結(jié)點(diǎn)，其，其rchild域域的指針指向中序遍歷時(shí)訪問(wèn)的的指針指向中序遍歷時(shí)訪問(wèn)的最后一最后一個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)。令二叉樹(shù)中序序列中的第一個(gè)結(jié)點(diǎn)的令二叉樹(shù)中序序列中的第一個(gè)結(jié)點(diǎn)的lchild域域指針和最后一個(gè)結(jié)點(diǎn)指針和最后一個(gè)結(jié)點(diǎn)rchild域域的