數(shù)據(jù)結(jié)構(gòu)-合肥工業(yè)大學(xué) 6

數(shù)據(jù)結(jié)構(gòu)NorthChinaElectricPowerUniversityDataStructure華北電力大學(xué)計(jì)算機(jī)科學(xué)與工程系Dept.ofComputerScience&EngineeringofNorthChinaElectricPowerUniversity第六章樹(shù)★基本術(shù)語(yǔ)★樹(shù)的抽象數(shù)據(jù)類(lèi)型和存儲(chǔ)★二叉樹(shù)★二叉樹(shù)的遍歷及線索二叉樹(shù)★樹(shù)的遍歷★哈夫曼樹(shù)及其應(yīng)用NorthChinaElectricPowerUniversity§6.1基本術(shù)語(yǔ)樹(shù)型結(jié)構(gòu)是一類(lèi)重要的非線性數(shù)據(jù)結(jié)構(gòu)，其中以二叉樹(shù)最為常用。樹(shù)是以分支關(guān)系定義的層次結(jié)構(gòu)，它為計(jì)算機(jī)應(yīng)用中出現(xiàn)的具有層次關(guān)系或分支關(guān)系的數(shù)據(jù)提供了一種自然的表示方法。用樹(shù)結(jié)構(gòu)描述的信息模型在客觀世界普遍存在。計(jì)算機(jī)科學(xué)與工程系辦公室教研室實(shí)驗(yàn)室研究室行政辦公室總支辦公室計(jì)算機(jī)教研室軟件教研室軟件實(shí)驗(yàn)室綜合實(shí)驗(yàn)室數(shù)字邏輯實(shí)驗(yàn)室組成原理試驗(yàn)室管理信息系統(tǒng)研究室知識(shí)工程研究室微機(jī)應(yīng)用研究室NorthChinaElectricPowerUniversity

1.樹(shù)的定義：

樹(shù)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集T,在一棵非空樹(shù)中：

1)有且僅有一個(gè)特定的稱(chēng)為根的結(jié)點(diǎn)；

2)當(dāng)n>1時(shí),其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集合T1,T2,…,Tm,其中每個(gè)集合本身又是一棵樹(shù)，并且稱(chēng)為根的子樹(shù)。樹(shù)的定義可以用如下形式化描述來(lái)表示：Tree=(D,R)其中：D是具有相同特性的數(shù)據(jù)元素的集合；若D只含有一個(gè)元素，則R為空集；否則R是D上的某個(gè)二元關(guān)系H的集合，即R={H}，H為如下描述的二元關(guān)系:NorthChinaElectricPowerUniversity2.樹(shù)的幾種表示方法：1)有且僅有一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)，該結(jié)點(diǎn)被稱(chēng)為樹(shù)的根；2)除樹(shù)根結(jié)點(diǎn)外，其余每個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)；3)包含樹(shù)根結(jié)點(diǎn)在內(nèi)的每個(gè)結(jié)點(diǎn)，可以有任意多個(gè)(包含

0個(gè))后繼。ABCDEFGHIJKLM1)二元組表示D={A,B,C,D,E,F,G,H,I,J,K,L,M}R={<A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<C,G>,<D,H>,<D,I>,<D,J>,<F,K>,<F,L>,<J,M>}NorthChinaElectricPowerUniversity4)廣義表表示法：A(B(E,F(K,L)),C(G),D(H,I,J(M)))ABEKLFCGHIMDJ2)集合圖表示3)凹入表表示NorthChinaElectricPowerUniversityJIHGFEACDB5)樹(shù)形表示法

