數(shù)據(jù)結(jié)構(gòu)CH6樹和二叉樹

1、(線性表, 棧,隊(duì)列等) : 至少存在一個(gè)數(shù)據(jù)元素有不止一個(gè)直接前驅(qū)或后繼(樹樹,圖等)6.1 樹的類型定義樹的類型定義6.2 6.2 二叉樹的類型定義二叉樹的類型定義6.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)6.4 二叉樹的遍歷二叉樹的遍歷6.5 線索二叉樹線索二叉樹6.6 樹和森林的表示方法樹和森林的表示方法6.7 樹和森林的遍歷樹和森林的遍歷6.8 哈夫曼樹與哈夫曼編碼哈夫曼樹與哈夫曼編碼6.1 樹的類型定義樹的類型定義數(shù)據(jù)對象數(shù)據(jù)對象 D：D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 若若D為空集，則稱為空樹為空集，則稱為空樹 。 否則否則: (1) 在在D中存在唯

2、一的稱為根的數(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：樹的結(jié)構(gòu)示意圖rootT1T2T3 A A B C D I H G F E J K L M 2.樹的表示方法： （1）樹形結(jié)構(gòu)表示法（直觀表示法） （2） 凹入表示法 樹的凹入表示法主要用于樹的屏幕和打印顯示。 A B E J K L F C G D H M I

3、 （3） 嵌套集合表示法 A B E J K L F C G D H M I (4).廣義表表示法（形式化表示方法）：（A（B（E（J，K，L），F(xiàn)），C（G），D（H（M），I） 主要用于樹的理論描述 小結(jié)： 樹的表示方法的多樣性，正說明了樹結(jié)構(gòu)在日常生活中及計(jì)算機(jī)程序設(shè)計(jì)中的重要性。 一般來說，分等級的分類方案都可用層次結(jié)構(gòu)來表示，也就是說，都可產(chǎn)生一個(gè)樹結(jié)構(gòu)?；?本本 術(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): :數(shù)據(jù)元素+ +若干指向子樹的分支結(jié)點(diǎn)擁有的分支的個(gè)數(shù)樹中所有結(jié)點(diǎn)的度的最大值度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)DHIJM

4、(從根到結(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)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成ABCDEFGHIJMKL假設(shè)根結(jié)點(diǎn)的層次為1，第l 層的結(jié)點(diǎn)的子樹根結(jié)點(diǎn)的層次為l+1樹中葉子結(jié)點(diǎn)所在的最大層次任何一棵非空樹是一個(gè)二元組 Tree = （root，F(xiàn)）其中：root 被稱為根結(jié)點(diǎn) F 被稱為子樹森林森林：森林：是m（m0）棵互不相交的樹的集合ArootBCDEFGHIJMKLF 基本操作：基本操作：查查 找找 類類 插插 入入 類類刪刪 除除 類類 Root(T) / 求樹的根結(jié)點(diǎn)求樹的根結(jié)點(diǎn) 查

5、找類：查找類：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() ) / 遍歷遍歷InitTree(&T) / 初始化置空樹初始化置空樹 插入類：插入類：Creat

6、eTree(&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棵子樹棵子樹 ClearTree(&T) / 將樹清空將樹清空 刪除類：刪除類：DestroyTree(&T) / 銷毀樹的結(jié)構(gòu)銷毀樹的結(jié)構(gòu)DeleteChild(&T, &p, i) / 刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)p的第的第i棵子樹棵子樹對比對比樹型結(jié)構(gòu)樹型結(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)樹型結(jié)構(gòu)樹型結(jié)構(gòu)第一個(gè)數(shù)

7、據(jù)元素第一個(gè)數(shù)據(jù)元素 ( (無前驅(qū)無前驅(qū)) ) 根結(jié)點(diǎn)根結(jié)點(diǎn) ( (無前驅(qū)無前驅(qū)) )最后一個(gè)數(shù)據(jù)元素最后一個(gè)數(shù)據(jù)元素 (無后繼無后繼)多個(gè)葉子結(jié)點(diǎn)多個(gè)葉子結(jié)點(diǎn) ( (無后繼無后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 一個(gè)后繼一個(gè)后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 多個(gè)后繼多個(gè)后繼) )6.2 二叉樹的類型定義二叉樹的類型定義 二叉樹或?yàn)榭諛淇諛?，或是由一個(gè)根結(jié)根結(jié)點(diǎn)點(diǎn)加上兩棵兩棵分別稱為左子樹左子樹和右子樹的、互不交的互不交的二叉樹二叉樹組成。ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹二叉樹的五種基本形態(tài)：二叉樹的五種基本形態(tài)：N空樹空樹只含根結(jié)點(diǎn)只含

8、根結(jié)點(diǎn)NNNLRR右子樹為空樹右子樹為空樹L左子樹為空樹左子樹為空樹左右子左右子樹均不樹均不為空樹為空樹二叉樹的特點(diǎn)和性質(zhì)：二叉樹的特點(diǎn)和性質(zhì)：324123413241 注意：注意： 二叉樹的定義也是一個(gè)遞歸定義；二叉樹的定義也是一個(gè)遞歸定義； 二叉樹與樹是兩個(gè)不同的概念二叉樹與樹是兩個(gè)不同的概念，它不是樹的它不是樹的特殊情況特殊情況；這是因?yàn)槎鏄涞淖訕溆凶笥抑贿@是因?yàn)槎鏄涞淖訕溆凶笥抑?，而樹的子樹不必區(qū)分次序。分，而樹的子樹不必區(qū)分次序。 二叉樹與度為二叉樹與度為2的有序樹也是不同的概念的有序樹也是不同的概念；對于二叉樹的子樹而言，要么是根的左子對于二叉樹的子樹而言，要么是根的左子樹

