數(shù)據(jù)結(jié)構(gòu)-第六章樹(shù)與二叉樹(shù)

提綱樹(shù)的定義和基本術(shù)語(yǔ)二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)樹(shù)和森林赫

樹(shù)及其應(yīng)用小結(jié)2提綱樹(shù)的定義和基本術(shù)語(yǔ)二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)樹(shù)和森林赫

樹(shù)及其應(yīng)用小結(jié)3樹(shù)的定義和基本術(shù)語(yǔ)樹(shù)的定義樹(shù)是由n(n

0)個(gè)結(jié)點(diǎn)的有限集合。如果n=0，稱為空樹(shù)；如果n>0，則有且僅有一個(gè)特定的稱之為根(Root)的結(jié)點(diǎn)，它只有直接后繼，但沒(méi)有直接前驅(qū)；當(dāng)n>1，除根以外的其它結(jié)點(diǎn)劃分為m(m>0)個(gè)互不相交的有限集T1,T2,…,Tm，其中每個(gè)集合本身又是一棵樹(shù)，并且稱為根的

(SubTree)。4ABCDE

F

G

H

I

JK

L

M有13個(gè)結(jié)點(diǎn)的樹(shù)其中:A是根,其余結(jié)點(diǎn)分成三個(gè)互不相交的子集，T1={B,E,F,K,L}；

T2={C,G}；

T3={D,H,I,J,M},T1,T2,T3都是根A的

，且本身也是一棵樹(shù)A只有根結(jié)點(diǎn)的樹(shù)樹(shù)的舉例樹(shù)的基本術(shù)語(yǔ)樹(shù)的結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向子樹(shù)的分支；孩子結(jié)點(diǎn)：結(jié)點(diǎn)的

的根稱為該結(jié)點(diǎn)的孩子；雙親結(jié)點(diǎn)：B結(jié)點(diǎn)是A結(jié)點(diǎn)的孩子，則A結(jié)點(diǎn)是B結(jié)點(diǎn)的雙親；兄弟結(jié)點(diǎn)：同一雙親的孩子結(jié)點(diǎn)；堂兄結(jié)點(diǎn)：雙親在同一層的結(jié)點(diǎn)互為堂兄弟6樹(shù)的基本術(shù)語(yǔ)（續(xù)）結(jié)點(diǎn)層：根結(jié)點(diǎn)的層定義為1；根的孩子為第二層結(jié)點(diǎn)，依此類推；樹(shù)的高度：樹(shù)中結(jié)點(diǎn)的最大層次。結(jié)點(diǎn)的度：結(jié)點(diǎn)

的個(gè)數(shù)。樹(shù)的度：樹(shù)內(nèi)各結(jié)點(diǎn)的度的最大值。葉子結(jié)點(diǎn)：也叫終端結(jié)點(diǎn)，是度為0的結(jié)點(diǎn)分枝結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)；有序樹(shù)：

有序的樹(shù)，（

不能互換）無(wú)序樹(shù)：不考慮

的順序；

7是m（m≥0）棵互不相交的樹(shù)的集合ArootBEK

L任何一棵非空樹(shù)是一個(gè)二元組Tree

=

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

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

被稱為

森林C

DF

G

H

I

JM樹(shù)的基本術(shù)語(yǔ)（續(xù)）F路徑：樹(shù)中的k

個(gè)結(jié)點(diǎn)n1,n2，…，nk，滿足ni

是ni+1

的雙親，n1到nk有一條路徑路徑長(zhǎng)度：分支數(shù)＝路徑上結(jié)點(diǎn)個(gè)數(shù)一1根沒(méi)有雙親，葉子沒(méi)有孩子；vi是vj

的雙親，則L(vi)=L(vj)-1;堂兄弟的雙親是兄弟關(guān)系嗎？有序樹(shù)和無(wú)序樹(shù)的區(qū)別；注意樹(shù)的基本術(shù)語(yǔ)（續(xù)）根結(jié)點(diǎn)(無(wú)前驅(qū))多個(gè)葉子結(jié)點(diǎn)(無(wú)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、一個(gè)或多個(gè)后繼)(a1,

a2,

a3,

…an-2,

an-1,

an)第一個(gè)數(shù)據(jù)元素(無(wú)前驅(qū))最后一個(gè)數(shù)據(jù)元素(無(wú)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、一個(gè)后繼)線性結(jié)構(gòu)（1:1）樹(shù)型結(jié)構(gòu)（1:n）

ADB

CE

F

G

H

I

JMK

L對(duì)比線性結(jié)構(gòu)和樹(shù)型結(jié)構(gòu)樹(shù)的抽象數(shù)據(jù)類型定義ADT

Tree

{數(shù)據(jù)對(duì)象

D：具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系

R：若D為空集，則稱為空樹(shù)。否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；(2)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,

T2,…,Tm，其中每一棵子集本身又是。一棵符合本定義的樹(shù)，稱為根root的基本操作：……}

ADT

Tree11樹(shù)的基本操作InitTree（＆T）；操作結(jié)果：構(gòu)造空樹(shù)T。DestroyTree（＆T）；初始條件：樹(shù)T存在。操作結(jié)果：銷毀樹(shù)T。CreateTree（＆T，definition）初始條件：definition給出樹(shù)T的定義。操作結(jié)果：按definition構(gòu)造樹(shù)T。1樹(shù)的基本操作（續(xù)）

ClearTree（＆T）；初始條件：樹(shù)T存在。操作結(jié)果：將樹(shù)T清為空樹(shù)。TreeEmpty（T）初始條件：樹(shù)T存在。操作結(jié)果：若T為空樹(shù)，則返回ture，否則false。TreeDepth（T）初始條件：樹(shù)T存在。操作結(jié)果：返回T的深度。1樹(shù)的基本操作（續(xù)）Root（T）初始條件：樹(shù)T存在。操作結(jié)果：返回T的根。Value（T,

cur_e）初始條件：樹(shù)T存在，cur＿e是T中某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回cur＿e的值。Assign（T，cur_e，value）初始條件：樹(shù)T存在，cur＿e是T中某個(gè)結(jié)點(diǎn)。操作結(jié)果：結(jié)點(diǎn)cur_e賦值為value。1樹(shù)的基本操作（續(xù)）Parent（T，cur＿e）初始條件：樹(shù)T存在，cur＿e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：若cur＿e是T的非根結(jié)點(diǎn)，則返回它的雙親，否則函數(shù)值為“空”。Rightsibling（T，cur＿e）初始條件：樹(shù)T存在，cur＿e是T中某個(gè)結(jié)點(diǎn)。操作結(jié)果：若cur＿e有右兄弟，則返回它的右兄弟，否則函數(shù)值為“空”。樹(shù)的基本操作（續(xù)）LeftChild（T，cur＿e）初始條件：樹(shù)T存在，cur＿e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：若cur＿e是T的非葉子結(jié)點(diǎn)，則返回它的最左孩子，否則返回“空”。InsertChild（＆T，＆p，i，c）；初始條件：樹(shù)T存在，p指向T中某個(gè)結(jié)點(diǎn)，1≤i≤p所指結(jié)點(diǎn)的度＋1，非空樹(shù)c與T不相交。操作結(jié)果：

c為T(mén)中p指結(jié)點(diǎn)的第i棵

