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

1、1第第6 6章章 二叉樹和樹二叉樹和樹2【重點掌握重點掌握】： 1. 二叉樹的結(jié)構(gòu)特性二叉樹的結(jié)構(gòu)特性; 2. 二叉樹的各種存儲結(jié)構(gòu)的特點及適用范圍二叉樹的各種存儲結(jié)構(gòu)的特點及適用范圍; 3. 二叉樹各種遍歷策略的遞歸算法，且能靈活運用遍歷算二叉樹各種遍歷策略的遞歸算法，且能靈活運用遍歷算法實現(xiàn)二叉樹的其它操作；法實現(xiàn)二叉樹的其它操作； 4. 最優(yōu)二叉樹的特性，建立最優(yōu)樹和哈夫曼編碼的方法。最優(yōu)二叉樹的特性，建立最優(yōu)樹和哈夫曼編碼的方法。 【掌掌 握握】： 1. 線索二叉樹的建立、使用；線索二叉樹的建立、使用； 2. 樹的各種存儲結(jié)構(gòu)及其特點；樹的各種存儲結(jié)構(gòu)及其特點； 3. 樹、森林與二叉樹

2、之間的轉(zhuǎn)換；樹、森林與二叉樹之間的轉(zhuǎn)換； 4. 樹、森林的遍歷。樹、森林的遍歷。3 線性結(jié)構(gòu)線性結(jié)構(gòu)的特點是邏輯結(jié)構(gòu)簡單，易于進(jìn)行查找、刪除、插入等操的特點是邏輯結(jié)構(gòu)簡單，易于進(jìn)行查找、刪除、插入等操作。其主要用于對客觀世界中具有單一的前驅(qū)和后繼的數(shù)據(jù)關(guān)系進(jìn)行描作。其主要用于對客觀世界中具有單一的前驅(qū)和后繼的數(shù)據(jù)關(guān)系進(jìn)行描述。述。 非線性結(jié)構(gòu)非線性結(jié)構(gòu)是指在該結(jié)構(gòu)中至少存在一個數(shù)據(jù)元素有兩個或兩個以是指在該結(jié)構(gòu)中至少存在一個數(shù)據(jù)元素有兩個或兩個以上的直接前驅(qū)或直接后繼。上的直接前驅(qū)或直接后繼。 樹形結(jié)構(gòu)樹形結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)。樹形結(jié)構(gòu)是結(jié)點之間有分支、是一類重要的非線性結(jié)構(gòu)。樹形結(jié)構(gòu)是

3、結(jié)點之間有分支、并且具有并且具有層次關(guān)系層次關(guān)系的結(jié)構(gòu)，它非常類似于自然界中的樹。樹結(jié)構(gòu)在客觀的結(jié)構(gòu)，它非常類似于自然界中的樹。樹結(jié)構(gòu)在客觀世界是大量存在的，例如世界是大量存在的，例如家譜家譜、行政組織機(jī)構(gòu)行政組織機(jī)構(gòu)都可用樹形象地表示。樹都可用樹形象地表示。樹在計算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用，例如在在計算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯程序編譯程序中，用樹來表示源中，用樹來表示源程序的語法結(jié)構(gòu)；在程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)庫系統(tǒng)中，可用樹來組織信息；在中，可用樹來組織信息；在分析算法分析算法的的行為時，可用樹來描述其執(zhí)行過程等等。行為時，可用樹來描述其執(zhí)行過程等等。 圖形結(jié)構(gòu)圖形結(jié)構(gòu)

4、是十分重要的非線性結(jié)構(gòu)，可以用來描述客觀世界中廣泛是十分重要的非線性結(jié)構(gòu)，可以用來描述客觀世界中廣泛存在的網(wǎng)狀結(jié)構(gòu)的關(guān)系。存在的網(wǎng)狀結(jié)構(gòu)的關(guān)系。46.1 6.1 二叉樹二叉樹6.1.2 6.1.2 二叉樹的基本概念二叉樹的基本概念1.1.二叉樹二叉樹(binary tree)(binary tree) (1) (1)定義：二叉樹是定義：二叉樹是n n（n=0n=0）個數(shù)據(jù)元素的集合，該集合或為空，或個數(shù)據(jù)元素的集合，該集合或為空，或含有唯一的稱為根的元素，且其余元素分成兩個互不相交的子集，每個含有唯一的稱為根的元素，且其余元素分成兩個互不相交的子集，每個子集自身也是一棵二叉樹，分別稱為左子樹和