9、，要么是根的右子樹，即使只有一棵子樹，要么是根的右子樹，即使只有一棵子樹也要區(qū)分是左是右；樹也要區(qū)分是左是右；度為度為2的有序樹中，當(dāng)一個(gè)結(jié)點(diǎn)有兩棵子樹的有序樹中，當(dāng)一個(gè)結(jié)點(diǎn)有兩棵子樹時(shí)有左右之分，而只有一棵子樹時(shí)就無左時(shí)有左右之分，而只有一棵子樹時(shí)就無左右之分。右之分。 問題： 1.只有兩個(gè)結(jié)點(diǎn)的二叉樹有幾種不同的形態(tài)？2.只有只有3個(gè)結(jié)點(diǎn)的二叉樹有幾種不同形態(tài)？分別畫出來。個(gè)結(jié)點(diǎn)的二叉樹有幾種不同形態(tài)？分別畫出來。 3.有4個(gè)結(jié)點(diǎn)的二叉樹有幾種不同形態(tài)？211nnnC一般地：一般地：有有n個(gè)結(jié)點(diǎn)的不相似二叉樹有：個(gè)結(jié)點(diǎn)的不相似二叉樹有： 二叉樹的主要基本操作二叉樹的主要基本操作：查查 找找

10、 類類插插 入入 類類刪刪 除除 類類 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(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit(); InitBiTree(&T); Assi

11、gn(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);ClearBiTree(&T); DestroyBiTree(&T);DeleteChild(T, p, LR);二叉樹二叉樹的重要特性的重要特性用歸納法用歸納法 ： 對任何一棵二叉樹對任何一棵二叉樹T，若其終端結(jié)點(diǎn)數(shù)目為，若其終端結(jié)點(diǎn)數(shù)目為n0 ，度為，度為2的的結(jié)點(diǎn)數(shù)目為結(jié)點(diǎn)數(shù)目為n2，則，則n0n21。 證明：證明：設(shè)二叉樹設(shè)二叉樹T的總結(jié)點(diǎn)數(shù)目為的總結(jié)點(diǎn)數(shù)目為n ，度為，度為1的結(jié)點(diǎn)數(shù)目為的結(jié)點(diǎn)數(shù)目為n1， 則則nn0 n1n2 (1) 又由

12、于二叉樹又由于二叉樹T中，除根結(jié)點(diǎn)以外，每個(gè)結(jié)點(diǎn)剛好有一個(gè)中，除根結(jié)點(diǎn)以外，每個(gè)結(jié)點(diǎn)剛好有一個(gè)分支指入，設(shè)分支指入，設(shè)B為分支總數(shù)，則為分支總數(shù)，則 B n 1 (2) 而二叉樹的這些分支是由度為而二叉樹的這些分支是由度為1和度為和度為2的結(jié)點(diǎn)產(chǎn)生，則的結(jié)點(diǎn)產(chǎn)生，則Bn1 2 n2 (3) 綜上三式，可知綜上三式，可知n0n21成立。成立。 練習(xí)練習(xí)： 1.有一棵三叉樹，已知度為有一棵三叉樹，已知度為1,2,3的結(jié)點(diǎn)數(shù)分別的結(jié)點(diǎn)數(shù)分別n1,n2,n3,則該三叉樹的葉結(jié)點(diǎn)數(shù)則該三叉樹的葉結(jié)點(diǎn)數(shù)n0為多少？為多少？ 2.如果一棵樹有如果一棵樹有n1個(gè)度數(shù)為個(gè)度數(shù)為1的結(jié)點(diǎn)，的結(jié)點(diǎn)，n2個(gè)度數(shù)為個(gè)度

13、數(shù)為2的結(jié)點(diǎn)，的結(jié)點(diǎn)，nm個(gè)度數(shù)為個(gè)度數(shù)為m的結(jié)點(diǎn)，則終端結(jié)點(diǎn)的結(jié)點(diǎn)，則終端結(jié)點(diǎn)數(shù)數(shù)n0 ？ 對深度為對深度為h的一棵滿的一棵滿k叉樹來說，其叉樹來說，其終端結(jié)點(diǎn)數(shù)終端結(jié)點(diǎn)數(shù)n0為多少為多少?n0 = 2n3 + n2+1n0 = (m-1)nm + n2+1n0 = kh-11237654K=3n=23-1=7 滿二叉樹 兩類兩類特殊特殊的二叉樹：的二叉樹：完全二叉樹完全二叉樹:深度為深度為k k，結(jié)點(diǎn)數(shù)為，結(jié)點(diǎn)數(shù)為n n的二叉樹，的二叉樹，當(dāng)且僅當(dāng)每個(gè)結(jié)點(diǎn)的編號都與相同深度的當(dāng)且僅當(dāng)每個(gè)結(jié)點(diǎn)的編號都與相同深度的滿二叉樹中從滿二叉樹中從1 1到到n n的結(jié)點(diǎn)一一對應(yīng)時(shí)，稱的結(jié)點(diǎn)一一對應(yīng)時(shí)，稱

14、為完全二叉樹。為完全二叉樹。兩類兩類特殊特殊的二叉樹：的二叉樹：45231。4521316.3 6.3 二叉樹概念及性質(zhì)二叉樹概念及性質(zhì)LH2=0RH2=11324653241LH1=3RH1=1LH1 -RH1=2 LH2-RH2=0-1=-16.3 6.3 二叉樹概念及性質(zhì)二叉樹概念及性質(zhì)完全二叉樹的任意結(jié)點(diǎn)的左右子樹深度相差：完全二叉樹的任意結(jié)點(diǎn)的左右子樹深度相差：0或者或者1性質(zhì)性質(zhì)4.4. 結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù)為n n的完全二叉樹，其深度為的完全二叉樹，其深度為 loglog2 2n n + 1+ 1證明：設(shè)深度為證明：設(shè)深度為k k， 則則 由性質(zhì)由性質(zhì)2 2和完全二叉樹定義有：和完全二

15、叉樹定義有： 結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù)n n滿足：滿足：2 2k-1k-1-1-1n2n2k k-1-1 或?qū)憺榛驅(qū)憺? 2k-1k-1nn2 2k k 于是有：于是有：k-1logk-1log2 2n nk k 因?yàn)橐驗(yàn)?k-1k-1和和k k均為整數(shù)均為整數(shù) 顯然有顯然有l(wèi)oglog2 2n n=k-1, =k-1, 故故 k=k=loglog2 2n n + 1+ 16.3 6.3 二叉樹概念及性質(zhì)二叉樹概念及性質(zhì)n 問題：問題： 具有具有n（n1）個(gè)結(jié)點(diǎn)的二叉樹的最小深度是多少？）個(gè)結(jié)點(diǎn)的二叉樹的最小深度是多少？最大深度是多少？最大深度是多少？當(dāng)當(dāng)i1,結(jié)點(diǎn)結(jié)點(diǎn)i為根結(jié)點(diǎn)，無雙親結(jié)為根結(jié)點(diǎn)，無雙親