北航計(jì)算機(jī)系借助自然界中一棵倒置的樹(shù)的形狀來(lái)表示數(shù)據(jù)元素之間層次關(guān)系的方法。NorthChinaElectricPowerUniversity樹(shù)型結(jié)構(gòu)和線性結(jié)構(gòu)的比較樹(shù)型結(jié)構(gòu)線性結(jié)構(gòu)根結(jié)點(diǎn)無(wú)前驅(qū)結(jié)點(diǎn)第一個(gè)數(shù)據(jù)元素?zé)o前驅(qū)多個(gè)葉子結(jié)點(diǎn)無(wú)后繼最后一個(gè)數(shù)據(jù)元素?zé)o后繼其它數(shù)據(jù)元素有一個(gè)前驅(qū)和多個(gè)后繼其它元素有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼NorthChinaElectricPowerUniversity3.樹(shù)中的基本術(shù)語(yǔ)：ABCDEFGHIJKLM1.結(jié)點(diǎn)、結(jié)點(diǎn)的度、樹(shù)的度2.葉子結(jié)點(diǎn)、分支結(jié)點(diǎn)3.孩子、雙親、兄弟、堂兄弟、祖先、子孫4.結(jié)點(diǎn)的層次、樹(shù)的深度5.有序樹(shù)和無(wú)序樹(shù)6.森林BCDEFGHIJKLMNorthChinaElectricPowerUniversity4.樹(shù)的性質(zhì)：性質(zhì)1:樹(shù)中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度加1。ABCDEFGHIJKLM證明：除樹(shù)的根結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)有且只有一個(gè)直接前驅(qū)，除樹(shù)的根結(jié)點(diǎn)之外的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的分支數(shù)。性質(zhì)2:度為k的樹(shù)中第i層至多有ki-1個(gè)結(jié)點(diǎn)。性質(zhì)3:深度為h的k叉樹(shù)至多有(kh-1)/(k-1)個(gè)結(jié)點(diǎn)。性質(zhì)4:具有n個(gè)結(jié)點(diǎn)的k叉樹(shù)的最小深度為logk(n(k-1)+1)。NorthChinaElectricPowerUniversity§6.2樹(shù)的抽象數(shù)據(jù)類(lèi)型和存儲(chǔ)1.樹(shù)的基本運(yùn)算1.Root(T):求樹(shù)T的根結(jié)點(diǎn)，若T為空則返回結(jié)果為“空”。2.Parent(T,x):求結(jié)點(diǎn)x在樹(shù)T上的雙親結(jié)點(diǎn)，若結(jié)點(diǎn)x是樹(shù)T的根結(jié)點(diǎn)或x不在樹(shù)T中，則返回結(jié)果為“空”。3.Initiate(T):置T為空樹(shù)。4.Child(T,x,i):求樹(shù)T上結(jié)點(diǎn)x在的第i個(gè)孩子，若x不在樹(shù)T上或x

沒(méi)有第i個(gè)孩子，則返回結(jié)果為“空”。5.Create(x,T1,T2,…,Tk):建立一棵以x為根，以T1,T2,…,Tk為第1,2,3…,k棵子樹(shù)的樹(shù)。6.Delete(T,x,i):刪除樹(shù)T上結(jié)點(diǎn)x的第i棵子樹(shù)，若結(jié)點(diǎn)x無(wú)第i棵子樹(shù)，則為空操作。7.Traverse(T):按某個(gè)次序依次訪問(wèn)樹(shù)中的各個(gè)結(jié)點(diǎn)，并使每個(gè)結(jié)點(diǎn)只被訪問(wèn)一次。NorthChinaElectricPowerUniversity2.樹(shù)的存儲(chǔ)結(jié)構(gòu)1.孩子表示法由于樹(shù)中每個(gè)結(jié)點(diǎn)可能有多棵子樹(shù)，可用多重鏈表，即每個(gè)結(jié)點(diǎn)有多個(gè)指針域，其中每個(gè)指針指向一棵子樹(shù)的根結(jié)點(diǎn)，則結(jié)點(diǎn)形式有如下兩種：在第一種形式中，結(jié)點(diǎn)是同構(gòu)的，存儲(chǔ)空間浪費(fèi)較大，在第二種形式中，結(jié)點(diǎn)是不同構(gòu)的，雖能節(jié)約存儲(chǔ)空間，但實(shí)現(xiàn)和運(yùn)算很不方便。datachild1child2childd…(1)datachild1child2childd…degree(2)NorthChinaElectricPowerUniversity可以把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，看成一個(gè)線性表，且以單鏈表作存儲(chǔ)結(jié)構(gòu)，n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表，n個(gè)頭指針又組成一個(gè)線性表，為了便于查找，可用向量表示。typedef

struct

TNode{intchild;

struct

TNode*next;}*TreeNode;typedef

Treenode

Tree[maxn];12345623456^^123456^^^^23456^^123456011222^^^^NorthChinaElectricPowerUniversity2.孩子兄弟表示法又稱(chēng)二叉鏈表表示法，即以二叉鏈表作樹(shù)的存儲(chǔ)結(jié)構(gòu)，鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)，分別命名為first-child和nextsibling。datafirst-childnextsibling123456123456^^^^^^^在孩子兄弟表示法中，要找結(jié)點(diǎn)x的第i個(gè)孩子,則只要先從first-child域找到第一個(gè)孩子結(jié)點(diǎn)上，然后沿著該孩子結(jié)點(diǎn)的nextsibling域連續(xù)走i-1步，便可找到x的第i個(gè)孩子。NorthChinaElectricPowerUniversity3.雙親表示法用一個(gè)數(shù)組順序地存放樹(shù)的各個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)存放的順序是任意的。每一結(jié)點(diǎn)有兩個(gè)域組成：數(shù)據(jù)域和指針域，分別存儲(chǔ)樹(shù)上結(jié)點(diǎn)中的數(shù)據(jù)元素和用于指示本結(jié)點(diǎn)之雙親所在的存儲(chǔ)結(jié)點(diǎn)。指針域的類(lèi)型定義有兩種：高級(jí)語(yǔ)言中的指針類(lèi)型和整型或子界類(lèi)型，與之對(duì)應(yīng)的鏈表分別成為動(dòng)態(tài)鏈表和靜態(tài)鏈表。靜態(tài)雙親鏈表的定義：#definesize結(jié)點(diǎn)數(shù)typedef