5、右子樹。子集自身也是一棵二叉樹，分別稱為左子樹和右子樹。說明說明: :1 1）二叉樹是遞歸結(jié)構(gòu)，在二叉樹的定義中又用到了二叉樹的概念）二叉樹是遞歸結(jié)構(gòu)，在二叉樹的定義中又用到了二叉樹的概念2 2）二叉樹中每個結(jié)點最多有兩棵子樹）二叉樹中每個結(jié)點最多有兩棵子樹, ,二叉樹每個結(jié)點度小于等于二叉樹每個結(jié)點度小于等于2 2abcdefg53 3）左、右子樹不能顛例）左、右子樹不能顛例 二叉樹結(jié)點的子樹要區(qū)分左子樹和右子樹：二叉樹結(jié)點的子樹要區(qū)分左子樹和右子樹：即使只有一棵子樹也要即使只有一棵子樹也要進(jìn)行區(qū)分，說明它是左子樹，還是右子樹。這是二叉樹與樹的最主要進(jìn)行區(qū)分，說明它是左子樹，還是右子樹。這是

6、二叉樹與樹的最主要的差別。的差別。abab兩棵不同的二叉樹兩棵不同的二叉樹(2) (2) 二叉樹的二叉樹的 5 5 種基本形態(tài)種基本形態(tài)空二叉樹空二叉樹根和空的根和空的左右子樹左右子樹根和左子樹根和左子樹根和右子樹根和右子樹 根和左右子樹根和左右子樹62. 2. 二叉樹的基本術(shù)語二叉樹的基本術(shù)語 1) 孩子孩子(child)(child)：結(jié)點的子樹的根稱為該結(jié)點的孩子；左孩子，右孩子：結(jié)點的子樹的根稱為該結(jié)點的孩子；左孩子，右孩子。 2) 2) 雙親雙親(parents)(parents)：孩子結(jié)點的上層結(jié)點。：孩子結(jié)點的上層結(jié)點。 3) 3) 兄弟兄弟(sibling)(sibling)：

7、同一雙親的孩子結(jié)點；堂兄弟、祖先結(jié)點、子孫：同一雙親的孩子結(jié)點；堂兄弟、祖先結(jié)點、子孫結(jié)點結(jié)點 4) 4) 葉子葉子(leaf)(leaf)：終端結(jié)點，左右子樹均為空的結(jié)點；反之，分支結(jié)點：終端結(jié)點，左右子樹均為空的結(jié)點；反之，分支結(jié)點。 5) 5) 結(jié)點的度結(jié)點的度(degree)(degree)：結(jié)點擁有的子樹數(shù)。：結(jié)點擁有的子樹數(shù)。 6) 6) 二叉樹的度：二叉樹的度： 樹中最大的結(jié)點度。樹中最大的結(jié)點度。 7) 7) 結(jié)點層結(jié)點層(level)(level)：從根結(jié)點開始算起，根為第一層；根的孩子為第：從根結(jié)點開始算起，根為第一層；根的孩子為第2 2層結(jié)點；層結(jié)點； 8 8）二叉樹的深

8、度）二叉樹的深度(depth)(depth)：二叉樹中葉子結(jié)點的最大層次數(shù)。：二叉樹中葉子結(jié)點的最大層次數(shù)。7二叉樹的基本性質(zhì)二叉樹的基本性質(zhì)性質(zhì)性質(zhì)1 1：一棵非空二叉樹的第一棵非空二叉樹的第i i層上最多有層上最多有2 2i-1i-1個結(jié)點（個結(jié)點（i1i1）。）。8性質(zhì)性質(zhì)2 2：一棵深度為一棵深度為k k的二叉樹中，最多有的二叉樹中，最多有2 2k k-1-1個結(jié)點（個結(jié)點（k1)k1)。 深度為深度為k k的二叉樹取最多結(jié)點時，二叉樹中的每層上均應(yīng)取最多結(jié)的二叉樹取最多結(jié)點時，二叉樹中的每層上均應(yīng)取最多結(jié)點。根據(jù)性質(zhì)點。根據(jù)性質(zhì)1 1得到每層上的最大結(jié)點數(shù)為得到每層上的最大結(jié)點數(shù)為2

