數(shù)據(jù)結(jié)構(gòu)《第6章樹(shù)和二叉樹(shù)》

1、頁(yè)眉內(nèi)容第6章樹(shù)和二叉樹(shù)本章學(xué)習(xí)要點(diǎn)熟悉樹(shù)的遞歸定義、相關(guān)術(shù)語(yǔ)以及基本概念熟悉二叉樹(shù)的遞歸定義、二叉樹(shù)的有關(guān)術(shù)語(yǔ)以及基本概念掌握二叉樹(shù)的基本性質(zhì)以及相應(yīng)的證明方法了解二叉樹(shù)的兩種存儲(chǔ)結(jié)構(gòu)、各種存儲(chǔ)方法的特點(diǎn)和適用范圍熟練掌握二叉樹(shù)的各種遍歷算法，能通過(guò)應(yīng)用二叉樹(shù)的遍歷操作實(shí)現(xiàn)二叉樹(shù)的其它基本操作了解線(xiàn)索二叉樹(shù)的實(shí)質(zhì)和目的，掌握在中序線(xiàn)索化的二叉樹(shù)中，查找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法掌握樹(shù)、森林與二叉樹(shù)之間的關(guān)系和轉(zhuǎn)換方法掌握樹(shù)的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)、適應(yīng)范圍以及樹(shù)和森林的遍歷算法樹(shù)型結(jié)構(gòu)是一種應(yīng)用非常廣泛的非線(xiàn)性結(jié)構(gòu)，其中以二叉樹(shù)最為常用。樹(shù)型結(jié)構(gòu)反映了元素之間的層次關(guān)系和分支關(guān)系，它非常類(lèi)似于自

2、然界中的樹(shù)。樹(shù)型結(jié)構(gòu)在計(jì)算機(jī)領(lǐng)域中廣泛應(yīng)用。比如，在計(jì)算機(jī)操作系統(tǒng)中對(duì)文件的目錄管理就是采用樹(shù)型結(jié)構(gòu)；在編譯程序中，使用樹(shù)來(lái)表示程序的語(yǔ)法結(jié)構(gòu)；在數(shù)據(jù)庫(kù)系統(tǒng)中，樹(shù)型結(jié)構(gòu)也是信息的重要組織形式之一。本章將詳細(xì)討論二叉樹(shù)的邏輯結(jié)構(gòu)、各種存儲(chǔ)結(jié)構(gòu)及其基本操作的實(shí)現(xiàn)，研究樹(shù)、森林和二叉樹(shù)之間的轉(zhuǎn)換關(guān)系，最后介紹一個(gè)二叉樹(shù)的應(yīng)用實(shí)例Huffman樹(shù)及其應(yīng)用。6.1樹(shù)的定義和基本術(shù)語(yǔ)機(jī)T(Tree)是n(n=0)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))的有限集合D,如果D為空集，則稱(chēng)T為空樹(shù)；否則有下面的定義：(1)在D中有且僅有一個(gè)特定的結(jié)點(diǎn)，稱(chēng)為根結(jié)點(diǎn)；(2)當(dāng)n1時(shí)，其余的結(jié)點(diǎn)可分成m(m0)個(gè)互不相交的有限集：Ti,T

3、2,Tm,期中每個(gè)集合又都是一棵樹(shù)，并稱(chēng)它們?yōu)闃?shù)T的根結(jié)點(diǎn)的子樹(shù)。樹(shù)是以遞歸的方式來(lái)定義的，即在敘述樹(shù)的定義的過(guò)程中又用到了樹(shù)的概念。樹(shù)的這種遞歸定義方式反映了樹(shù)型結(jié)構(gòu)的層次特性。直觀地講，樹(shù)是由根結(jié)點(diǎn)和若干棵子樹(shù)組成，其中的每棵子樹(shù)又都是由一個(gè)根結(jié)點(diǎn)和它自己的若干棵子樹(shù)組成，依此類(lèi)推。例如，圖6.1是用圖形表示法表示的一棵樹(shù)T。根據(jù)樹(shù)的定義，T的數(shù)據(jù)元素集合D中一共包含有10個(gè)結(jié)點(diǎn)：D=ABC,D,E,F,G,H,I,J，其中結(jié)點(diǎn)A為T(mén)的根結(jié)點(diǎn)。根結(jié)點(diǎn)A有三棵子樹(shù)萬(wàn)213,子樹(shù)的根結(jié)點(diǎn)分別為B、C、D均為A的孩子結(jié)點(diǎn)，每棵子樹(shù)中所含數(shù)據(jù)元素的集合分別為Di、Q、D3,它們互不相交且為：Di=