。1樹(shù)的基本操作（續(xù)）DeleteChild（＆T，＆p，i）；初始條件：樹(shù)T存在，p指向T中某個(gè)結(jié)點(diǎn)，1≤i≤p指結(jié)點(diǎn)的度。。操作結(jié)果：刪除T中p所指結(jié)點(diǎn)的第i棵TraverseTree（T，visit（））；初始條件：樹(shù)T存在，visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：按某種次序?qū)的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit()

一次且至多一次。一旦visit（）失敗，則操作失敗。1提綱樹(shù)的定義和基本術(shù)語(yǔ)二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)樹(shù)和森林赫 樹(shù)及其應(yīng)用小結(jié)1二叉樹(shù)定義二叉樹(shù)或?yàn)榭諛?shù)；或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左和右的、互不相交的二叉樹(shù)組成。（二叉樹(shù)中不存在度特點(diǎn)每個(gè)結(jié)點(diǎn)至多只有兩棵大于2的結(jié)點(diǎn)）。1二叉樹(shù)ABCDEFGH

K根結(jié)點(diǎn)左右2二叉樹(shù)的五種基本形態(tài)N空樹(shù)只含根結(jié)點(diǎn)NNNLRR右L為空樹(shù)

左為空樹(shù)左右子樹(shù)均不為空樹(shù)2二叉樹(shù)應(yīng)用舉例a+b*(c-d)-e/fedcbfa+*/-可以用二叉樹(shù)表示表達(dá)式-22二叉樹(shù)性質(zhì)1在二叉樹(shù)的第i

層上至多有2i-1個(gè)結(jié)點(diǎn)。(i

[證明用歸納法]證明：當(dāng)i=1時(shí)，只有根結(jié)點(diǎn)，2

i-1=2

0=1。假設(shè)對(duì)所有j，i>j1，命題成立，即第j層上至多有2

j-1

個(gè)結(jié)點(diǎn)。由歸納假設(shè)第i-1層上至多有2i-2個(gè)結(jié)點(diǎn)。由于二叉樹(shù)的每個(gè)結(jié)點(diǎn)的度至多為2，故在第i層上的最大結(jié)點(diǎn)數(shù)為第i-1層上的最大結(jié)點(diǎn)數(shù)的2倍，即2*

2i-2=2

i-1。2二叉樹(shù)性質(zhì)2深度為k

的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)(k

1)證明：由性質(zhì)1可見(jiàn)，深度為k的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)為k

(

第i

層上的最大結(jié)點(diǎn)數(shù)）i

1k＝

i

12

i

1＝20

+

21

+

…

+

2k-1

=

2k-12二叉樹(shù)性質(zhì)3對(duì)任何一棵二叉樹(shù)T,如果其葉結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則n0＝n2＋1.證明：若度為1的結(jié)點(diǎn)有n1

個(gè)，總結(jié)點(diǎn)個(gè)數(shù)為n，總邊數(shù)為e，則根據(jù)二叉樹(shù)的定義，n

=

n0

+

n1

+

n2

e

=

2n2

+

n1=

n

-

1因此，有2n2

+n1

=n0

+n1

+n2

-1n2

=n0

-

1n0

=

n2

+

1滿二叉樹(shù)62定義：一棵深度為k且有2

k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。1275438

9

10

11

12

13

14

15完全二叉樹(shù)62定義：若設(shè)二叉樹(shù)的高度為h，則共有h層。除第h層外，其它各層(0

h-1)的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h

層從右向左連續(xù)缺若干結(jié)點(diǎn)。1275438

9

10 11

122二叉樹(shù)性質(zhì)4具有n(n

0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2(n)

＋1證明：設(shè)完全二叉樹(shù)的深度為h，則根據(jù)性質(zhì)2和完全二叉樹(shù)的定義有2h-1

-1<n

2h-1或2h-1

n<2h取對(duì)數(shù)h-1

log2n<h，又h是整數(shù)，因此有h=log2(n)

＋1二叉樹(shù)性質(zhì)5如將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)自頂向下0,

1,

2,…,，同一層自左向右連續(xù)給結(jié)點(diǎn)1，則有以下關(guān)系：若i=0,則i

無(wú)雙親若i>0,則i

的雙親為(i-1)/2若2*i+1

<

n,則i

的左 為

2*i+1，若2*i+2

<

n,則i

的右若結(jié)點(diǎn)若結(jié)點(diǎn)為2*i+2i為偶數(shù)，且i≠0,則左兄弟結(jié)點(diǎn)i-1i為奇數(shù)，且i≠n-1,則右兄弟結(jié)點(diǎn)為

i+1

2二叉樹(shù)性質(zhì)50713234568

9二叉樹(shù)的

結(jié)構(gòu)二叉樹(shù)也可以采用兩種方式：結(jié)構(gòu)。順序順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)結(jié)構(gòu)適用于完全二叉樹(shù)。形式為：用一組連續(xù)的

單元按照完全二叉樹(shù)的每個(gè)結(jié)點(diǎn) 的順序存放結(jié)點(diǎn)內(nèi)容。3二叉樹(shù)的順序表示一般二叉樹(shù)的順序表示1

2

3

4

5

6

7

8

9101

2

3

4

0

5

6

7

8

0

0

910124

58

9

106

7391236547810完全二叉樹(shù)的順序表示3二叉樹(shù)的順序

表示#

define

MAX_TREE_SIZE

100//二叉樹(shù)的最大結(jié)點(diǎn)數(shù)typedef

emType

SqBiTree[MAX_TREE_SIZE];//0號(hào)單元存放根結(jié)點(diǎn)SqBiTree

bt;

情況：深度為k的且只有k個(gè)結(jié)點(diǎn)的單支樹(shù)，需要長(zhǎng)度為2k-1的一維數(shù)組。3鏈?zhǔn)?/p>

結(jié)構(gòu)在順序置及元結(jié)構(gòu)中，利用

表示元素的位間孩子或雙親的關(guān)系。對(duì)于非完全二叉樹(shù)，需要將空缺的位置用特定的符號(hào)填補(bǔ)，若空缺結(jié)點(diǎn)較多，勢(shì)必造成空間利用率的下降。這種情況下可考慮鏈?zhǔn)浇Y(jié)構(gòu)。常見(jiàn)的二叉樹(shù)結(jié)點(diǎn)結(jié)構(gòu)如下所示：lChild

data

rChild3鏈?zhǔn)?/p>

結(jié)構(gòu)其中，Lchild和Rchild是分別指向該結(jié)點(diǎn)左孩子和右孩子的指針，data是數(shù)據(jù)元素的內(nèi)容。類型定義為：typedef

struct

BiTNode{emType

data;struct

BiTNode

*Lchild,*Rchlid;}BTNode,*BTree;3鏈?zhǔn)?/p>

結(jié)構(gòu)這種結(jié)構(gòu)的特點(diǎn)是尋找孩子結(jié)點(diǎn)容易，雙親比較。若需要頻繁地尋找雙親，可以給每個(gè)結(jié)點(diǎn)添加一個(gè)指向雙親結(jié)點(diǎn)的指針域，其結(jié)點(diǎn)結(jié)構(gòu)如下所示。lChild

data

parent