9、 2i-1i-1，則二叉樹中的總結(jié)點，則二叉樹中的總結(jié)點數(shù)為：數(shù)為：20 + 2 1+ 2 k-1 = 2k-1。 4 2 3 1 6 7 8 9101112131415 5此樹的深度此樹的深度k=4k=4，共有，共有2 24 4-1=15-1=15個結(jié)點個結(jié)點9性質(zhì)性質(zhì)3 3：對于非空二叉樹，如果葉子結(jié)點數(shù)為對于非空二叉樹，如果葉子結(jié)點數(shù)為n n0 0，度為，度為2 2的結(jié)點數(shù)為的結(jié)點數(shù)為n n2 2，則有則有n n0 0=n=n2 2+1+1。證明：設(shè)二叉樹中度為證明：設(shè)二叉樹中度為1 1的結(jié)點數(shù)為的結(jié)點數(shù)為n n1 1，二叉樹中總結(jié)點數(shù)為，二叉樹中總結(jié)點數(shù)為n n，因為二，因為二叉樹中所

10、有結(jié)點均小于或等于叉樹中所有結(jié)點均小于或等于2 2，所以有：，所以有： n nn n0 0n n1 1n n2 2 (6-1) (6-1) 再看二叉樹中的分支數(shù)，除根結(jié)點外，其余結(jié)點都由一個分支與其再看二叉樹中的分支數(shù)，除根結(jié)點外，其余結(jié)點都由一個分支與其雙親相連接，設(shè)雙親相連接，設(shè)b b為二叉樹中的分支總數(shù)，則有：為二叉樹中的分支總數(shù)，則有： n nb b1 1 （6-2)6-2) 由于這些分支都是由度為由于這些分支都是由度為1 1和和2 2的結(jié)點射出的，所以有：的結(jié)點射出的，所以有： b bn n1 1+2+2* *n n2 2 （6-3)6-3) 即：即：n nb b1 1n n1 12

11、 2n n2 21 1 由式（由式（6-16-1）得到：）得到：n n0 0+n+n1 1+n+n2 2=n=n1 1+2+2* *n n2 2+1+1 即：即：n n0 0n n2 21 1n n0 0=3=3n n2 2=2=2abcdefg10 兩種特殊的二叉樹兩種特殊的二叉樹(1) (1) 滿二叉樹滿二叉樹：如果深度為：如果深度為k k的二叉樹有的二叉樹有2 2k k-1-1個結(jié)點，則稱為滿二叉樹。個結(jié)點，則稱為滿二叉樹。 特點：每一層上都含有最大結(jié)點數(shù)。特點：每一層上都含有最大結(jié)點數(shù)。k=4k=4的滿二叉樹的滿二叉樹 42316789101112131415511（2 2）完全二叉樹

12、完全二叉樹：如果二叉樹除最后一層外每一層都是滿的，且最后一：如果二叉樹除最后一層外每一層都是滿的，且最后一層或者是滿的，或者結(jié)點都連續(xù)地集中在該層的最左端，則稱其為完全二層或者是滿的，或者結(jié)點都連續(xù)地集中在該層的最左端，則稱其為完全二叉樹。叉樹。123114589126710特點：特點：1)1)所有的葉子結(jié)點都出現(xiàn)在第所有的葉子結(jié)點都出現(xiàn)在第k k層或?qū)踊騥-1k-1層層; ; 2) 2)對任一結(jié)點，如果其右子樹的最大層次為對任一結(jié)點，如果其右子樹的最大層次為l l，則其左子樹的最，則其左子樹的最 大層次為大層次為l l或或l+1l+1。12123456 非完全二叉樹非完全二叉樹1231145

13、89121367101415滿二叉樹（完全二叉樹滿二叉樹（完全二叉樹) )123114589126710 完全二叉樹完全二叉樹1234567 非完全二叉樹非完全二叉樹13性質(zhì)性質(zhì)4 4：具有具有n n個結(jié)點的完全二叉樹的深度為：個結(jié)點的完全二叉樹的深度為： loglog2 2n+1n+1。（符號。（符號x x 表示不大于表示不大于x x的最大整數(shù)）的最大整數(shù)） 4231678542316789 10 11 12 13 14 155n2k-1n2k-1 2k-1n2k-1 取對數(shù)得到：k-1log2n1i1，則其雙親，則其雙親是結(jié)點是結(jié)點i/2i/2 ； （2 2）如果）如果2in2in，則其左