struct

TNode{

ElemTypedata;

intparent;}TreeNode;typedef

TreeNode

stalist[size];

123456^123456132456dataparent011333結(jié)點(diǎn)序號(hào)NorthChinaElectricPowerUniversity§6.3二叉樹(shù)二叉樹(shù)是一種重要的數(shù)據(jù)結(jié)構(gòu)類(lèi)型，它有許多良好的性質(zhì)和簡(jiǎn)單的物理表示，它的特點(diǎn)是最多有兩個(gè)孩子，并且二叉樹(shù)的子樹(shù)有左右之分，且其子樹(shù)的順序不能任意顛倒。1.二叉樹(shù)的定義二叉樹(shù)是由n(n≥0)個(gè)結(jié)點(diǎn)的有限集合，此集合或者是空的，或者是有一個(gè)根結(jié)點(diǎn)加上兩棵分別稱(chēng)為左右子樹(shù)的、互不相交的二叉樹(shù)組成。注意：二叉樹(shù)和樹(shù)是兩個(gè)不同的概念，樹(shù)的子樹(shù)不必區(qū)分其次序，而二叉樹(shù)的子樹(shù)有左右之分，另外，二叉樹(shù)也不能簡(jiǎn)單地看成是一有序樹(shù)，因?yàn)橹挥幸豢米訕?shù)時(shí)，無(wú)法區(qū)分其次序。NorthChinaElectricPowerUniversity2.二叉樹(shù)的基本形態(tài)：(空)根根左子樹(shù)根右子樹(shù)根左子樹(shù)右子樹(shù)具有三個(gè)結(jié)點(diǎn)的二叉樹(shù)具有以下五種基本形態(tài)：NorthChinaElectricPowerUniversity3.兩種特殊形態(tài)的二叉樹(shù)

若一棵二叉樹(shù)中的結(jié)點(diǎn),或者為葉結(jié)點(diǎn)，或者具有兩棵非空子樹(shù),并且葉結(jié)點(diǎn)都集中在二叉樹(shù)的最下面一層.這樣的二叉樹(shù)為滿(mǎn)二叉樹(shù).1.滿(mǎn)二叉樹(shù)若一棵二叉樹(shù)中只有最下面兩層的結(jié)點(diǎn)的度可以小于2,并且最下面一層的結(jié)點(diǎn)(葉結(jié)點(diǎn))都依次排列在該層從左至右的位置上。這樣的二叉樹(shù)為完全二叉樹(shù).2.完全二叉樹(shù)NorthChinaElectricPowerUniversity1.一棵非空二叉樹(shù)的第i層最多有2i–1個(gè)結(jié)點(diǎn)(i1)。證明(采用歸納法)(1).當(dāng)i=1時(shí),結(jié)論顯然正確。非空二叉樹(shù)的第1層有且僅有一個(gè)結(jié)點(diǎn),即樹(shù)的根結(jié)點(diǎn).(2).假設(shè)對(duì)于第j層(1

ji–1)結(jié)論也正確,即第j層最多有2j-1個(gè)結(jié)點(diǎn).(3).有定義可知,二叉樹(shù)中每個(gè)結(jié)點(diǎn)最多只能有兩個(gè)孩子結(jié)點(diǎn)。若第i–1層的每個(gè)結(jié)點(diǎn)都有兩棵非空子樹(shù),則第i層的結(jié)點(diǎn)數(shù)目達(dá)到最大.而第i–1層最多有2i–2個(gè)結(jié)點(diǎn)已由假設(shè)證明,于是,應(yīng)有

2

2i–2=2i–1證畢.4.二叉樹(shù)的性質(zhì)NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity2.深度為h的非空二叉樹(shù)最多有2h-1個(gè)結(jié)點(diǎn).證明:

由性質(zhì)1可知,若深度為h的二叉樹(shù)的每一層的結(jié)點(diǎn)數(shù)目都達(dá)到各自所在層的最大值,則二叉樹(shù)的結(jié)點(diǎn)總數(shù)一定達(dá)到最大。即有

20+21+22+…+2i-1+…+2h-1=2h-1證畢.華電計(jì)算機(jī)系NorthChinaElectricPowerUniversity3.若非空二叉樹(shù)有n0個(gè)葉結(jié)點(diǎn),有n2個(gè)度為2的結(jié)點(diǎn),

則n0=n2+1

證明:

設(shè)該二叉樹(shù)有n1個(gè)度為1的結(jié)點(diǎn),結(jié)點(diǎn)總數(shù)為n,有

n=n0+n1+n2

--------(1)設(shè)二叉樹(shù)的分支數(shù)目為B,有

B=n-1

--------(2)這些分支來(lái)自度于為1的結(jié)點(diǎn)與度為2結(jié)點(diǎn),即

B=n1+2n2

