5選講樹和二叉樹解析

樹和二叉樹

預習檢查什么是二叉樹樹的遍歷有哪幾種方式樹有那些應用2024/11/73

本章目標了解樹的定義和基本術語了解二叉樹的定義、性質、和存儲結構掌握二叉樹的遍歷本章結構樹的邏輯結構和存儲結構樹和二叉樹二叉樹遍歷二叉樹2024/11/75

5.1.1樹型結構實例

1．家族樹

5-1

樹的邏輯結構和存儲結構

圖5-1家族樹

2024/11/762．書的目錄結構

圖5-2書的目錄

5-1書的目錄結構2024/11/77

5.1.2

樹的定義

1．樹的定義樹(Tree)是n(n≥0)個結點的有限集(記為T)，T為空時稱為空樹，否則它滿足以下兩個條件：(1)有且僅有一個結點沒有前驅，稱該結點為根結點(Root)；(2)除根結點以外，其余結點可分為m(m≥0)個互不相交的有限集合T0，Tl，…，Tm-1。其中每個集合又構成一棵樹，樹T0，Tl，…，Tm-1被稱為根結點的子樹(Subree)。每棵子樹的根結點有且僅有一個直接前驅，但可以有0個或多個后繼。樹的邏輯結構表示數據之間的關系是一對多，或者多對一的關系。它的結構特點具有明顯的層次關系，是一種十分重要的非線性的數據結構。

5-1

樹的邏輯結構和存儲結構

2024/11/78圖5-3樹的示例

圖5-3(a)是一棵只有一個根結點的樹；圖5-3(b)是一棵有12個結點的樹，即T={A，B，C，…，K，L}。A是棵根，除根結點A之外，其余的11個結點分為三個互不相交的集合。T1，T2和T3是根A的三棵子樹，且本身又都是一棵樹。所以樹的定義是遞歸的。

2024/11/792．樹的基本術語樹的結點包含一個數據元素及若干指向其子樹的分支。1.樹的結點:包含一個DE和指向其子樹的所有分支;2.結點的度:一個結點擁有的子樹個數,度為零的結點稱為葉結點;3.樹的度:樹中所有結點的度的最大值Max(D(I))

含義:樹中最大分支數為樹的度;4.結點的層次及樹的深度:根為第一層,根的孩子為第二層,若某結點為第k層,則其孩子為k+1層.樹中結點的最大層次稱為樹的深度或高度5.森林:是m(m>=0)棵互不相的樹的集合森林與樹概念相近,相互很容易轉換.6.有序樹、無序樹如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無序樹。2024/11/7107.森林:是m（m≥0）棵互不相交的樹的集合。在樹結構中，結點之間的關系又可以用家族關系描述，定義如下：8.孩子、雙親:結點子樹的根稱為這個結點的孩子，而這個結點又被稱為孩子的雙親。9.子孫:以某結點為根的子樹中的所有結點都被稱為是該結點的子孫。10.祖先:從根結點到該結點路徑上的所有結點。11.兄弟:同一個雙親的孩子之間互為兄弟。12.堂兄弟:雙親在同一層的結點互為堂兄弟。

2024/11/7113.

樹的基本運算樹的基本運算主要有：

⒈初始化操作INITIATE(T)：創(chuàng)建一棵空樹。⒉求根函數ROOT(T)：求樹T的根；ROOT(X)：求結點x所在樹的根。⒊求雙親函數PARENT(T,x)：在樹T中求x的雙親。⒋求第i個孩子函數CHILD(T,x,i)：在樹T中求結點x的第i個孩子。⒌建樹函數CRT-TREE(x,F)：建立以結點x為根，森林F為子樹的樹。

6.遍歷樹操作TRAVERSE(T)：按順序訪問樹T中各個結點。

2024/11/7121．樹的遍歷所謂樹的遍歷，就是按照某種順序依次訪問樹中各個結點，并使得每個結點只被訪問一次。也就是把非線性結構的樹結點變成線性序列的一種方式

。樹的遍歷可以按深度優(yōu)先遍歷，也可以按照廣度優(yōu)先（按層次）遍歷。深度優(yōu)先遍歷通常有兩種方式：前序遍歷和后序遍歷。

(1)前序遍歷的遞歸定義：

若樹T非空，則：訪問根結點R；按照從左到右的順序依次前序遍歷根結點R的各子樹T1，T2，…，Tk。5-1-5

樹的遍歷2024/11/713