rChild3二叉樹(shù)鏈表表示的示例ABDFErootCFBC

DErootAABCDFEroot3三叉鏈表二叉樹(shù)二叉鏈表三叉鏈表的靜態(tài)結(jié)構(gòu)二叉鏈表或三叉鏈表是用指針實(shí)現(xiàn)，是一種動(dòng)態(tài)的鏈?zhǔn)浇Y(jié)構(gòu)，鏈?zhǔn)浇Y(jié)構(gòu)也可用一維數(shù)組來(lái)實(shí)現(xiàn)。用一維數(shù)組表示的二叉鏈表或三叉鏈表，稱為靜態(tài)鏈表。3三叉鏈表的靜態(tài)結(jié)構(gòu)BC

DE

FrootAdata

parent

leftChild

rightChild012345A-11-1B023C1-1-1D145E3-1-1F3-1-13提綱樹(shù)的定義和基本術(shù)語(yǔ)二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)樹(shù)和森林赫 樹(shù)及其應(yīng)用小結(jié)4遍歷二叉樹(shù)二叉樹(shù)一次，而定義按一定規(guī)律（順著某一條搜索路徑）中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被且僅被

一次?！?/p>

”的含義可以很廣，如：輸出或修改結(jié)點(diǎn)的信息等。二叉樹(shù)的遍歷把一個(gè)非線性結(jié)構(gòu)的二叉樹(shù)轉(zhuǎn)化為一個(gè)線性結(jié)構(gòu)；4遍歷二叉樹(shù)（續(xù)）二叉樹(shù)的遞歸定義

二叉樹(shù)或?yàn)榭諛?shù)，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左

和右 的二叉樹(shù)組成。二叉樹(shù)由三部分組成：根結(jié)點(diǎn)D

，左

L和右

R遍歷二叉樹(shù)的方案有6種：先左后右：DLR,LDR,LRD

先右后左：

DRL

,

RDL

,

RLD

DL

R4先（根）序的遍歷算法DLR若二叉樹(shù)為空樹(shù)，則空操作；否則，根結(jié)點(diǎn)；先序遍歷左

；若左左為空樹(shù)，則空操作；否則，的根結(jié)點(diǎn)；先序遍歷左先序遍歷左的左的右；。先序遍歷右。4ADBCDLRAD

L

RD

L

RBDCD

L

R先序遍歷序列：A

B

D

C先（根）序的遍歷算法DLR中（根）序的遍歷算

DR45若二叉樹(shù)為空樹(shù)，則空操作；否則，中序遍歷左

；若左

為空樹(shù)，則空操作；否則，中序遍歷左

的左

；左中序遍歷左的根結(jié)點(diǎn)；的右。根結(jié)點(diǎn)；中序遍歷右。-+a*b

-c

de

f/ADBCLDRBL

D

RL

D

RACL

D

RD中序遍歷序列：B

D

A

C中（根）序的遍歷算

DR后（根）序的遍歷算

R

D47若二叉樹(shù)為空樹(shù)，則空操作；否則，后序遍歷左

；若左

為空樹(shù)，則空操作；否則，后序遍歷左后序遍歷左的左的右；。左的根結(jié)點(diǎn)；后序遍歷右。根結(jié)點(diǎn)；ADBCDL

R

DACL

R

DL

R

DD后序遍歷序列：

D

B

C

AB后（根）序的遍歷算

R

DLR-+/a*efb

-c

d先序遍歷：-+a

*

b-c

d/e

f中序遍歷：a+b

*

c-d-e/f后序遍歷：a

b

c

d-*+e

f/-三種遍歷算法比較算法的遞歸描述二叉鏈表C

語(yǔ)言的類型描述如下:結(jié)點(diǎn)結(jié)構(gòu):#definetypedefemType

char

//二叉樹(shù)的數(shù)據(jù)元素類型struct

BiTNode

{//結(jié)點(diǎn)結(jié)構(gòu)emType

data;struct

BiTNode

*lchild,

*rchild;//左右孩子指針}

*BiTree;lchilddatarchild50先（根）序遍歷算法的遞歸描述void

Preorder

(BiTree

T,

void(

*visit)(emType&

e)){//先序遍歷二叉樹(shù)if

(T)

{visit(T->data);

//

結(jié)點(diǎn)，如輸出cout<<T->dataPreorder(T->lchild,visit);//中序遍歷左Preorder(T->rchild,visit);//中序遍歷右}}51中（根）序遍歷算法的遞歸描述void

Inorder

(BiTree

T,

void(

*visit)(emType&

e)){//中序遍歷二叉樹(shù)if

(T)

{Inorder(T->lchild,visit);//中序遍歷左visit(T->data);

//

根結(jié)點(diǎn)Inorder(T->rchild,visit);//中序遍歷右}}52后（根）序遍歷算法的遞歸描述Void

Postorder

(BiTree

T,

void(

*visit)(emType&

e)){//后序遍歷二叉樹(shù)if

(T)

{Postorder(T->lchild,visit);//后序遍歷左Postorder(T->rchild,

visit);//后序遍歷右visit(T->data);

//

根結(jié)點(diǎn)}}53算法分析3種遍歷算法不同之處根結(jié)點(diǎn)、遍歷左

和右

先后關(guān)系不同若不考慮visit()語(yǔ)句，則三種遍歷方法完全相同三種遍歷算法均是遞歸算法：樹(shù)的定義本身就是遞歸的；遞歸和棧密切聯(lián)系：遞歸過(guò)程實(shí)際就是對(duì)棧的操作過(guò)程；可以直接通過(guò)對(duì)棧的操作，來(lái)把遞歸算法寫(xiě)為非

遞歸算法。

54中序遍歷的非遞歸算法思路設(shè)待遍歷的二叉樹(shù)的根結(jié)點(diǎn)指針為T(mén)（算法開(kāi)始時(shí)，令p=T），則可能出現(xiàn)兩種情況：若p不空，先按中序次序遍歷T(p)的左

后打印p->data，再按中序次序遍歷p的右，然。在遍歷p的左

前要保留根結(jié)點(diǎn)指針p，以便返回后再打印p->data，接著遍歷其右

。若p為空，以p為根的二叉樹(shù)遍歷完畢，應(yīng)該返回下面應(yīng)該

T’的根結(jié)點(diǎn)，并對(duì)其右

遍歷。若棧不空，則棧頂元素一定為T(mén)’，取出棧頂?shù)闹羔槻①x予p，在

完p之后，繼續(xù)遍歷其右

；

若棧為空，則整個(gè)二叉樹(shù)遍歷完畢。

55中序遍歷的非遞歸算法描述1Status

InOrderTraverse(

BiTree

T,

status

(*visit)( emType

e

)){ InitStack(

S

); Push(S,

T);while(!StackEmpty(

S

)){while(GetTop(S,p)&&p) Push(S,p->lchild);//向左走到盡頭Pop(S,p);if

(!StackEmpty(S)){Pop(S,p);//空指針退棧if(

!(*Visit)(

p->data)) return

ERROR;Push(S,

p->rchild);}//if}//

whileABCreturn

OK;D }//

InOrderTraverse

56中序遍歷的非遞歸算法描述2Status

InOrderTraverse(

BiTree

T,

status

(*visit)(emType

e

)){ InitStack(

S

); p

=

T;while(

p

||!StackEmpty(

S

)){if(p)//根指針進(jìn)棧，遍歷左{

Push(

S,

p

); p

=

p>lchild;

}根結(jié)點(diǎn)，遍歷右else//根指針出棧，{

Pop(

S,

p

);if(

!(*Visit)(

p->data)) return

ERROR;p

=

p->rchild;}//

else}//

while//右ABCreturn

OK;D }//

InOrderTraverse

57先序遍歷的非遞歸算法描述1emType

e

))Status