--------(3)聯(lián)列關(guān)系(1),(2)與(3),可得到

n0=n2+1證畢.4.具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度h=

log2n

+1.證明:(略)推論：n0=n2+2n3+3n4+

+(m-1)nm+1NorthChinaElectricPowerUniversity5.若對(duì)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按照層次從上到下,每層從左到右的順序進(jìn)行編號(hào),則編號(hào)為i的結(jié)點(diǎn)具有以下性質(zhì):(1)當(dāng)i=1,則編號(hào)為i的結(jié)點(diǎn)為二叉樹(shù)的根結(jié)點(diǎn);

若i>1,則編號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為

i/2

;(2)若i<n/2,即2i≤n,則編號(hào)為i的結(jié)點(diǎn)為分支結(jié)點(diǎn),否則為葉子結(jié)點(diǎn),n/2是最后一個(gè)分支結(jié)點(diǎn);(3)若n為奇數(shù),則樹(shù)中每個(gè)分支結(jié)點(diǎn)都有左右孩子,若n為偶數(shù),則編號(hào)最大的分支結(jié)點(diǎn)只有左孩子、無(wú)右孩子，其余分支結(jié)點(diǎn)都有左右孩子；

(4)若編號(hào)為i的結(jié)點(diǎn)有左孩子，則左孩子結(jié)點(diǎn)的編號(hào)為2i;

若編號(hào)為i的結(jié)點(diǎn)有右孩子，則右孩子的編號(hào)為2i+1;NorthChinaElectricPowerUniversity5二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)一.二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)12345678910ABCDEFGHIJBT[1:15]123456789101112131415ABCDEFGHIJ

根據(jù)完全二叉樹(shù)的性質(zhì)5,對(duì)于深度為h的完全二叉樹(shù),將樹(shù)中所有結(jié)點(diǎn)的數(shù)據(jù)信息按照編號(hào)的順序依次存儲(chǔ)到一維數(shù)組BT[1:2h-1]中,由于編號(hào)與數(shù)組的下標(biāo)一一對(duì)應(yīng),該數(shù)組就是該完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu).

1.完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)華電計(jì)算機(jī)系NorthChinaElectricPowerUniversity12345678910ABCDEFGHIJ111213123456789101112131415BT[1:15]ABCDEFGHJ

I

2.一般二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)華電計(jì)算機(jī)系A(chǔ)BCDEFHIJGNorthChinaElectricPowerUniversity

對(duì)于一般二叉樹(shù),只須在二叉樹(shù)中“添加”一些實(shí)際上二叉樹(shù)中并不存在的“虛結(jié)點(diǎn)”(可以認(rèn)為這些結(jié)點(diǎn)的數(shù)據(jù)信息為空),使其在形式上成為一棵“完全二叉樹(shù)”,然后按照完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)的構(gòu)造方法將所有結(jié)點(diǎn)的數(shù)據(jù)信息依次存放于數(shù)組BT[1:2h-1]中。ABCBT[1:7]ABCDBT[1:15]ACB對(duì)于一些稱(chēng)為“退化二叉樹(shù)”的二叉樹(shù)，順序存儲(chǔ)結(jié)構(gòu)的空間開(kāi)銷(xiāo)浪費(fèi)的缺點(diǎn)比較突出。ACBDNorthChinaElectricPowerUniversity二.二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(二叉鏈表)鏈結(jié)點(diǎn)的構(gòu)造為lchilddatarchild其中,data為數(shù)據(jù)域

lchild

與rchild

分別為指向左、右子樹(shù)的指針域.ABCDEFGIJABCDEFGJIT^^^^^^^^^^華電計(jì)算機(jī)系NorthChinaElectricPowerUniversity在Pascal語(yǔ)言中，可以如下描述一個(gè)鏈結(jié)點(diǎn)的構(gòu)造：

TYPE

nodeptr=

nodetype

nodetype=RECORDdata:datatype;

lchild,rchild:nodeptr;END;VART:nodeptr;在C語(yǔ)言中，一個(gè)鏈結(jié)點(diǎn)的描述為：

typedef

struct

btnode{

ElemTypedata;

struct

btnode*Lchild,*Rchild;}*bitreptr;華電計(jì)算機(jī)系三.三重鏈表結(jié)構(gòu)鏈結(jié)點(diǎn)的構(gòu)造parentrchildlchilddata

其中,data為數(shù)據(jù)域;lchild為指針域,指向左孩子結(jié)點(diǎn);

parent為指針域,指向該結(jié)點(diǎn)的雙親結(jié)點(diǎn);

rchild

為指針域,指向右孩子結(jié)點(diǎn).華電計(jì)算機(jī)系A(chǔ)BCDEFGIJ^ACBDEFGIJ^^^^^^^^^^^NorthChinaElectricPowerUniversity例:已知深度為h的二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)存放于數(shù)組