4、B,E,F,D2=C,G和D3=D,H,I。13樹(shù)的表示方法還有廣義表表示法、集合表示法和凹入表示法等。圖6.2分別給出圖6.1中所表示的樹(shù)T的其它三種表示方法。樹(shù)1隼合表示注(1)結(jié)點(diǎn)(Node)樹(shù)的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素以及若干個(gè)指向其子樹(shù)的分支指針。(2)結(jié)點(diǎn)的度(Degree)結(jié)點(diǎn)所擁有的子樹(shù)個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度。例如，在圖6.1所示的樹(shù)T中，度為零的結(jié)點(diǎn)有E、F、G、H、I、J,度為1的結(jié)點(diǎn)有C,度為2的結(jié)點(diǎn)有B,度為3的結(jié)點(diǎn)有A、B。(3)葉子結(jié)點(diǎn)(Leaf)度為0的結(jié)點(diǎn)稱(chēng)為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)。例如，樹(shù)T中，其葉結(jié)點(diǎn)為E、F、G、H、I、Jo(4)分支結(jié)點(diǎn)(Offshoot-Node)度

5、不為。的結(jié)點(diǎn)稱(chēng)為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。例如，樹(shù)T中，分支結(jié)點(diǎn)有A、B、C、Do(5)樹(shù)的度(Tree-Degree)樹(shù)內(nèi)各結(jié)點(diǎn)的度的最大值稱(chēng)為該樹(shù)的度。例如，樹(shù)T的度等于3。（6）孩子（Child）結(jié)點(diǎn)的子樹(shù)的根稱(chēng)為該結(jié)點(diǎn)的孩子。顯然葉結(jié)點(diǎn)無(wú)孩子，例如，樹(shù)T中，根結(jié)點(diǎn)A的孩子結(jié)點(diǎn)有B、C、D，結(jié)點(diǎn)B的孩子結(jié)點(diǎn)有E、F,結(jié)點(diǎn)C的孩子結(jié)點(diǎn)為G,結(jié)點(diǎn)D的孩子結(jié)點(diǎn)有H、I、J。（7）雙親（Parents）結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的所有子樹(shù)的根的雙親。顯然根結(jié)點(diǎn)無(wú)雙親，例如，樹(shù)T中，根結(jié)點(diǎn)A為B、C、D的雙親結(jié)點(diǎn)，結(jié)點(diǎn)B為E、F的雙親結(jié)點(diǎn)，結(jié)點(diǎn)C為G的雙親結(jié)點(diǎn)，結(jié)點(diǎn)D為H、I、J的雙親結(jié)點(diǎn)。（8）兄弟（Broth

6、er）同一個(gè)雙親的孩子之間互為兄弟。顯然根結(jié)點(diǎn)無(wú)兄弟，例如，樹(shù)T中，結(jié)點(diǎn)B、C、D為兄弟結(jié)點(diǎn)，結(jié)點(diǎn)H、I、J為兄弟結(jié)點(diǎn)，（9）祖先（Ancestor）從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)均為該結(jié)點(diǎn)的祖先。例如，樹(shù)T中，結(jié)點(diǎn)E的祖先有A、B。（10）子孫（Offspring）以某結(jié)點(diǎn)為根的樹(shù)中的任一個(gè)結(jié)點(diǎn)都是該結(jié)點(diǎn)的子孫。在非空樹(shù)中所有結(jié)點(diǎn)（根結(jié)點(diǎn)除外）均為其根結(jié)點(diǎn)的子孫。（11）層次（Level）從根開(kāi)始定義起，根為第一層，根的孩子為第二層，若某結(jié)點(diǎn)在第m層，則其子樹(shù)的根就在第m+1層。例如，在樹(shù)T中，第一層的結(jié)點(diǎn)為A，第二層的結(jié)點(diǎn)為B、C、D，第三層的結(jié)點(diǎn)為E、F、G、H、I、J。（12）堂兄弟

7、（Brother-in-low）雙親在同一層的結(jié)點(diǎn)互為堂兄弟。例如，在樹(shù)T中，結(jié)點(diǎn)E、G、H為堂兄弟。（13）樹(shù)的深度（Tree-Degree）樹(shù)中結(jié)點(diǎn)的最大層數(shù)稱(chēng)為該樹(shù)的深度。顯然樹(shù)的深度等于該樹(shù)中葉結(jié)點(diǎn)的最大層數(shù)。（14）有序樹(shù)與無(wú)序樹(shù)如果將樹(shù)中結(jié)點(diǎn)的各子樹(shù)看成從左到右是有次序的（即不能互換），則稱(chēng)該樹(shù)是有序樹(shù)，否則稱(chēng)為無(wú)序樹(shù)（本章所討論的樹(shù)均為有序樹(shù)）。（15）森林（Forest）森林是m（m=0）棵互不相交的樹(shù)的集合。說(shuō)明：在一棵樹(shù)中，雙親結(jié)點(diǎn)與其孩子結(jié)點(diǎn)的關(guān)系即為前驅(qū)與后繼的關(guān)系，可以寫(xiě)成。顯然，樹(shù)的根結(jié)點(diǎn)無(wú)前驅(qū)結(jié)點(diǎn)，而樹(shù)的葉子結(jié)點(diǎn)無(wú)后繼結(jié)點(diǎn)。例如，圖6.1所表示的樹(shù)T中，所有結(jié)點(diǎn)的