16、結(jié)點(diǎn)，否則其雙親為點(diǎn)，否則其雙親為 ;若若2in,結(jié)點(diǎn)結(jié)點(diǎn)i無左子女無左子女;否則其左否則其左子女為子女為2i;若若2i1n,結(jié)點(diǎn)結(jié)點(diǎn)i無右子女無右子女;否則否則其右子女為其右子女為2i1。2in性質(zhì)性質(zhì)5： 對完全二叉樹進(jìn)行編號（按層次從左到右）編號可以反映二對完全二叉樹進(jìn)行編號（按層次從左到右）編號可以反映二叉樹結(jié)點(diǎn)之間的關(guān)系叉樹結(jié)點(diǎn)之間的關(guān)系 。（如下圖）。（如下圖）ii+1 2i2i12i22i32i i2i+12ii+12i+32i+2.i與 i+1同層.i2i+12ii+12i+32i+2.i與 i+1不同層 6.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)二、二叉樹的鏈?zhǔn)蕉⒍鏄涞逆準(zhǔn)?/p>

17、 存儲表示存儲表示一、一、 二叉樹的順序二叉樹的順序 存儲表示存儲表示6. 3.二叉樹的存儲結(jié)構(gòu) 一、二叉樹的一、二叉樹的 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) 特點(diǎn)：特點(diǎn)： 用一組用一組連續(xù)的存儲單元連續(xù)的存儲單元存儲二叉樹的數(shù)據(jù)元素，存儲二叉樹的數(shù)據(jù)元素， 必須把二叉樹的所有結(jié)點(diǎn)安排成為一個(gè)恰當(dāng)?shù)男蛄?，必須把二叉樹的所有結(jié)點(diǎn)安排成為一個(gè)恰當(dāng)?shù)男蛄?，結(jié)點(diǎn)在這個(gè)序列中的相互位置能反映出結(jié)點(diǎn)之間的邏結(jié)點(diǎn)在這個(gè)序列中的相互位置能反映出結(jié)點(diǎn)之間的邏輯關(guān)系。輯關(guān)系。 編號的方法編號的方法 二叉樹的順序存儲表示二叉樹的順序存儲表示- - - - - - - #define MAX_TREE_SIZE 100 typ

18、edef ElemType SqBiTreeMAX_TREE_SIZE+1二叉樹的順序存儲示例一二叉樹的順序存儲示例一ABCABC12312345AB#C12345ABC1231A2B3C4#5D6E7F8#9#10G11H二叉樹的順序存儲示例二二叉樹的順序存儲示例二 練習(xí)： 對如下一棵二叉樹采用順序存儲結(jié)構(gòu)，需要添加幾個(gè)空結(jié)點(diǎn)? 小結(jié)： 對于完全二叉樹來說 二叉樹中的結(jié)點(diǎn)的編號完全可以反映出該二叉樹中結(jié)點(diǎn)之間的邏輯關(guān)系，可將此類二叉樹中結(jié)點(diǎn)的編號與數(shù)組下標(biāo)建立一一對應(yīng)關(guān)系，所以采用順序存儲結(jié)構(gòu)較好。 對于一般的二叉樹 需要添加 “空”結(jié)點(diǎn)，使之成為一棵完全二叉樹，此時(shí)仍可用順序存儲結(jié)構(gòu)表示這

19、棵二叉樹。 但這樣可能造成空間浪費(fèi)，最壞的情況是：深度為k且只有k個(gè)結(jié)點(diǎn)的單支樹，需要長為2k1的數(shù)組空間。 例如，深度為例如，深度為k k，且只有，且只有k k個(gè)結(jié)點(diǎn)的右單枝樹個(gè)結(jié)點(diǎn)的右單枝樹(每每個(gè)非葉結(jié)點(diǎn)只有右孩子個(gè)非葉結(jié)點(diǎn)只有右孩子) )，需，需2 2k k-1-1個(gè)單元，即有個(gè)單元，即有2 2k k-1-k-1-k個(gè)單元被浪費(fèi)。個(gè)單元被浪費(fèi)。1k二、二叉樹的鏈?zhǔn)酱鎯Ρ硎径⒍鏄涞逆準(zhǔn)酱鎯Ρ硎?. 1. 二叉鏈表二叉鏈表2三叉鏈表三叉鏈表3 3雙親鏈表雙親鏈表4線索鏈表線索鏈表typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data; stru

20、ct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BiTree;lchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):C 語言的類型描述如下語言的類型描述如下: :1. 1. 二叉鏈表二叉鏈表ABCDEF如下面的樹:ADEBCF rootlchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):ADEBCF root 2三叉鏈表三叉鏈表parent lchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu): typedef struct TriTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data; struct TriTNode *lchild,

21、 *rchild; / 左右孩子指針 struct TriTNode *parent; /雙親指針 TriTNode, *TriTree;parent lchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):C 語言的類型描述如下語言的類型描述如下: : 思考：含n個(gè)結(jié)點(diǎn)的三叉鏈表有多少個(gè)空鏈域？n+26.4二叉樹的遍歷二叉樹的遍歷一、問題的提出一、問題的提出二、先左后右的遍歷算法二、先左后右的遍歷算法三、算法的遞歸描述三、算法的遞歸描述四、中序遍歷算法的非遞歸描述四、中序遍歷算法的非遞歸描述五五、遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例 順著某一條搜索路徑巡訪巡訪二叉樹中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪

22、問一均被訪問一次次，而且僅被訪問一次僅被訪問一次。一、問題的提出一、問題的提出“訪問訪問”的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。 “遍歷遍歷”是任何類型均有的操作，對線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)， 每個(gè)結(jié)點(diǎn)有兩個(gè)后繼每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷存在如何遍歷即按什么樣的搜索搜索路徑路徑遍歷的問題。一次一次遍歷遍歷后，使樹中結(jié)點(diǎn)的非線性排列，后，使樹中結(jié)點(diǎn)的非線性排列，按訪問的先后順序變?yōu)槟撤N線性排列。按訪問的先后順序變?yōu)槟撤N線性排列。遍歷的次序遍歷的次序：若設(shè)二叉樹根為：若設(shè)二叉樹根為D D，左子樹為，左子樹為L L，