PreOrderTraverse(

BiTree

T,

status

(*visit)({

p=T;

InitStack(S);Push(S,NULL);while

(p){if(

!(*Visit)(

p->data)) return

ERROR;if

(p->rchild)Push(S,p->rchild);if

(p->lchild)p=p->lchild;else

Pop(S,p);}return

OK;}//

PreOrderTraverseADBC58先序遍歷的非遞歸算法描述2emType

e

))Status

PreOrderTraverse(

BiTree

T,

status

(*visit)({int

top=0;

BiTree

stack[20],

p=T;do

{while

(p){if(

!(*Visit)(

p->data)) return

ERROR;stack[top]=p;

top++;p=p->lchild;}if

(top){top--;

p=stack[top];p=p->rchild;}}while

(top

||

p);return

OK;}//

PreOrderTraverseADBC59后序遍歷的非遞歸算法描述1Status

PostOrderTraverse(

BiTree

T,

status

(*visit)(emType

e

)){ BiTree

p=T,q=NULL; SqStack

S;InitStack(S);

Push(S,p);while

(!StackEmpty(S)){ if

(p

&&p!=q) {

Push(S,p);

p=p->lchild;

}else

{

Pop(S,p);if

(!StackEmpty(S))if

(p->rchild

&&

p->rchild!=q){

Push(S,p);

p=p->rchild;}else

{if(

!(*Visit)(

p->data)) return

ERROR;q=p;}}} return

OK; }//PostOrderTraverse

ADBC6061后序遍歷的非遞歸算法描述1循環(huán)次數(shù)pqSRes1BNullAA2NullNullAAB3DNullAAB4NullNullAABD5DDAABD6BBAADB7CBAADB8NullBAACDB9CCAADBC10AAADBCA11AADBCA后序遍歷的非遞歸算法描述2emType

e

))Status