(2)后序遍歷的遞歸定義：若樹T非空，則：按照從左到右的順序依次后序遍歷根T的各子樹Tl，T2，…，Tk；訪問根結點R。

(3)廣度優(yōu)先（按層）遍歷廣度優(yōu)先（按層次）遍歷定義為：先訪問第一層結點（即樹根結點），再從左至右訪問第二層結點，依次按層訪問……，直到樹中結點全部被訪問為止。對圖6-6(a)中的樹進行按層次遍歷得到樹的廣度優(yōu)先遍歷序列為：ABCDEFG。

說明：

①前序遍歷一棵樹恰好等價于前序遍歷該樹所對應的二叉樹。（6.2節(jié)將介紹二叉樹）②后序遍歷樹恰好等價于中序遍歷該樹所對應的二叉樹。

2024/11/714樹的先序遍歷算法描述如下：voidPreorder(Btree*root)//先根遍歷k叉樹{if(root!=NULL){printf(“%c\n”,root->data);//訪問根結點

for(i=0;i<k;i++)preorder(root->t[i]);//遞歸前序遍歷每一個子結點

}}

2024/11/715

5.2.1二叉樹的定義與性質

二叉樹(BinaryTree)是另一種重要的樹型結構。是度為2的有序樹，它的特點是每個結點至多有兩棵子樹。和樹結構的定義類似，二叉樹的定義也可以用遞歸形式給出。1．二叉樹的遞歸定義二叉樹(BinaryTree)是n(n≥0)個結點的有限集。它或者是空集(n=0)，或者同時滿足以下兩個條件：(1)有且僅有一個根結點；(2)其余的結點分成兩棵互不相交的左子樹和右子樹。

5-2

二叉樹2024/11/716

二叉樹與樹有區(qū)別：樹至少應有一個結點，而二叉樹可以為空；樹的子樹沒有順序，但如果二叉樹的根結點只有一棵子樹，必須明確區(qū)分它是左子樹還是右子樹，因為兩者將構成不同形態(tài)的二叉樹。因此，二叉樹不是樹的特例。它們是兩種不同的數據結構。二叉樹有5種基本形態(tài)：圖5-7二叉樹的五種基本形態(tài)

(a)空二叉樹(b)只有根結點的二叉樹(c)右子樹為空的二叉樹

(d)左子樹為空的二叉樹(e)左右子樹均不為空的二叉樹

2024/11/717兩種特殊形態(tài)的二叉樹：滿二叉樹和完全二叉樹。

(1)滿二叉樹(FullBinaryTree)

深度為k，且有2k-1個結點的二叉樹。特點：（1）每一層上結點數都達到最大（2）度為1的結點n1=0，樹葉都在最下一層上。

結點層序編號方法：從根結點起從上到下逐層（層內從左到右）對二叉樹的結點進行連續(xù)編號。1237654K=3n=23-1=7滿二叉樹2024/11/718

(2)完全二叉樹(CompleteBinaryTree)

深度為k，結點數為n的二叉樹，當且僅當每個結點的編號都與相同深度的滿二叉樹中從1到n的結點一一對應時，稱為完全二叉樹。圖5-8完全二叉樹完全二叉樹的特點：（1）每個結點i的左子樹的深度Lhi-其結點i的右子樹的深度Rhi等于0或1，即葉結點只可能出現(xiàn)在層次最大或次最大的兩層上。（2）完全二叉樹結點數n滿足2k-1-1＜n≤2k-1（3）滿二叉樹一定是完全二叉樹，反之不成立。452132024/11/7191324653241LH1=3RH1=1LH1-RH1=2

非完全二叉樹非完全二叉樹LH2=0RH2=1LH2-RH2=0-1=-12024/11/7202．二叉樹的性質

性質1在二叉樹的第i層上至多有2i-1個結點(i≥1)。性質2深度為k的二叉樹至多有2k-1個結點(k≥1)。

（深度一定，二叉樹的最大結點數也確定）

性質3

二叉樹中,終端結點數n0與度為2的結點數n2有如下關系:n0=n2+1性質4

結點數為n的完全二叉樹，其深度為

log2n

+l

性質5

在按層序編號的n個結點的完全二叉樹中，任意一結點i(1≤i≤n)有：⑴i=1時，結點i是樹的根；否則，結點i的雙親為結點

i/2

(i>1)