23、右子樹為，右子樹為R R，并限定先左后右，則有，并限定先左后右，則有以下三種遍歷次序（限定先左后右）：以下三種遍歷次序（限定先左后右）： LDR LDR 中序遍歷中序遍歷； LRD LRD 后序遍歷后序遍歷； DLR DLR 先序遍歷先序遍歷 若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹。先（根）序的遍歷算法：先（根）序的遍歷算法：acdef-b*-+先序遍歷結(jié)果先序遍歷結(jié)果: -+a*b-cd/ef 問題：問題： 對應(yīng)于先序遍歷序列為對應(yīng)于先序遍歷序列為ABC的二叉樹有幾種的二叉樹有幾種形態(tài)，分別圖示出。形態(tài)，分別圖示出。 如何實(shí)現(xiàn)二叉鏈表表示

24、的二叉樹的先序遍歷如何實(shí)現(xiàn)二叉鏈表表示的二叉樹的先序遍歷算法？算法？ABBBBBCCCCCAAAA三、先序遍歷的遞歸描述三、先序遍歷的遞歸描述void Preorder (BiTree T) / 先序遍歷二叉樹 if (T) visit(T-data); / 訪問結(jié)點(diǎn) Preorder(T-lchild); / 遍歷左子樹 Preorder(T-rchild);/ 遍歷右子樹 若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹。中（根）序的遍歷算法：中（根）序的遍歷算法：acdef-b*-+中序遍歷結(jié)果中序遍歷結(jié)果: a+b*c-d-e/f 問題：問題

25、： 對應(yīng)于先序遍歷序列為對應(yīng)于先序遍歷序列為ABC的二叉樹的形態(tài)，的二叉樹的形態(tài)，分別寫出中序遍歷的序列。分別寫出中序遍歷的序列。 如何實(shí)現(xiàn)二叉鏈表表示的二叉樹的中序遍歷如何實(shí)現(xiàn)二叉鏈表表示的二叉樹的中序遍歷算法？算法？ABBBBBCCCCCAAAA三、中序遍歷的遞歸描述三、中序遍歷的遞歸描述void Inorder (BiTree T) / 中序遍歷二叉樹 if (T) Inorder(T-lchild); / 遍歷左子樹 visit(T-data); / 訪問結(jié)點(diǎn) Inorder(T-rchild);/ 遍歷右子樹 若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹

26、；（3）訪問根結(jié)點(diǎn)。后（根）序的遍歷算法：后（根）序的遍歷算法：acdef-b*-+后序遍歷結(jié)果后序遍歷結(jié)果: abcd-*+ef/- 問題：問題： 對應(yīng)于先序遍歷序列為對應(yīng)于先序遍歷序列為ABC的二叉樹的形態(tài)，的二叉樹的形態(tài)，分別寫出后序遍歷的序列。分別寫出后序遍歷的序列。 如何實(shí)現(xiàn)二叉鏈表表示的二叉樹的后序遍歷如何實(shí)現(xiàn)二叉鏈表表示的二叉樹的后序遍歷算法？算法？ABBBBBCCCCCAAAA三、后序遍歷的遞歸描述三、后序遍歷的遞歸描述void Postorder (BiTree T) /后序遍歷二叉樹 if (T) Postorder(T-lchild); / 遍歷左子樹 Postorder

27、(T-rchild);/ 遍歷右子樹 visit(T-data); / 訪問結(jié)點(diǎn) 二叉樹遍歷的二叉樹遍歷的實(shí)質(zhì)實(shí)質(zhì)：將非線性結(jié)構(gòu)進(jìn)行線性化：將非線性結(jié)構(gòu)進(jìn)行線性化。問題的提出問題的提出: : 給定一棵二叉樹按某種次序遍歷可以得到給定一棵二叉樹按某種次序遍歷可以得到唯一唯一的結(jié)點(diǎn)序列的結(jié)點(diǎn)序列. . 給定一個(gè)按某種次序遍歷的結(jié)點(diǎn)序列能否唯一給定一個(gè)按某種次序遍歷的結(jié)點(diǎn)序列能否唯一確定一棵二叉樹確定一棵二叉樹? ? 任意給定按兩種不同次序遍歷的結(jié)點(diǎn)序列能否任意給定按兩種不同次序遍歷的結(jié)點(diǎn)序列能否唯一確定一棵二叉樹唯一確定一棵二叉樹? ? 由二叉樹的先序序列和中序序列建立該二叉樹由二叉樹的先序序列和

28、中序序列建立該二叉樹 分析：分析： 若二叉樹的任意兩個(gè)結(jié)點(diǎn)的值都不相同，則二若二叉樹的任意兩個(gè)結(jié)點(diǎn)的值都不相同，則二叉樹的前序序列和中序序列能唯一確定一棵二叉樹的前序序列和中序序列能唯一確定一棵二叉樹。叉樹。 另外，由前序序列和中序序列的定義可知，前另外，由前序序列和中序序列的定義可知，前序序列中第一個(gè)結(jié)點(diǎn)必為根結(jié)點(diǎn)，而在中序序序序列中第一個(gè)結(jié)點(diǎn)必為根結(jié)點(diǎn)，而在中序序列中，根結(jié)點(diǎn)剛好是左、右子樹的分界點(diǎn)。列中，根結(jié)點(diǎn)剛好是左、右子樹的分界點(diǎn)。 因此，可按如下方法建立二叉樹因此，可按如下方法建立二叉樹： 步驟如下：步驟如下： 1.1.用前序序列的第一個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn)用前序序列的第一個(gè)結(jié)點(diǎn)作為根結(jié)

29、點(diǎn); ; 2.2.在中序序列中查找根結(jié)點(diǎn)的位置，并以此在中序序列中查找根結(jié)點(diǎn)的位置，并以此為界將中序序列劃分為左、右兩個(gè)序列為界將中序序列劃分為左、右兩個(gè)序列( (左、左、右子樹右子樹);); 3.3.根據(jù)左、右子樹的中序序列中的結(jié)點(diǎn)個(gè)數(shù)，根據(jù)左、右子樹的中序序列中的結(jié)點(diǎn)個(gè)數(shù)，將前序序列去掉根結(jié)點(diǎn)后的序列劃分為左、將前序序列去掉根結(jié)點(diǎn)后的序列劃分為左、右兩個(gè)序列，它們分別是左、右子樹的前序右兩個(gè)序列，它們分別是左、右子樹的前序序列序列; ; 4.4.對左、右子樹的前序序列和中序序列遞歸對左、右子樹的前序序列和中序序列遞歸地實(shí)施同樣方法，直到所得左、右子樹為空。地實(shí)施同樣方法，直到所得左、右子樹