PostOrderTraverse(

BiTree

T,

status

(*visit)({BiTree

p=T,q; int

flag; SqStack

S;

InitStack(S);do

{

while

(p){

*(S.top)=p;S.top++;p=p->lchild;}q=NULL;

flag=1;while

((S.top!=S.base)

&&

flag){

p=*(S.top-1);if

(p->rchild

==

q){if(

!(*Visit)(

p->data)) return

ERROR;S.top--;

q=p;}else

{

p=p->rchild;

flag=0;}}}while

((S.top!=S.base));return

OK;}//

PostOrderTraverseADBC6263后序遍歷的非遞歸算法描述2循環(huán)次數(shù)pqflagSRes1.1DNull0AB2.1DD1ABD2.2BB1ADB2.3CB0ADB3.1CC1ADBC3.2AA1DBCA二叉樹(shù)遍歷方法比較遍歷的第一個(gè)結(jié)點(diǎn)：先序：根結(jié)點(diǎn)；中序：從根結(jié)點(diǎn)出發(fā)，沿著左鏈走，找到一個(gè)沒(méi)有左孩子的結(jié)點(diǎn)；后序：從根結(jié)點(diǎn)出發(fā)，沿著左鏈走，找到一個(gè)沒(méi)有左孩子的結(jié)點(diǎn)；如果該結(jié)點(diǎn)有右孩子，再沿著其右孩子的左鏈走，以此類推，直到找到一個(gè)沒(méi)有孩子的結(jié)點(diǎn)。ADBC64遍歷的最后一個(gè)結(jié)點(diǎn)：先序：從根結(jié)點(diǎn)出發(fā)，沿著右鏈走，找到一個(gè)沒(méi)有右孩子的結(jié)點(diǎn)；如果該結(jié)點(diǎn)有左孩子，再沿著其左孩子的右鏈走，以此類推，直到找到一個(gè)沒(méi)有孩子的結(jié)點(diǎn)。中序：從根結(jié)點(diǎn)出發(fā)，沿著右鏈走，找到一個(gè)沒(méi)有右孩子的結(jié)點(diǎn);后序：根結(jié)點(diǎn)；二叉樹(shù)遍歷方法比較（續(xù)）ADBC65二叉樹(shù)遍歷的基礎(chǔ)，可以在，如：“遍歷”是二叉樹(shù)遍歷過(guò)程中對(duì)結(jié)點(diǎn)進(jìn)行對(duì)于一棵已知樹(shù)可求結(jié)點(diǎn)的雙親；求結(jié)點(diǎn)的孩子結(jié)點(diǎn)；判定結(jié)點(diǎn)所在層次。反之，也可在遍歷過(guò)程中生成結(jié)點(diǎn)，建立二叉樹(shù)的

結(jié)構(gòu)。66先序序列產(chǎn)生二叉樹(shù)的二叉鏈表Status

CreateBiTree(BiTree

&T){scanf(&ch);if(ch

==

‘#‘)

T

=NULL;else{if(!(T=(BiTNode

*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data

=

ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}return

OK;}//CreateBiTreeABC

DE字符輸入順序：AB

C##D#E###67按層次遍歷二叉樹(shù)-+/a*b-efc

d層次遍歷：-+/a

*

e

fb–c

d68二叉樹(shù)構(gòu)造一棵二叉樹(shù)可確定唯一的先(中、后)序序列由一個(gè)單獨(dú)的先(中、后)序序列一般不能唯一地確定一棵二叉樹(shù)；先序+中序或后序+中序均可唯一地確定一棵二叉樹(shù)。已知二叉樹(shù)的：先序序列：AB后序序列：BA構(gòu)造的二叉樹(shù)如右圖所示：69二叉樹(shù)構(gòu)造（續(xù)）70已知二叉樹(shù)的：先序序列：ABCDEFGHI中序序列：BCAEDGHFI構(gòu)造的二叉樹(shù)如下圖所示：二叉樹(shù)遍歷的時(shí)間和空間復(fù)雜度時(shí)間復(fù)雜度基本操作是

結(jié)點(diǎn)不論哪種次序進(jìn)行遍歷，對(duì)于含有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其時(shí)間復(fù)雜度均為O(n)。空間復(fù)雜度所需輔助空間為遍歷過(guò)程中棧的最大容量，即樹(shù)的深度。情況下為n，所以其空間復(fù)雜度也為O(n)。71線索二叉樹(shù)遍歷二叉樹(shù)實(shí)質(zhì)對(duì)一個(gè)非線性結(jié)構(gòu)進(jìn)行線性化操作使每個(gè)結(jié)點(diǎn)(除第一個(gè)和最后一個(gè)外）在這些線性序列中有且僅有一個(gè)直接前驅(qū)和直接后繼（以后將分別簡(jiǎn)稱為“前驅(qū)”和“后繼”）。以二叉鏈表作為結(jié)構(gòu)時(shí)，只能找到結(jié)點(diǎn)的左右孩子信息，不能直接得到結(jié)點(diǎn)在任一序列中的前驅(qū)和后繼信息。如何遍歷過(guò)程中得到的關(guān)于結(jié)點(diǎn)的前驅(qū)和后繼信息？線索二叉樹(shù)。72線索二叉樹(shù)定義結(jié)構(gòu)作如下規(guī)定對(duì)二叉樹(shù)的若結(jié)點(diǎn)有左

，則其lchild域指示其左孩子，否則令lchild域指示其前驅(qū)；若結(jié)點(diǎn)有右

，則其rchild域指示其右孩子，否則令rchild域指示其后繼。在結(jié)點(diǎn)結(jié)構(gòu)中增加兩個(gè)標(biāo)志域lchildLTagdataRTagrchildRTag

0lchild域指示結(jié)點(diǎn)的左孩子1

lchild域指示結(jié)點(diǎn)的前驅(qū)rchild域指示結(jié)點(diǎn)的右孩子1

rchild域指示結(jié)點(diǎn)的后繼LTag

073線索二叉樹(shù)定義（續(xù)）以上述結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹(shù)的

結(jié)構(gòu)，叫做線索鏈表指向結(jié)點(diǎn)前驅(qū)和后繼的指針，叫做線索。加上線索的二叉樹(shù)稱之為線索二叉樹(shù)。對(duì)二叉樹(shù)以某種次序遍歷使其變?yōu)榫€索二叉樹(shù)的過(guò)程叫做線索化。7475線索二叉樹(shù)生成步驟按二叉樹(shù)相應(yīng)位置畫(huà)出每個(gè)結(jié)點(diǎn)結(jié)構(gòu)（包括五個(gè)域），標(biāo)出結(jié)點(diǎn)值及非空指針域；將非空指針域?qū)?yīng)標(biāo)志位寫(xiě)0；將空指針域?qū)?yīng)標(biāo)志位寫(xiě)1；寫(xiě)出先序序列；對(duì)應(yīng)先序序列將原來(lái)的空指針域改為指向結(jié)點(diǎn)前驅(qū)或后繼的線索；找不到前驅(qū)或后繼的空指針域仍為空。線索二叉樹(shù)示例（先序）ABDCE0A01B00D11C11E1^T76先序序列：ABCDE先序線索二叉樹(shù)線索二叉樹(shù)示例（中序）ABDC

ECE0A0T中序序列：BCAED中序線索二叉樹(shù)110D1^11^1B077線索二叉樹(shù)示例（后序）ABDC

ECE0A01B00D1T后序序列：CBEDA后序線索二叉樹(shù)1111^78帶表頭結(jié)點(diǎn)的線索二叉樹(shù)（中序）ABCDE0A01B00D11C11E1T中序序列：BCAED結(jié)點(diǎn)的中序線索二叉樹(shù)01頭結(jié)點(diǎn)：LTag=0,lchild指向根結(jié)點(diǎn);RTag=1,rchild指向遍歷序列中最后一個(gè)結(jié)點(diǎn);遍歷序列中第一個(gè)結(jié)點(diǎn)的lchild域和最后一個(gè)結(jié)點(diǎn)的rchild域都指向頭結(jié)點(diǎn)79線索二叉樹(shù)

表示typedef

enum

PointerTag{Link=0,

Thread=1};//Link==0：指針，指向孩子結(jié)點(diǎn)//Thread==1:線索，指向前驅(qū)或后繼結(jié)點(diǎn)typedef

struct

BiThrNode{emTypestruct

BiThrNodePointerTagdata;*lchild,

*rchild;Ltag,

Rtag;}BiThrNode,

*BiThrTree80遍歷線索二叉樹(shù)說(shuō)明81步驟：先找到序列中的第一個(gè)結(jié)點(diǎn)；然后依次找結(jié)點(diǎn)后繼直至其后繼為空時(shí)停止。從遍歷的第一個(gè)結(jié)點(diǎn)來(lái)看：先序序列中第一個(gè)結(jié)點(diǎn)必為根結(jié)點(diǎn);中、后序序列中第一個(gè)結(jié)點(diǎn)的左孩子定為空;從遍歷的最后一個(gè)結(jié)點(diǎn)來(lái)看：先、中序序列中最后一個(gè)結(jié)點(diǎn)的右孩子必為空;

后序序列中最后一個(gè)結(jié)點(diǎn)一定為根結(jié)點(diǎn);

遍歷線索二叉樹(shù)說(shuō)明（續(xù)）優(yōu)點(diǎn)：對(duì)于遍歷操作，線索樹(shù)優(yōu)于非線索樹(shù)；遍歷線索樹(shù)不用設(shè)棧。如果程序中所用二叉樹(shù)需經(jīng)常遍歷或查找結(jié)點(diǎn)在遍歷所得線性序列中的前驅(qū)或后繼，則應(yīng)采用線索鏈表作結(jié)構(gòu)。82遍歷中序線索二叉樹(shù)Status

InOrderTraverse_Thr(BiThrTree

T){p=T->lchild;

//T頭結(jié)點(diǎn),p指向根結(jié)點(diǎn);Link=0;

Thread=1;while(p!=T){ //空樹(shù)或遍歷結(jié)束時(shí)p==Twhile(p->LTag==Link) p=p->lchild;//找第一個(gè)結(jié)點(diǎn)

printf(“%c”,p->data);while(p->Rtag==Thread

&&

p->rchild

!=

T){p=

p->rchild;

printf(“%c”,

p->data);//

后繼結(jié)點(diǎn)}p

=p->rchild;}return

OK;}//

InOrderTraverse_Thr83遍歷先序線索二叉樹(shù)void

preorder_Thr(BiThrTree

T){

BiThrTree

p=T;printf("%c",p->data);while

(p->rchild){ if

(p->LTag==Link)else

p=p->rchild;printf("%c",p->data);}}p=p->lchild;T840A01B00D11C11E1^先序序列：ABCDE遍歷后序線索二叉樹(shù)85void

postorder_Thr(TriThrTree

T){

TriThrTree

f,p=T;do

{while

(p->LTag==Link)

p=p->lchild;if

(p->RTag==Link)

p=p->rchild;} //查找后序遍歷第一個(gè)結(jié)點(diǎn)while

(p->LTag!=Thread

||

p->RTag!=Thread);printf("%c",p->data);while

(p!=T){

if

(p->RTag==Link){

f=p->parent; if

(f->RTag==Thread

||

p==f->rchild)

p=f;

遍歷后序線索二叉樹(shù)（續(xù)）86else{p=f->rchild;do

{

while(p->LTag==Link)

p=p->lchild;if

(p->RTag==Link)

p=p->rchild;}while

(p->LTag!=Thread

||

p->RTag!=Thread);}}else

p=p->rchild;printf("%c",p->data);}

}

中序線索化二叉樹(shù)0A01B00D1中序序列：BCAED111

C1

E01線索化二叉樹(shù)實(shí)質(zhì)：將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索87T中序線索化二叉樹(shù)Status

InOrderThreading(BiThrTree

&Thrt,

BiThrTree

T){//生成

結(jié)點(diǎn)的線索化二叉樹(shù)if(!(Thrt

=

(BiThrTree)

malloc

(sizeof(BiThrNode))))exit(OVERFLOW);Thrt->Ltag

=

Link;Thrt->Rtag=Thread;//建立頭結(jié)點(diǎn)Thrt->rchild=Thrt; //右指針回指if(!T)Thrt->lchild=Thrt;//樹(shù)空左指針回指else{Thrt->lchild

=

T;pre

=

Thrt;

//

pre為全局變量InThreading(T); //中序遍歷線索化88中序線索化二叉樹(shù)（續(xù)）pre->rchild

=

Thrt;pre->Rtag

=

Thread;Thrt->rchild

=

pre;//pre為最后一個(gè)結(jié)點(diǎn)//最后一個(gè)結(jié)點(diǎn)線索化}return

OK;}//

InOrderThreadingvoid

InThreading(BiThrTree

p){//無(wú)頭結(jié)點(diǎn)的二叉樹(shù)中序線索化if(p){InThreading(p->lchild);//左線索化89中序線索化二叉樹(shù)（續(xù)）if(!p->lchild)

//前驅(qū)線索{p->Ltag=Thread;//原來(lái)標(biāo)志域?yàn)?p->lchild

=

pre;

//pre指向剛剛

過(guò)的結(jié)點(diǎn)}if(!pre->rchild)

//后繼線索{pre->Rtag

=

Thread;

pre->rchild

=

p;}pre

=

p; //保持pre指向p的前驅(qū)InThreading(p->rchild); //右

線索化}}90先序線索化二叉樹(shù)voidPreThreading(BiThrTree

P){ if

(P){ if

(!P->lchild){

P->LTag=Thre

->lchild=pre;}if

(!P->rchild)P->RTag=Thread;if

(pre

&&

pre->RTag==Thread)

pre->rchild=P;pre=P;if

(P->LTag==Link)PreThreading(P->lchild);if

(P->RTag==Link)

PreThreading(P->rchild);}}9192后序線索化二叉樹(shù)voidPostThreading(TriThrTree

P){ if

(P){

PostThreading(P->lchild);PostThreading(P->rchild);if(!P->lchild){

P->LTag=Thread;

P->lchild=pre;}if

(!P->rchild)P->RTag=Thread;if

(pre

&&pre->RTag==Thread)pre->rchild=P;pre=P;}}提綱樹(shù)的定義和基本術(shù)語(yǔ)二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)樹(shù)和森林赫