。⑵2i＞n時，結點i無左孩子，為葉結點；否則，結點i的左孩子為結點2i。⑶2i+1＞n時，結點i無右孩子；否則，結點i的右孩子為結點2i+1。2024/11/721鏈式存儲結構（二叉鏈表）設計不同的結點結構，可以構成不同的鏈式存儲結構。常用的有：二叉鏈表三叉鏈表線索鏈表用空鏈域存放指向前驅或后繼的線索2024/11/722

由于二叉樹每個結點至多只有2個孩子，分別為左孩子和右孩子。因此可以把每個結點分成三個域：一個域存放結點本身的信息，另外兩個是指針域，分別存放左、右孩子的地址。每個結點的結構表示為：

其中左鏈域lchild為指向左孩子的指針，右鏈域rchild為指向右孩子的指針，數據域data表示結點的值。若某結點沒有左孩子或右孩子，其相應的鏈域為空指針。

對應的結構類型定義如下：typedefstructnode{ElemTypedata;structnode*lchild;structnode*rchild;}BTree,*tree;其中，tree是指向根結點的指針。

2024/11/723二叉鏈表的結點結構

lchilddatarchildD

二叉樹CEBAACBDE∧∧∧∧∧∧二叉鏈表說明：●一個二叉鏈表由根指針root唯一確定。若二叉樹為空，則root=NULL；若結點的某個孩子不存在，則相應的指針為空?！?/p>

具有n個結點的二叉鏈表中，共有2n個指針域。其中只有n-1個用來指示結點的左、右孩子，其余的n+1個指針域為空。

2024/11/724lchilddataparentrchildD

二叉樹CEBAACBDE∧∧∧∧∧∧∧三叉鏈表3．帶雙親指針的二叉鏈表由于經常要在二叉樹中尋找某結點的雙親時，可在每個結點上再加一個指向其雙親的指針parent，形成一個帶雙親指針的二叉鏈表。就是三叉鏈表。三叉鏈表的結點結構性質6

含有n個結點的二叉鏈表中，有n+1個空鏈域。二叉樹存儲方法的選擇，主要依賴于所要實施的各種運算的頻度。2024/11/7251．二叉樹的基本運算（1）Inittree(&T)功能：初始化操作(建立一棵空的二叉樹)。（2）Root(T)功能：求二叉樹的根。（3）Parent(T,x)功能：求二叉樹T中值為x的結點的雙親。（4）Lchild(T,x)功能：求結點的左孩子。（5）Rchild(T,x)功能：求結點的右孩子。（6）Traverse(T)功能：遍歷或訪問二叉樹T。（7）creatree(&T)功能：創(chuàng)建二叉樹T5-2-3

二叉樹的基本運算節(jié)實現(xiàn)2024/11/726

2．二叉樹部分運算的算法描述(1)創(chuàng)建二叉樹creatree(&root,str)：