8、邏輯結(jié)構(gòu)可以表示為：,樹(shù)的基本操作主要有：（1）InitTree（&T）構(gòu)造一棵空樹(shù)T；(2)DestroyTree(&T)若樹(shù)T非空，則收回T所占的內(nèi)存資源； 3) 3)CreateTree(&T,definition)根據(jù)definition構(gòu)造樹(shù)T； 4) 4)TreeEmpty(T)判斷樹(shù)T是否為空樹(shù)； 5) 5)TreeDepth(T)返回樹(shù)T的深度； 6) Value(T,cur_e)返回樹(shù)T中結(jié)點(diǎn)cur_e的值； 7) 7)Assign(&T,cur_e,value)置T中結(jié)點(diǎn)cur_e的值為value； 8) Parent(T,cur_e)返回T中結(jié)點(diǎn)cur_e的雙親結(jié)點(diǎn)； 9

9、) InsertChild(&T,&p,i,e)子樹(shù)e插入到T中p所指的結(jié)點(diǎn)中，p的度數(shù)+1,使其成為p結(jié)點(diǎn)的第i棵子樹(shù)(T與e不交)； 10) 10)DeleteChild(&T,&p,i)刪除T中p所指結(jié)點(diǎn)的第i棵子樹(shù)；(11)TraverseTree(T)按照某種次序?qū)?shù)T的每個(gè)結(jié)點(diǎn)進(jìn)行一次且僅有一次的訪(fǎng)問(wèn)。6.2二叉樹(shù)二叉樹(shù)(BineryTree)是一種重要的樹(shù)型結(jié)構(gòu)，許多實(shí)際問(wèn)題抽象出來(lái)的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹(shù)的形式。與樹(shù)的結(jié)構(gòu)相比，二叉樹(shù)在結(jié)構(gòu)上更規(guī)范和更具有確定性，而且操作比較簡(jiǎn)單。一般的樹(shù)和森林都可以轉(zhuǎn)換為二叉樹(shù)，因此，本章主要討論二叉樹(shù)的性質(zhì)、存儲(chǔ)結(jié)構(gòu)、基本操作的實(shí)現(xiàn)以及二叉樹(shù)

10、的應(yīng)用。1 二叉樹(shù)的定義二叉樹(shù)T(BinaryTree)是n(n)0)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))的有限集合，當(dāng)n=0時(shí)稱(chēng)T為空二叉樹(shù),簡(jiǎn)稱(chēng)為空樹(shù)，當(dāng)n0時(shí)存在唯一的稱(chēng)為根的結(jié)點(diǎn)，且其余元素分成互不相交的兩個(gè)子集，每個(gè)子集自身也是一棵二叉樹(shù)，分別稱(chēng)為T(mén)的左子樹(shù)和右子樹(shù)。顯然，二叉樹(shù)是一種特殊的樹(shù)型結(jié)構(gòu)，二叉樹(shù)的度最多為2，且二叉樹(shù)的子樹(shù)有左右之分，其次序不能顛倒。2 二叉樹(shù)的五種基本形態(tài)二叉樹(shù)有5種基本形態(tài)，它們分別是：(1) 空二叉樹(shù)(2)僅有根結(jié)點(diǎn)的二叉樹(shù)(3)只有左子樹(shù)而右子樹(shù)為空的二叉樹(shù)(4)左子樹(shù)和右子樹(shù)都不為空的二叉樹(shù)(5)有右子樹(shù)而左子樹(shù)為空的二叉樹(shù)。圖6.3所示的就是以上5種二叉樹(shù)的基本

11、形態(tài)。S)僅有左子樹(shù) 的二義村空二叉樹(shù)3)僅有根結(jié)點(diǎn) 的二支樹(shù)S)僅有方子樹(shù)弟一歹捌E6.3二型.柄的五種基本形態(tài)3 .滿(mǎn)二叉樹(shù)和完全二叉樹(shù)有關(guān)二叉樹(shù)的基本術(shù)語(yǔ)與樹(shù)完全相同，不再贅述。基于二叉樹(shù)的特點(diǎn)，此處給出兩種特殊形態(tài)的二叉樹(shù)，即滿(mǎn)二叉樹(shù)和完全二叉樹(shù)的概念。(1)滿(mǎn)二叉樹(shù)(FullBinaryTree)如果二叉樹(shù)中的所有分支結(jié)點(diǎn)的度數(shù)均為2,且葉子結(jié)點(diǎn)都在同一層次上，則稱(chēng)此類(lèi)二叉樹(shù)為滿(mǎn)二叉樹(shù)。(2)完全二叉樹(shù)(CompleteBinaryTree)對(duì)滿(mǎn)二叉樹(shù)T上的所有結(jié)點(diǎn)從上到下從左到右從1開(kāi)始編號(hào)，1,2,3,4。那么，任意一棵二叉樹(shù)都可以和一棵同深度的滿(mǎn)二叉樹(shù)相對(duì)比，假如這棵含有n個(gè)結(jié)