樹(shù)及其應(yīng)用小結(jié)93樹(shù)和森林樹(shù)的

結(jié)構(gòu)雙親表示法孩子表示法孩子兄弟表示法（二叉鏈表表示法）森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)和森林的遍歷94雙親表示法在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)的位置。R-1A0B0C0D1E1F3G6H6K60123456789RD

EAB

CFG

H

K95雙親表示法說(shuō)明該

結(jié)構(gòu)中，PARENT(T,x)操作可以在常量時(shí)間內(nèi)實(shí)現(xiàn)。反復(fù)調(diào)用PARENT操作直到遇見(jiàn)無(wú)雙親的結(jié)點(diǎn)時(shí)，便找到了樹(shù)的根。在這種表示法中，求結(jié)點(diǎn)的孩子時(shí)需要遍歷整個(gè)結(jié)構(gòu)。96雙親表示法

表示#define

MAX_TREE_SIZE

100typedef

struct

PTNode{

//結(jié)點(diǎn)結(jié)構(gòu)emType

data;parent;

//雙親位置int}PTNode;typedef

struct{PTNodeint}PTree//樹(shù)結(jié)構(gòu)nodes[MAX_TREE_SIZE];r,n;

//根的位置和結(jié)點(diǎn)數(shù)97孩子表示法說(shuō)明使用多重鏈表表示樹(shù)，每個(gè)結(jié)點(diǎn)有多個(gè)指針域，每個(gè)指針指向一棵的根結(jié)點(diǎn)。其結(jié)點(diǎn)有如下兩種格式。第一種格式結(jié)點(diǎn)同構(gòu)，鏈表中會(huì)產(chǎn)生許多空鏈域，浪費(fèi)空間；第二種格式結(jié)點(diǎn)不同構(gòu)，空間比較節(jié)約，但操作不方便。d

hild1child2…childddatadegreechild1child2…childd98孩子鏈表表示法每個(gè)結(jié)點(diǎn)的孩子排列起來(lái)，看成一個(gè)線性表，以單鏈表作為

結(jié)構(gòu)。則n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表（葉子的孩子鏈表為空表）。n個(gè)頭指針又組成一個(gè)線性表，為便于查找，可采用順序

結(jié)構(gòu)。99孩子鏈表表示法RD

EA

B

CFG

H

KABΛCDΛREΛFGΛHΛKΛ012345678935

Λ6

Λ012

Λ789

Λ100孩子鏈表

表示typedef

struct

CTNode{//孩子結(jié)構(gòu)intstructchild;CTNode

*next;data;child;}*ChildPtr;typedef

struct{emTypeChildPtr}CTBox;typedef

struct{CTBoxint//孩子鏈表頭指針nodes[MAX_TREE_SIZE];n,r;

//結(jié)點(diǎn)數(shù)和根的位置;

}CTree;

101孩子兄弟表示法定義又稱二叉樹(shù)表示法，或二叉鏈表表示法。以二叉鏈表做樹(shù)的結(jié)構(gòu)，鏈表中的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。AB

C

EDBΛCΛEΛΛAΛDΛ102孩子兄弟表示法這種結(jié)構(gòu)便于實(shí)現(xiàn)各種樹(shù)的操作。易于實(shí)現(xiàn)找結(jié)點(diǎn)孩子等的操作。例如要結(jié)點(diǎn)

x的第i個(gè)孩子，則只要先從child域找到第1個(gè)孩子，然后沿著孩子結(jié)點(diǎn)的nextsibling域連續(xù)走i-1步，便可找到x的第i個(gè)孩子。如果為每個(gè)結(jié)點(diǎn)增設(shè)一個(gè)PARENT域，則同樣能方便地實(shí)現(xiàn)PARENT(T,x)操作。103孩子兄弟表示法示例RD

EA

B

CFG

H

KR

ΛA

?Λ

D

?

Λ

B

?ΛEΛC

ΛF

ΛΛ

G

?Λ

H

?ΛKΛ104孩子兄弟

表示typedef

struct

CSNode{child,

*nextsibling;ElemType

data;struct

CSNode

*}CSNode,

*CSTree;105106森林與二叉樹(shù)的轉(zhuǎn)換二叉鏈表的橋梁作用樹(shù)與二叉樹(shù)的對(duì)應(yīng)關(guān)系示例森林與二叉樹(shù)：對(duì)應(yīng)關(guān)系示例；轉(zhuǎn)換規(guī)則：森林

二叉樹(shù)；二叉樹(shù)

森林二叉鏈表的橋梁作用由于二叉樹(shù)和樹(shù)都可用二叉鏈表作為結(jié)構(gòu)，則以二叉鏈表作為媒介可導(dǎo)出樹(shù)與二叉

樹(shù)之間的一個(gè)對(duì)應(yīng)關(guān)系。也就是說(shuō)，給定一棵樹(shù)，可以找到唯一的一棵二叉樹(shù)與之對(duì)應(yīng)。從物理結(jié)構(gòu)來(lái)看，他們的二叉鏈表是相同的，只是解釋不同而已。107樹(shù)與二叉樹(shù)的對(duì)應(yīng)關(guān)系示例AB

C

EDABCEDΛABΛCΛDΛΛEΛBΛCΛEΛΛAΛDΛΛAΛDΛCBΛΛEΛ108樹(shù)轉(zhuǎn)換成二叉樹(shù)的簡(jiǎn)單方法在同胞兄弟之間加連線；保留結(jié)點(diǎn)與第一個(gè)孩子之間的連線，去掉其余連線；將結(jié)點(diǎn)與孩子之間的連線調(diào)整為垂直線，將同胞兄弟之間的連線調(diào)整為水平線；以根結(jié)點(diǎn)為軸，順時(shí)針旋轉(zhuǎn)45度。ABCEDA.B.

CAB

C

EEDDAB

C

ED109森林與二叉樹(shù)的對(duì)應(yīng)關(guān)系示例因?yàn)闃?shù)的根結(jié)點(diǎn)無(wú)兄弟結(jié)點(diǎn)，因此其對(duì)應(yīng)的二叉樹(shù)的右