30、為空。 例如：例如： 假設(shè)前序序列為假設(shè)前序序列為ABDGHCEFIABDGHCEFI，中序序列為，中序序列為GDHBAECIFGDHBAECIF，試建立這棵二叉樹。，試建立這棵二叉樹。6.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹三種遍歷過程示意圖例三種遍歷過程示意圖例 acbab*c-ba*-cab*c-abc 虛線表示執(zhí)行過程虛線表示執(zhí)行過程: 向下表示更深層的遞歸調(diào)用向下表示更深層的遞歸調(diào)用; 向上表示遞歸調(diào)用返回向上表示遞歸調(diào)用返回; 沿虛線記下各類符號沿虛線記下各類符號,便得到遍歷的結(jié)果便得到遍歷的結(jié)果. 中序遍歷算法的非遞歸算法中序遍歷算法的非遞歸算法 Status ino

31、rder(BiTree T)/中序遍歷非遞歸算法中序遍歷非遞歸算法,s為存儲二叉樹結(jié)點(diǎn)指針棧為存儲二叉樹結(jié)點(diǎn)指針棧 InitStack(S);push(S,T); while (!StackEmpty(S) while (GetTop(S,p)& p) push(S,p-lchild); pop(S,p); if (!StackEmpty(S) pop(S,p); visit(p-data); push(S,p-rchild); /if /whilereturn OK;/inorder 根結(jié)點(diǎn)先進(jìn)棧，根結(jié)點(diǎn)先進(jìn)棧， 左結(jié)點(diǎn)緊跟根后面左結(jié)點(diǎn)緊跟根后面進(jìn)棧進(jìn)棧,右結(jié)點(diǎn)在根右結(jié)點(diǎn)在根出棧后入棧出棧后

32、入棧 每個(gè)結(jié)點(diǎn)都要進(jìn)每個(gè)結(jié)點(diǎn)都要進(jìn)一次和出一次棧，一次和出一次棧， 并且總是訪問棧頂并且總是訪問棧頂元素，元素， 因此，因此， 算算法正確，法正確， 時(shí)間復(fù)時(shí)間復(fù)雜度為雜度為 O(n)DCEBAABDNILDNILBENILENILACNILCNIL 2. 中序遍歷算法的非遞歸算法二Status inorder(BiTree T) InitStack(S); p=T; while (p|!StackEmpty(S) if (p) push(S,p); p=p-lchild; else pop(S,p); visit(p-data)； p=p-rchild; /whilereturn OK;in

33、orderABCDE五五、遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例3、求二叉樹的深度、求二叉樹的深度(后序遍歷后序遍歷)1 1、建立二叉樹的存儲結(jié)構(gòu)、建立二叉樹的存儲結(jié)構(gòu)2 2、結(jié)點(diǎn)、結(jié)點(diǎn)X X的查找的查找4 ：統(tǒng)計(jì)葉子結(jié)點(diǎn)的數(shù)目：統(tǒng)計(jì)葉子結(jié)點(diǎn)的數(shù)目1 1、建立二叉樹的存儲、建立二叉樹的存儲結(jié)構(gòu)結(jié)構(gòu)不同的定義方法相應(yīng)有不同的不同的定義方法相應(yīng)有不同的存儲結(jié)構(gòu)的建立算法存儲結(jié)構(gòu)的建立算法 以字符串的形式以字符串的形式 根根 左子樹左子樹 右子樹右子樹定義一棵二叉樹定義一棵二叉樹例如:ABCD以空白字符“”表示A(B(,C(,),D(,)空樹空樹只含一個(gè)根結(jié)點(diǎn)只含一個(gè)根結(jié)點(diǎn)的二叉樹的二叉樹A以字符串“

34、A ”表示以下列字符串表示Status 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)造左子樹 CreateBiTree(T-rchild); / 構(gòu)造右子樹 return OK; / CreateBiTreeA B C D #A BCD上頁算法執(zhí)行過程舉例如下：ATBCDTTT三、二叉樹的建立三、二叉樹

35、的建立 例：例：建立如圖所示二叉樹的二叉鏈表建立如圖所示二叉樹的二叉鏈表結(jié)構(gòu)應(yīng)輸入：結(jié)構(gòu)應(yīng)輸入： ABC#DE#G#F#ABC#DE#G#F#ABCDFEG2、求二叉樹的深度、求二叉樹的深度(后序遍歷后序遍歷)算法基本思想算法基本思想: : 從二叉樹深度的定義可知，二叉樹的二叉樹的深度應(yīng)為其左、右子樹深度的最大值加深度應(yīng)為其左、右子樹深度的最大值加1 1。由此，需先分別求得左、右子樹的深度，需先分別求得左、右子樹的深度，算法中“訪問結(jié)點(diǎn)”的操作為：求得左、求得左、右子樹深度的最大值，然后加右子樹深度的最大值，然后加 1 1 。 首先分析二叉樹的深度二叉樹的深度和它的左左、右子右子樹深度樹深度之

36、間的關(guān)系。int Depth (BiTree T ) / 返回二叉樹的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;int countleaf(bitree T) int num1,num2,num; if (T=NULL) num=0;else if(T-lchild=NULL)&(T-rchi

37、ld=NULL) num=1 elsenum1=countleaf (T-lchild);num2= countleaf(T-rchild)num= num1+num2;return num;3 ：統(tǒng)計(jì)葉子結(jié)點(diǎn)的數(shù)目：統(tǒng)計(jì)葉子結(jié)點(diǎn)的數(shù)目思考：如何統(tǒng)計(jì)思考：如何統(tǒng)計(jì)總結(jié)點(diǎn)數(shù)？總結(jié)點(diǎn)數(shù)？ 統(tǒng)計(jì)出給定二叉樹中統(tǒng)計(jì)出給定二叉樹中結(jié)點(diǎn)的數(shù)目結(jié)點(diǎn)的數(shù)目int count_n(BiTree T) if (T=NULL) num=0;else num1=count_n(T-lchild);num2=count_n(T-rchild);num= num1+num2+1; return num; Status l

38、eafnode(treelink T,int &leafnum) if(T-lchild=NULL&T-rchild=NULL)visit(T-data);leafnum+;if(T-lchild!=NULL)leafnode(T-lchild,leafnum);if(T-rchild!=NULL)leafnode(T-rchild,leafnum);return OK; 思考：思考： 統(tǒng)計(jì)單分支結(jié)點(diǎn)及雙分支結(jié)點(diǎn)數(shù)？統(tǒng)計(jì)單分支結(jié)點(diǎn)及雙分支結(jié)點(diǎn)數(shù)？ 交換二叉樹的左右子樹交換二叉樹的左右子樹void change_left_right(BiTree T) BiTree temp; if (T) c

39、hange_left_right(T-lchild); change_left_right(T-rchild); tmep=T-lchild; T-lchild =T-rchild;T-rchild=temp; 思考：交換左右子樹？思考：交換左右子樹？層次遍歷二叉樹層次遍歷二叉樹層次遍歷二叉樹：層次遍歷二叉樹：從根開始，依次逐層訪問各結(jié)點(diǎn)，同層從左到右。從根開始，依次逐層訪問各結(jié)點(diǎn)，同層從左到右。(From root,visiting each node level by (From root,visiting each node level by level,in the same leve

40、l from left to level,in the same level from left to right)right)層次遍歷二叉樹層次遍歷二叉樹acdef-b*-+層次遍歷結(jié)果層次遍歷結(jié)果: - + / a*efb-cd1.1.試編寫按層次遍歷二叉樹的算法試編寫按層次遍歷二叉樹的算法. .Status LevelOrder(BiTree T) /按層次遍歷二叉樹T， Q為隊(duì)列 InitQueue(Q); If (T!=NULL)/ 若樹非空 EnQueue(Q,T);/根結(jié)點(diǎn)入隊(duì)列 While (!QueueEmpty(Q) DeQueue(Q,b); /隊(duì)首元素出隊(duì)列 visit

41、(b-data); /訪問結(jié)點(diǎn) if (b-lchild!=NULL) EnQueue(Q,b-lchild);/左子樹非空，則入隊(duì)列 if (b-rchild!=NULL) EnQueue(Q,b-rchild);/右子樹非空，則入隊(duì)列 /while /ifLevelOrder補(bǔ)充 ： 二叉樹的建立 方法二：建立二叉排序樹方法二：建立二叉排序樹 二叉排序樹的定義二叉排序樹的定義 或者為一棵空樹，或?yàn)闈M足如下條件的二叉樹或者為一棵空樹，或?yàn)闈M足如下條件的二叉樹 1.若左子樹非空，則左子樹上所有結(jié)點(diǎn)的值若左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；均小于它的根結(jié)點(diǎn)的值； 2.若右子樹

42、非空，則右子樹上所有結(jié)點(diǎn)的值若右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；均大于它的根結(jié)點(diǎn)的值； 3.它的左右子樹也分別為二叉排序樹。它的左右子樹也分別為二叉排序樹。例如：輸入序列例如：輸入序列45，12，37，3，53，100，2445125333710024void insert(BiTree &T,ElemType x) if (T=NULL) T=(BiTree)malloc(sizeof(BiTNode); T-data=x; T-lchild=T-rchild=NULL; else if (xdata) insert(T-lchild,x); if (xT-data)

43、insert(T-rchild,x); /insert void CreateBiTree(BiTree &root) ElemType x; root=NULL; scanf(&x); while (x!=-1) insert(root,x); scanf(&x); /while/CreateBiTree二、線索二叉樹二、線索二叉樹 問題的提出問題的提出：通過遍歷二叉樹可得到結(jié)點(diǎn)通過遍歷二叉樹可得到結(jié)點(diǎn)的一個(gè)線性序列，在線性序列中，就存在結(jié)的一個(gè)線性序列，在線性序列中，就存在結(jié)點(diǎn)和前驅(qū)和后繼，但是在二叉鏈表上只能找點(diǎn)和前驅(qū)和后繼，但是在二叉鏈表上只能找到結(jié)點(diǎn)的左孩子、右孩子，結(jié)點(diǎn)的前驅(qū)和后到

44、結(jié)點(diǎn)的左孩子、右孩子，結(jié)點(diǎn)的前驅(qū)和后繼只有在遍歷過程中才能得到，那么，能否繼只有在遍歷過程中才能得到，那么，能否通過結(jié)點(diǎn)的兩個(gè)鏈域查找出任一結(jié)點(diǎn)的前驅(qū)通過結(jié)點(diǎn)的兩個(gè)鏈域查找出任一結(jié)點(diǎn)的前驅(qū)和后繼和后繼? ?一、一、何謂線索二叉樹？何謂線索二叉樹？遍歷二叉樹的結(jié)果是， 求得結(jié)點(diǎn)的一個(gè)線性序列。ABCDEFGHK例如:先序先序序列: A B C D E F G H K中序中序序列: B D C A H G K F E后序后序序列: D C B H K G F E A指向該線性序列中的“前驅(qū)”和 “后繼” 的指針指針，稱作“線線索索”與其相應(yīng)的二叉樹，稱作 “線索二叉樹線索二叉樹”包含 “線索” 的

45、存儲結(jié)構(gòu)，稱作 “線索鏈線索鏈表表”A B C D E F G H K D C B E 2. 2. 分析分析： n n個(gè)結(jié)點(diǎn)一共有個(gè)結(jié)點(diǎn)一共有2n2n個(gè)鏈域，其中：個(gè)鏈域，其中：n+1n+1個(gè)空鏈域，個(gè)空鏈域，n-1n-1個(gè)指針域；個(gè)指針域； 因此因此, , 必須用空鏈域來存放結(jié)點(diǎn)的前驅(qū)和后繼。必須用空鏈域來存放結(jié)點(diǎn)的前驅(qū)和后繼。線索二叉樹就是利用線索二叉樹就是利用n+1n+1個(gè)空鏈域來存放結(jié)點(diǎn)個(gè)空鏈域來存放結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)的信息。的前驅(qū)和后繼結(jié)點(diǎn)的信息。對對線索鏈表線索鏈表中結(jié)點(diǎn)的約定：中結(jié)點(diǎn)的約定： 在二叉鏈表的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域增加兩個(gè)標(biāo)志域，并作如下規(guī)定：若該結(jié)點(diǎn)的左子樹不空若該

46、結(jié)點(diǎn)的左子樹不空，則Lchild域的指針指向其左子樹， 且左標(biāo)志域的值為“指針 Link”； 否則，Lchild域的指針指向其“前驅(qū)”， 且左標(biāo)志的值為“線索 Thread” 。若該結(jié)點(diǎn)的右子樹不空，若該結(jié)點(diǎn)的右子樹不空，則rchild域的指針指向其右子樹， 且右標(biāo)志域的值為 “指針 Link”；否則，rchild域的指針指向其“后繼”， 且右標(biāo)志的值為“線索 Thread”。 如此定義的二叉樹的存儲結(jié)構(gòu)稱作如此定義的二叉樹的存儲結(jié)構(gòu)稱作“線索鏈表線索鏈表”。typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *r

47、child; / 左右指針 PointerThr LTag, RTag; / 左右標(biāo)志 BiThrNode, *BiThrTree;線索鏈表的類型描述： typedef enum Link, Thread PointerThr; / Link=0:指針，Thread=1:線索3. 3. 線索二叉樹線索二叉樹： 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)在二叉鏈表中增加在二叉鏈表中增加 ltag ltag 和和 rtag rtag 兩個(gè)標(biāo)志域兩個(gè)標(biāo)志域 lchild ltag data rtag rchild 若結(jié)點(diǎn)有左子樹，則左鏈域若結(jié)點(diǎn)有左子樹，則左鏈域lchildlchild指示其左孩子（指示其左孩子（ltag=0

48、ltag=0）；）；否則，令左鏈域指示其前驅(qū)（否則，令左鏈域指示其前驅(qū)（ltag=1ltag=1）；）； 若結(jié)點(diǎn)有右子樹，則右鏈域若結(jié)點(diǎn)有右子樹，則右鏈域rchildrchild指示其右孩子（指示其右孩子（rtag=0rtag=0）；）；否則，令右鏈域指示其后繼（否則，令右鏈域指示其后繼（rtag=1rtag=1）；）； 稱這種結(jié)點(diǎn)結(jié)構(gòu)為稱這種結(jié)點(diǎn)結(jié)構(gòu)為線索鏈表線索鏈表； 其中指示前驅(qū)和后繼的鏈域稱為其中指示前驅(qū)和后繼的鏈域稱為線索線索； 加上線索的二叉樹稱為加上線索的二叉樹稱為線索二叉樹線索二叉樹； 對二叉樹以對二叉樹以某種次序某種次序遍歷使其變?yōu)榫€索二叉遍歷使其變?yōu)榫€索二叉樹的過程稱為樹的