14、孩子是結(jié)點，則其左孩子是結(jié)點2i2i；否則；否則i i無左孩子、為葉子結(jié)無左孩子、為葉子結(jié)點；點； （3 3）如果）如果2i+1n2i+1n，則其右孩子是結(jié)點，則其右孩子是結(jié)點2i2i1 1；否則結(jié)點；否則結(jié)點i i無右孩子。無右孩子。abcdefg1234568d7156.2 6.2 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu) 1. 1. 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) 所謂二叉樹的順序存儲，就是用一組連續(xù)的存儲單元存放二叉樹的所謂二叉樹的順序存儲，就是用一組連續(xù)的存儲單元存放二叉樹的結(jié)點。一般是按照從上至下、從左至右的順序存儲。但是，這樣存儲后結(jié)點。一般是按照從上至下、從左至右的順序存儲。但是，這樣存儲后

15、結(jié)點在存儲位置上的前驅(qū)、后繼關(guān)系并不一定就是它們在邏輯上的鄰接結(jié)點在存儲位置上的前驅(qū)、后繼關(guān)系并不一定就是它們在邏輯上的鄰接關(guān)系關(guān)系，只有通過一些方法能夠確定結(jié)點在邏輯上的前驅(qū)和后繼結(jié)點，這，只有通過一些方法能夠確定結(jié)點在邏輯上的前驅(qū)和后繼結(jié)點，這種存儲才有意義。種存儲才有意義。 (1) (1)完全二叉樹的順序存儲完全二叉樹的順序存儲 完全二叉樹按照這種編號方式時，所有結(jié)點編號時連續(xù)的；完全二叉樹按照這種編號方式時，所有結(jié)點編號時連續(xù)的；，這，這樣既能夠最大可能地節(jié)省存儲空間，又可以利用數(shù)組元素的下標(biāo)值確定樣既能夠最大可能地節(jié)省存儲空間，又可以利用數(shù)組元素的下標(biāo)值確定結(jié)點在二叉樹中的位置以及結(jié)

16、點之間的關(guān)系。所以比較適合于采用順序結(jié)點在二叉樹中的位置以及結(jié)點之間的關(guān)系。所以比較適合于采用順序存儲方式。存儲方式。 16若父結(jié)點在數(shù)組中若父結(jié)點在數(shù)組中 i 下標(biāo)處，其左孩子在下標(biāo)處，其左孩子在2*i處，右孩子在處，右孩子在2*i+1處；處；結(jié)點結(jié)點i的雙親是的雙親是 i/2i/2。例如下完全二叉樹：例如下完全二叉樹：17(2)(2)一般二叉樹的順序存儲一般二叉樹的順序存儲 對于一般二叉樹，如果仍按從上至下、從左至右的順序?qū)渲械膶τ谝话愣鏄?，如果仍按從上至下、從左至右的順序?qū)渲械慕Y(jié)點順序地存儲在一維數(shù)組中可，則數(shù)組元素下標(biāo)之間的關(guān)系不能反結(jié)點順序地存儲在一維數(shù)組中可，則數(shù)組元素下標(biāo)之

17、間的關(guān)系不能反映二叉樹中結(jié)點之間的邏輯關(guān)系，只有映二叉樹中結(jié)點之間的邏輯關(guān)系，只有，使其成為一棵完全二叉樹，再用一維數(shù)組存儲。使其成為一棵完全二叉樹，再用一維數(shù)組存儲。1111abcfed 1 1 2 2 4 4 8 8 9 91010 5 5 6 6 3 3 7 71514131211109876543210fe000dc0ba0 表示該處沒有元素存在表示該處沒有元素存在18 這種存儲方式對于需增加結(jié)點才能將一棵二叉樹改造成一棵完全二這種存儲方式對于需增加結(jié)點才能將一棵二叉樹改造成一棵完全二叉樹的存儲時叉樹的存儲時, ,會造成空間的大量浪費，不宜采取順序結(jié)構(gòu)。最壞的情況會造成空間的大量浪費，

18、不宜采取順序結(jié)構(gòu)。最壞的情況是單支樹。是單支樹。abdcabdc 192.2.鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu) 用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。（1 1）二叉鏈表）二叉鏈表 鏈表中每個結(jié)點包含三個域，除數(shù)據(jù)域外，還有兩個指針域，分別用鏈表中每個結(jié)點包含三個域，除數(shù)據(jù)域外，還有兩個指針域，分別用來給出該結(jié)點的左孩子和右孩子所在的結(jié)點的存儲地址。來給出該結(jié)點的左孩子和右孩子所在的結(jié)點的存儲地址。 結(jié)點的存儲結(jié)構(gòu)為：結(jié)點的存儲結(jié)構(gòu)為： lchilddatarchild結(jié)點存儲結(jié)構(gòu)的描述：結(jié)點存儲結(jié)構(gòu)的描述：typedef struct