12、點(diǎn)的二叉樹(shù)中的每個(gè)結(jié)點(diǎn)都可以和T中的編號(hào)為1至n的結(jié)點(diǎn)對(duì)應(yīng)，則稱(chēng)該二叉樹(shù)為完6.4(a)為一棵滿(mǎn)二叉全二叉樹(shù)。顯然，滿(mǎn)二叉樹(shù)本身也一定是一棵完全二叉樹(shù)，反之不然。例如，圖樹(shù)，而圖6.4(b)為一棵完全二叉樹(shù)。囤6 4芮二叉樹(shù)與完全二夏桐面一出樹(shù)全二叉樹(shù)由二叉樹(shù)的定義可知，二叉樹(shù)具有以下5個(gè)重要性質(zhì)。性質(zhì)1在二叉機(jī)勺第i層上最多有2i1個(gè)結(jié)點(diǎn)。證明：(利用歸納法證明此性質(zhì))當(dāng)i=1時(shí)，由于該層上最多只有一個(gè)根結(jié)點(diǎn)，所以第1層最多有2i-1=20=1個(gè)結(jié)點(diǎn)；假設(shè)第i層上最多有2i-1個(gè)結(jié)點(diǎn)成立，下面來(lái)證明在第i+1層上最多有2=2。+1)-1個(gè)結(jié)點(diǎn)成立：由于二叉樹(shù)的度為2,所以每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩

13、子，根據(jù)歸納的假設(shè)，在第i層最多有2i-1個(gè)結(jié)點(diǎn)，所以在第i+1層上最多有zxzi-JzZzQ+D-1個(gè)結(jié)點(diǎn)成立。性質(zhì)2深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)(k1)。證明：根據(jù)性質(zhì)1的結(jié)論可知，深度為k的二叉樹(shù)至多有20+21+22+2k-1=2k-1個(gè)結(jié)點(diǎn)。性質(zhì)3如果二叉樹(shù)T的葉結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2，則n0n21。證明：設(shè)共有n個(gè)結(jié)點(diǎn)，其中度為1的結(jié)點(diǎn)有n1個(gè)，那么nn0n1n2；又因?yàn)椋Y(jié)點(diǎn)的總數(shù)等于二叉樹(shù)中總的分支數(shù)加1(根結(jié)點(diǎn)無(wú)分支)，即n0n01nl2n21o所以：n0+n1+n2=n1+2n2+1,即：n0n21。性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n1。證

14、明：設(shè)該完全二叉樹(shù)的深度為h,那么由性質(zhì)2和完全二叉樹(shù)的定義可知，結(jié)點(diǎn)數(shù)n滿(mǎn)足：2h1n2h1,即2h1n2h,在不等式兩邊取以2為底的對(duì)數(shù)可得：h1log2nh,所以必有：log2nh1,即hlog2n1。性質(zhì)5將具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)T的結(jié)點(diǎn)按層序從上到下，同一層的結(jié)點(diǎn)從左到右編號(hào)，則對(duì)任一個(gè)結(jié)點(diǎn)i(1&i1,則其雙親結(jié)點(diǎn)編號(hào)為|_2；(2)如果2Xin,則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)；否則結(jié)點(diǎn)i的左孩子結(jié)點(diǎn)的編號(hào)為2i;(3)如果2Xi+1n,則結(jié)點(diǎn)i無(wú)右孩子；否則結(jié)點(diǎn)i右孩子結(jié)點(diǎn)的編號(hào)為2i+1。證明：只要能證明(2)、(3)成立，那么可以由此導(dǎo)出結(jié)論(1)也成立。以下用歸納法對(duì)結(jié)論(2)、(3

15、)給出證明。當(dāng)i=1時(shí)，其左孩子結(jié)點(diǎn)編號(hào)為2=2i,右孩子結(jié)點(diǎn)編號(hào)為3=2i+1,所以結(jié)論成立；假設(shè)i=k時(shí)結(jié)論成立，即其左孩子結(jié)點(diǎn)編號(hào)為2k,右孩子結(jié)點(diǎn)編號(hào)為2k+1;以下證明當(dāng)i=k+1時(shí)結(jié)論也成立：根據(jù)歸納的假設(shè)，由完全二叉樹(shù)的特點(diǎn)以及編號(hào)的順序可知，當(dāng)?shù)趉個(gè)和第k+1個(gè)結(jié)點(diǎn)在同一層時(shí)其結(jié)構(gòu)如圖6.5(a)所示，第k+1個(gè)結(jié)點(diǎn)的左孩子結(jié)點(diǎn)編號(hào)為2k+2=2(k+1)=2i,右孩子結(jié)點(diǎn)編號(hào)為2k+3=2(k+1)+1=2i+1結(jié)論成立；當(dāng)?shù)趉個(gè)和第k+1個(gè)結(jié)點(diǎn)不在同一層時(shí)，第k個(gè)必為上一層的最右一個(gè)結(jié)點(diǎn)，而第k+1個(gè)結(jié)點(diǎn)必為下一層最左一個(gè)結(jié)點(diǎn)，其結(jié)構(gòu)如圖6.5(b)所示，此時(shí)如前所述，結(jié)論