BT[1:2h-1]中,寫(xiě)一算法，求二叉樹(shù)中葉結(jié)點(diǎn)的數(shù)目。intLEAF(BT,h){return(total);}

total=0if(BT[i]!=^)thenif(BT[2i]=^&&BT[2i+1]=^)or(i>

(2h-1)/2

)thentotal=total+1;

for(i=1;i<=2h-1;i++){}算法北航計(jì)算機(jī)系6樹(shù)與二叉樹(shù)之間的轉(zhuǎn)換NorthChinaElectricPowerUniversity1.在兄弟結(jié)點(diǎn)之間加一條連線；2.對(duì)每個(gè)結(jié)點(diǎn)，除去其最左的孩子之外，去掉該結(jié)點(diǎn)與其他孩子之間的連線；3.以樹(shù)的根結(jié)點(diǎn)為軸心，將整棵樹(shù)順時(shí)針旋轉(zhuǎn)45度。ABCDEFGHIJABCDEFGHIJABCDEFGHIJ森林與二叉樹(shù)之間的轉(zhuǎn)換NorthChinaElectricPowerUniversity1.將森林中各棵樹(shù)的根結(jié)點(diǎn)之間加一條連線；2.對(duì)每棵樹(shù)，用樹(shù)的二叉樹(shù)表示法相連，然后順時(shí)針旋轉(zhuǎn)45度。ABCDEGFHJIABEGCDFHIJNorthChinaElectricPowerUniversity§6.4二叉樹(shù)的遍歷及線索二叉樹(shù)常用的二叉樹(shù)的遍歷方法:

1.先序遍歷

2.中序遍歷

3.后序遍歷

4.按層次遍歷右子樹(shù)左子樹(shù)根華電計(jì)算機(jī)系

按照一定的順序(原則)對(duì)二叉樹(shù)中每一個(gè)結(jié)點(diǎn)都訪問(wèn)一次(僅訪問(wèn)一次),得到一個(gè)由該二叉樹(shù)的所有結(jié)點(diǎn)組成的序列,這一過(guò)程稱(chēng)為二叉樹(shù)的遍歷.NorthChinaElectricPowerUniversity前序序列:ABDEJCFI原則:

若被遍歷的二叉樹(shù)非空,則

1.訪問(wèn)根結(jié)點(diǎn);

2.以前序遍歷原則遍歷根結(jié)點(diǎn)的左子樹(shù);

3.以前序遍歷原則遍歷根結(jié)點(diǎn)的右子樹(shù).G華電計(jì)算機(jī)系1.先序遍歷ABCDEFGJINorthChinaElectricPowerUniversity華電計(jì)算機(jī)系2.中序遍歷ABCDEFGJI中序序列:DBJEAFIC原則:

若被遍歷的二叉樹(shù)非空,則

1.以中序遍歷原則遍歷根結(jié)點(diǎn)的左子樹(shù);

2.訪問(wèn)根結(jié)點(diǎn);

3.以中序遍歷原則遍歷根結(jié)點(diǎn)的右子樹(shù).GNorthChinaElectricPowerUniversity華電計(jì)算機(jī)系3.后序遍歷ABCDEFGJI后序序列:DJEBIFGC原則:

若被遍歷的二叉樹(shù)非空,則

1.以后序遍歷原則遍歷根結(jié)點(diǎn)的左子樹(shù);

2.以后序遍歷原則遍歷根結(jié)點(diǎn)的右子樹(shù).

3.訪問(wèn)根結(jié)點(diǎn);ANorthChinaElectricPowerUniversity先序遍歷voidInorder(bitreptrp){if(p){

Preorder(p->Lchild);//遍歷左子樹(shù)

printf(“%d”,p->data);//訪問(wèn)根結(jié)點(diǎn)

Preorder(p->Rchild);//遍歷右子樹(shù)

}}中序遍歷華電計(jì)算機(jī)系voidPrecorder(bitreptrp){if(p){

printf(“%d”,p->data);//訪問(wèn)根結(jié)點(diǎn)

Preorder(p->Lchild);//遍歷左子樹(shù)

Preorder(p->Rchild);//遍歷右子樹(shù)

}}NorthChinaElectricPowerUniversity按層次遍歷按層次遍歷序列:A,B,C,D,E,F,G,J,IvoidPostorder(bitreptrp){if(p){

printf(“%d”,p->data);//訪問(wèn)根結(jié)點(diǎn)

Preorder(p->Rchild);//遍歷右子樹(shù)

Preorder(p->Lchild);//遍歷左子樹(shù)

}}后序遍歷華電計(jì)算機(jī)系A(chǔ)BCDEFGJI例下圖是代表表達(dá)式a+b*(c-d)-e/f的二叉樹(shù)-+/a*efb-cd華電計(jì)算機(jī)系

a+b*c-d-e/f中序遍歷序列:

abcd-*+ef/-后序遍歷序列:

