數(shù)據(jù)結(jié)構(gòu)課件版

6.1樹的定義與基本術(shù)語樹是遞歸結(jié)構(gòu)，樹的定義是遞歸定義。樹(Tree)是n個結(jié)點的有限集合，在任意一棵非空樹中：有且僅有一個稱為根(Root)的結(jié)點。其余結(jié)點可分為若干個互不相交的集合，且這些集合中的每一集合本身又是一棵樹，稱為根的子樹(SubTree)。AB

C

DG

H

I

JE

F第2

頁6.1樹的定義與基本術(shù)語例：右面的圖是一棵樹T。T

={

A，B，C，D，E，F(xiàn)，G，H，I，J

}A是根，其余結(jié)點可以劃分為3個互不相交的集合：T1={

B,E,F

} T2={

C,G

} T3={

D,H,I,J

}這些集合中的每一集合本身又都是一棵樹，它們是根A

的子樹。對于T1，B是根，其余結(jié)點可以劃分為兩個互不相交的集合：T11={E} T12={F} T11，T12是B的子樹。JABC

DG

H

IE

F第3

頁6.1樹的定義與基本術(shù)語除根外，其余結(jié)點都有且僅一個前趨；樹的結(jié)點，可以有零個或多個后繼；除根之外的其它結(jié)點，都存在唯一一條從根到該結(jié)點的路徑；

5）樹是一種分支結(jié)構(gòu)（除了一個稱為根的結(jié)點之外）每個元素都有且僅有一個直接前趨，有且僅有零個或多個直接后繼。1）樹中只有根結(jié)點沒有前趨；A從邏輯結(jié)構(gòu)看:B

CDG

H

I

JE

F第4

頁6.1樹的定義與基本術(shù)語樹的應(yīng)用家族樹第5

頁血統(tǒng)樹(二叉樹)6.1樹的定義與基本術(shù)語樹的應(yīng)用常用的數(shù)據(jù)組織形式——計算機(jī)的文件系統(tǒng)。不論是DOS文件系統(tǒng)還是window文件系統(tǒng)，所有的文件都是用樹的形式進(jìn)行組織。C文件夾1

…

文件夾n 文件1…文件2文件夾2

1…

文件夾22

文件21

…

文件22第6

頁6.1樹的定義與基本術(shù)語樹的應(yīng)用DNS

Name

Space.“.”…...comcn

eduedutshuacspkueebitss中國教育和科研網(wǎng)北理校園網(wǎng)第7

頁6.1樹的定義與基本術(shù)語樹的表示圖示表示二元組表示文氏圖表示廣義表表示凹入表示法（類似書的目錄）ACBDG

H

I

JFE第8

頁樹的定義與基本術(shù)語樹的表示2）二元組表示D

={

A，B，C，D，E，F(xiàn)，G，H，I，J

}

R

=

{

<A,B>,

<A,C>,

<A,D>,

<B,E>,

<B,F>,<C,G>,

<D,H>,

<D,I>,

<D,J>

}ACBDG

H

I

JFE第9

頁樹的定義與基本術(shù)語樹的表示3）文氏圖表示A

BCEGD

HIJ

MF

KLABCDEF

G

H

I

JMK

L第10

頁樹的定義與基本術(shù)語樹的表示4）廣義表表示假設(shè)樹的根為root，子樹為T1,T2,…,Tn，與該樹對應(yīng)的廣義表為L，則：L=(原子(子表1,子表2,…,子表n))，其中原子對應(yīng)root，子表i(1<i<=n)對應(yīng)Ti。(A(B(E,F),C,

D))ABCDE

FT1T2樹根

T3第11

頁樹的定義與基本術(shù)語樹的表示5）凹入表示ABCDEF

GHI

JMK

LABEFKLCGDHIJM第12

頁6.1樹的定義與基本術(shù)語結(jié)點的度:葉子結(jié)點:分支結(jié)點:結(jié)點:

數(shù)據(jù)元素+若干指向子樹的分支分支的個數(shù)樹的度:

樹中所有結(jié)點的度的最大值度為零的結(jié)點度大于零的結(jié)點DHIJM第13

頁6.1樹的定義與基本術(shù)語孩子結(jié)點、雙親結(jié)點、兄弟結(jié)點、堂兄弟結(jié)點祖先結(jié)點、子孫結(jié)點結(jié)點的層次:(從根到結(jié)點的)路徑：由根到該結(jié)點所經(jīng)分支和結(jié)點構(gòu)成假設(shè)根結(jié)點的層次為1,第l層的結(jié)點的子樹根結(jié)點的層次為l+1樹的深度：樹中葉子結(jié)點所在的最大層次ABCDEF

GHI

JMK

L第14

頁6.1樹的定義與基本術(shù)語森林：是m（m≥0）棵互不相交的樹的集合。ArootBEK

LC

DF

G

H

I

JMF任何一棵非空樹是一個二元組Tree

=

（root，F(xiàn)）其中：root

稱為根結(jié)點，F(xiàn)

稱為子樹森林。有序樹：子樹之間存在明確的次序關(guān)系的樹。無序樹：子樹之間沒有順序要求。第15

頁6.1樹的定義與基本術(shù)語數(shù)據(jù)對象DD是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R若D為空集，則稱為空樹。否則：D中存在唯一的稱為根的數(shù)據(jù)元素root；當(dāng)n>1時，其余結(jié)點可分為m(m>0)

