電

料K

K

K

低R

電

6.1樹的類型定義

6.2二叉樹的類型定義

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

6.4二叉樹的通歷

6.5線索二叉樹

6.6樹和森林的表示方法

6.7樹和森林的遍歷

6.8哈夫曼樹與哈夫曼編碼

U9

數(shù)據(jù)對象D:

D是具有相同特性的數(shù)據(jù)元素的集合。

數(shù)據(jù)關(guān)系R:

若D為空集，則稱為空樹。

否則：

(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root;

(2)當n>l時，其余結(jié)點可分為m(m>0)個互

不相交的有限集T\,T2,…,Tm，其中每一

棵子集本身又是一棵符合本定義的樹，

稱為根root的子樹。

基本操作：

+查找類

+插人類

+刪除類

查找類：

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

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

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

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

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

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

TreeDepth(T)〃求樹的深度

TraverseTree(T,VisitQ)//遍歷

插入類:

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

CreateTree(&T5definition)

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

Assign。，cure,value)

〃給當前結(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棵子樹

例如:A

樹根

T2

有向樹：

(1)有確定的根；

(2)樹根和子樹根之間為有向關(guān)系。

有序樹：

子樹之間存在確定的次序關(guān)系。

無序樹：

子樹之間不存在確定的次序關(guān)系。

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

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

構(gòu)

結(jié)

性

線

構(gòu)

結(jié)

赳

樹

第-

I

點

結(jié)

三根

前

）

驅(qū)

無

三（

三

結(jié)

個

點

子

葉

三多

）

繼

后

無

三（

素

元

據(jù)

數(shù)

它

其三

其

素

元

據(jù)

數(shù)

它

一

（

、

驅(qū)

前

個二

、

驅(qū)

前

個

一

三（

繼

）

后

個

一

）

繼

后

個

多

基本術(shù)語

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

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

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

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

?u)CJ

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

（從才艮到結(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被稱為子樹森林

M

收

潮

兼

招

K尊

H

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

點加上兩棵分別稱為左子樹和右子樹

的、互不交的二叉樹組成。

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

二叉樹的主要基本操作:

「查找類

r插入類

色刪除類

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);

二叉樹

的重要特性

?性質(zhì)1:

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

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

用歸納法證明：

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

2"1=2。=1;

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

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

則第，層的結(jié)點數(shù)=2"義2=2"o

■性質(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

兩類特殊的二叉樹：,>3

滿二叉樹：指的是

深度為兒且含有2乜?個?R

結(jié)點的二叉樹。

完全二叉樹：樹

中所含的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é)點的完全二叉樹從上到下且從左

至右進行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é)點。

6.3

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

一、二叉樹的順序

存儲表示

二、二叉樹的鏈式

存儲表示

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

#defineMAXTREESIZE100

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

typedefTElemTypeSqBiTree[MAX_

TREESIZE];

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

SqBiTreebt;

例如:

012345678910111213

ABDCEF

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

1.二叉鏈表3.雙親鏈表

2.三叉鏈表4.線索鏈表

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

3.雙親鏈表結(jié)點結(jié)構(gòu):

dataparentLRTag

o

1

2

3

4

5

6

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

TElemTypedata;

int*parent;//指向雙親的指針

charLRTag;〃左、右孩子標志域

}BPTNode

typedefstructBPTree{〃樹結(jié)構(gòu)

BPTNodenodes[MAXTREESIZE];

intnum_node;〃結(jié)點數(shù)目

introot;〃根結(jié)點的位置

}BPTree

3超

K

it

一、問題的提出

二、先左后右的遍歷算法

三、算法的遞歸描述

序遍歷算法的非遞歸描述

五、遍歷算法的應(yīng)用舉例

一、問題的提出

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

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

次，而且僅被訪問一次。

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

點的信息等。

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

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

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

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

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

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

路徑遍歷的問題。

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

三條搜索路徑：

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

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

的遍歷；

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

的遍歷。

二、先左后右的遍歷算法

先（根）序的遍歷算法

后（根）序的遍歷算法

。先(根)序的遍歷算法：

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

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

(2)先序遍歷左子樹；

(3)先序遍歷右子樹。

(根)序的遍歷算法:

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

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

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

(3)中序遍歷右子樹。

。后(根)序的遍歷算法:

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

(1)后序遍歷左子樹；

(2)后序遍歷右子樹；

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

遍歷二叉樹

例如，可以利用上面介紹的遍歷算法，寫出

如圖所示二叉樹的三種遍歷序列為：

先序遍歷序列：ABDGCEFH

中序遍歷序列：BGDAECFH??

后序遍歷序列：GDBEHFCA鼠

H

遍歷二叉樹

另外，在編譯原理中，有用二叉樹來表示一個算術(shù)

表達式的情形。在一棵二叉樹中，若用操作數(shù)代表

樹葉，運算符代表非葉子結(jié)點，則這樣的樹可以代

表一個算術(shù)表達式。若按前序、中序、后序?qū)υ摱?/p>

叉樹進行遍歷，則得到的遍歷序列分別稱為前綴表

達式（或稱波蘭式）、中綴表達式、后綴奏達式（遞波

蘭式）。（3

對應(yīng)的前綴表達式：-*abc。

對應(yīng)的中綴表達式：a*b-co

對應(yīng)的后綴表達式：ab*c-o0Q

三、算法的遞歸描述

voidPreorder(BiTreeT,

void(*visit)(TElemType&e))

{〃先序遍歷二叉樹

if(T){

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

Preorder(T->lc