數(shù)據(jù)結構第六章二叉樹

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

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

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

4、是十分重要的非線性結構，可以用來描述客觀世界中廣泛是十分重要的非線性結構，可以用來描述客觀世界中廣泛存在的網(wǎng)狀結構的關系。存在的網(wǎng)狀結構的關系。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）二叉樹是遞歸結構，在二叉樹的定義中又用到了二叉樹的概念）二叉樹是遞歸結構，在二叉樹的定義中又用到了二叉樹的概念2 2）二叉樹中每個結點最多有兩棵子樹）二叉樹中每個結點最多有兩棵子樹, ,二叉樹每個結點度小于等于二叉樹每個結點度小于等于2 2abcdefg53 3）左、右子樹不能顛例）左、右子樹不能顛例 二叉樹結點的子樹要區(qū)分左子樹和右子樹：二叉樹結點的子樹要區(qū)分左子樹和右子樹：即使只有一棵子樹也要即使只有一棵子樹也要進行區(qū)分，說明它是左子樹，還是右子樹。這是二叉樹與樹的最主要進行區(qū)分，說明它是左子樹，還是右子樹。這是

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

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

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

9、 2i-1i-1，則二叉樹中的總結點，則二叉樹中的總結點數(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個結點個結點9性質性質3 3：對于非空二叉樹，如果葉子結點數(shù)為對于非空二叉樹，如果葉子結點數(shù)為n n0 0，度為，度為2 2的結點數(shù)為的結點數(shù)為n n2 2，則有則有n n0 0=n=n2 2+1+1。證明：設二叉樹中度為證明：設二叉樹中度為1 1的結點數(shù)為的結點數(shù)為n n1 1，二叉樹中總結點數(shù)為，二叉樹中總結點數(shù)為n n，因為二，因為二叉樹中所

10、有結點均小于或等于叉樹中所有結點均小于或等于2 2，所以有：，所以有： n nn n0 0n n1 1n n2 2 (6-1) (6-1) 再看二叉樹中的分支數(shù)，除根結點外，其余結點都由一個分支與其再看二叉樹中的分支數(shù)，除根結點外，其余結點都由一個分支與其雙親相連接，設雙親相連接，設b b為二叉樹中的分支總數(shù)，則有：為二叉樹中的分支總數(shù)，則有： n nb b1 1 （6-2)6-2) 由于這些分支都是由度為由于這些分支都是由度為1 1和和2 2的結點射出的，所以有：的結點射出的，所以有： 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個結點，則稱為滿二叉樹。個結點，則稱為滿二叉樹。 特點：每一層上都含有最大結點數(shù)。特點：每一層上都含有最大結點數(shù)。k=4k=4的滿二叉樹的滿二叉樹 42316789101112131415511（2 2）完全二叉樹

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

13、89121367101415滿二叉樹（完全二叉樹滿二叉樹（完全二叉樹) )123114589126710 完全二叉樹完全二叉樹1234567 非完全二叉樹非完全二叉樹13性質性質4 4：具有具有n n個結點的完全二叉樹的深度為：個結點的完全二叉樹的深度為： 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，則其雙親，則其雙親是結點是結點i/2i/2 ； （2 2）如果）如果2in2in，則其左

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

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

16、點之間的關系。所以比較適合于采用順序結點在二叉樹中的位置以及結點之間的關系。所以比較適合于采用順序存儲方式。存儲方式。 16若父結點在數(shù)組中若父結點在數(shù)組中 i 下標處，其左孩子在下標處，其左孩子在2*i處，右孩子在處，右孩子在2*i+1處；處；結點結點i的雙親是的雙親是 i/2i/2。例如下完全二叉樹：例如下完全二叉樹：17(2)(2)一般二叉樹的順序存儲一般二叉樹的順序存儲 對于一般二叉樹，如果仍按從上至下、從左至右的順序將樹中的對于一般二叉樹，如果仍按從上至下、從左至右的順序將樹中的結點順序地存儲在一維數(shù)組中可，則數(shù)組元素下標之間的關系不能反結點順序地存儲在一維數(shù)組中可，則數(shù)組元素下標之

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

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

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

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

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

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

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

24、序遍歷根結點的左子樹； （3 3）先序遍歷根結點的右子樹；）先序遍歷根結點的右子樹； 先序遍歷序列為：先序遍歷序列為：a, b ,d ,e, g, c ,f例：先序遍歷右圖所示的二叉樹例：先序遍歷右圖所示的二叉樹 （1 1）訪問根結點）訪問根結點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) /采用二叉鏈表結構，采用二叉鏈表結構，visit( )是訪問結點的函數(shù)是訪問結點的函數(shù) if (t) /若若t=null時時,遞歸調用結束遞歸調用結束visit(t)； /訪問根結點訪問根結點preorder(t-lchild); /先序遍歷左子樹先序遍歷左子樹preorder(t-rchild); /先序遍歷右子樹先序遍歷右子樹 先序遍歷遞歸算法先序遍歷遞歸算法 對于根結點，最簡單的對于根結點，最簡單的“訪問訪問”是輸出處理是輸出處理。28例例. .求二叉樹中的葉子結點數(shù)求二叉樹中的葉子結點數(shù)需要對二叉樹中的每個結點都進行判斷需要對二叉樹中的每個結點都進行判

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

27、id=null & t-rchild=null是葉子結點則計數(shù)器加是葉子結點則計數(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)計右子樹中的葉子*/ 調用前調用前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; /*建立二叉鏈表結構*/ countleaf(t); printf(“the numbers of leaf: %d n”, n);332.2.中序遍歷（中序遍歷（ldr）若二叉樹為空，遍歷結束。否則，若二叉樹為空，遍歷結束。否則，（1 1）中序遍歷根結點的左子樹）中序遍歷根結點的左子樹（2 2）訪問根結點）訪問根結點（3 3）中序遍歷根結點的右子樹）中序遍歷根結點的右子樹 中序遍歷序列：中序遍歷序列

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

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

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

33、樹從根結點向左子樹查找，找到第一個左子樹為空的結點，接著向右子樹找，至一葉子結點。找，至一葉子結點。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 由遍歷序列恢復二叉樹由遍歷序列恢復二叉樹 任意一棵二叉樹結點的先序序列和中序

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

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

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

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