第六章樹和二叉樹

考查目標(biāo)(一)樹的基本概念(二)二叉樹

1.二叉樹的定義及其主要特征

2.二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)

3.二叉樹的遍歷

4.線索二叉樹的基本概念和構(gòu)造(三)樹、森林

1.樹的存儲結(jié)構(gòu)

2.森林與二叉樹的轉(zhuǎn)換

3.樹和森林的遍歷(四)樹和二叉樹的應(yīng)用

1.二叉排序樹

2.平衡二叉樹

3.哈夫曼(Huffman)樹和哈夫曼編碼

6.1樹的類型定義6.2二叉樹的類型定義6.3

二叉樹的存儲結(jié)構(gòu)6.4二叉樹的遍歷6.5線索二叉樹6.6樹和森林的表示方法6.7樹和森林的遍歷6.8哈夫曼樹與哈夫曼編碼6.1樹的類型定義數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。

若D為空集，則稱為空樹。否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；

(2)當(dāng)n>1時，其余結(jié)點可分為m(m>0)個互不相交的有限集T1,T2,…,Tm，其中每一個子集本身又是一棵符合本定義的樹，稱為根root的子樹。

數(shù)據(jù)關(guān)系R：這個定義是遞歸的，我們用子樹來定義樹：只包含一個結(jié)點的樹必然僅由根組成，包含n>1個結(jié)點的樹借助于少于n個結(jié)點的樹來定義

北京大學(xué)信息學(xué)院版權(quán)所有，轉(zhuǎn)載或翻印必究Page9

樹形結(jié)構(gòu)的各種表示法（a）樹形表示法北京大學(xué)信息學(xué)院版權(quán)所有，轉(zhuǎn)載或翻印必究Page10

樹形結(jié)構(gòu)的各種表示法（b）文氏圖表示法北京大學(xué)信息學(xué)院版權(quán)所有，轉(zhuǎn)載或翻印必究Page11

樹形結(jié)構(gòu)的各種表示法（c）凹入表表示法北京大學(xué)信息學(xué)院版權(quán)所有，轉(zhuǎn)載或翻印必究Page12

樹形結(jié)構(gòu)的各種表示法(A(B(D)(E(I)(J)(F))(C(G)(H)))（d）嵌套括號表示法基本術(shù)語結(jié)點:結(jié)點的度:樹的度:葉子結(jié)點:分支結(jié)點:數(shù)據(jù)元素+若干指向子樹的分支分支的個數(shù)樹中所有結(jié)點的度的最大值度為零的結(jié)點度大于零的結(jié)點DHIJM(從根到結(jié)點的)路徑：孩子結(jié)點、雙親結(jié)點兄弟結(jié)點、堂兄弟祖先結(jié)點、子孫結(jié)點結(jié)點的層次:樹的深度：由從根到該結(jié)點所經(jīng)分支和結(jié)點構(gòu)成ABCDEFGHIJMKL假設(shè)根結(jié)點的層次為1，第l層的結(jié)點的子樹根結(jié)點的層次為l+1樹中葉子結(jié)點所在的最大層次(１)有確定的根；(２)樹根和子樹根之間為有向關(guān)系。有向樹：有序樹：子樹之間存在確定的次序關(guān)系。無序樹：子樹之間不存在確定的次序關(guān)系。任何一棵非空樹是一個二元組

Tree=（root，F(xiàn)）其中：root被稱為根結(jié)點

F被稱為子樹森林森林：是m（m≥0）棵互不相交的樹的集合ArootBCDEFGHIJMKLF北京大學(xué)信息學(xué)院版權(quán)所有，轉(zhuǎn)載或翻印必究Page18

自然界的樹和森林是不同的概念，而數(shù)據(jù)結(jié)構(gòu)的樹和森林只有微小的差別。刪去樹根，樹就變成森林。加上一個結(jié)點作樹根，森林就變成樹

基本操作：查找類

插入類刪除類

Root(T)//求樹的根結(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,Visit())//遍歷InitTree(&T)//初始化置空樹

插入類：CreateTree(&T,definition)//按定義構(gòu)造樹Assign(T,cur_e,value)//給當(dāng)前結(jié)點賦值InsertChild(&T,&p,i,c)//將以c為根的樹插入為結(jié)點p的第i棵子樹

ClearTree(&T)//將樹清空

刪除類：DestroyTree(&T)//銷毀樹的結(jié)構(gòu)DeleteChild(&T,&p,i)//刪除結(jié)點p的第i棵子樹對比樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)樹型結(jié)構(gòu)第一個數(shù)據(jù)元素

(無前驅(qū))

根結(jié)點

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

(無后繼)多個葉子結(jié)點

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

二叉樹的類型定義

二叉樹或為空樹，或是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。ABCDEFGHK根結(jié)點左子樹右子樹二叉樹的五種基本形態(tài)：N空樹只含根結(jié)點NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹

二叉樹的主要基本操作：查找類插入類刪除類

Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);

PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);二叉樹

的重要特性

性質(zhì)1：

在二叉樹的第i

層上至多有2i-1個結(jié)點。(i≥1)用歸納法證明：

歸納基礎(chǔ)：

歸納假設(shè)：

歸納證明：i=1

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

2i-1=20=1；假設(shè)對所有的i=k，結(jié)點數(shù)=2k-1成立；則第i=k+1層的結(jié)點數(shù)最多

=2k-12=2(k+1)-1

。性質(zhì)2：

深度為k的二叉樹上至多含2k-1個結(jié)點（k≥1）。證明：

基于上一條性質(zhì)，深度為k的二叉樹上的結(jié)點數(shù)至多為

20+21+

+2k-1=2k-1

。

性質(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+1。兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個結(jié)點的二叉樹。完全二叉樹：樹中所含的n個結(jié)點和滿二叉樹中編號為1至n的結(jié)點一一對應(yīng)。123456789101112131415abcdefghij

性質(zhì)4：

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

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

即

k-1≤log2n<k

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

+1。性質(zhì)5：若對含n個結(jié)點的完全二叉樹從上到下且從左至右進(jìn)行1

至n

的編號，則對完全二叉樹中任意一個編號為i

的結(jié)點：

(1)若i=1，則該結(jié)點是二叉樹的根，無雙親，否則，編號為i/2的結(jié)點為其雙親結(jié)點；

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

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

(3)若2i+1>n，則該結(jié)點無右孩子結(jié)點，

否則，編號為2i+1的結(jié)點為其右孩子結(jié)點。6.3二叉樹的存儲結(jié)構(gòu)二、二叉樹的鏈?zhǔn)酱鎯Ρ硎疽?、二叉樹的順序存儲表?/p>

為了查找方便，可以將樹中的所有結(jié)點依次自上而下，自左至右存儲在一個一維數(shù)組中，這樣每個結(jié)點子女的位置便可以通過數(shù)組的下標(biāo)來體現(xiàn)。1、完全二叉樹的順序存儲表示

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

ABCDEJOQ

012345678910111213FHLMNP012345678910111213#defineMAX_TREE_SIZE100//二叉樹的最大結(jié)點數(shù)typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0號單元存儲根結(jié)點SqBiTreebt;2、一般二叉樹的順序存儲ABCDEF

ABDCEF

0123456789101112131401326∧∧∧∧∧∧∧∧可見，順序表示用于完全二叉樹的存儲表示非常有效，單表示一般二叉樹，尤其是形態(tài)劇烈變化的二叉樹，存儲空間利用不是很理想。使用鏈?zhǔn)酱鎯Ρ硎?，可以克服這些缺點。二、二叉樹的鏈?zhǔn)酱鎯Ρ硎?.二叉鏈表2．三叉鏈表3．雙親鏈表ADEBCFrootlchilddatarchild結(jié)點結(jié)構(gòu):1.二叉鏈表N個結(jié)點的二叉鏈表中有N+1個空鏈域。typedefstruct

BiTNode

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

TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;lchilddatarchild結(jié)點結(jié)構(gòu):C語言的類型描述如下:ADEBCFroot2．三叉鏈表parent

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

typedefstruct

TriTNode

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

TElemTypedata;

structTriTN