計算機(jī)軟件及應(yīng)用溫大課件

審

他霞

琳

需

單#

掩包

K博印

H垂羋

衩

印小建耿

空長

單K

，羋食

犁H

料寸

E

Z

1

S?

s

缺5

n

l

Z

I

a

案

掩

博

srM艮

取

(1)樹的基本概念

樹是n(nK))個結(jié)點的有限集合T。當(dāng)n=0時，稱為空樹;

當(dāng)n>0時，該集合滿足如下條件：

(1)其中必有一個稱為根(root)的特定結(jié)點，它沒有直接

前驅(qū)，但有零個或多個直接后繼。

(2)其余個結(jié)點可以劃分成m(m>0)個互不相交的有

限集TLT2,T3,…，Tm,其中Ti又是一棵樹，稱為根root

的子樹。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但有零

個或多個直接后繼。

A

圖1樹的圖示方法

(2)樹的表示法

①樹型表示法：見右上角

②文氏圖表示法：

③廣義表表示法(嵌套括號表示法)

(A(B(E(K,L),F),C(G),D(H(M),I,J)))A

B

④凹入表表示法

E

F

C

D

(3)樹的相關(guān)術(shù)語

結(jié)點：數(shù)據(jù)元素+若干指向子樹的分支

結(jié)點的度：分支的個數(shù)

樹的度：樹中所有結(jié)點的度的最大值

葉子結(jié)點：度為零的結(jié)點

分支結(jié)點：度大于零的結(jié)點

（從根到結(jié)點的）路徑:

由從根到該結(jié)點

所經(jīng)分支和結(jié)點構(gòu)成

孩子結(jié)點、雙親結(jié)點

兄親結(jié)點、堂兄弟

祖兔結(jié)點、子孫結(jié)點

結(jié)點的層次：假設(shè)根結(jié)點的層次為1,第/

層的結(jié)點的子樹根結(jié)點的層

次為/+/

樹的深度：樹中葉子結(jié)點所在的最大層次

森林：

是m(m>0)棵互

不相交的樹的集合

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

Tree=(root,F)

其中：root被稱為根結(jié)點

F被稱為子樹森林

基本操作：

+查找類

+插入類

刪除類

查找類：

Root(T)11求樹的根結(jié)點

Value(T,cur_e)〃求當(dāng)前結(jié)點的元素值

Parent(T,cur_e)〃求當(dāng)前結(jié)點的雙親結(jié)點

LeftChild(T,cur_e)〃求當(dāng)前結(jié)點的最左孩子

RightSibling(T,cur_e)〃求當(dāng)前結(jié)點的右兄弟

TreeEmpty(T)〃判定樹是否為空樹

TreeDepth(T)〃求樹的深度

TraverseTree(T,VisitQ)//遍歷

插入類:

InitTree(&T)〃初始化置空樹

CreateTree(&T5definition)

//按定義構(gòu)造樹

Assign。，cure,value)

〃給當(dāng)前結(jié)點賦值

InsertChild(&T5&p,i,c)

//將以c為根的樹插入為結(jié)點p的第i棵子樹

刪除類：

ClearTree(&T)11將樹清空

DestroyTree(&T)〃銷毀樹的結(jié)構(gòu)

DeleteChild(&T,&p,i)

〃刪除結(jié)點p的第i棵子樹

對比樹型結(jié)構(gòu)和線性結(jié)構(gòu)

的結(jié)構(gòu)特點

構(gòu)

結(jié)

性

線

構(gòu)

結(jié)

赳

生樹

第

三

點

結(jié)

三根

前

）

驅(qū)

無

三（

三

結(jié)

個

點

子

葉

三多

）

繼

后

無

三（

素

元

據(jù)

數(shù)

它

其三

其

素

元

據(jù)

數(shù)

它

一

（

、

驅(qū)

前

個二

、

驅(qū)

前

個

一

三（

繼

）

后

個

一

）

繼

后

個

多

5.2.1二叉樹的定義與基本操作

二叉樹或為空樹，或是由一個根結(jié)點加上兩