19、bitnode datatype data; struct bitnode *lchild,*rchild; bitnode, *bitree;20abcdefg在在n n個結(jié)點的二叉鏈表中，有個結(jié)點的二叉鏈表中，有n+1n+1個空指針域。個空指針域。 ab c d e f g21(2) (2) 三叉鏈表存儲結(jié)構(gòu)三叉鏈表存儲結(jié)構(gòu) 三叉鏈表中每個結(jié)點由三叉鏈表中每個結(jié)點由4 4個域組成：個域組成：、。rchilddatalchildparent 域為指向該結(jié)點雙親結(jié)點的指針。域為指向該結(jié)點雙親結(jié)點的指針。 這種結(jié)構(gòu)既便于查找孩子結(jié)點，又便于查找雙親結(jié)點；但是，相這種結(jié)構(gòu)既便于查找孩子結(jié)點，又便于

20、查找雙親結(jié)點；但是，相對二叉鏈表而言它增加了空間開銷。對二叉鏈表而言它增加了空間開銷。 盡管在二叉鏈表中無法由結(jié)點直接找到其雙親，但由于二叉鏈表盡管在二叉鏈表中無法由結(jié)點直接找到其雙親，但由于二叉鏈表結(jié)構(gòu)靈活，操作方便，對于一般情況的二叉樹，甚至比順序結(jié)構(gòu)還節(jié)結(jié)構(gòu)靈活，操作方便，對于一般情況的二叉樹，甚至比順序結(jié)構(gòu)還節(jié)省空間。因此，省空間。因此，是最常用的二叉樹存儲方式。是最常用的二叉樹存儲方式。22abcdefg a b c d e f g三叉鏈表示意圖三叉鏈表示意圖236.2 6.2 二叉樹的遍歷二叉樹的遍歷6.2.1 6.2.1 二叉樹的遍歷算法及遞歸實現(xiàn)二叉樹的遍歷算法及遞歸實現(xiàn) 遍歷

21、：按某種搜索路徑訪問二叉樹的每個結(jié)點，使每個結(jié)點被訪問一遍歷：按某種搜索路徑訪問二叉樹的每個結(jié)點，使每個結(jié)點被訪問一次且僅被訪問一次。次且僅被訪問一次。 遍歷是二叉樹經(jīng)常要用到的一種操作。因為在實際應(yīng)用問題中，常要遍歷是二叉樹經(jīng)常要用到的一種操作。因為在實際應(yīng)用問題中，常要按一定次序?qū)Χ鏄渲械拿總€結(jié)點做逐一訪問，或查找具有某個特點的按一定次序?qū)Χ鏄渲械拿總€結(jié)點做逐一訪問，或查找具有某個特點的結(jié)點，然后對這些滿足條件的結(jié)點進(jìn)行處理。遍歷是各種數(shù)據(jù)結(jié)構(gòu)最基結(jié)點，然后對這些滿足條件的結(jié)點進(jìn)行處理。遍歷是各種數(shù)據(jù)結(jié)構(gòu)最基本的操作，許多其他的操作可以在遍歷基礎(chǔ)上實現(xiàn)。本的操作，許多其他的操作可以在遍

22、歷基礎(chǔ)上實現(xiàn)。 訪問：含義很廣，可以是對結(jié)點的各種處理，如修改結(jié)點數(shù)據(jù)、輸出訪問：含義很廣，可以是對結(jié)點的各種處理，如修改結(jié)點數(shù)據(jù)、輸出結(jié)點數(shù)據(jù)。結(jié)點數(shù)據(jù)。 如何訪問二叉樹，如何訪問二叉樹， 使每個結(jié)點僅被訪問一次？使每個結(jié)點僅被訪問一次？24 由二叉樹的定義可知，一棵二叉樹是由根結(jié)點、根結(jié)點的左子樹、根由二叉樹的定義可知，一棵二叉樹是由根結(jié)點、根結(jié)點的左子樹、根結(jié)點的右子樹三部分組成。因此，只要依次遍歷這三部分，就可以遍歷整結(jié)點的右子樹三部分組成。因此，只要依次遍歷這三部分，就可以遍歷整個二叉樹。個二叉樹。 二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹。二叉樹的遍歷可以分解為：訪問

