5選講樹和二叉樹解析

樹和二叉樹

預(yù)習(xí)檢查什么是二叉樹樹的遍歷有哪幾種方式樹有那些應(yīng)用2024/11/73

本章目標(biāo)了解樹的定義和基本術(shù)語(yǔ)了解二叉樹的定義、性質(zhì)、和存儲(chǔ)結(jié)構(gòu)掌握二叉樹的遍歷本章結(jié)構(gòu)樹的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)樹和二叉樹二叉樹遍歷二叉樹2024/11/75

5.1.1樹型結(jié)構(gòu)實(shí)例

1．家族樹

5-1

樹的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)

圖5-1家族樹

2024/11/762．書的目錄結(jié)構(gòu)

圖5-2書的目錄

5-1書的目錄結(jié)構(gòu)2024/11/77

5.1.2

樹的定義

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

5-1

樹的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)

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

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

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

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

2024/11/7113.

樹的基本運(yùn)算樹的基本運(yùn)算主要有：

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

6.遍歷樹操作TRAVERSE(T)：按順序訪問樹T中各個(gè)結(jié)點(diǎn)。

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

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

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

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

樹的遍歷2024/11/713

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

(3)廣度優(yōu)先（按層）遍歷廣度優(yōu)先（按層次）遍歷定義為：先訪問第一層結(jié)點(diǎn)（即樹根結(jié)點(diǎn)），再?gòu)淖笾劣以L問第二層結(jié)點(diǎn)，依次按層訪問……，直到樹中結(jié)點(diǎn)全部被訪問為止。對(duì)圖6-6(a)中的樹進(jìn)行按層次遍歷得到樹的廣度優(yōu)先遍歷序列為：ABCDEFG。

說明：

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

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

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

}}

2024/11/715

5.2.1二叉樹的定義與性質(zhì)

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

5-2

二叉樹2024/11/716

二叉樹與樹有區(qū)別：樹至少應(yīng)有一個(gè)結(jié)點(diǎn)，而二叉樹可以為空；樹的子樹沒有順序，但如果二叉樹的根結(jié)點(diǎn)只有一棵子樹，必須明確區(qū)分它是左子樹還是右子樹，因?yàn)閮烧邔?gòu)成不同形態(tài)的二叉樹。因此，二叉樹不是樹的特例。它們是兩種不同的數(shù)據(jù)結(jié)構(gòu)。二叉樹有5種基本形態(tài)：圖5-7二叉樹的五種基本形態(tài)

(a)空二叉樹(b)只有根結(jié)點(diǎn)的二叉樹(c)右子樹為空的二叉樹

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

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

(1)滿二叉樹(FullBinaryTree)

深度為k，且有2k-1個(gè)結(jié)點(diǎn)的二叉樹。特點(diǎn)：（1）每一層上結(jié)點(diǎn)數(shù)都達(dá)到最大（2）度為1的結(jié)點(diǎn)n1=0，樹葉都在最下一層上。

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

(2)完全二叉樹(CompleteBinaryTree)

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

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

性質(zhì)1在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i≥1)。性質(zhì)2深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)(k≥1)。

（深度一定，二叉樹的最大結(jié)點(diǎn)數(shù)也確定）

性質(zhì)3

二叉樹中,終端結(jié)點(diǎn)數(shù)n0與度為2的結(jié)點(diǎn)數(shù)n2有如下關(guān)系:n0=n2+1性質(zhì)4

結(jié)點(diǎn)數(shù)為n的完全二叉樹，其深度為

log2n

+l

性質(zhì)5

在按層序編號(hào)的n個(gè)結(jié)點(diǎn)的完全二叉樹中，任意一結(jié)點(diǎn)i(1≤i≤n)有：⑴i=1時(shí)，結(jié)點(diǎn)i是樹的根；否則，結(jié)點(diǎn)i的雙親為結(jié)點(diǎn)

i/2

(i>1)