必為空。若把森林中的第二棵樹(shù)的根結(jié)點(diǎn)看成是第一棵樹(shù)的根結(jié)點(diǎn)的兄弟(又一前提假設(shè))，則同樣可以導(dǎo)出森林與二叉樹(shù)之間的對(duì)應(yīng)關(guān)系。110森林與二叉樹(shù)的對(duì)應(yīng)關(guān)系示例AB

C

DEGF

H

IJABCDEFGHIJABCDEF

GHIJ111森林轉(zhuǎn)換成二叉樹(shù)如果F={T1,T2,…,Tm}是森林,其對(duì)應(yīng)的二叉樹(shù)設(shè)為B=(root,

LB,RB),

則若F為空，即m=0,則B為空樹(shù)；若F非空，即m不等于0，則B的根root即為森林中第一棵樹(shù)T1的根ROOT(T1)；B的左

LB是從T1中根結(jié)點(diǎn)的

森林F1={T11,T12,

…,T1m’}轉(zhuǎn)換而成的二叉樹(shù);B的右

RB是從森林F’={T2,

T3,

…,Tm}轉(zhuǎn)換而成的二叉樹(shù)。112二叉樹(shù)轉(zhuǎn)換成森林AB

C

DEGF

H

IJABCDEF

GHIJ113二叉樹(shù)轉(zhuǎn)換成森林如果B=(root,

LB,RB)是一棵二叉樹(shù),其對(duì)應(yīng)的森林設(shè)為F={T1,T2,…,Tm},則若B為空,則F為空；若B非空，則F中第一棵樹(shù)T1的根ROOT(T1)即為二叉樹(shù)的根root;T1中的根結(jié)點(diǎn)的

森林F1是由B的左

LB轉(zhuǎn)換而成的森林;F中除T1之外其余樹(shù)組成的森林F’={T2,

T3,…,Tm}是由B的右

RB轉(zhuǎn)換而成的森林。114樹(shù)的遍歷先根(次序)遍歷樹(shù)先

樹(shù)的根結(jié)點(diǎn)，然后依。次先根遍歷根的每棵先根序列為:A

B

C

D

E后根(次序)遍歷樹(shù)先依次后根遍歷每棵，然后

樹(shù)的根結(jié)點(diǎn)。后根序列為:B

D

C

E

A注意：沒(méi)有中根(次序)！AB

C

ED115AB

C

ED樹(shù)的先根序列:A

B

CD

E樹(shù)的后根序列:B

D

C

E

AAEBCD二叉樹(shù)的先根序列：ABCDE二叉樹(shù)的中根序列：BDCEA二叉樹(shù)的后根序列:D

E

CB

A116樹(shù)的遍歷與對(duì)應(yīng)二叉樹(shù)遍歷關(guān)系先序遍歷森林B

C

D若森林非空,其遍歷規(guī)則為:森林中第一棵樹(shù)的根結(jié)點(diǎn);先序遍歷第一棵樹(shù)中根結(jié)點(diǎn)的森林;先序遍歷除去第一棵樹(shù)之后剩余樹(shù)構(gòu)成的森林;A

EGF

H

IJ先序序列為：A

B

C

D

E

F

G

H

I

J117中序遍歷森林B

C

D若森林非空,其遍歷規(guī)則為:中序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的

森林;第一棵樹(shù)的根結(jié)點(diǎn);中序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林;A

EGF

H

IJ中序序列為：B

CD

A

F

E

H

J

I

G118后序遍歷森林B

C

D若森林非空,其遍歷規(guī)則為:后序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的

森林;后序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林;第一棵樹(shù)的根結(jié)點(diǎn)。A

EGF

H

IJ后序序列為：D

C

BF

J

I

H

G

E

A119森林的先根序列:ABCDEFGHIJ森林的中根序列:BCDAFEHJIG森林的后根序列:DCBFJIHGEA二叉樹(shù)的先根序列：ABCDEFGHIJ二叉樹(shù)的中根序列：BCDAFEHJIG二叉樹(shù)的后根序列:DCBFJIHGEAAB

C

DEGF

H

IJABCDEFGHIJ森林的遍歷示例120121樹(shù)的遍歷小結(jié)樹(shù)的先根遍歷和后根遍歷即為其對(duì)應(yīng)的二叉樹(shù)的先序和中序遍歷；森林的先序、中序和后序遍歷即為其對(duì)應(yīng)的二叉樹(shù)的先序、中序和后序遍歷。提綱樹(shù)的定義和基本術(shù)語(yǔ)二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)樹(shù)和森林赫

樹(shù)及其應(yīng)用小結(jié)122曼樹(shù)及其應(yīng)用基本概念曼算法應(yīng)用實(shí)例：判定問(wèn)題曼編碼曼編碼的由來(lái)；示例；算法123曼樹(shù)基本概念從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑；路徑上的分支數(shù)目稱作路徑長(zhǎng)度。樹(shù)的路徑長(zhǎng)度是從樹(shù)根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。c

dba124曼樹(shù)基本概念結(jié)點(diǎn)帶權(quán)時(shí)，結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為從該結(jié)點(diǎn)到樹(shù)根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積。樹(shù)的帶權(quán)路徑長(zhǎng)度為樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，n通常記作WPL

w

l

k

k

k

1

c

dbaa7

5b2

4c

dWPL=7*2+5*2+2*2+4*2=36125曼樹(shù)定義i假設(shè)有n個(gè)權(quán)值{w1,w2,…,wn}，構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)，每個(gè)葉子結(jié)點(diǎn)帶權(quán)為w，則其中帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹(shù)稱作最優(yōu)二叉樹(shù)或

曼樹(shù)。7

a1265b2

c

d

4要使二叉樹(shù)WPL小,就須在構(gòu)造樹(shù)時(shí),將權(quán)值大的結(jié)點(diǎn)靠近根。曼樹(shù)對(duì)比a2

4c

d7

5b(a)5b2cd

4a7(b)da

7b5c

2

4(c)WPL=7*2

+

5*2

+

2*2

+

4*2=36WPL=7*3

+

5*3

+

2*1

+

4*2=46WPL=7*1

+

5*2

+

2*3

+