49、過程稱為線索化線索化。 按中序遍歷得到的線索二叉樹稱為按中序遍歷得到的線索二叉樹稱為中序線索中序線索二叉樹二叉樹；按先序遍歷得到的線索二叉樹稱為；按先序遍歷得到的線索二叉樹稱為先先序線索二叉樹序線索二叉樹；按后序遍歷得到的線索二叉樹；按后序遍歷得到的線索二叉樹稱為稱為后序線索二叉樹后序線索二叉樹；中序線索二叉樹 如圖所示二叉樹的中序線索化。 abcdef 如何尋找結(jié)點(diǎn)的后繼 rtag=1 rtag=0 如何尋找結(jié)點(diǎn)的前驅(qū) ltag=1 ltag=0aebfcdNULLNULL（2 2）整體結(jié)構(gòu)）整體結(jié)構(gòu) 增設(shè)一個(gè)頭結(jié)點(diǎn)，令其增設(shè)一個(gè)頭結(jié)點(diǎn)，令其lchildlchild指向二叉樹的根結(jié)指向二叉樹

50、的根結(jié)點(diǎn)，點(diǎn)，ltag=0ltag=0、rtag=1rtag=1； 并將該結(jié)點(diǎn)作為遍歷訪問的第一個(gè)結(jié)點(diǎn)的前驅(qū)和并將該結(jié)點(diǎn)作為遍歷訪問的第一個(gè)結(jié)點(diǎn)的前驅(qū)和最后一個(gè)結(jié)點(diǎn)的后繼；最后一個(gè)結(jié)點(diǎn)的后繼； 最后用頭指針指示該頭結(jié)點(diǎn)。最后用頭指針指示該頭結(jié)點(diǎn)。acb0 10 01 c 10 01 b 11 a 1中序線索二叉樹中序線索二叉樹二、線索鏈表的遍歷算法二、線索鏈表的遍歷算法: for ( p = firstNode(T); p; p = Succ(p) ) Visit (p);由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡化了遍歷的算法。例如例如: 對中序線索化鏈表的遍歷算法對