16、也成立，所以在一般情況下(2),(3)的結(jié)論也是成立的。me.5完生二叉樹(shù)中結(jié)點(diǎn)i和結(jié)點(diǎn)i*i的左右珠子1 .順序存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)是，用一組地址連續(xù)的存儲(chǔ)單元來(lái)存放一顆二叉樹(shù)的所有結(jié)點(diǎn)元素。為此,必須將二叉樹(shù)中的所有結(jié)點(diǎn)依照一定的規(guī)律安排在數(shù)組的存儲(chǔ)單元中。具體方法如下：(1)對(duì)于完全二叉樹(shù)，按照至上而下，自左到右的次序存放樹(shù)中的所有結(jié)點(diǎn)元素即可。(2)對(duì)于一般二叉樹(shù)，首先要將其轉(zhuǎn)化”為完全二叉樹(shù)，然后再按照完全二叉樹(shù)的順序存儲(chǔ)方式將每個(gè)結(jié)點(diǎn)存儲(chǔ)在一維數(shù)組的相應(yīng)分量中。其轉(zhuǎn)化”過(guò)程是，在非完全二叉樹(shù)的所有殘缺”位置上(相對(duì)于完全二叉樹(shù)而言)增設(shè)虛結(jié)點(diǎn)“，通常用犢示不存在的點(diǎn)。例如：