23、根，遍歷左子樹和遍歷右子樹。令：令：l：遍歷左子樹：遍歷左子樹 d：訪問根結(jié)點：訪問根結(jié)點 r：遍歷右子樹：遍歷右子樹 有六種遍歷方法：有六種遍歷方法： dlr，ldr，lrd， drl，rdl，rld 約定先左后右約定先左后右, ,有三種遍歷方法：有三種遍歷方法： dlr、ldr、lrd ，分別稱為，分別稱為先序遍歷、中序遍歷、后序遍歷。先序遍歷、中序遍歷、后序遍歷。dlrldr、lrd、dlrrdl、rld、drl25 1.1.先序遍歷（先序遍歷（dlr） 若二叉樹空，遍歷結(jié)束。否則，若二叉樹空，遍歷結(jié)束。否則， （1 1）訪問根結(jié)點；）訪問根結(jié)點； （2 2）先序遍歷根結(jié)點的左子樹；）先

24、序遍歷根結(jié)點的左子樹； （3 3）先序遍歷根結(jié)點的右子樹；）先序遍歷根結(jié)點的右子樹； 先序遍歷序列為：先序遍歷序列為：a, b ,d ,e, g, c ,f例：先序遍歷右圖所示的二叉樹例：先序遍歷右圖所示的二叉樹 （1 1）訪問根結(jié)點）訪問根結(jié)點a （2 2）先序遍歷）先序遍歷a的左子樹：即按的左子樹：即按dlr順序遍歷順序遍歷a的左子樹的左子樹 （3 3）先序遍歷）先序遍歷a的右子樹：即按的右子樹：即按dlr順序遍歷順序遍歷a的右子樹的右子樹abcdefg26adbcd l rad l rd l rbdcd l r先序遍歷序列：先序遍歷序列：a b d c先序遍歷過程示例:27void pr

25、eorder(bitree t) /采用二叉鏈表結(jié)構(gòu)，采用二叉鏈表結(jié)構(gòu)，visit( )是訪問結(jié)點的函數(shù)是訪問結(jié)點的函數(shù) if (t) /若若t=null時時,遞歸調(diào)用結(jié)束遞歸調(diào)用結(jié)束visit(t)； /訪問根結(jié)點訪問根結(jié)點preorder(t-lchild); /先序遍歷左子樹先序遍歷左子樹preorder(t-rchild); /先序遍歷右子樹先序遍歷右子樹 先序遍歷遞歸算法先序遍歷遞歸算法 對于根結(jié)點，最簡單的對于根結(jié)點，最簡單的“訪問訪問”是輸出處理是輸出處理。28例例. .求二叉樹中的葉子結(jié)點數(shù)求二叉樹中的葉子結(jié)點數(shù)需要對二叉樹中的每個結(jié)點都進(jìn)行判斷需要對二叉樹中的每個結(jié)點都進(jìn)行判

26、斷 借用遍歷算法（如：先序遍歷算法）借用遍歷算法（如：先序遍歷算法） 方法：當(dāng)訪問到某個結(jié)點時，進(jìn)行是否是葉子結(jié)點的判斷；方法：當(dāng)訪問到某個結(jié)點時，進(jìn)行是否是葉子結(jié)點的判斷； 如果是葉子結(jié)點，則將計數(shù)器加如果是葉子結(jié)點，則將計數(shù)器加1 1看先序遍歷算法看先序遍歷算法29 應(yīng)用遍歷算法求二叉樹中的葉子結(jié)點數(shù)應(yīng)用遍歷算法求二叉樹中的葉子結(jié)點數(shù)void preoder (bitree t) if (t) visit(t)； preorder(t-lchild); preorder(t-rchild); 本算法中的本算法中的訪問是什么？訪問是什么？ 判斷判斷t是否為葉子結(jié)點是否為葉子結(jié)點t-lchil

27、id=null & t-rchild=null是葉子結(jié)點則計數(shù)器加是葉子結(jié)點則計數(shù)器加1n+;30void preoder (bitree t) if (t) visit(t)； preorder(t-lchild); preorder(t-rchild); void preoder (bitree t) if (t) if (t-lchilid=null & t-rchild=null) n+; preorder(t-lchild); preorder(t-rchild); 可以為函數(shù)可以為函數(shù)換個名字換個名字（見名知義）（見名知義）31void countleaf(bitr

28、ee t)if (t) if (t-lchild=null & t-rchild=null) n+; /*若若t為葉子，則累加為葉子，則累加 */ countleaf (t-lchild); /*統(tǒng)計左子樹中的葉子統(tǒng)計左子樹中的葉子*/ countleaf (t-rchild); /*統(tǒng)計右子樹中的葉子統(tǒng)計右子樹中的葉子*/ 調(diào)用前調(diào)用前n的初值的初值為為032void countleaf(bitree t)if (t) if (t-lchild=null & t-rchild=null) n+; /*若若t為葉子，則累加為葉子，則累加 */ countleaf (t-lchi

29、ld); /*統(tǒng)計左子樹中的葉子統(tǒng)計左子樹中的葉子*/ countleaf (t-rchild); /*統(tǒng)計右子樹中的葉子統(tǒng)計右子樹中的葉子*/ int n=0; main()bitree t; /*建立二叉鏈表結(jié)構(gòu)*/ countleaf(t); printf(“the numbers of leaf: %d n”, n);332.2.中序遍歷（中序遍歷（ldr）若二叉樹為空，遍歷結(jié)束。否則，若二叉樹為空，遍歷結(jié)束。否則，（1 1）中序遍歷根結(jié)點的左子樹）中序遍歷根結(jié)點的左子樹（2 2）訪問根結(jié)點）訪問根結(jié)點（3 3）中序遍歷根結(jié)點的右子樹）中序遍歷根結(jié)點的右子樹 中序遍歷序列：中序遍歷序列