4*3=35127構(gòu)造

曼樹(shù)1.

根據(jù)給定的n個(gè)權(quán)值{w1,w2,...,wn}

構(gòu)成n棵二叉樹(shù)的集合F={T1,T2,...,Tn}，其中每棵二叉樹(shù)Ti只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右

為空在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作為左右構(gòu)造一棵新二叉樹(shù)，且置新二叉樹(shù)的根結(jié)點(diǎn)權(quán)值為其左右上根結(jié)點(diǎn)的權(quán)值之和；在F中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入到F中；重復(fù)上面2和3，直到F中只含一棵二叉樹(shù)為止。這棵二叉樹(shù)就是

曼樹(shù)。128構(gòu)造

曼樹(shù)7a5b2c4d7a5b2c4d67a5b2c4d6(1)117a5b4d611(2)182c(4)(3)129曼樹(shù)構(gòu)造過(guò)程示例(非唯一性)6

5

2

4a

b

c

dac

d6

5

6a

bda611bcc1dabcd117db11a

b

cc26da

b

cd217WPL1=6*1+5*2+2*3+4*3=34130WPL2=6*2+5*2+2*2+4*2=34練習(xí)：構(gòu)造

曼樹(shù)例197

8

112919115

3145

329835

37

81942142929157

858100判定問(wèn)題132在很多問(wèn)題的處理過(guò)程中，需要進(jìn)行大量的條件判斷，這些判斷結(jié)構(gòu)的設(shè)計(jì)直接影響著程序的執(zhí)行效率。例如，編程將百分制轉(zhuǎn)換成五個(gè)等級(jí)輸出。大家可能認(rèn)為這個(gè)程序很簡(jiǎn)單，并且很快就可以用下列形式編寫(xiě)出來(lái)：if

(score<60)

printf(“bad”);else

if

(score

<70)

printf(“pass”);else

if

(score<80)

printf(“general”);else

if

(score<90)

printf(“good”); esle

printf(“very

good”);

判定問(wèn)題（續(xù)）實(shí)際應(yīng)用中，往往各個(gè)分?jǐn)?shù)段的分布并不是均勻的。例如：為了使程序運(yùn)行的更有效率（也就是盡量減少程序運(yùn)行過(guò)程中的比較次數(shù)），可以使用曼算法建立該問(wèn)題的最佳判定樹(shù)。分?jǐn)?shù)0-5960-6970-7980-8990-100比例數(shù)0.050.150.400.300.10133判定問(wèn)題（續(xù)）80≤a<90不及格優(yōu)秀及格良好中等YYY以5,15,40,30和10為權(quán)構(gòu)曼造一棵有5個(gè)結(jié)點(diǎn)的樹(shù)如下：70≤a<80Y

NN60≤a<70Na<60N將判定框中的兩次比較語(yǔ)句轉(zhuǎn)化為單次比較語(yǔ)句，得最終判定樹(shù)如下：a<80a<90a<70不及格優(yōu)秀及格良好中等YYa<60YYNNN134兩種編程方式比較次數(shù)對(duì)比a<80a<90a<70不及格優(yōu)秀及格良好中等YYa<60YYNNNYa<60不及格優(yōu)秀及格良好中等YYYNa<70Na<80Na<90N1*5+2*15+3*40+4*(30+10)=3152*(40+30+10)+3*(5+15)=220135分?jǐn)?shù)0-5960-6970-7980-8990-100比例數(shù)0.050.150.400.300.10曼編碼的由來(lái)在電文傳輸中，需要將電文中出現(xiàn)的每個(gè)字符進(jìn)行二進(jìn)制編碼，即將傳送的字符轉(zhuǎn)換成二進(jìn)制字符組成的字符串。例如，需傳送的電文為“ABACCDA”。只需兩個(gè)二進(jìn)制字符的因?yàn)橹挥?種字符，串即可分辨。設(shè)A、B、C、D的編碼分別為00、01、10、11。則上述7個(gè)字符的電文可轉(zhuǎn)換為

“00010010101100”。136曼編碼的由來(lái)（續(xù)）通常有兩類編碼方式。一種為等長(zhǎng)編碼，另一種為不等長(zhǎng)編碼。等長(zhǎng)編碼方式的特點(diǎn)是每個(gè)字符的編碼長(zhǎng)度相同（如上例中每個(gè)字符的編碼長(zhǎng)度均為2），這種編碼方式譯碼簡(jiǎn)單且具有唯一性，但編碼長(zhǎng)度并不是最短的。在傳送電文時(shí)，為了使其二進(jìn)制位數(shù)盡可能地少，可以使用不等長(zhǎng)編碼方式。其特點(diǎn)是每個(gè)字符的編碼長(zhǎng)度不等，使用頻度較高的字符分配一個(gè)相對(duì)比較短的編碼，使用頻度較低的字符分配一個(gè)比較長(zhǎng)的編碼。137曼編碼的由來(lái)（續(xù)）例如，

面的例子中，可以為A，B，C，D四個(gè)字符分別分配0，00，1，01，并可將7個(gè)字符電文“ABACCDA”用二進(jìn)制序列：000011010發(fā)送，其長(zhǎng)度只有9個(gè)二進(jìn)制位。但隨之帶來(lái)了一個(gè)問(wèn)題，接收方接到這段電文后無(wú)法進(jìn)行譯碼，因?yàn)闊o(wú)法斷定前4個(gè)字符串‘0000’該譯為‘AAAA’，或是‘ABA’，或是‘BB’。即譯碼不唯一。因此，在設(shè)計(jì)不等長(zhǎng)編碼時(shí)，必須滿足任一個(gè)字符的編碼都不是另一個(gè)字符的前綴，這種編碼也稱做前綴編碼。138如何得到前綴編碼？可以利用二叉樹(shù)設(shè)計(jì)二進(jìn)制的前綴編碼。假設(shè)如下圖所示的二叉樹(shù)，其4個(gè)葉子結(jié)點(diǎn)分別表示A、B、C、D，且約定左右分支分別表示字符‘0’,‘1’。則可以將從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑上分支字符組成的字符串作為該葉子結(jié)點(diǎn)字符的編碼。0

1a1390b10c編碼:

A(0)B(10)C(110)D(111)1d如何得到長(zhǎng)度最短的前綴編碼？假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為wi,其編碼長(zhǎng)度為li,電文中只有n種字符，則電文對(duì)應(yīng)到二叉樹(shù)上，若置wi為葉子結(jié)點(diǎn)的權(quán)，li為從根到葉子結(jié)點(diǎn)的路徑長(zhǎng)度。則上面的電文總長(zhǎng)恰好為二叉樹(shù)的帶權(quán)路徑長(zhǎng)度。由此可見(jiàn)，設(shè)計(jì)電文總長(zhǎng)最短的二進(jìn)制前綴編碼即為以n種字符出現(xiàn)的頻率作權(quán)，設(shè)計(jì)一棵赫夫曼樹(shù)的問(wèn)題，由此得到的二進(jìn)制前綴編碼便稱為曼編碼。n總長(zhǎng)為w

i

l

ii

1140曼編碼示例某通訊系統(tǒng)只可能出現(xiàn)8種字符，其概率分別為(0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11),

求其

曼編碼.設(shè)計(jì)過(guò)程為