17、對(duì)于圖6.6(a)所示的完全二叉樹(shù)可以順序存儲(chǔ)表示為圖6.6(b)。此時(shí)，根據(jù)性質(zhì)5可知：對(duì)于任意一個(gè)結(jié)點(diǎn)的序號(hào)i(0ilchild,Visit);先序遍歷左子樹(shù)PreOrder(T-rchild,Visit);先序遍歷右子樹(shù)2 .中序遍歷的遞歸算法voidInOrder(BiTreeT,void(*Visit)(BiTree)if(T)InOrder(T-lchild,Visit);中序遍歷左子樹(shù)Visit(T);/訪(fǎng)問(wèn)根結(jié)點(diǎn)InOrder(T-rchild,Visit);中序遍歷右子樹(shù)3 .后序遍歷的遞歸算法voidPostOrder(BiTreeT,void(*Visit)(BiTree

18、)if(T)PostOrder(T-lchild,Visit);/后序遍歷左子樹(shù)PostOrder(T-rchild,Visit);后序遍歷右子樹(shù)Visit(T);/訪(fǎng)問(wèn)根結(jié)點(diǎn)函數(shù)voidPT(BiTreeT)的功能是輸出(顯示)結(jié)點(diǎn)T的數(shù)據(jù)域的值。voidPT(BiTreeT)coutdata;/PT(T)為訪(fǎng)問(wèn)結(jié)點(diǎn)T的函數(shù)T的三種遍歷序列。函數(shù)voidPtTree(BiTreeT)的作用是分別按先序、中序、后序輸出二叉樹(shù)voidPtTree(BiTreeT)/函數(shù)PtTree(T)輸出二叉樹(shù)T的三種遍歷序列cout先序遍歷序列為:n;PreOrder(T,PT);coutn中序遍歷序列為：

19、n;InOrder(T,PT);coutn后序遍歷序列為:n;PostOrder(T,PT);coute;if(e=*)T=NULL;return;/輸入嚷示空指針NULLT=newBiTNode;當(dāng)e不為零時(shí)建立結(jié)點(diǎn)TT-data=e;Create_BiT(T-lchild);/通過(guò)遞歸調(diào)用建立T的左子樹(shù)T-lchildCreate_BiT(T-rchild);/通過(guò)遞歸調(diào)用建立T的右子樹(shù)T-rchild先序建立二叉樹(shù)的演示程序代碼如下：voidmain()BiTree T1,T2;cout”先序建立二叉樹(shù) T1:n;cout輸入T1的先序遍歷全序列(用Create_BiT(T1);cout

20、對(duì)T1進(jìn)行遍歷:n;PtTree(T1);cout”先序建立二叉樹(shù) T2:n;cout輸入T2的先序遍歷全序列(用Create_BiT(T2);coutlchild);/通過(guò)遞歸調(diào)用計(jì)算左子樹(shù)的深度h2=1+Depth_BiT(T-rchild);/通過(guò)遞歸調(diào)用計(jì)算右子樹(shù)的深度returnh1h2?h1:h2;3 .復(fù)制一棵二叉樹(shù)遞歸算法函數(shù)BiTreeCopyTree(BiTreeT)的作用是通過(guò)二叉樹(shù)T復(fù)制生成另一棵二叉樹(shù)T1并將其返回。叉樹(shù)的復(fù)制過(guò)程是通過(guò)遞歸調(diào)用來(lái)完成的。即先復(fù)制根結(jié)點(diǎn)，再分別復(fù)制其左子樹(shù)和右子樹(shù)。BiTreeCopyTree(BiTreeT)BiTreeT1;if(!

21、T)T1=NULL;elseT1=newBiTNode;/建立新樹(shù)的根結(jié)點(diǎn)T1T1-data=T-data;T1-lchild=CopyTree(T-lchild);/通過(guò)遞歸用復(fù)制T的左子樹(shù)到T1的左子樹(shù)中T1-rchild=CopyTree(T-rchild);/通過(guò)遞歸用復(fù)制T的右子樹(shù)到T1的右子樹(shù)中returnT1;4 交換一棵二叉樹(shù)中所有結(jié)點(diǎn)的左孩子和右孩子函數(shù)voidChange(BiTree&T)的功能是交換二叉樹(shù)T的所有結(jié)點(diǎn)的左右孩子。函數(shù)的實(shí)現(xiàn)過(guò)程是通過(guò)遞歸調(diào)用來(lái)完成的。即先交換根結(jié)點(diǎn)的左右孩子，再分別交換根結(jié)點(diǎn)的左孩子和右孩子結(jié)點(diǎn)的左右孩子。voidChange(BiTre

22、e&T)BiTreett;if(T)tt=T-lchild;T-lchild=T-rchild;T-rchild=tt;Change(T-lchild);/通過(guò)遞歸調(diào)用交換左子樹(shù)中根結(jié)點(diǎn)的左右孩子Change(T-rchild);/通過(guò)遞歸調(diào)用交換右子樹(shù)中根結(jié)點(diǎn)的左右孩子5 求二叉樹(shù)的所有葉結(jié)點(diǎn)的個(gè)數(shù)操作intLeaf_BiT(BiTreeT)的功能是返回二叉樹(shù)T中所有葉結(jié)點(diǎn)的個(gè)數(shù)。函數(shù)的實(shí)現(xiàn)過(guò)程是通過(guò)遞歸調(diào)用來(lái)完成的。即分別計(jì)算根結(jié)點(diǎn)的左子樹(shù)葉結(jié)點(diǎn)和右子樹(shù)葉結(jié)點(diǎn)，最后返回其和值。intLeaf_BiT(BiTreeT)intnum;if(!T)num=0;/空樹(shù)的葉結(jié)點(diǎn)數(shù)為0elseif(!

23、T-lchild&!T-rchild)num=1;/只有根結(jié)點(diǎn)的樹(shù)的葉結(jié)點(diǎn)數(shù)為1elsenum=Leaf_BiT(T-lchild)+Leaf_BiT(T-rchild);/通過(guò)遞歸調(diào)用計(jì)算其左右子樹(shù)的葉子結(jié)點(diǎn)數(shù)returnnum;6 求結(jié)點(diǎn)x的雙親結(jié)點(diǎn)Parent函數(shù)BiTreeParent(BiTreeT,ETypex)的作用是返回二叉樹(shù)T中結(jié)點(diǎn)值為x的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的首地址。其結(jié)點(diǎn)的尋訪(fǎng)順序是按先序遍歷的順序進(jìn)行的，如果查找失敗返回NULL。顯然，該操作的實(shí)現(xiàn)過(guò)程是通過(guò)遞歸調(diào)用來(lái)完成的。BiTreeParent(BiTreeT,ETypex)BiTreep;if(!T|T-data=x)

24、p=NULL;/樹(shù)的根結(jié)點(diǎn)T無(wú)雙親結(jié)點(diǎn)elseif(T-lchild&T-lchild-data=x|T-rchild&T-rchild-data=x)p=T;/如果T的左孩子或右孩子結(jié)點(diǎn)值為x則返回Telseif(!(p=Parent(T-lchild,x)/如果在左子樹(shù)中遞歸差找不成功p=Parent(T-rchild,x);/在右子樹(shù)中遞歸查找return(p);7 求一個(gè)結(jié)點(diǎn)x的所有祖先結(jié)點(diǎn)Ancestor操作voidAncestor(BiTreeT,ETypex)的功能是輸出二叉樹(shù)T中值為x的結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)的值。函數(shù)的實(shí)現(xiàn)過(guò)程是通過(guò)多次調(diào)用函數(shù)BiTreeParent(BiTre

25、eT,ETypex)，從其雙親結(jié)點(diǎn)開(kāi)始輸出，逐步上升到根結(jié)點(diǎn)。voidAncestor(BiTreeT,ETypex)BiTreep;cout結(jié)點(diǎn)xdata;coutx;coutlchild)/如果有左孩子則左孩子入隊(duì)Qr+=t-lchild;r%=n;if(t-rchild)/如果有右孩子則右孩子入隊(duì)Qr+=t-rchild;r%=n;cout刪除結(jié)點(diǎn)：datadata=x)/如果x為根結(jié)點(diǎn)則刪除整棵樹(shù)DelBiTree(T);return;elseDelSubTree(T-lchild,x);/通過(guò)遞歸調(diào)用在T的左子樹(shù)中完成刪除操作DelSubTree(T-rchild,x);通過(guò)遞歸調(diào)用

26、在T的右子樹(shù)中完成刪除操作9 .二叉樹(shù)基本操作演示主函數(shù)函數(shù)要求按先序遍歷全序列來(lái)創(chuàng)建二叉樹(shù)T1。其功能是:1)輸出T1的三種遍歷序列、深度、葉結(jié)點(diǎn)數(shù)；2)復(fù)制T1到二叉樹(shù)T2,并輸出T2的深度、以及交換T2中所有結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)后，T2的三種遍歷序列和深度，并釋放T2的存儲(chǔ)空間；3)根據(jù)輸入的結(jié)點(diǎn)值x輸出T1中x的所有祖先結(jié)點(diǎn)的值;4)刪除T1中所有以x為根的子樹(shù)，并釋放空間。voidmain()voidDelSubTree(BiTree&T,ETypex);voidDelBiTree(BiTree&T);BiTreeT1,T2;cout先序建立一棵二叉樹(shù)：n;Create_BiT(T1)