-+a*b-cd/ef先序遍歷序列:NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity三種遍歷方法的非遞歸算法用自然語(yǔ)言表達(dá)的算法(1)若p指向的結(jié)點(diǎn)非空，則將p指的結(jié)點(diǎn)的地址進(jìn)棧,然后,將p指向左子樹(shù)的根;(2)

若p指向的結(jié)點(diǎn)為空,則從堆棧中退出棧頂元素送p，訪問(wèn)該結(jié)點(diǎn)，然后,將p指向右子樹(shù)的根；重復(fù)上述過(guò)程,直到p為空,并且堆棧也為空。STACK[M]

---保存遍歷過(guò)程中鏈結(jié)點(diǎn)的地址top

---

棧頂指針,初始為0p

---

為遍歷過(guò)程中使用的指針變量，初始時(shí)指向根結(jié)點(diǎn)。(以中序遍歷為例)p

rchild(p)p

lchild(p)NorthChinaElectricPowerUniversity中序遍歷voidInorder(bitreptrp);{ifp==nullreturnelse{i=0;p=t;}repeatwhilep<>nil{i=i+1;s[i]=p;p=p->lchild;}ifi<>0{p=s[i];i=i-1;

printf(“%d”,p->data);p=p->rchild;}until(i==0)&&(p==null);}NorthChinaElectricPowerUniversity先序遍歷voidPreorder(bitreptrt){if(t==NULL)return;else{i=0;p=t;}do{while(p!=NULL){printf(“%d”,p->data);//訪問(wèn)根結(jié)點(diǎn)

if(p->Rchild!=NULL){i++;S[i]=p->Rchild;}p=p->Lchild;}if(i!=0){p=S[i];i--;}}while((i!=0)||(p!=NULL));}

NorthChinaElectricPowerUniversity后序遍歷voidPostorder(bitreptrt){if(t==NULL)return;else{p=t;i=0;}do{while(p!=NULL){i++;S[i]=p;p=p->Lchild;}while((i!=0)&&(p==NULL)){p=S[i];i--;if(p>0){i++;S[i]=-p;p=p->Rchild;}else{p=-p;

printf(“%d”,p->data);p=NULL;}}}while((i!=0)||(p!=NULL));}NorthChinaElectricPowerUniversity前序序列:A,B,D,E,J,C,F,I,G中序序列:

D,B,J,E,A,F,I,C,G后序序列:

D,J,E,B,I,F,G,C,A前序序列:

A,B,D,E,J,C,F,I,G中序序列:

D,B,J,E,A,F,I,C,G后序序列:

?！華電計(jì)算機(jī)系由遍歷序列恢復(fù)二叉樹(shù)NorthChinaElectricPowerUniversity前序序列:

A,B,D,E,

J,C,F,I,G中序序列:

D,B,J,E,A,F,I,C,GAF,I,C,GBDEJ前序序列:

A,

B,D,E,J,

C,F,I,G中序序列:

D,

B,J,E,

A,

F,I,C,GAF,I,C,GBJ,ED前序序列:

A,

B,D,E,J,C,F,I,G中序序列:

D,B,J,E,

A,F,I,C,GAD,B,J,EF,I,C,G華電計(jì)算機(jī)系NorthChinaElectricPowerUniversity后序序列:

D,J,E,B,I,F,G,C,A規(guī)律(前,中):

在前序序列中找根;

到中序序列中分左右。

規(guī)律(中,后):

在后序序列中找根;

到中序序列中分左右。華電計(jì)算機(jī)系A(chǔ)BCDEFGIJNorthChinaElectricPowerUniversity1.建立二叉樹(shù)voidCreateBtr(bitreptr&t);{

getchar(x);ifx==“#”t=nullelse{p=newnode;p->data=x;t=p;

CreateBtr(t->lchild);

CreateBtr(t->rchild);}}二叉樹(shù)遍歷算法的應(yīng)用示例ABECDF輸入序列為：ABC##D##EF###NorthChinaElectricPowerUniversity2.統(tǒng)計(jì)二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)BitNode(t)=0若t=null1若t->lchild=null&&t->rchild=nullBitNode(t->lchild)+BitNode(t->rchild)+1其他統(tǒng)計(jì)方法voidnumnode((bitreptrt,int&num){if(t!=NULL){if((t->Lchild==NULL)&&(t->Rchild==NULL))num++;//計(jì)數(shù)器加1else{node1=numnode(t->Lchild,num);node2=numnode(t->Rchild,num);

return(nodes1+nodes2+1);}}}

NorthChinaElectricPowerUniversity3.交換二叉樹(shù)中各結(jié)點(diǎn)的左右子樹(shù)voidSwap(bitreptrt){if(t!=Null){if(t->lchild

!=

Null)||(t->

rchild

!=

Null){p=t->

rchild;t->

rchild=t->

lchild;t->

lchild=p;}if(t->

lchild

!=

Null)Swap(t

->

lchild);if(t->

rchild

!=

Null)Swap(t

->

rchild);}}ABCDEF注意：這里不能用中序遍歷。ABCEDFACFBED4.在二叉樹(shù)中查詢(xún)給定結(jié)點(diǎn)x基本思想：