棵分別稱為左子樹和右子樹的、互不交的二叉

樹組成。______

右子樹

左子樹

二叉樹的五種基本形態(tài):

二叉樹的主要基本操作:

步查找類

廣插入類

療刪除類

Root(T);Value(T,e);Parent(T5e);

LeftChild(T,e);RightChild(T,e);

LeftSibling(T,e);RightSibling(T,e);

BiTreeEmpty(T);BiTreeDepth(T);

PreOrderTraversedVisit());

InOrderTraverse(T5Visit());

PostOrderTraverse(T5Visit());

LevelOrderTraverse(T5VisitQ);

InitBiTree(&T);

Assign(T,&e,value);

CreateBiTree(&T,definition);

InsertChild(T,p,LR,c);

ClearBiTree(&T);

DestroyBiTree((&T);

DeleteChild(T,p,LR);

522二叉樹

的重要特性

?性質(zhì)1:

在二叉樹的第i層上至多有力1

個結(jié)點。(i>l)

用歸納法證明：

歸納基：層時，只有一個根結(jié)點：

2，"=2。=7;

歸納假設(shè)：假設(shè)對所有的y,l<j<i,命題成立;

歸納證明：二叉樹上每個結(jié)點至多有兩棵子樹，

則第，層的結(jié)點數(shù)=2%2=2iAo

■性質(zhì)2:

深度為k的二叉樹上至多含2仁1

個結(jié)點（k>l）。

證明：

基于上一條性質(zhì)，深度為人的二叉

樹上的結(jié)點數(shù)至多為

2°+2J+....+2肛1=2k-l。

?性質(zhì)3:

對任何一棵二叉樹，若它含有巧個葉

子結(jié)點、%個度為2的結(jié)點，則必存在

關(guān)系式：n0=n2+lo

證明：

設(shè)二叉樹上結(jié)點總數(shù)n=n0+H]+n2

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

而b=n-1=n0+Hj+n2-1

由此，n0=n2+1o

兩類特殊的二叉樹:

滿二叉樹：指的是深度

為〃且含有2個結(jié)點的

二叉樹。（離散數(shù)學(xué)中的

2元完全正則樹）89

完全二叉樹：樹

中所含的n個結(jié)點

和滿二叉樹中編號

為I至〃的結(jié)點一

一■對應(yīng)。

■性質(zhì)4:

具有n個結(jié)點的完全二叉樹的深度

為/log2nj+lo

證明：

設(shè)完全二叉樹的深度為k

則根據(jù)第二條性質(zhì)得2k'!<n<2k

即<log2n<k

因為人只能是整數(shù),因此，k=Llog2nJ+1o

■性質(zhì)5:

若對含〃個結(jié)點的完全二叉樹從上到下且從左

至右進(jìn)行I至n的編號，則對完全二叉樹中任意

一個編號為i的結(jié)點：

⑴若i=I,則該結(jié)點是二叉樹的根，無雙親，

否則，編號為Li/2」的結(jié)點為其雙親結(jié)點；

(2)若2，>〃，則該結(jié)點無左孩子，

否則，編號為2i的結(jié)點為其左孩子結(jié)點；

(3)若2計7>",則該結(jié)點無右孩子結(jié)點，

否則，編號為2升1的結(jié)點為其右孩子結(jié)點。

5.2.3

二叉樹的存儲結(jié)構(gòu)

一、二叉樹的順序

存儲表示

二、二叉樹的鏈?zhǔn)?/p>

存儲表示

一、二叉樹的順序存儲表示

#defineMAXTREESIZE100

〃二叉樹的最大結(jié)點數(shù)

typedefTElemTypeSqBiTree[MAX_

TREESIZE+l];

//1號單元存儲根結(jié)點

SqBiTreebt;

ABCDEFGHIJKL

123456789101112

ABCD

123456789101112131415

01234567891011121314

ABDCEF

二、二叉樹的鏈?zhǔn)酱鎯Ρ硎?/p>

1.二叉鏈表

2.三叉鏈表

1.二叉鏈表結(jié)點結(jié)構(gòu):