27、;PtTree(T1);cout深度為:Depth_BiT(T1)endl;cout葉結(jié)點(diǎn)的個(gè)數(shù)為：Leaf_BiT(T1)endl;T2=CopyTree(T1);cout”復(fù)制后的二叉樹(shù)為：n;PtTree(T2);cout深度為:Depth_BiT(T2)endl;Change(T2);cout”交換后的二叉樹(shù)T2為:n;PtTree(T2);cout深度為:Depth_BiT(T2)endl;ETypex;coutx;Ancestor(T1,x);cout銷(xiāo)毀T1中所有根為x的子樹(shù)！n;DelSubTree(T1,x);cout刪除后的T1為:n;PtTree(T1);coutlchi

28、ld,T2-lchild);like2=LikeTree(Ti-rchild,T2-rchild);return(likei*like2);【例6.5】編寫(xiě)遞歸算法，輸出在二叉樹(shù)的先序遍歷序列中第k個(gè)位置上的結(jié)點(diǎn)的值。解：本題的算法思想是，通過(guò)先序遍歷二叉樹(shù)的遞歸調(diào)用方法，在執(zhí)行過(guò)程中每訪(fǎng)問(wèn)一次結(jié)點(diǎn)前先執(zhí)行操作“k-;”一次，并判斷k的值是否為0。如果在某次訪(fǎng)問(wèn)結(jié)點(diǎn)時(shí)k的值為0,那么該結(jié)點(diǎn)即為所求結(jié)點(diǎn)，輸出該結(jié)點(diǎn)的值結(jié)束操作。算法實(shí)現(xiàn)如下：voidPreOrder_k(BiTreeT,int&k)由于在函數(shù)調(diào)用過(guò)程中的參數(shù)k為值傳遞是單向的，所以此處的參數(shù)k應(yīng)定義為引用參數(shù)&koif(T)k-

29、;if(k=0)coutdatalchild,k);PreOrder_k(T-rchild,k);【例6.6】編寫(xiě)按層次順序遍歷一棵二叉樹(shù)T的算法TraverseLevel(T)。解：按層次遍歷二叉樹(shù)的過(guò)程是，由根結(jié)點(diǎn)開(kāi)始，按照從上到下從左到右的次序依次訪(fǎng)問(wèn)樹(shù)中的每一個(gè)結(jié)點(diǎn)。為此，先建立一個(gè)初始僅有根結(jié)點(diǎn)的隊(duì)列Q，每次提取一個(gè)隊(duì)首元素，并在訪(fǎng)問(wèn)該結(jié)點(diǎn)的值后將其左、右孩子結(jié)點(diǎn)(如果存在)依次入隊(duì)，直至隊(duì)列為空為止。其程序?qū)崿F(xiàn)過(guò)程如下：voidTraverseLevel(BiTreeT)intf=0,r=0,n=100;/r為隊(duì)尾指針,f為隊(duì)首指針，n為最大隊(duì)列長(zhǎng)度BiTreeQ100,t;/Q為

30、存放樹(shù)T中結(jié)點(diǎn)的隊(duì)列if(!(Qr+=T)return;while(f!=r)t=Qf+;f%=n;/t出隊(duì)coutdatalchild)/如果t有左孩子則左孩子入隊(duì)Qr+=t-lchild;r%=n;if(t-rchild)/如果t有右孩子則右孩子入隊(duì)Qr+=t-rchild;r%=n;coutlchild&!T-rchild)return1;Qr+=T;while(r!=f)&(!leaf)t=Qf+;f%=n;if(t-lchild&t-rchild)/結(jié)點(diǎn)t的度為2時(shí)繼續(xù)Qr+=t-lchild;r%=n;Qr+=t-rchild;r%=n;elseif(t-lchild)/結(jié)點(diǎn)t的度

