審

他霞

琳

需

單#

掩包

K博印

H垂羋

衩

印小建耿

空長

單K

，羋食

犁H

料寸

E

Z

1

S?

s

缺5

n

l

Z

I

a

案

掩

博

srM艮

取

(1)樹的基本概念

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

當n>0時，該集合滿足如下條件：

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

前驅，但有零個或多個直接后繼。

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

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

的子樹。每棵子樹的根結點有且僅有一個直接前驅，但有零

個或多個直接后繼。

A

圖1樹的圖示方法

(2)樹的表示法

①樹型表示法：見右上角

②文氏圖表示法：

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

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

B

④凹入表表示法

E

F

C

D

(3)樹的相關術語

結點：數據元素+若干指向子樹的分支

結點的度：分支的個數

樹的度：樹中所有結點的度的最大值

葉子結點：度為零的結點

分支結點：度大于零的結點

（從根到結點的）路徑:

由從根到該結點

所經分支和結點構成

孩子結點、雙親結點

兄親結點、堂兄弟

祖兔結點、子孫結點

結點的層次：假設根結點的層次為1,第/

層的結點的子樹根結點的層

次為/+/

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

森林：

是m(m>0)棵互

不相交的樹的集合

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

Tree=(root,F)

其中：root被稱為根結點

F被稱為子樹森林

基本操作：

+查找類

+插入類

刪除類

查找類：

Root(T)11求樹的根結點

Value(T,cur_e)〃求當前結點的元素值

Parent(T,cur_e)〃求當前結點的雙親結點

LeftChild(T,cur_e)〃求當前結點的最左孩子

RightSibling(T,cur_e)〃求當前結點的右兄弟

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

TreeDepth(T)〃求樹的深度

TraverseTree(T,VisitQ)//遍歷

插入類:

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

CreateTree(&T5definition)

//按定義構造樹

Assign。，cure,value)

〃給當前結點賦值

InsertChild(&T5&p,i,c)

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

刪除類：

ClearTree(&T)11將樹清空

DestroyTree(&T)〃銷毀樹的結構

DeleteChild(&T,&p,i)

〃刪除結點p的第i棵子樹

對比樹型結構和線性結構

的結構特點

構

結

性

線

構

結

赳

生樹

第

三

點

結

三根

前

）

驅

無

三（

三

結

個

點

子

葉

三多

）

繼

后

無

三（

素

元

據

數

它

其三

其

素

元

據

數

它

一

（

、

驅

前

個二

、

驅

前

個

一

三（

繼

）

后

個

一

）

繼

后

個

多

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

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

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

樹組成。______

右子樹

左子樹

二叉樹的五種基本形態:

二叉樹的主要基本操作:

步查找類

廣插入類

療刪除類

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二叉樹

的重要特性

?性質1:

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

個結點。(i>l)

用歸納法證明：

歸納基：層時，只有一個根結點：

2，"=2。=7;

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

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

則第，層的結點數=2%2=2iAo

■性質2:

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

個結點（k>l）。

證明：

基于上一條性質，深度為人的二叉

樹上的結點數至多為

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

?性質3:

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

子結點、%個度為2的結點，則必存在

關系式：n0=n2+lo

證明：

設二叉樹上結點總數n=n0+H]+n2

又二叉樹上分支總數b=tij+2n2

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

由此，n0=n2+1o

兩類特殊的二叉樹:

滿二叉樹：指的是深度

為〃且含有2個結點的

二叉樹。（離散數學中的

2元完全正則樹）89

完全二叉樹：樹

中所含的n個結點

和滿二叉樹中編號

為I至〃的結點一

一■對應。

■性質4:

具有n個結點的完全二叉樹的深度

為/log2nj+lo

證明：

設完全二叉樹的深度為k

則根據第二條性質得2k'!<n<2k

即<log2n<k

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

■性質5:

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

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

一個編號為i的結點：

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

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

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

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

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

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

5.2.3

二叉樹的存儲結構

一、二叉樹的順序

存儲表示

二、二叉樹的鏈式

存儲表示

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

#defineMAXTREESIZE100

〃二叉樹的最大結點數

typedefTElemTypeSqBiTree[MAX_

TREESIZE+l];

//1號單元存儲根結點

SqBiTreebt;

ABCDEFGHIJKL

123456789101112

ABCD

123456789101112131415

01234567891011121314

ABDCEF

二、二叉樹的鏈式存儲表示

1.二叉鏈表

2.三叉鏈表

1.二叉鏈表結點結構:

rootIchilddatarchild

C語言的類型描述如下：

typedefstructBiTNode{〃結點結構

TElemTypedata;

structBiTNode*lchild,*rchild;

〃左右孩子指針

}BiTNode,*BiTree;

結點結構:

Ichilddatarchild

2.三叉鏈表結點結構:

C語言的類型描述如下:

typedefstructTriTNode{〃結點結構

TElemTypedata;

structTriTNode*lchild,*rchild;

//左右孩子指針

structTriTNode*parent;〃雙親指針

}TriTNode,*TriTree;

結點結構：parentIchilddatarchild

還可以用靜態三叉鏈表來表示

5.2.4

二叉樹的遍歷

一、問題的提出

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

中的結點，使得每個結點均被訪問一

次，而且僅被訪問一次。

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

點的信息等。

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

對線性結構而言，只有一條搜索路

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

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

線性結構，每個結點有兩個后繼，

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

路徑遍歷的問題。

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

三條搜索路徑：

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

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

的遍歷；

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

的遍歷。

二、先左后右的遍歷算法

先（根）序的遍歷算法

（根）序的遍歷算法

后（根）序的遍歷算法

先(根)序的遍歷算法：

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

(1)訪問根結點；

(2)先序遍歷左子樹；

(3)先序遍歷右子樹。

(根)序的遍歷算法:

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

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

(2)訪問根結點；

(3)中序遍歷右子樹。

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

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

(1)后序遍歷左子樹；

(2)后序遍歷右子樹；

(3)訪問根結點。

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

序列如下:

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

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

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

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

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

對此二叉樹進行先序、中序、后序遍歷時，便可獲得表達式的

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

前綴：-+a*bc/de

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

后綴：abc*+de/-

其中中綴形式是算術表達式的通常形式，只是沒有括號。

前綴表達式稱為波蘭表達式。算術表達式的后綴表達式被稱作

逆波蘭表達式。在計算機內，使用后綴表達式易于求值。

三、算法的遞歸描述

voidPreorderTravserse(BiTreeT)

{〃先序遍歷二叉樹

if⑴(

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

PreorderTravserse(T->lchild);

//遍歷左子樹

PreorderTravserse(T->rchild);

〃遍歷右子樹

voidInorderTravserse(BiTreeT)

{//中序遍歷二叉樹

if(T){

InorderTravserse(T->lchild);

〃遍歷左子樹

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

Inor