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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、)if(T)PostOrder(T-lchild,Visit);/后序遍歷左子樹PostOrder(T-rchild,Visit);后序遍歷右子樹Visit(T);/訪問根結(jié)點函數(shù)voidPT(BiTreeT)的功能是輸出(顯示)結(jié)點T的數(shù)據(jù)域的值。voidPT(BiTreeT)coutdata;/PT(T)為訪問結(jié)點T的函數(shù)T的三種遍歷序列。函數(shù)voidPtTree(BiTreeT)的作用是分別按先序、中序、后序輸出二叉樹voidPtTree(BiTreeT)/函數(shù)PtTree(T)輸出二叉樹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不為零時建立結(jié)點TT-data=e;Create_BiT(T-lchild);/通過遞歸調(diào)用建立T的左子樹T-lchildCreate_BiT(T-rchild);/通過遞歸調(diào)用建立T的右子樹T-rchild先序建立二叉樹的演示程序代碼如下：voidmain()BiTree T1,T2;cout”先序建立二叉樹 T1:n;cout輸入T1的先序遍歷全序列(用Create_BiT(T1);cout

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

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

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

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

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

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

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

27、;PtTree(T1);cout深度為:Depth_BiT(T1)endl;cout葉結(jié)點的個數(shù)為：Leaf_BiT(T1)endl;T2=CopyTree(T1);cout”復(fù)制后的二叉樹為：n;PtTree(T2);cout深度為:Depth_BiT(T2)endl;Change(T2);cout”交換后的二叉樹T2為:n;PtTree(T2);cout深度為:Depth_BiT(T2)endl;ETypex;coutx;Ancestor(T1,x);cout銷毀T1中所有根為x的子樹！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】編寫遞歸算法，輸出在二叉樹的先序遍歷序列中第k個位置上的結(jié)點的值。解：本題的算法思想是，通過先序遍歷二叉樹的遞歸調(diào)用方法，在執(zhí)行過程中每訪問一次結(jié)點前先執(zhí)行操作“k-;”一次，并判斷k的值是否為0。如果在某次訪問結(jié)點時k的值為0,那么該結(jié)點即為所求結(jié)點，輸出該結(jié)點的值結(jié)束操作。算法實現(xiàn)如下：voidPreOrder_k(BiTreeT,int&k)由于在函數(shù)調(diào)用過程中的參數(shù)k為值傳遞是單向的，所以此處的參數(shù)k應(yīng)定義為引用參數(shù)&koif(T)k-

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

30、存放樹T中結(jié)點的隊列if(!(Qr+=T)return;while(f!=r)t=Qf+;f%=n;/t出隊coutdatalchild)/如果t有左孩子則左孩子入隊Qr+=t-lchild;r%=n;if(t-rchild)/如果t有右孩子則右孩子入隊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é)點t的度為2時繼續(xù)Qr+=t-lchild;r%=n;Qr+=t-rchild;r%=n;elseif(t-lchild)/結(jié)點t的度

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

32、結(jié)點，直至完成所有結(jié)點的建立。算法實現(xiàn)如下：voidTreeSqToL(BiTree&T,ETypeST,intn,inti=1)/i為根結(jié)點的序號，n為結(jié)點總數(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è)計一個算法，由二叉樹T的先序遍歷序列preoder口和中序遍歷序列inoder口來構(gòu)造二叉樹T。解：根據(jù)二叉樹的遞歸定義和遍歷過程可知，在先序遍歷序列preoder中的第一個數(shù)據(jù)元素必為樹的根結(jié)點，根結(jié)點

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

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

35、ta=*Lev;T-lchild=T-rchild=NULL;Qr+=T;/建立一個初始只有根結(jié)點T的隊列Qwhile(r!=f)/當(dāng)隊列Q不空時繼續(xù)p=Qf+;f%=n;for(i=0;idata)break;/查找p-data在Inn中的下標(biāo)值iIni=A;將Inn中訪問過的元素Ini設(shè)置為if(i0&Ini-1!=w)建立結(jié)點p的左子樹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;演示主程序代碼該程序的主要功能是，通過調(diào)用前面給出的各種算法完成以下操作：(1)判斷兩棵二叉樹T1和T2是否為相似二叉樹；(2)查找位于先序序列中第k個位置的結(jié)點的值；(3)按層次順序遍歷一棵二叉樹T1；(4)判斷一棵二叉樹是否為完全二叉樹；(5)由順序表存儲的完全二叉樹STn建立二叉鏈表T；(6)由二叉樹的先序和中序序列構(gòu)造該二叉樹的二叉鏈表存儲結(jié)構(gòu)。voidmain()ETypest100,pre100,in100;BiTreeT1,T2;intnum,k,n,i;while(1)cout1-判斷兩棵二叉樹T1和T2是否為相似二叉樹n;cout2-求位于先序序列中第k個位置的結(jié)點的值.n;cout3-按層次順序遍歷一棵二叉樹T1n;cout4-判斷一棵二叉樹是否為完全二叉樹.n;cout5-由順序表存儲的完全二叉樹STn建立二叉鏈表Ton;cout6-由二叉樹的先序和中序序列構(gòu)造二叉樹.n;coutnum;switch(num)case 1:cout先序建立一棵二叉樹T1:n;Create_BiT(T1);cout”先序建立一棵二叉樹T2:n;Create_BiT(T2)