個互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹，稱為根

root的子樹。第16

頁6.1樹的定義與基本術(shù)語第17

頁樹的基本操作InitTree(&T);構(gòu)造空樹T。DestroyTree(&T);銷毀樹T。CreateTree(&T,definition);按definition構(gòu)造樹T。ClearTree(&T);將樹T清空。TreeEmpty

(

T

);若樹T為空，返回TURE，否則返回FALSE。TreeDepth(T);返回樹T的深度。樹的定義與基本術(shù)語樹的基本操作Root

(

T

);返回T的根結(jié)點。Value

(

T,

&cur_e

);返回T樹中cur_e結(jié)點的值。Assign

(

T,

cur_e,

value

);將T樹中結(jié)點cur_e的值賦值為value。Parent

(

T,

cur_e

);返回T樹cur_e結(jié)點的雙親。LeftChild

(

T,

cur_e

);返回T樹cur_e結(jié)點的最左孩子。第18

頁6.1樹的定義與基本術(shù)語第19

頁樹的基本操作RightSibling(T,cur_e);返回T樹cur_e結(jié)點的右兄弟。InsertChild

(

&T,

&p,

i,

c

);將c插入到樹T中p所指向的第i棵子樹中。DeleteChild

(

&T,

&p,

i

);刪除樹T中p所指向的第i棵子樹。TraverseTree

(

T,

Visit(

)

);按某種次序?qū)樹的每個結(jié)點調(diào)用函數(shù)

Visit()一次且至多一次。也稱為按照某種次序?qū)溥M(jìn)行遍歷。6.1樹的定義與基本術(shù)語第20

頁線性結(jié)構(gòu)第一個數(shù)據(jù)元素

(無前驅(qū))最后一個數(shù)據(jù)元素(無后繼)其它數(shù)據(jù)元素

(一個前驅(qū)、一個后繼)樹型結(jié)構(gòu)根結(jié)點(無前驅(qū))多個葉子結(jié)點

(無后繼)其它數(shù)據(jù)元素

(一個前驅(qū)、多個后繼)6.2二叉樹第21

頁定義一棵二叉樹是結(jié)點的一個有限集合，該集合或者為空，或者是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。形式定義數(shù)據(jù)關(guān)系R滿足：若D＝Φ，則R＝Φ，稱為是空二叉樹。若D≠Φ，則R＝{H

}，H是如下二元關(guān)系：在D中存在惟一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；若D-{root}≠Φ，則存在D-{root}＝{Dl,Dr}，且Dl∩Dr=Φ。6.2二叉樹定義一棵二叉樹是結(jié)點的一個有限集合，該集合或者為空，或者是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。ABCDEFGHK根結(jié)點左子樹右子樹第22

頁6.2二叉樹NN第23

頁NN說明：1）二叉樹中每個結(jié)點最多有兩棵子樹；二叉樹每個結(jié)點度小于等于2；2）左、右子樹不能顛倒——有序樹。二叉樹的五種基本形態(tài)空樹只有根結(jié)點L

R只有左子樹

只有右子樹L

R左右子樹均非空6.2二叉樹二叉樹AGEDBCF(a)

(b)(a)、(b)是不同的二叉樹(a)的左子樹有四個結(jié)點，(b)的左子樹有兩個結(jié)點AFGEDCB第24

頁6.2二叉樹性質(zhì)1：在二叉樹的第i

層上至多有2i-1

個結(jié)點(i≥1)。i=1：最多1個結(jié)點i=2：最多2個結(jié)點i=3：最多4個結(jié)點GAFEDCB第25

頁6.2二叉樹第26

頁性質(zhì)1：在二叉樹的第i層上至多有2i-1

個結(jié)點(i≥1)。用歸納法證明：歸納基：i

=1

層時，只有一個根結(jié)點，2

i-1

=

2

0=

1；歸納假設(shè)：假設(shè)對所有的j,1≤j<i，命題成立；歸納證明：二叉樹上每個結(jié)點至多有兩棵子樹，則第i

層的結(jié)點數(shù)=2i-2·2=2i-1。6.2二叉樹第27

頁性質(zhì)2：深度為k的二叉樹上至多含2k-1個結(jié)點(k≥1)。證明：基于上一條性質(zhì)，深度為k的二叉樹上的結(jié)點數(shù)至多為：20+21+

+2k-1

=

2k-16.2二叉樹第28

頁性質(zhì)3：對任何一棵二叉樹，若它含有n0個葉子結(jié)點、n2

個度為2

的結(jié)點，則必存在關(guān)系式：n0

=

n2+1證明：設(shè)二叉樹上結(jié)點總數(shù)：n=n0

+n1

+n2又二叉樹上分支總數(shù)：b=n1

+2n2而b=n-1=n0

+n1

+n2

-1由此，n0

=n2

+16.2二叉樹兩類特殊的二叉樹滿二叉樹：指的是深度為k且含有2k-1

個結(jié)點的二叉樹。完全二叉樹：樹中所含的n

個結(jié)點和滿二叉樹中編號為1至n的結(jié)點一一對應(yīng)。12345678

9

10

11

12

13

14

15abcdefgh

i

j第29

頁6.2二叉樹第30

頁性質(zhì)4：具有n

個結(jié)點的完全二叉樹的深度為

log2n

+1。證明：設(shè)完全二叉樹的深度為k則根據(jù)第二條性質(zhì)得