31、為1且僅有左孩子時(shí)以后均為葉結(jié)點(diǎn)Qr+=t-lchild;r%=n;leaf=1;elseif(t-rchild)/結(jié)點(diǎn)t的度為1時(shí)不能有右孩子結(jié)點(diǎn)h=0;break;elseleaf=1;/結(jié)點(diǎn)t的度為0時(shí)以后結(jié)點(diǎn)的度均為0while(h&(f!=r)/在剩下的結(jié)點(diǎn)中均為葉結(jié)點(diǎn)t=Qf+;f%=n;if(t-lchild|t-rchild)h=0;returnh;【例6.8】設(shè)計(jì)算法，通過(guò)由順序表存儲(chǔ)的完全二叉樹(shù)STn建立該完全二叉樹(shù)的二叉鏈表結(jié)構(gòu)T。解：本問(wèn)題的算法思想是，通過(guò)遞歸調(diào)用的方法來(lái)逐步完成對(duì)二叉樹(shù)T中各個(gè)結(jié)點(diǎn)的建立操作。即先建立根結(jié)點(diǎn)，再依次建立根結(jié)點(diǎn)的左子樹(shù)根結(jié)點(diǎn)和右子樹(shù)的根

32、結(jié)點(diǎn)，直至完成所有結(jié)點(diǎn)的建立。算法實(shí)現(xiàn)如下：voidTreeSqToL(BiTree&T,ETypeST,intn,inti=1)/i為根結(jié)點(diǎn)的序號(hào)，n為結(jié)點(diǎn)總數(shù)if(in)T=NULL;return;elseT=newBiTNode;T-data=STi-1;TreeSqToL(T-lchild,ST,n,i*2);TreeSqToL(T-rchild,ST,n,i*2+1);【例6.9】設(shè)計(jì)一個(gè)算法，由二叉樹(shù)T的先序遍歷序列preoder口和中序遍歷序列inoder口來(lái)構(gòu)造二叉樹(shù)T。解：根據(jù)二叉樹(shù)的遞歸定義和遍歷過(guò)程可知，在先序遍歷序列preoder中的第一個(gè)數(shù)據(jù)元素必為樹(shù)的根結(jié)點(diǎn)，根結(jié)點(diǎn)

33、后面的前一部分為其左子樹(shù)的先序遍歷序列，后一部分為其右子樹(shù)的先序遍歷序列；在中序遍歷序列inoder中，根結(jié)點(diǎn)前面的元素序列為其左子樹(shù)的中序遍歷序列，而在根結(jié)點(diǎn)后面的元素序列為其右子樹(shù)的中序遍歷序列。所以本問(wèn)題可以采用遞歸調(diào)用的方法，先建立根結(jié)點(diǎn)，再分別建立根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)。算法實(shí)現(xiàn)代碼如下：BiTreeBiTreeCreate(EType*preoder,EType*inoder,intn)/preoder為先序首地址，inoder為中序首地址，n為結(jié)點(diǎn)總數(shù)BiTreeT;intk;EType*p;if(ndata=*preoder;/建立根結(jié)點(diǎn)for(p=inoder;plchild

34、=BiTreeCreate(preoder+1,inoder,k);/建立左子樹(shù)T-rchild=BiTreeCreate(preoder+k+1,p+1,n-1-k);/建立右子樹(shù)returnT;【例6.10】編寫(xiě)通過(guò)中序遍歷序列Inn和層次遍歷序列Levn建立一棵由二叉鏈表存儲(chǔ)的二叉樹(shù)的程序代碼。voidInLev_Create(EType*In,EType*Lev,intn,BiTree&T)BiTreep,q,*Q;inti,f=0,r=0,k=1;/f,r分別為隊(duì)列Q的頭、尾指針，k指向Levn中第二個(gè)元素Q=newBiTreen;T=newBiTNode;/建立樹(shù)的根結(jié)點(diǎn)TT-da

35、ta=*Lev;T-lchild=T-rchild=NULL;Qr+=T;/建立一個(gè)初始只有根結(jié)點(diǎn)T的隊(duì)列Qwhile(r!=f)/當(dāng)隊(duì)列Q不空時(shí)繼續(xù)p=Qf+;f%=n;for(i=0;idata)break;/查找p-data在Inn中的下標(biāo)值iIni=A;將Inn中訪(fǎng)問(wèn)過(guò)的元素Ini設(shè)置為if(i0&Ini-1!=w)建立結(jié)點(diǎn)p的左子樹(shù)qq=newBiTNode;p-lchild=q;q-data=Levk+;q-lchild=q-rchild=NULL;Qr+=q;r%=n;if(irchild=q;q-data=Levk+;q-lchild=q-rchild=NULL;Qr+=q;r

36、%=n;deleteQ;演示主程序代碼該程序的主要功能是，通過(guò)調(diào)用前面給出的各種算法完成以下操作：(1)判斷兩棵二叉樹(shù)T1和T2是否為相似二叉樹(shù)；(2)查找位于先序序列中第k個(gè)位置的結(jié)點(diǎn)的值；(3)按層次順序遍歷一棵二叉樹(shù)T1；(4)判斷一棵二叉樹(shù)是否為完全二叉樹(shù)；(5)由順序表存儲(chǔ)的完全二叉樹(shù)STn建立二叉鏈表T；(6)由二叉樹(shù)的先序和中序序列構(gòu)造該二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)。voidmain()ETypest100,pre100,in100;BiTreeT1,T2;intnum,k,n,i;while(1)cout1-判斷兩棵二叉樹(shù)T1和T2是否為相似二叉樹(shù)n;cout2-求位于先序序列中第k個(gè)位置的結(jié)點(diǎn)的值.n;cout3-按層次順序遍歷一棵二叉樹(shù)T1n;cout4-判斷一棵二叉樹(shù)是否為完全二叉樹(shù).n;cout5-由順序表存儲(chǔ)的完全二叉樹(shù)STn建立二叉鏈表Ton;cout6-由二叉樹(shù)的先序和中序序列構(gòu)造二叉樹(shù).n;coutnum;switch(num)case 1:cout先序建立一棵二叉樹(shù)T1:n;Create_BiT(T1);cout”先序建立一棵二叉樹(shù)T2:n;Create_BiT(T2)