1）若二叉樹(shù)為空樹(shù)，則二叉樹(shù)不存在這個(gè)結(jié)點(diǎn)，返回False。否則，和根結(jié)點(diǎn)的元素進(jìn)行比較，若相等，則返回指向該結(jié)點(diǎn)的指針和函數(shù)值True，查找過(guò)程結(jié)束；2）否則在左子樹(shù)中查找，若找到，返回True；3）否則返回在右子樹(shù)中進(jìn)行查找的結(jié)果，因?yàn)樵谟易訕?shù)上查找的結(jié)果即為整個(gè)查找過(guò)程的結(jié)果。即若找到，則返回值為T(mén)rue，并且已經(jīng)得到指向該結(jié)點(diǎn)的指針，否則返回值為False。NorthChinaElectricPowerUniversitybool

Locate(bitreptrt,ElemTypex,bitreptr

p){//若二叉樹(shù)中存在和x相同的元素，則p指向該結(jié)點(diǎn)并返回True。

//否則p=null，返回False。

if(t=Null){p=Null;Return(False);}else{if(t->data=x){p:=t;Return(True);}else{if(Locate(t->Lchild,x,p)=True)Return(True);else

Return(Locate(t->Rchild,x,p));}}}NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity5.表達(dá)式的計(jì)算

采用的結(jié)點(diǎn)結(jié)構(gòu)如右圖所示：lchildrchilddatavalue

其中val域存放以該結(jié)點(diǎn)為根的子樹(shù)的值：-+/-*aeabcd表達(dá)式:(a-b)+(c*d)-(a/e)voidPostorder_val(bitreptr

t);{

if(t!=null){Postorder_val(t->lchild);

Postorder_val(t->rchild);caset->dataof‘+’:t->val:=t->lchild->val+t->rchild->val;…default:t->val:=t->data;}}NorthChinaElectricPowerUniversity

利用二叉鏈表中空的指針域指出結(jié)點(diǎn)在遍歷序列中的直接前驅(qū)和直接后繼;這些指向前驅(qū)和后繼的指針?lè)Q為線索,加了線索的二叉樹(shù)稱(chēng)為線索二叉樹(shù).利用鏈結(jié)點(diǎn)的空的左指針域存放該結(jié)點(diǎn)的直接前驅(qū)的地址,空的右指針域存放該結(jié)點(diǎn)直接后繼的地址;而非空的指針域仍然存放結(jié)點(diǎn)的左孩子或右孩子的地址.二叉線索樹(shù)的構(gòu)造

§6.5二叉線索樹(shù)NorthChinaElectricPowerUniversityNIL(a)先序NIL(b)中序NILNIL(c)后序線索樹(shù)示例ABDCEFGHABDCEFGHABDCEFGHNorthChinaElectricPowerUniversityltaglchilddatarchildrtag

1

表示

lchild(p)為指向直接前驅(qū)的線索ltag(p)=

0

表示

lchild(p)為指向左孩子的指針

1

表示

rchild(p)為指向直接后繼的線索rtag(p)=

0

表示

rchild(p)為指向右孩子的指針

指針與線索的區(qū)分方法之一:華電計(jì)算機(jī)系NorthChinaElectricPowerUniversity指針與線索的區(qū)分方法之二:

不改變鏈結(jié)點(diǎn)的構(gòu)造,而是在作為線索的地址前加一個(gè)負(fù)號(hào),即負(fù)地址表示線索,正地址表示指針.華電計(jì)算機(jī)系NorthChinaElectricPowerUniversityNILa

bcde

f