2k-1≤ n

<2k即

k-1≤ log2

n

<k因為

k

只能是整數(shù)，因此，k

=log2n

+

16.2二叉樹第31

頁性質(zhì)5：若對含n個結(jié)點的完全二叉樹從上到下且從左至右進(jìn)行1至n的編號，則對完全二叉樹中任意一個編號為i

的結(jié)點：若i=1，則該結(jié)點是二叉樹的根，無雙親；否則i?1

，編號為i/2

的結(jié)點為其雙親結(jié)點；若2i>n，則該結(jié)點無左孩子；否則，編號為

2i

的結(jié)點為其左孩子結(jié)點；若2i+1>n，則該結(jié)點無右孩子結(jié)點；否則，編號為2i+1

的結(jié)點為其右孩子結(jié)點。6.2二叉樹性質(zhì)5：i/2ii+12i+22i

2i+1

2i+3(a)

i

和i+1

結(jié)點在同一層i+12i2i+12i+2

2i+3(b)

i

和i+1

結(jié)點不在同一層i

-1i

-2i第32

頁6.2二叉樹二叉樹的存儲結(jié)構(gòu)1.二叉樹的順序結(jié)構(gòu)對于完全二叉樹，采用一組連續(xù)的內(nèi)存單元，按編號順序依次存儲完全二叉樹的結(jié)點。m-1ABCDEFACB1第33

頁234D

5

E

F1

2

3

4

5

6

766.2二叉樹對于一棵一般的二叉樹，如果補(bǔ)齊構(gòu)成完全二叉樹所缺少的那些結(jié)點，便可以對二叉樹的結(jié)點進(jìn)行編號。AFEDC1672

B4538

9G

10第34

頁6.2二叉樹將二叉樹原有的結(jié)點按編號存儲到內(nèi)存單元“相應(yīng)”的位置上。1

2

3

4

5

6

7

8

9

10m-1ABCDE0F00GAFEDC1672

B4538

9G

10第35

頁6.2二叉樹對于一些“退化二叉樹”，順序存儲結(jié)構(gòu)存在突出缺點：比較浪費空間。DACBACBDABCD第36

頁BT[8]ABCDBT[15]6.2二叉樹指針域數(shù)據(jù)域指針域結(jié)點2.二叉鏈表二叉鏈表中每個結(jié)點包含三個域：數(shù)據(jù)域、左指針域、右指針域。typedef

struct

BiTNode{ ElemType

data;struct

BiTNode *

lchild,

*

rchild;}

BiTNode,

*

BiTree;存儲數(shù)據(jù)元素指向右孩子指向左孩子第37

頁6.2二叉樹二叉樹的二叉鏈表表示AFEDCB二叉鏈表圖示D∧AB∧C∧∧E∧∧F∧T第38

頁6.2二叉樹第39

頁parentlchilddatarchild3.三叉鏈表三叉鏈表中每個結(jié)點包含四個域：數(shù)據(jù)域、雙親指針域、左指針域、右指針域。typedef

struct

BiTNode{

ElemType

data;struct

BiTNodestruct

BiTNode*

lchild,

*

rchild;*

parent;}

BiTNode,*BiTree;結(jié)點結(jié)構(gòu)：6.2二叉樹root第40

頁ADEBCFCEFD二叉樹的三叉鏈表表示AB6.2二叉樹孩子結(jié)點在數(shù)組中的位置。用-1表示無左孩子或右孩子01234564.靜態(tài)二叉鏈表采用數(shù)組區(qū)間存貯的鏈表。Lchild

data

rchildroot

=

0AFEDCB2A13C-15B-1-1E-1-1F-1-1D4第41

頁6.2二叉樹第42

頁4.靜態(tài)二叉鏈表typedef

struct

BPTNode{//結(jié)點結(jié)構(gòu)TElemType

data;int lchild,

rchild

;}

BNodetypedef

struct

BTree{

//樹結(jié)構(gòu)BNode

nodes[

MAX_TREE_SIZE

];//結(jié)點數(shù)目//根結(jié)點的位置int

num_node;int

root;}

BTree;6.2二叉樹結(jié)點dataparentLRTagGAFEDCB5.雙親鏈表data

parent第43

頁0B2L1C2R2A-13D0L4E0R5F1L6G4L6.2二叉樹第44

頁5.雙親鏈表typedef

struct

BPTNode{//結(jié)點結(jié)構(gòu)TElemType

data;//指向雙親的指針//左、右孩子標(biāo)志域int

parent;char

LRTag;}

BPTNodetypedef

struct

BPTree{//樹結(jié)構(gòu)BPTNode

nodes[

MAX_TREE_SIZE

];//結(jié)點數(shù)目//根結(jié)點的位置int

num_node;int

root;}

BPTree;6.3遍歷二叉樹與線索二叉樹第45

頁遍歷的基本概念遍歷：按某種搜索路徑訪問二叉樹中的每個結(jié)點，且每個結(jié)點僅被訪問一次。訪問：含義很廣，可以是對結(jié)點的各種處理，如修改結(jié)點數(shù)據(jù)、輸出結(jié)點數(shù)據(jù)等。遍歷是各種數(shù)據(jù)結(jié)構(gòu)最基本的操作，許多其它的操作可以在遍歷的基礎(chǔ)上實現(xiàn)。遍歷對線性結(jié)構(gòu)來說很容易解決，但二叉樹每個結(jié)點都可能有兩棵子樹，因而需要尋找一種規(guī)律，使得二叉樹上的結(jié)點能線性排列。6.3遍歷二叉樹與線索二叉樹二叉樹的遍歷二叉樹的遍歷，就是按某種次序訪問二叉樹中的全部結(jié)點，要求每個結(jié)點訪問一次且僅訪問一次。二叉樹由根、左子樹、右子樹三部分組成。二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹。第46