。⑵2i＞n時(shí)，結(jié)點(diǎn)i無左孩子，為葉結(jié)點(diǎn)；否則，結(jié)點(diǎn)i的左孩子為結(jié)點(diǎn)2i。⑶2i+1＞n時(shí)，結(jié)點(diǎn)i無右孩子；否則，結(jié)點(diǎn)i的右孩子為結(jié)點(diǎn)2i+1。2024/11/721鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（二叉鏈表）設(shè)計(jì)不同的結(jié)點(diǎn)結(jié)構(gòu)，可以構(gòu)成不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。常用的有：二叉鏈表三叉鏈表線索鏈表用空鏈域存放指向前驅(qū)或后繼的線索2024/11/722

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

其中左鏈域lchild為指向左孩子的指針，右鏈域rchild為指向右孩子的指針，數(shù)據(jù)域data表示結(jié)點(diǎn)的值。若某結(jié)點(diǎn)沒有左孩子或右孩子，其相應(yīng)的鏈域?yàn)榭罩羔槨?/p>

對(duì)應(yīng)的結(jié)構(gòu)類型定義如下：typedefstructnode{ElemTypedata;structnode*lchild;structnode*rchild;}BTree,*tree;其中，tree是指向根結(jié)點(diǎn)的指針。

2024/11/723二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)

lchilddatarchildD

二叉樹CEBAACBDE∧∧∧∧∧∧二叉鏈表說明：●一個(gè)二叉鏈表由根指針root唯一確定。若二叉樹為空，則root=NULL；若結(jié)點(diǎn)的某個(gè)孩子不存在，則相應(yīng)的指針為空?！?/p>

具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，共有2n個(gè)指針域。其中只有n-1個(gè)用來指示結(jié)點(diǎn)的左、右孩子，其余的n+1個(gè)指針域?yàn)榭铡?/p>

2024/11/724lchilddataparentrchildD

二叉樹CEBAACBDE∧∧∧∧∧∧∧三叉鏈表3．帶雙親指針的二叉鏈表由于經(jīng)常要在二叉樹中尋找某結(jié)點(diǎn)的雙親時(shí)，可在每個(gè)結(jié)點(diǎn)上再加一個(gè)指向其雙親的指針parent，形成一個(gè)帶雙親指針的二叉鏈表。就是三叉鏈表。三叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)性質(zhì)6

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

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

2．二叉樹部分運(yùn)算的算法描述(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;//為左結(jié)點(diǎn)

case’)’：top--;break;case’,’：k=2;break;//為右結(jié)點(diǎn)

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)//為根結(jié)點(diǎn)*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)查找給定的結(jié)點(diǎn)find(root，x)(3)找左孩子結(jié)點(diǎn)lchild(p)或右孩子結(jié)點(diǎn)rchild(p)(4)輸出二叉樹disptree(root)2024/11/7295.3.1遍歷二叉樹

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

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

5-3

遍歷二叉樹和線索二叉樹

2024/11/730

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

DLR——先（根）序遍歷，

LDR——中（根）序遍歷，

LRD——后（根）序遍歷。

1．遍歷方案

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

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

if(bt){//根非空

Inorder(bt->lchild);

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

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

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

visit(bt->data)；

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

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

if(bt){//根非空

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

preorder(root->lchild);//遞歸前序遍歷左子結(jié)點(diǎn)

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

return;//結(jié)束

}

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

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

voidpostorder(BTree*root)//后序遍歷{if(root!=NULL)//如果不是空結(jié)點(diǎn){postorder(root->lchild);//遞歸后序遍歷左子結(jié)點(diǎn)postorder(root->rchild);//遞歸后序遍歷右子結(jié)點(diǎn)printf(“%c\n”,root->data);//輸出當(dāng)前結(jié)點(diǎn)值}}（2）中序遍歷的遞歸算法如下（假定結(jié)點(diǎn)的元素值為字符型）：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為存儲(chǔ)二叉樹結(jié)點(diǎn)指針棧：操作過程：根結(jié)點(diǎn)先進(jìn)棧，左結(jié)點(diǎn)緊跟根后面進(jìn)棧,右結(jié)點(diǎn)在根出棧后入棧；

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