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

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

1.樹的定義：

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

1)有且僅有一個特定的稱為根的結(jié)點；

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

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

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

struct

TNode{intchild;

struct

TNode*next;}*TreeNode;typedef

Treenode

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

struct

TNode{

ElemTypedata;

intparent;}TreeNode;typedef

TreeNode

stalist[size];

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

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

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

2

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

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

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

則n0=n2+1

證明:

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

n=n0+n1+n2

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

B=n-1

--------(2)這些分支來自度于為1的結(jié)點與度為2結(jié)點,即

B=n1+2n2

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

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

log2n

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

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

若i>1,則編號為i的結(jié)點的雙親結(jié)點的編號為

i/2

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

(4)若編號為i的結(jié)點有左孩子，則左孩子結(jié)點的編號為2i;

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

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

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

I

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

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

lchild

與rchild

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

TYPE

nodeptr=

nodetype

nodetype=RECORDdata:datatype;

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

typedef

struct

btnode{

ElemTypedata;

struct

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

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

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

rchild

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

BT[1:2h-1]中,寫一算法，求二叉樹中葉結(jié)點的數(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++){}算法北航計算機系6樹與二叉樹之間的轉(zhuǎn)換NorthChinaElectricPowerUniversity1.在兄弟結(jié)點之間加一條連線；2.對每個結(jié)點，除去其最左的孩子之外，去掉該結(jié)點與其他孩子之間的連線；3.以樹的根結(jié)點為軸心，將整棵樹順時針旋轉(zhuǎn)45度。ABCDEFGHIJABCDEFGHIJABCDEFGHIJ森林與二叉樹之間的轉(zhuǎn)換NorthChinaElectricPowerUniversity1.將森林中各棵樹的根結(jié)點之間加一條連線；2.對每棵樹，用樹的二叉樹表示法相連，然后順時針旋轉(zhuǎn)45度。ABCDEGFHJIABEGCDFHIJNorthChinaElectricPowerUniversity§6.4二叉樹的遍歷及線索二叉樹常用的二叉樹的遍歷方法:

1.先序遍歷

2.中序遍歷

3.后序遍歷

4.按層次遍歷右子樹左子樹根華電計算機系

按照一定的順序(原則)對二叉樹中每一個結(jié)點都訪問一次(僅訪問一次),得到一個由該二叉樹的所有結(jié)點組成的序列,這一過程稱為二叉樹的遍歷.NorthChinaElectricPowerUniversity前序序列:ABDEJCFI原則:

若被遍歷的二叉樹非空,則

1.訪問根結(jié)點;

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

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

若被遍歷的二叉樹非空,則

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

2.訪問根結(jié)點;

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

若被遍歷的二叉樹非空,則

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

---保存遍歷過程中鏈結(jié)點的地址top

---

棧頂指針,初始為0p

---

為遍歷過程中使用的指針變量，初始時指向根結(jié)點。(以中序遍歷為例)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);//訪問根結(jié)點

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后序序列:

?！華電計算機系由遍歷序列恢復(fù)二叉樹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華電計算機系NorthChinaElectricPowerUniversity后序序列:

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

在前序序列中找根;

到中序序列中分左右。

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

在后序序列中找根;

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

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

CreateBtr(t->lchild);

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

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

NorthChinaElectricPowerUniversity3.交換二叉樹中各結(jié)點的左右子樹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.在二叉樹中查詢給定結(jié)點x基本思想：

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

Locate(bitreptrt,ElemTypex,bitreptr

p){//若二叉樹中存在和x相同的元素，則p指向該結(jié)點并返回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.表達式的計算

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

其中val域存放以該結(jié)點為根的子樹的值：-+/-*aeabcd表達式:(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é)點在遍歷序列中的直接前驅(qū)和直接后繼;這些指向前驅(qū)和后繼的指針稱為線索,加了線索的二叉樹稱為線索二叉樹.利用鏈結(jié)點的空的左指針域存放該結(jié)點的直接前驅(qū)的地址,空的右指針域存放該結(jié)點直接后繼的地址;而非空的指針域仍然存放結(jié)點的左孩子或右孩子的地址.二叉線索樹的構(gòu)造

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

1

表示

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

0

表示

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

1

表示

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

0

表示

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

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

不改變鏈結(jié)點的構(gòu)造,而是在作為線索的地址前加一個負號,即負地址表示線索,正地址表示指針.華電計算機系NorthChinaElectricPowerUniversityNILa

bcde

f

NIL中序線索樹示例-+/*-由于左圖中l(wèi)child(a)與rchild(f)是懸空的，為了不使線索斷開，這里對于所有的線索樹將假定一個頭結(jié)點，其data域為空或與其它結(jié)點的data域值不同.-+/a*efb-cd010000001100111100111111NorthChinaElectricPowerUniversity

(1).當rtag(x)=1時,rchild(x)指出的結(jié)點就是x的直接后繼結(jié)點。

(2).當rtag(x)=0時,沿著x的右子樹的根的左子樹方向往下找,直到某結(jié)點的lchild

域為線索時,此結(jié)點就是x結(jié)點直接后繼結(jié)點。中序二叉線索樹二叉線索樹的利用

(3).當ltag(x)=1時,lchild(x)指出的結(jié)點就是x的直接前驅(qū)結(jié)點。

(4).當ltag(x)=0時,從x的左鏈沿右找下去，直到某結(jié)點的rlchild

域為線索時,此結(jié)點就是x結(jié)點直接前驅(qū)結(jié)點。NorthChinaElectricPowerUniversity后序二叉線索樹

(1).當rtag(x)=1時,rchild(x)指出的結(jié)點就是x的直接后繼結(jié)點。

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

域為線索時,然后再看此結(jié)點有無右孩子，若有，則再沿著右孩子走下去，如此遞歸進行，直到一個無左、右孩子的結(jié)點便是x的后繼，若結(jié)點x的雙親沒有右孩子或右孩子就是結(jié)點本身，則此雙親結(jié)點便是x的直接后繼結(jié)點。

(3).當ltag(x)=1時,lchild(x)指出的結(jié)點就是x的直接前驅(qū)結(jié)點。

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

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

1）訪問森林中第一棵樹的根結(jié)點；

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

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

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

2）訪問第一棵樹的根結(jié)點；

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

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