頁6.3遍歷二叉樹與線索二叉樹二叉樹的遍歷令：L：遍歷左子樹

D：訪問根結(jié)點R：遍歷右子樹有六種遍歷方法：基本：DLR，LDR，LRD鏡象：DRL，RDL，RLD約定先左后右，有三種遍歷方法：DLR、LDR、LRD，由分別根據(jù)訪問根結(jié)點的次序稱為：先序遍歷、中序遍歷和后序遍歷。A第47

頁FGEDCB6.3遍歷二叉樹與線索二叉樹二叉樹的先序遍歷（DLR）先序遍歷（DLR）若二叉樹非空（1）訪問根結(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。例：先序遍歷二叉樹

1）訪問根結(jié)點A先序遍歷左子樹：即按DLR

的順序遍歷左子樹先序遍歷右子樹：即按DLR

的順序遍歷右子樹A第48

頁FGEDCB6.3遍歷二叉樹與線索二叉樹二叉樹的先序遍歷（DLR）先序遍歷（DLR）若二叉樹非空（1）訪問根結(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。A第49

頁FGEDCB先序遍歷序列：A,B,D,E,G,C,F6.3遍歷二叉樹與線索二叉樹二叉樹的中序遍歷（LDR）中序遍歷（LDR）若二叉樹非空（1）中序遍歷左子樹；（2）訪問根結(jié)點；（3）中序遍歷右子樹。例：中序遍歷二叉樹1）中序遍歷左子樹：即按LDR

的順序遍歷左子樹2）訪問根結(jié)點A3）中序遍歷右子樹：即按LDR

的順序遍歷右子樹A中序遍歷序列：D,B,G,E,A,C,F第50

頁FGD

ECB6.3遍歷二叉樹與線索二叉樹二叉樹的后序遍歷（LRD）后序遍歷（LRD）若二叉樹非空（1）后序遍歷左子樹；（2）后序遍歷右子樹。（3）訪問根結(jié)點；例：后序遍歷二叉樹后序遍歷左子樹：即按LRD

的順序遍歷左子樹后序遍歷右子樹：即按LRD

的順序遍歷右子樹3）訪問根結(jié)點AA后序遍歷序列：D,G,E,B,F,C,A第51

頁FGD

ECBdcbfa+*

e/-6.3遍歷二叉樹與線索二叉樹例：先序遍歷、中序遍歷、后序遍歷二叉樹。-先序遍歷序列：-,+,a,*,b,-,c,d,/,e,f中序遍歷序列：a,+,b,*,c,-,d,-,e,/,f后序遍歷序列：a,b,c,d,-,*,+,e,f,/,-第52

頁6.3遍歷二叉樹與線索二叉樹第53

頁遍歷的遞歸算法先序遍歷（DLR）的定義：若二叉樹非空（1）訪問根結(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹；上面先序遍歷的定義等價于：若二叉樹為空，結(jié)束——基本項（也叫終止項）若二叉樹非空——遞歸項（1）訪問根結(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。6.3遍歷二叉樹與線索二叉樹1、先序遍歷遞歸算法void

PreOrderTraverse

(

BiTree

T,Status

(

*

Visit

)

(

ElemType e

)

){

//采用二叉鏈表存貯二叉樹，visit()是訪問結(jié)點的函數(shù)//本算法先序遍歷以T為根結(jié)點指針的二叉樹if

(

T

)

{Visit(

T->data

)；//若二叉樹不為空//訪問根結(jié)點PreOrderTraverse(T->lchild,

Visit);

//先序遍歷T的左子樹

PreOrderTraverse(T->rchild,

Visit);

//先序遍歷T的右子樹}}

//PreOrderTraverse最簡單的Visit

函數(shù)是：Status

PrintElement(

TElemType e

){

//輸出元素e的值output(

e

); return

OK;}D∧AB∧C∧∧E∧∧F∧T第54

頁∧D∧ABC∧∧F∧∧G∧TE

∧6.3遍歷二叉樹與線索二叉樹Tra(PA)

{if

(PA!=NULL){V(A);Tra(PA->lc);Tra(PA->rc);}}A

B

D

E

G

C

FTra(PB)

{if

(PB!=NULL){V(B);Tra(PB->lc);Tra(PB->rc);}}Tra(PD){if(PD!=NULL){V(D);Tra(PD->lc);Tra(PD->rc);}}Tra(PA)

{if

(PA!=NULL){V(A);Tra(PA->lc);Tra(PA->rc);}}Tra(PB)

{if

(PB!=NULL){V(B);Tra(PB->lc);Tra(PB->rc);}}Tra(PB)

{if

(PB!=NULL){V(B);Tra(PB->lc);Tra(PB->rc);}}Tra(PA)

{if(PA!=NULL){V(A);Tra(PA->lc);Tra(PA->rc);}}Tra(PC)

{if

(PC!=NULL){V(C);Tra(PC->lc);Tra(PC->rc);}}Tra(PC)

{if

(PC!=NULL){V(C);Tra(PC->lc);Tra(PC->rc);}}Tra(PC)

{if

(PC!=NULL){V(C);Tra(PC->lc);Tra(PC->rc);}}Tra(PD){if(PD!=NULL){V(D);Tra(PD->lc);Tra(PD->rc);}}Tra(PE){if(PE!=NULL){V(E);Tra(PE->lc);Tra(PE->rc);}}Tra(PE){if(PE!=NULL){V(E);Tra(PE->lc);Tra(PE->rc);}}Tra(PE){if(PE!=NULL){V(E);Tra(PE->lc);Tra(PE->rc);}}Tra(PF){if(PF!=NULL){V(F);Tra(PF->lc);Tra(PF->rc);}}Tra(PF){if(PF!=NULL){V(F);Tra(PF->lc);Tra(PF->rc);}}第55

頁6.3遍歷二叉樹與線索二叉樹第56

頁先序遍歷遞歸算法（教材P129）void

PreOrderTraverse

(

BiTree

T,Status

(

*

Visit

)

(

ElemType e

)

){

//采用二叉鏈表存貯二叉樹，visit()是訪問結(jié)點的函數(shù)

if(T){if (Visit(

T->data))

//如果訪問根結(jié)點成功，則繼續(xù)if(PreOrderTraverse(T->lchild,

Visit)) //左子樹

if(PreOrderTraverse(T->rchild,

Visit))//右子樹return

OK;return

ERROR;}elsereturnok;}

//

PreOrderTraverse6.3遍歷二叉樹與線索二叉樹第57

頁2、中序遍歷遞歸算法void

InOrderTraverse(

BiTree

T,Status

(

*

Visit

)

(

ElemType e

)

){

//采用二叉鏈表存貯二叉樹，visit()是訪問結(jié)點的函數(shù)//本算法中序遍歷以T為根結(jié)點指針的二叉樹if

(

T

){//若二叉樹不為空InOrderTraverse(T->lchild,

Visit);

//中序遍歷T的左子樹Visit(T->data)；

//訪問根結(jié)點InOrderTraverse(T->rchild,

Visit);

//中序遍歷T的右子樹}}

//

InOrderTraverse∧D∧ABC

∧∧F∧∧G∧TE

∧6.3遍歷二叉樹與線索二叉樹Tra(PA)

{if(PA!=NULL){Tra(PA->lc);V(A)

;Tra(PA->rc);}}CD

B

G

E

A

FTra(PB)

{if

(PB!=NULL){

Tra(PB->lc);V(B)

;Tra(PB->rc);}}Tra(PD){if(PD!=NULL){Tra(PD->lc);V(D);Tra(PD->rc);}}第58

頁6.3遍歷二叉樹與線索二叉樹第59

頁3、后序遍歷遞歸算法void

PostOrderTraverse(

BiTree

T

,Status

(

*

Visit

)

(

ElemType e

)

){

//采用二叉鏈表存貯二叉樹，visit()是訪問結(jié)點的函數(shù)//本算法后序遍歷以T為根結(jié)點指針的二叉樹if

(

T

){//若二叉樹不為空

PostOrderTraverse(T->lchild,

Visit);//后序遍歷左子樹

PostOrderTraverse(T->rchild,

Visit);//后序遍歷右子樹Visit(T->data)；

//訪問根結(jié)點}}

//

PostOrderTraverse6.3遍歷二叉樹與線索二叉樹例1：編寫求二叉樹的葉子結(jié)點個數(shù)的算法。輸入：二叉樹的二叉鏈表結(jié)果：二叉樹的葉子結(jié)點個數(shù)void

leaf

(

BiTree

T

){//二叉鏈表存貯二叉樹，計算二叉樹的葉子結(jié)點個數(shù)//先序遍歷的過程中進(jìn)行統(tǒng)計，初始全局變量n=0if(T){ if

(

T->lchild==null

&&

T->rchild==null

)n

+=

1;

//若T所指結(jié)點為葉子結(jié)點則計數(shù)else

{

leaf

(

T->lchild

);leaf

(

T->rchild

);}}

//

if}

//

leaf與先序遍歷算法比較一下！第60

頁6.3遍歷二叉樹與線索二叉樹}例1：編寫求二叉樹的葉子結(jié)點個數(shù)的算法。int

Countleave(

BiTree

T

){//采用二叉鏈表存貯二叉樹，返回葉子結(jié)點的個數(shù)if

(

!T

)

return

0;if

(

T->lchild==NULL

&&

T->rchild==NULL

)return

1;elsereturn

Countleave(

T->lchild

)

+

Countleave(

T->rchild

)

;∧D∧ABC∧∧F∧∧G∧TE

∧第61

頁6.3遍歷二叉樹與線索二叉樹第62

頁例2：建立二叉鏈表。結(jié)果：二叉樹的二叉鏈表。是否可利用“遍歷”，建立二叉鏈表的所有結(jié)點并完成相應(yīng)結(jié)點的鏈接？基本思想：輸入（在空子樹處添加字符*的二叉樹的）先序序列（設(shè)每個元素是一個字符）。按先序遍歷的順序，建立二叉鏈表的所有結(jié)點并完成相應(yīng)結(jié)點的鏈接。6.3遍歷二叉樹與線索二叉樹*CAEDB**

F***

*A

B

D

*

F

*

*

*

C

E

*

*

*AFEDCB先序序列：A

B

D

F

C

E第63

頁例2：建立二叉鏈表。對原來的二叉樹進(jìn)行擴(kuò)充，在空子樹處添加*

。6.3遍歷二叉樹與線索二叉樹第64

頁Status

CreateBiTree

(

BiTree&T

){

//按先序遍歷的順序建立二叉鏈表scanf(

&ch

);if

(ch==‘*’)

T=NULL;

//若ch==

‘*’

則表示空子樹else

{if

(

!

(T=(

BiTNode

*

)

malloc(

sizeof(

BiTNode

)))

)exit(OVERFLOW

);T->date=ch;

//建立（根）結(jié)點CreateBiTree(T->lchild);

//遞歸構(gòu)造左子樹鏈表CreateBiTree(T->rchild);

//遞歸構(gòu)造右子樹鏈表}return

OK;}

//CreateBiTreeA6.3遍歷二叉樹與線索二叉樹例2：建立二叉鏈表。A

B

*

C

*

*

D

*

*TB^^C^^D^第65

頁6.3遍歷二叉樹與線索二叉樹例3：復(fù)制二叉鏈表。輸入：二叉鏈表結(jié)果：復(fù)制的新二叉鏈表∧D∧ABC∧∧F∧∧G∧TE∧第66

頁6.3遍歷二叉樹與線索二叉樹第67

頁例3：復(fù)制二叉鏈表。void

CopyBiTree(

BiTree

T,

BiTree

&newT

){

//

采用后序遍歷的框架，新二叉鏈表根為

newTif

(

!T

)

newT=NULL;else{CopyBiTree(T->lchild,

plchild);//復(fù)制左子樹

CopyBiTree(T->rchild,

prchild);//復(fù)制右子樹

newT=(BiTree)malloc(sizeof(BiTNode));newT->data

=

T->data;newT->lchild

=

plchild;newT->rchild

=

prchild;//復(fù)制結(jié)點//鏈接新結(jié)點的左子樹//鏈接新結(jié)點的右子樹}}6.3遍歷二叉樹與線索二叉樹第68

頁遍歷算法的應(yīng)用1.查詢二叉樹中某個結(jié)點2.求二叉樹的深度（后序遍歷）3.判斷二叉樹相等4.建立二叉樹的存儲結(jié)構(gòu)（給出全部左右子樹）5.由二叉樹的先序序列和中序序列建立二叉樹6.3遍歷二叉樹與線索二叉樹第69

頁遍歷的非遞歸算法棧是實現(xiàn)遞歸的最常用的結(jié)構(gòu)。利用一個棧來記下尚待遍歷的結(jié)點或子樹，以備以后訪問。D

B

G

E

A

F

C最左下結(jié)點;否則后繼結(jié)點為?6.3遍歷二叉樹與線索二叉樹中序遍歷的非遞歸算法？中序遍歷的第一個結(jié)點二叉樹的最左下結(jié)點。？當(dāng)前結(jié)點的后繼結(jié)點若當(dāng)前結(jié)點有右子樹，后繼結(jié)點為右子樹的∧D∧ABC∧∧F∧∧G∧TE∧第70

頁6.3遍歷二叉樹與線索二叉樹最左下結(jié)點;否則后繼結(jié)點為棧頂結(jié)點。中序遍歷的非遞歸算法？中序遍歷的第一個結(jié)點二叉樹的最左下結(jié)點。？當(dāng)前結(jié)點的后繼結(jié)點若當(dāng)前結(jié)點有右子樹，后繼結(jié)點為右子樹的AD

B G

E

A

F

CBDEGCF∧D∧ABC∧∧F∧∧G∧TE∧第71

頁6.3遍歷二叉樹與線索二叉樹第72

頁Status

InTrav(

BiTree

T,

void(*

Visit)(TelemType

e)

){

InitStack(S); p

=

T;while

(p

||!StackEmpty(S))

//樹非空或棧非空{(diào)

if

(p)

//若樹非空{(diào)

Push(S,

p); p

=

p->lchild;}

//

p有左子樹則p結(jié)點入棧，直到找到最左下結(jié)點else

//（最左下結(jié)點）退棧，訪問之{

Pop

(S,

p); Visit(

p->data

);p=p->rchild;

//p指向右子樹}}//

whileDesrroyStack(S);return

OK;}//

InTravP131

算法6.36.3遍歷二叉樹與線索二叉樹例如：先序序列：A

BDEGCF中序序列：DBGE

A

F

C后序序列：D

G

E

B

F

C

AGAE

FDCB第73

頁線索二叉樹遍歷二叉樹的結(jié)果可求得結(jié)點的一個線性序列。指向線性序列中的“前趨”和“后繼”的指針，稱作“線索”。第74

頁6.3遍歷二叉樹與線索二叉樹線索二叉樹如何在二叉鏈表中保存線索？——借用結(jié)點的空鏈域保存線索G中序序列：D

B

G

E

A

F

CAE

FDCB包含“線索”的存儲結(jié)構(gòu)，稱作“線索鏈表”?！腄∧ABC∧F∧∧∧

G

∧TE

∧6.3遍歷二叉樹與線索二叉樹第75

頁線索鏈表中的結(jié)點在二叉鏈表的結(jié)點中增加兩個標(biāo)志域Ltag,

Rtag：0表示lchild(p)為指向左孩子的指針1表示lchild(p)為指向直接前驅(qū)的線索ltag(p)={0表示rchild(p)為指向右孩子的指針1表示rchild(p)為指向直接后繼的線索lchild

ltag

data

rtag

rchildrtag(p)={6.3遍歷二叉樹與線索二叉樹第76

頁線索鏈表的類型說明typedef

enum{

link,

thread

}

PointerTag;//

link=0,

thread=1typedef

struct

BiThrNode{TElemType

data;struct

BiThrNode *lchild,*rchild;PointerTag Ltag,Rtag;//左、右標(biāo)志域}

BiThrNode，*

BiThrTree；lchild

ltag

data

rtag

rchild6.3遍歷二叉樹與線索二叉樹線索鏈表頭結(jié)點01ThrT1

GF110

E10D

1A00B00C001第77

頁116.3遍歷二叉樹與線索二叉樹③①②G第78

頁E

FDCB線索二叉樹的遍歷(中序線索二叉樹)中序遍歷的第一個結(jié)點 二叉樹的最左下結(jié)點當(dāng)前結(jié)點的后繼結(jié)點若結(jié)點的右鏈域為線索，則后繼結(jié)點為右鏈結(jié)點；否則，后繼結(jié)點為右子樹的最左下結(jié)點A6.3遍歷二叉樹與線索二叉樹第79

頁Status InTra_ThrT

(

BiThrTree

ThrT,void(*Visit)

(TElemType e)

){ p=ThrT->lchild;

//p指向根結(jié)點

while(p!=ThrT){ while(p->Ltag==link)p=p->lchild;

//最左下結(jié)點Visit(

p->data

);

//

p->Ltag==

threadwhile

(

p->Rtag==Thread

&&

p->rchild!=ThrT

){//若右孩子域是線索p

=

p->rchild; Visit(

p->data

);}p=p->rchild;

//若右孩子域不是線索}return

OK;}//

InTra_ThrT算法6.5

P1346.3遍歷二叉樹與線索二叉樹二叉樹的線索化(建立中序線索二叉樹)在中序遍歷過程中為二叉樹結(jié)點加線索增加指針pre、p,

保持指針p指向當(dāng)前訪問的結(jié)點，pre指向當(dāng)前訪問結(jié)點的前趨。Ppre1

GF11E01D01A00B000C01第80

頁6.3遍歷二叉樹與線索二叉樹第81

頁void

InThreading(

BiThrTree

p)//中序線索化二叉樹{//pre為全局變量，初值為NULLif(p){

InThreading(

p->lchild);

//左子樹線索化if(p->lchild==NULL)

//為當(dāng)前結(jié)點加前趨線索{

p->Ltag

=Thread;

p->lchild=pre;}if(pre->rchild

==NULL)

//為前趨結(jié)點加后繼線索{

pre->Rtag=Thread;

pre->rchild=p;}//pre指向ppre

=

p;InThreading(

p->rchild

);}

//

if}

//

InThreadingP135

算法6.76.3遍歷二叉樹與線索二叉樹Status

InThread(

BiThrTree

&

Thrt,

BiThrTree

T

){ if

(

Thrt

=

(BiThrTree)

malloc(

sizeof(BiThrNode)

)exit

(

OVERFLOW

);Thrt->Ltag

=

Link;Thrt->Rtag

=

Thread;Thrt->rchild

=

Thrt;//

0//1.

建頭結(jié)點//右指針指向頭結(jié)點……

//進(jìn)行中序線索化return

OK;}

//InThread

P134

算法6.601頭結(jié)點第82

頁6.3遍歷二叉樹與線索二叉樹//左指針指向頭結(jié)點……if

(

!T

)Thrt->lchild

=

Thrt;else{Thrt->lchild=T;

//樹非空，左指針指向根結(jié)點pre

=

Thrt;InThreading(T);//頭結(jié)點是中序第一個結(jié)點的前趨//中序線索化//最后一個結(jié)點線索化pre->rchild

=

Thrt;pre->Rtag

=

Thread;Thrt->rchild

=

pre;}……01頭結(jié)點第83

頁6.4樹和森林第84

頁樹的存貯結(jié)構(gòu)1、雙親表示法通過保存樹每個結(jié)點的雙親結(jié)點的位置，來表示樹中結(jié)點之間的結(jié)構(gòu)關(guān)系。6.4樹和森林雙親表示的類型定義#define

MAX_TREEE_SIZE

100typedef

struct

PTNode{

ElemType

data;第85

頁//雙親位置域int

parent;}

PTNode;typedef

struct{

PTNode nodes[MAX_TREE_SIZE];int r,n;

//r為根的位置，n為結(jié)點數(shù)}

Ptree;6.4樹和森林雙親表示法r=0n=70123456A-1B0C0D0E2F2G5雙親結(jié)點在數(shù)組中的位置，-1表示無雙親AB

C

DEFG第86

頁6.4樹和森林第87

頁樹的存貯結(jié)構(gòu)2、孩子表示法通過保存樹中每個結(jié)點的孩子結(jié)點的位置，表示樹中結(jié)點之間的結(jié)構(gòu)關(guān)系。6.4樹和森林方法1：多重鏈表（類似二叉鏈表，采用多叉結(jié)點）兩種方式：定長結(jié)點和不定長結(jié)點

定長結(jié)點：優(yōu)點是結(jié)點結(jié)構(gòu)一致，便于實現(xiàn)樹的操作。缺點是浪費一些內(nèi)存空間。第88

頁datachild1child2......childd不定長結(jié)點：優(yōu)點是節(jié)省內(nèi)存空間。缺點是不定長的結(jié)點會使一些操作實現(xiàn)變復(fù)雜。datadegreechild1child2......childd6.4樹和森林第89

頁方式2：孩子鏈表將樹中的每個結(jié)點的孩子排列起來，看成一個線性表，采用線性鏈表進(jìn)行存貯。AB

C

DEFGr=0n=76.4樹和森林孩子鏈表表示法data

firstchildABCDFE0123456G64

51

2

3同一結(jié)點的孩子構(gòu)成鏈表結(jié)點數(shù)和根的位置第90

頁6.4樹和森林第91

頁樹的孩子鏈表類型定義typedef

struct

CTNode

//孩子結(jié)點{

int

child;*next;struct

CTNode}*

ChildPtr;typedef

struct{

ElemType

data;firstchild;//孩子鏈表頭指針ChildPtr}

CTBox;typedef

struct{

CTBox nodes

[

MAX_TREE_SIZE

];int n,r;

//結(jié)點數(shù)和根的位置}

CTree;6.4樹和森林第92

頁3、孩子兄弟表示法用二叉鏈表作為樹的存貯結(jié)構(gòu)。孩子兄弟表示法類型定義typedef

struct

CSNode{ElemType

data;struct

CSNode *

firstchild

,//指向第一個孩子*

nextsibling;

//指向下一個兄弟}

CSNode

,

*CSTree;6.4樹和森林3、孩子兄弟表示法B的第一個孩子結(jié)點E的緊鄰的右兄弟結(jié)點JACBDH

IF

GEA∧∧I∧HD∧∧G∧∧F∧C∧EB∧J

∧第93

頁6.4樹和森林樹根結(jié)點X的第一個孩子結(jié)點X緊鄰的右兄弟二叉樹根結(jié)點X的左孩子結(jié)點X的右孩子樹與二叉樹二叉樹與樹都可用二叉鏈表存貯，以二叉鏈表作中介，可實現(xiàn)樹與二叉樹之間的轉(zhuǎn)換。樹與二叉樹轉(zhuǎn)換方法第94

頁6.4樹和森林HI樹根結(jié)點X的第一個孩子結(jié)點X緊鄰的右兄弟二叉樹根結(jié)點X的左孩子結(jié)點X的右孩子ABCG

DJACBDH

IF

GEJ第95

頁6.4樹和森林森林與二叉樹的轉(zhuǎn)換森林：樹的集合將森林中樹的根看成兄弟，用樹與二叉樹的轉(zhuǎn)換方法，進(jìn)行森林與二叉樹轉(zhuǎn)換。ABC

DFE

GHABCDEFIJGHIJEFABCDGHIJ第96

頁6.4樹和森林第97

頁樹的遍歷遍歷——按一定規(guī)律走遍樹的各個頂點，且使每一頂點僅被訪問一次，即找一個完整而有規(guī)律的走法，以得到樹中所有結(jié)點的一個線性排列。常用方法先根（序）遍歷：先訪問樹的根結(jié)點，然后依次先根遍歷根的每棵子樹。后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點。按層次遍歷：先訪問第一層上的結(jié)點，然后依次遍歷第二層，……第n層的結(jié)點。6.4樹和森林樹的遍歷實例ABCDE

FGHIJ

K

L

MN

O先根遍歷：AB

E

F

I

G

CD

H

J

K

LNOM后根遍歷：E

I

FGB

CJ

K

N

OLM

HDA層次遍歷：A

BCDE

F

G

H

I

J

K

LM

NO第98

頁6.4樹和森林樹的遍歷與二叉樹遍歷的關(guān)系樹

森林

二叉樹先序遍歷

先序遍歷

先序遍歷后序遍歷

中序遍歷

中序遍歷第99

頁6.4樹和森林例：由廣義表建樹AB

CDE

F

G

H

I

JK

L

M(

A,

(

B,

(E,

(K),

(L)),

(F)

),

(

C,

(G)

),

(D,

(H,(M)),(I),(J))

)根子樹1子樹2子樹3ADCB根Efirstchildnextsibling第100

頁6.4樹和森林例：由廣義表建樹AB

CDE

F

G

H

I

JK

L

M(

A,

(

B,

(E,

(K),

(L)),

(F)

),

(

C,

(G)

),

(D,

(H,(M)),(I),(J))

)樹根：Head(L)根的第一個孩子：Head(

tail(L)

)第一個孩子的下一個兄弟：Head(

tail(tail(L))

)tail(

tail(L)

)根根的第一個孩子第101

頁第102

頁6.4樹和森林void

CreateTree(

Tree

&t,

GList

L){

Create

root

node

tfrom

head(

L

);if

(

tail(L)

is

not

empty

){ curhead=head(

tail(L));

//表尾的頭curtail=tail(

tail(L));

//表尾的表尾CreateTree(

t->firstchild,

curhead

);p

=t->firstchild;while

(curtail)//若還有子樹(表尾非空){ curhead

=head(

curtail);//下一個兄弟curtail

=

tail(

curtail

);CreateTree(

p->nextsibling,

curhead

);p

=

p->next