NIL中序線索樹(shù)示例-+/*-由于左圖中l(wèi)child(a)與rchild(f)是懸空的，為了不使線索斷開(kāi)，這里對(duì)于所有的線索樹(shù)將假定一個(gè)頭結(jié)點(diǎn)，其data域?yàn)榭栈蚺c其它結(jié)點(diǎn)的data域值不同.-+/a*efb-cd010000001100111100111111NorthChinaElectricPowerUniversity

(1).當(dāng)rtag(x)=1時(shí),rchild(x)指出的結(jié)點(diǎn)就是x的直接后繼結(jié)點(diǎn)。

(2).當(dāng)rtag(x)=0時(shí),沿著x的右子樹(shù)的根的左子樹(shù)方向往下找,直到某結(jié)點(diǎn)的lchild

域?yàn)榫€索時(shí),此結(jié)點(diǎn)就是x結(jié)點(diǎn)直接后繼結(jié)點(diǎn)。中序二叉線索樹(shù)二叉線索樹(shù)的利用

(3).當(dāng)ltag(x)=1時(shí),lchild(x)指出的結(jié)點(diǎn)就是x的直接前驅(qū)結(jié)點(diǎn)。

(4).當(dāng)ltag(x)=0時(shí),從x的左鏈沿右找下去，直到某結(jié)點(diǎn)的rlchild

域?yàn)榫€索時(shí),此結(jié)點(diǎn)就是x結(jié)點(diǎn)直接前驅(qū)結(jié)點(diǎn)。NorthChinaElectricPowerUniversity后序二叉線索樹(shù)

(1).當(dāng)rtag(x)=1時(shí),rchild(x)指出的結(jié)點(diǎn)就是x的直接后繼結(jié)點(diǎn)。

(2).當(dāng)rtag(x)=0時(shí),從x的雙親結(jié)點(diǎn)的右孩子沿著左鏈一直往下找,直到某結(jié)點(diǎn)的lchild

域?yàn)榫€索時(shí),然后再看此結(jié)點(diǎn)有無(wú)右孩子，若有，則再沿著右孩子走下去，如此遞歸進(jìn)行，直到一個(gè)無(wú)左、右孩子的結(jié)點(diǎn)便是x的后繼，若結(jié)點(diǎn)x的雙親沒(méi)有右孩子或右孩子就是結(jié)點(diǎn)本身，則此雙親結(jié)點(diǎn)便是x的直接后繼結(jié)點(diǎn)。

(3).當(dāng)ltag(x)=1時(shí),lchild(x)指出的結(jié)點(diǎn)就是x的直接前驅(qū)結(jié)點(diǎn)。

(4).當(dāng)ltag(x)=0時(shí),若x有右孩子，則x的右即為其前驅(qū)，若

x無(wú)右孩子，則必有左孩子，這個(gè)左孩子就是x的直接前驅(qū)結(jié)點(diǎn)。NorthChinaElectricPowerUniversity§6.6樹(shù)的遍歷由于樹(shù)種每個(gè)結(jié)點(diǎn)可以有兩棵以上的子樹(shù)，所以有兩種遍歷樹(shù)的方法：1.先序遍歷：先訪問(wèn)樹(shù)的根結(jié)點(diǎn)，然后依次先序遍歷樹(shù)的各棵子樹(shù)。2.后序遍歷：依次后序遍歷樹(shù)的根的各棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)。樹(shù)沒(méi)有中序遍歷，因?yàn)闃?shù)中每個(gè)結(jié)點(diǎn)的子樹(shù)的個(gè)數(shù)可以有多個(gè)，把根放在那兩個(gè)子樹(shù)之間是無(wú)法確定的，算法實(shí)現(xiàn)上不易統(tǒng)一。ABCED先序序列：ABCDE后序序列：BDCEANorthChinaElectricPowerUniversity森林的遍歷1.先序遍歷森林：

1）訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；

2）先序遍歷第一棵樹(shù)中根結(jié)點(diǎn)的子樹(shù)森林；

3）先序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成森林。2.中序遍歷森林

1）中序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)林；

2）訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)；

3）中序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的樹(shù)林。由樹(shù)和二叉樹(shù)的轉(zhuǎn)換規(guī)則可知：森林的先序和中序遍歷即為其對(duì)應(yīng)的二叉樹(shù)的先序和中序遍歷。ABCDEFGHIJ先序序列：ABCDEFGHIJ中序序列：BCDAFEHJIG§6.7哈夫曼樹(shù)及其應(yīng)用1）結(jié)點(diǎn)間的路徑長(zhǎng)度：樹(shù)中從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的分支數(shù)為此對(duì)結(jié)點(diǎn)間的路徑長(zhǎng)度；2）樹(shù)中結(jié)點(diǎn)的路徑長(zhǎng)度：根結(jié)點(diǎn)與該結(jié)點(diǎn)間的路徑長(zhǎng)度；3）樹(shù)的路徑長(zhǎng)度：從樹(shù)的根到樹(shù)中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和，簡(jiǎn)稱(chēng)PL。NorthChinaElectricPowerUniversity例：下圖為計(jì)算樹(shù)的路徑長(zhǎng)度的例子1234567a圖中兩棵樹(shù)的路徑長(zhǎng)度分別為：（a）PL=0+1+2+2+3+4+5=17（b）PL=0+1+1+2+2+2+2+3=131245673b8NorthChinaElectricPowerUniversity樹(shù)的帶權(quán)路徑長(zhǎng)度：考慮這樣一棵帶權(quán)的二叉樹(shù)，即給定一組實(shí)數(shù){w1,w2,…,wn}若使得二叉樹(shù)的每個(gè)葉子對(duì)應(yīng)有一個(gè)實(shí)數(shù)wk，則將這種二叉樹(shù)的權(quán)路徑長(zhǎng)度定義為WPL=

(k=1,…,n)WkLR，其中LR為從根到葉子結(jié)點(diǎn)Wk的路徑長(zhǎng)度。例如：給定一數(shù)組{10，5，2，4}，則可以構(gòu)造如下圖所示的若干棵二叉樹(shù)：NorthChinaElectricP