30、：d,b,g,e,a,c,f例：中序遍歷右圖所示的二叉樹：例：中序遍歷右圖所示的二叉樹： （1 1）中序遍歷）中序遍歷a的左子樹：即按的左子樹：即按ldr的順序遍歷的順序遍歷a的左子樹的左子樹 （2 2）訪問根結(jié)點）訪問根結(jié)點a （3 3）中序遍歷）中序遍歷a的右子樹：即按的右子樹：即按ldr的順序遍歷的順序遍歷a的右子樹的右子樹abcdefg問題問題：如何確定中序遍歷過程中的第一個結(jié)點：如何確定中序遍歷過程中的第一個結(jié)點? ?從根結(jié)點向左子樹查找，第一個左子樹為空的結(jié)點。從根結(jié)點向左子樹查找，第一個左子樹為空的結(jié)點。34 void inorder (bitree t) if (t=null)

31、 return; /*遞歸遍歷結(jié)束遞歸遍歷結(jié)束*/ inorder(t-lchild); /*中序遍歷中序遍歷t的左子樹的左子樹*/ visit(t-data)； /*訪問根結(jié)點訪問根結(jié)點*/ inorder(t-rchild); /*中序遍歷中序遍歷t的右子樹的右子樹*/中序遍歷遞歸算法：中序遍歷遞歸算法：35adbcl d rbl d rl d radcl d r中序遍歷序列：中序遍歷序列：b d a c中序遍歷過程示例中序遍歷過程示例:363.3.后序遍歷（后序遍歷（lrd） 若二叉樹為空，則遍歷結(jié)束。否則，若二叉樹為空，則遍歷結(jié)束。否則，（1 1）后序遍歷根結(jié)點的左子樹）后序遍歷根結(jié)點

32、的左子樹（2 2）后序遍歷根結(jié)點的右子樹）后序遍歷根結(jié)點的右子樹（3 3）訪問根結(jié)點）訪問根結(jié)點 后序遍歷序列：后序遍歷序列： g,d,b,e,f,c,a例：后序遍歷右圖所示的二叉樹例：后序遍歷右圖所示的二叉樹 （1 1）后序遍歷）后序遍歷a的左子樹：即按的左子樹：即按lrd的順序遍歷的順序遍歷a的左子樹的左子樹 （2 2）后序遍歷）后序遍歷a的右子樹：即按的右子樹：即按lrd的順序遍歷的順序遍歷a的右子樹的右子樹 （3 3）訪問根結(jié)點）訪問根結(jié)點a問題：問題：如何確定后序遍歷過程中的第一個結(jié)點如何確定后序遍歷過程中的第一個結(jié)點? ?從根結(jié)點向左子樹查找，找到第一個左子樹為空的結(jié)點，接著向右子

33、樹從根結(jié)點向左子樹查找，找到第一個左子樹為空的結(jié)點，接著向右子樹找，至一葉子結(jié)點。找，至一葉子結(jié)點。abefdgc37void postorder(bitree t) if(t=null) return; postorder(t-lchild); postorder(t-rchild); visit(t-data); 后序遍歷遞歸算法：后序遍歷遞歸算法：38adbc l r dl r dl r dadcl r d后序遍歷序列：后序遍歷序列： d b c a后序遍歷過程示例后序遍歷過程示例:b396.2.2 6.2.2 由遍歷序列恢復(fù)二叉樹由遍歷序列恢復(fù)二叉樹 任意一棵二叉樹結(jié)點的先序序列和中序