51、中序線索化鏈表的遍歷算法 中序遍歷的第一個(gè)結(jié)點(diǎn)中序遍歷的第一個(gè)結(jié)點(diǎn) ？ 在中序線索化鏈表中結(jié)點(diǎn)的后繼在中序線索化鏈表中結(jié)點(diǎn)的后繼 ？左子樹上處于“最左下最左下”（沒有左子樹）的結(jié)點(diǎn)。若若無右子樹，則為則為后繼線索后繼線索所指結(jié)點(diǎn)；否則為否則為對其右子樹右子樹進(jìn)行中序遍歷遍歷時(shí)訪問的第一個(gè)結(jié)點(diǎn)。第一個(gè)結(jié)點(diǎn)。void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e) p = T-lchild; / p指向根結(jié)點(diǎn) while (p != T) / 空樹或遍歷結(jié)束時(shí)，p=T while (p-LTag=Link) p = p-lch

52、ild; / 第一個(gè)結(jié)點(diǎn) if (! Visit(p-data) return ERROR; while (p-RTag=Thread & p-rchild!=T) p = p-rchild; Visit(p-data); / 訪問后繼結(jié)點(diǎn) p = p-rchild; / p進(jìn)至其右子樹根 / 以線索鏈表為存儲結(jié)構(gòu)對二叉樹進(jìn)行遍歷的算法 6.6 樹和森林樹和森林 的表示方法的表示方法樹的三種存儲結(jié)構(gòu)樹的三種存儲結(jié)構(gòu)一、一、雙親表示法雙親表示法二、二、孩子鏈表表示法孩子鏈表表示法三、三、樹的二叉鏈表樹的二叉鏈表( (孩子孩子- -兄弟）兄弟） 存儲表示法存儲表示法ABCDEFG0 A -11 B

53、 02 C 03 D 04 E 2 5 F 26 G 5r=0n=7data parent一、雙親表示法一、雙親表示法: typedef struct PTNode Elem data; int parent; / 雙親位置域 PTNode; data parent#define MAX_TREE_SIZE 100結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):C語言的類型描述語言的類型描述: :typedef struct PTNode nodes MAX_TREE_SIZE; int r, n; / 根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù) PTree;樹結(jié)構(gòu)樹結(jié)構(gòu):ABCDEFG0 A1 B2 C3 D4 E5 F6 Gr=0n=7

54、data firstchild 1 2 34 56二、孩子鏈表表示法二、孩子鏈表表示法:-1000224typedef struct CTNode int child; struct CTNode *next; *ChildPtr;孩子結(jié)點(diǎn)結(jié)構(gòu)孩子結(jié)點(diǎn)結(jié)構(gòu): child nextC語言的類型描述語言的類型描述: : typedef struct Elem data; ChildPtr firstchild; / 孩子鏈的頭指針 CTBox;雙親結(jié)點(diǎn)結(jié)構(gòu)雙親結(jié)點(diǎn)結(jié)構(gòu) data firstchildtypedef struct CTBox nodesMAX_TREE_SIZE; int n, r;

55、 / 結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置 CTree;樹結(jié)構(gòu)樹結(jié)構(gòu):ABCDEFG AB C E D F Groot AB C E D F G 三、樹的二叉鏈表三、樹的二叉鏈表 (孩子孩子-兄弟）存儲表示法兄弟）存儲表示法typedef struct CSNode Elem data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;C語言的類型描述語言的類型描述: :結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu): firstchild data nextsibling 將樹轉(zhuǎn)換成二叉樹將樹轉(zhuǎn)換成二叉樹 加線：在兄弟之間加一連線加線：在兄弟之間加一連線 抹線：對每個(gè)結(jié)點(diǎn)

56、，除了其左孩子外，去除其與其余孩子之抹線：對每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與其余孩子之間的關(guān)系間的關(guān)系 旋轉(zhuǎn)：以樹的根結(jié)點(diǎn)為軸心，將整樹順時(shí)針轉(zhuǎn)旋轉(zhuǎn)：以樹的根結(jié)點(diǎn)為軸心，將整樹順時(shí)針轉(zhuǎn)45ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹轉(zhuǎn)換成的二叉樹其右子樹一定為空樹轉(zhuǎn)換成的二叉樹其右子樹一定為空 將二叉樹轉(zhuǎn)換成樹將二叉樹轉(zhuǎn)換成樹 加線：若加線：若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩的右孩子，右孩子的右孩子，子的右孩子，沿分支找到的所有右孩子，都與沿分支找到的所有右孩子，都與p的雙親的雙親用線連起來用線連起來

57、抹線：抹掉原二叉樹中雙親與右孩子之間的連線抹線：抹掉原二叉樹中雙親與右孩子之間的連線 調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹結(jié)構(gòu)調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹結(jié)構(gòu)ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI 森林和二叉樹的對應(yīng)關(guān)系森林和二叉樹的對應(yīng)關(guān)系設(shè)設(shè)森林森林 F = ( T1, T2, , Tn ); T1 = (root，t11, t12, , t1m);二叉樹二叉樹 B =( LBT, Node(root), RBT );由森林轉(zhuǎn)換成二叉樹由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為:若 F = ，則 B = ；否則， 由 ROOT( T1 ) 對應(yīng)得到 No

58、de(root)； 由 (t11, t12, , t1m ) 對應(yīng)得到 LBT； 由 (T2, T3, Tn ) 對應(yīng)得到 RBT。 森林轉(zhuǎn)換成二叉樹森林轉(zhuǎn)換成二叉樹 將各棵樹分別轉(zhuǎn)換成二叉樹將各棵樹分別轉(zhuǎn)換成二叉樹 將每棵樹的根結(jié)點(diǎn)用線相連將每棵樹的根結(jié)點(diǎn)用線相連 以第一棵樹根結(jié)點(diǎn)為二叉樹的根，再以根結(jié)點(diǎn)為軸心，順時(shí)以第一棵樹根結(jié)點(diǎn)為二叉樹的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ由二叉樹轉(zhuǎn)換為森林由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為：若 B = ， 則 F = ；否則，由 Node(

59、root) 對應(yīng)得到 ROOT( T1 )；由LBT 對應(yīng)得到 ( t11, t12, ，t1m)；由RBT 對應(yīng)得到 (T2, T3, , Tn)。 二叉樹轉(zhuǎn)換成森林二叉樹轉(zhuǎn)換成森林 抹線：將二叉樹中根結(jié)點(diǎn)與其右孩子連線，及沿右分支搜索抹線：將二叉樹中根結(jié)點(diǎn)與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹 還原：將孤立的二叉樹還原成樹還原：將孤立的二叉樹還原成樹ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ 由此，樹的各種操作均可對應(yīng)二叉樹的操作來完成。 應(yīng)當(dāng)注意的是，應(yīng)當(dāng)注意

60、的是，和樹對應(yīng)的二叉樹，其左、右子樹的概念已改變?yōu)椋?左是孩子，右是兄弟。左是孩子，右是兄弟。6.4.3 6.4.3 樹和森林的遍歷樹和森林的遍歷q先根遍歷 若樹為空，則空操作 否則 （1）訪問樹的根結(jié)點(diǎn) （2）依次先根遍歷每棵子樹一、樹的遍歷一、樹的遍歷RACDEFGHKB例：例：右圖所示樹的先根遍歷序列右圖所示樹的先根遍歷序列：RADEBCFGHKq后根遍歷后根遍歷 若樹為空，則空操作若樹為空，則空操作 否則否則 （1 1）依次后根遍歷每棵子樹）依次后根遍歷每棵子樹 （2 2）訪問樹的根結(jié)點(diǎn)）訪問樹的根結(jié)點(diǎn)RACDEFGHKB例：例：右圖所示樹的后根遍歷序列右圖所示樹的后根遍歷序列：DEA