功能：創(chuàng)建二叉樹T。算法描述如下：voidcreatree(BTree**b,char*str){BTree*stack[MAXSIZE],p=NULL;inttop=-1,k,j=0;charch;*b=NULL;ch=str[j];while(ch!=’\0’){switch(ch){case’(’：top++;stack[top]=p;k=1,break;//為左結點

case’)’：top--;break;case’,’：k=2;break;//為右結點

default：p=(BTree*)malloc(sizeof(BTree));p->data=ch;p->lchild=p->rchild=NULL;

2024/11/727

p->data=ch;p->lchild=p->rchild=NULL;if(*b==NULL)//為根結點*b=p;else{switch(k){case1：stack[top]->lchild=p;break;case2：stack[top]->rchild=p;break;}}}j++;ch=str[j];}}

2024/11/728(2)查找給定的結點find(root，x)(3)找左孩子結點lchild(p)或右孩子結點rchild(p)(4)輸出二叉樹disptree(root)2024/11/7295.3.1遍歷二叉樹

在二叉樹的一些應用中，常常要求在樹中查找具有某種特征的結點，或者對樹中全部結點逐一進行某種處理。這就引入了遍歷二叉樹的問題，即如何按某條搜索路徑訪問樹中的每一個結點，使得每一個結點僅切僅被訪問一次。遍歷二叉樹：指按一定的規(guī)律對二叉樹的每個結點，訪問且僅訪問一次的處理過程。

遍歷對線性結構是容易解決的。而二叉樹是非線性的，因而需要尋找一種規(guī)律，使二叉樹上的結點能排列在一個線性隊列上，從而便于遍歷。

5-3

遍歷二叉樹和線索二叉樹

2024/11/730

訪問是一種抽象操作，是對結點的某種處理，例如可以是求結點的度、或層次、打印結點的信息，或做其他任何工作。一次遍歷后，使樹中結點的非線性排列，按訪問的先后順序變?yōu)槟撤N線性排列。遍歷的次序：假如以L、D、R分別表示遍歷左子樹、遍歷根結點和遍歷右子樹，遍歷整個二叉樹則有DLR、LDR、LRD、DRL、RDL、RLD六種遍歷方案。若規(guī)定先左后右，則只有前三種情況，分別規(guī)定為：

DLR——先（根）序遍歷，

LDR——中（根）序遍歷，

LRD——后（根）序遍歷。

1．遍歷方案

LDR中序遍歷；LRD后序遍歷；DLR先序遍歷2024/11/7311）中序遍歷二叉樹算法思想:

若二叉樹非空，則：1）中序遍歷左子樹2）訪問根結點3）中序遍歷右子樹算法描述:voidInorder(BiTreebt){//bt為根結點指針

if(bt){//根非空

Inorder(bt->lchild);

visit(bt->data)；Inorder(bt->rchild);}}2）后序遍歷二叉樹算法思想:

若二叉樹非空，則：1）后序遍歷左子樹2）后序遍歷右子樹3）訪問根結點算法描述:voidPostorder(BiTreebt){//bt為根結點指針

if(bt){Postorder(bt->lchild);Postorder(bt->rchild);

visit(bt->data)；

}}2024/11/7323）先序遍歷二叉樹算法思想:

若二叉樹非空，則：1）訪問根結點2）先序遍歷左子樹3）先序遍歷右子樹算法描述:voidPreorder(BiTreebt){//bt為根結點指針

if(bt){//根非空

visit(bt->data)；Preorder(bt->lchild);Preorder(bt->rchild);}}例：表達式a+b×(c-d)-e/facdef－b×＋－+遍歷結果:中序:a+b×c-d-e/f后序:abcd-×+ef/-先序:-+a×b-cd/ef2024/11/733（1）先序遍歷的遞歸算法如下（假定結點的元素值為字符型）：#include"stdio.h"typedefcharElemType;typedefstructnode//定義鏈表結構{ElemTypedata;//定義結點值structnode*lchild;//定義左子結點指針structnode*rchild;//定義右子結點指針}BTree;preorder(BTree*root)//前序遍歷{if(root!=NULL)//如果不是空結點{printf(“%c\n”,root->data);//輸出當前結點值

preorder(root->lchild);//遞歸前序遍歷左子結點

preorder(root->rchild);//遞歸前序遍歷右子結點}

return;//結束

}

2．遍歷算法2024/11/734voidinorder(BTree*root)//中序遍歷{if(root!=NULL)//如果不是空結點{inorder(root->lchild);//遞歸中序遍歷左子結點printf(“%c\n”,root->data);//輸出當前結點值inorder(root->rchild);//遞歸中序遍歷右子結點}}

(3)后序遍歷的算法實現(xiàn)

voidpostorder(BTree*root)//后序遍歷{if(root!=NULL)//如果不是空結點{postorder(root->lchild);//遞歸后序遍歷左子結點postorder(root->rchild);//遞歸后序遍歷右子結點printf(“%c\n”,root->data);//輸出當前結點值}}（2）中序遍歷的遞歸算法如下（假定結點的元素值為字符型）：2024/11/735voidinorder(BiTreebt){InitStack(s)；Push(s,bt)；while(!StackEmpty(s)){

while(GetTop(s)){Push(s,GetTop(s)->lchild)；

p=POP(s)；if(!StackEmpty(s)){visit(GetTop(s)->data)；p=Pop(s)；Push(s,p->rchild);}}}}中序遍歷非遞歸算法,s為存儲二叉樹結點指針棧：操作過程：根結點先進棧，左結點緊跟根后面進棧,右結點在根出棧后入棧；

每個結點都要進一次和出一次棧，并且總是訪問棧頂元素，因此，算法正確，時間復雜度為O(n)。2024/11/736通過上述三種不同的遍歷方式得到三種不同的線性序列，它們的共同的特點是有且僅有一個開始結點和一個終端結點，其余各結點都有且僅有一個前驅結點和一個后繼結點。從二叉樹的遍歷定義可知，三種遍歷算法的不同之處僅在于訪問根結點和遍歷左右子樹的先后關系。如果在算法中隱去和遞歸無關的語句printf()，則三種遍歷算法是完全相同的。遍歷二叉樹的算法中的基本操作是訪問結點，顯然，不論按那種方式進行遍歷，對含