34、序列都是惟一的。反過任意一棵二叉樹結(jié)點的先序序列和中序序列都是惟一的。反過來，若已知結(jié)點的先序序列和中序序列，也能惟一地確定這棵二叉樹。來，若已知結(jié)點的先序序列和中序序列，也能惟一地確定這棵二叉樹。 在先序序列中，第一個結(jié)點一定是二叉樹的根結(jié)點在先序序列中，第一個結(jié)點一定是二叉樹的根結(jié)點 中序序列必然以根為界分割成兩個子序列，前一個子序列是根結(jié)點中序序列必然以根為界分割成兩個子序列，前一個子序列是根結(jié)點的左子樹的中序序列，而后一個子序列是根結(jié)點的右子樹的中序序列的左子樹的中序序列，而后一個子序列是根結(jié)點的右子樹的中序序列 在先序序列中，左子序列的第一個結(jié)點是左子樹的根結(jié)點，右子序在先序序列中，

35、左子序列的第一個結(jié)點是左子樹的根結(jié)點，右子序列中的第一個結(jié)點是右子樹的根結(jié)點列中的第一個結(jié)點是右子樹的根結(jié)點 左子樹和右子樹的根結(jié)點又在中序序列中分別把左子序列和右子序左子樹和右子樹的根結(jié)點又在中序序列中分別把左子序列和右子序列劃分成兩個子序列列劃分成兩個子序列 ，如此遞歸下去，當(dāng)取盡先序序列中的結(jié)點時，便可以得到一，如此遞歸下去，當(dāng)取盡先序序列中的結(jié)點時，便可以得到一棵二叉樹?？枚鏄?。先序序列先序序列中序序列中序序列40例：已知一棵二叉樹的先序序列和中序序列分別為例：已知一棵二叉樹的先序序列和中序序列分別為: 先序序列：先序序列：abcdefghi 中序序列：中序序列：bcaedghfi

36、試恢復(fù)該二叉樹。試恢復(fù)該二叉樹。a先：先：bc中：中：bc先：先：defghi中：中：edghfiabdce先：先：fghi中：中：ghfiabdcef先：先：gh中：中：ghiabdcefigh41二叉樹中的所有結(jié)點二叉樹中的所有結(jié)點 借用遍歷算法借用遍歷算法 問題問題1：使用哪種遍歷算法？：使用哪種遍歷算法？ 先序遍歷算法先序遍歷算法 問題問題2：“訪問訪問”所對應(yīng)的運算是什么？所對應(yīng)的運算是什么？ 建立該結(jié)點（分配存儲空間），對其賦值。建立該結(jié)點（分配存儲空間），對其賦值。 【例例1 1】 建立二叉樹的存儲結(jié)構(gòu)建立二叉樹的存儲結(jié)構(gòu) - - 二叉鏈表二叉鏈表6.2.3 遍歷算法的應(yīng)用42方

37、法：方法： 輸入先序序列（在空子樹處添加字符輸入先序序列（在空子樹處添加字符# #），按先序遍歷），按先序遍歷的順序，在遍歷過程中建立二叉鏈表的所有結(jié)點并完成相應(yīng)的順序，在遍歷過程中建立二叉鏈表的所有結(jié)點并完成相應(yīng)結(jié)點的鏈接。結(jié)點的鏈接。輸入序列：輸入序列：a b d # f # # c e # # #afedcb*43bitree creatbitree(bitree &t)/ 在先序遍歷二叉樹過程中輸入結(jié)點字符在先序遍歷二叉樹過程中輸入結(jié)點字符,建立二叉建立二叉鏈表存儲結(jié)構(gòu)鏈表存儲結(jié)構(gòu) / 指針指針t指向所建二叉樹的根結(jié)點指向所建二叉樹的根結(jié)點 cinch; if(ch=#) t=null; /建空樹建空樹 else t=new bitnode;/生成根結(jié)點生成根結(jié)點 t-data=ch; creatbitree(t-lchild);/構(gòu)造左子樹構(gòu)造左子樹creatbitree(t-rchild); /構(gòu)造右子樹構(gòu)造右子樹 adbc輸入序列：輸入序列：a b # d # # c # #44 通常，一個表達(dá)式由一個運算符和兩個操作數(shù)構(gòu)成。通常，一個表達(dá)式由一個運算符和兩個操作數(shù)構(gòu)成。 即，表達(dá)式即，表達(dá)式 = ( = (第一操作數(shù)第一操作數(shù)) () (運算符運算符) () (第二操作數(shù)第二操作數(shù)) )其中，