rootIchilddatarchild

C語言的類型描述如下：

typedefstructBiTNode{〃結(jié)點結(jié)構(gòu)

TElemTypedata;

structBiTNode*lchild,*rchild;

〃左右孩子指針

}BiTNode,*BiTree;

結(jié)點結(jié)構(gòu):

Ichilddatarchild

2.三叉鏈表結(jié)點結(jié)構(gòu):

C語言的類型描述如下:

typedefstructTriTNode{〃結(jié)點結(jié)構(gòu)

TElemTypedata;

structTriTNode*lchild,*rchild;

//左右孩子指針

structTriTNode*parent;〃雙親指針

}TriTNode,*TriTree;

結(jié)點結(jié)構(gòu)：parentIchilddatarchild

還可以用靜態(tài)三叉鏈表來表示

5.2.4

二叉樹的遍歷

一、問題的提出

順著某一條搜索路徑巡訪二叉樹

中的結(jié)點，使得每個結(jié)點均被訪問一

次，而且僅被訪問一次。

“訪問”的含義可以很廣，如：輸出結(jié)

點的信息等。

“通歷”是任何類型均有的操作,

對線性結(jié)構(gòu)而言，只有一條搜索路

徑（因為每個結(jié)點均只有一個后繼），

故不需要另加討論。而二叉樹是非

線性結(jié)構(gòu)，每個結(jié)點有兩個后繼，

則存在如何遍歷即按什么樣的搜索

路徑遍歷的問題。

對“二叉樹”而言，可以有

三條搜索路徑：

■1.先上后下的按層次遍歷；

■2.先左（子樹）后右（子樹）

的遍歷；

■3.先右（子樹）后左（子樹）

的遍歷。

二、先左后右的遍歷算法

先（根）序的遍歷算法

（根）序的遍歷算法

后（根）序的遍歷算法

先(根)序的遍歷算法：

若二叉樹為空樹，則空操作；否則,

(1)訪問根結(jié)點；

(2)先序遍歷左子樹；

(3)先序遍歷右子樹。

(根)序的遍歷算法:

若二叉樹為空樹，則空操作；否貝1,

(1)中序遍歷左子樹；'

(2)訪問根結(jié)點；

(3)中序遍歷右子樹。

9后(根)序的遍歷算法：

若二叉樹為空樹，則空操作；否貝I,

(1)后序遍歷左子樹；

(2)后序遍歷右子樹；

(3)訪問根結(jié)點。

對于如下圖所示的二叉樹，其先序、中序、后序遍歷的

序列如下:

先序遍歷:A、B、D、F、G、C、E、H。

中序遍歷:B、F、D、G、A、C、E、H。

后序遍歷:F、G、D、B、H、E、C、Ao

最早提出遍歷問題是對存儲在計算機(jī)中的表達(dá)式求值。例

如：（a+b*c）-d/e。該表達(dá)式用二叉樹表示下圖所示。當(dāng)我們

對此二叉樹進(jìn)行先序、中序、后序遍歷時，便可獲得表達(dá)式的

前綴、中綴、后綴書寫形式:

前綴：-+a*bc/de

中綴：a+b*c-d/e

后綴：abc*+de/-

其中中綴形式是算術(shù)表達(dá)式的通常形式，只是沒有括號。

前綴表達(dá)式稱為波蘭表達(dá)式。算術(shù)表達(dá)式的后綴表達(dá)式被稱作

逆波蘭表達(dá)式。在計算機(jī)內(nèi)，使用后綴表達(dá)式易于求值。

三、算法的遞歸描述

voidPreorderTravserse(BiTreeT)

{〃先序遍歷二叉樹

if⑴(

visit(T->data);11訪問結(jié)點

PreorderTravserse(T->lchild);

//遍歷左子樹

PreorderTravserse(T->rchild);

〃遍歷右子樹

voidInorderTravserse(BiTreeT)

{//中序遍歷二叉樹

if(T){

InorderTravserse(T->lchild);

〃遍歷左子樹

visit(T->data);//訪問結(jié)點

Inor