1第五章樹5.1

樹的概念5.2

二叉樹5.3二叉樹的遍歷5.4二叉樹其它運算5.7樹的 結(jié)構(gòu)和運算退出5.1樹的概念5.1.1

樹的定義樹的遞歸定義：（1）樹由具有相同特性的數(shù)據(jù)元素（稱為結(jié)點）組成，結(jié)點個數(shù)為0時，稱為空樹；

（2）在一棵非空樹中有且僅有一個根root結(jié)點，除根結(jié)點外，其余結(jié)點可分為m(m≥0)個互不相交的子集，每個子集也是一棵樹，稱為子樹SubTree。2AXBE

F

GA的第1棵子樹CHI

JA的第3棵子樹

A的第2棵子樹樹(邏輯上)的特點有且僅有一個結(jié)點沒有前驅(qū)結(jié)點,該結(jié)點為樹的根結(jié)點。除了根結(jié)點外,每個結(jié)點有且僅有一個直接前驅(qū)結(jié)點。包括根結(jié)點在內(nèi)，每個結(jié)點可以有多個后繼結(jié)點。35.1.3基本名詞術(shù)語4結(jié)點的度：樹的度：葉結(jié)點：分支結(jié)點:層次的定義:樹的深度:

樹林(森林):樹的有序性:5.2二叉樹55.2.1

二叉樹的定義二叉樹為度為2的有序樹。遞歸定義：或者是一棵空樹，或者是一棵由根結(jié)點和兩棵互不相交的左、右子樹組成的非空樹。左、右子樹同樣也是二叉樹。左孩子leftchild，左子樹的根結(jié)點。右孩子right

child，右子樹的根結(jié)點。兩種特殊形態(tài)的二叉樹滿二叉樹若一棵二叉樹中的結(jié)點,或者為葉結(jié)點， 或者具有兩棵非空子樹,

并且葉結(jié)點都集中在二叉樹的最下面一層.

這樣的二叉樹為滿二叉樹.完全二叉樹若一棵二叉樹中只有最下面兩層的結(jié)點的度可以小于2,并且最下面一層的結(jié)點(葉結(jié)點)都依次排列在該層從左至右的位置上。這樣的二叉樹為6

完全二叉樹.一棵非空二叉樹的第i

層最多有2i–1個結(jié)點(i1)。5.2.2二叉樹的性質(zhì)深度為h

的非空二叉樹最多有2h

-1個結(jié)點.若非空二叉樹有n0個葉結(jié)點,

有n2個度為2的結(jié)點,則

n0=n2+17具有n個結(jié)點的完全二叉樹的深度h=log2n+1.若對具有n個結(jié)點的完全二叉樹按照層次從上到下,每層從左到右的順序進行

,

則 為i

的結(jié)點具有以下性質(zhì):(1)

若 為i的結(jié)點有左孩子,則左孩子結(jié)點的若 為i

的結(jié)點有右孩子,則右孩子結(jié)點的為2i;為2i+1.(2)除樹根結(jié)點外,若一個結(jié)點的標號為i,則它的雙親結(jié)點的為i/2,為i/2,也就是說,當(dāng)i為偶數(shù)時,其雙親結(jié)點的它是雙親結(jié)點的左孩子,當(dāng)i為奇數(shù)時,其雙親結(jié)點的為(i-1)/2,它是雙親結(jié)點的右孩子.若i≦|_n/2_|,即2i

≦

n

,

則

為i

的結(jié)點為分支結(jié)點,否則為葉子結(jié)點.若n為奇數(shù),則每個分支結(jié)點都既有左孩子,又有右孩子;若n為偶數(shù),則 最大的分支結(jié)點( 為n/2)只有左孩子,沒有右孩子,其余分支結(jié)點左、右孩子都有.895.2.3

二叉樹的抽象數(shù)據(jù)類型ADT

BinaryTreeData：

類型BTreeType，用BT標識符表示Operations：void

InitBTree(BTreeType

&BT);//初始化一棵二叉樹，即置為空樹void

CreateBTree(BTreeType&

BT,

char*

a);//根據(jù)字符串a(chǎn)建立一棵二叉樹int

BTreeEmpty(BTreeType

BT);//判斷一棵二叉樹是否為空樹voidTraverseBTree(BTreeType

BT);//按照一定次序遍歷二叉樹int

BTreeDepth(BTreeType

BT);//求一棵二叉樹的深度void

PrintBTree(BTreeType

BT);//按照一種表示方法輸出二叉樹void

ClearBTree(BTreeType&

BT);//清除二叉樹中所有結(jié)點，使之為空樹end

BinaryTree5.2.4二叉樹的 結(jié)構(gòu)一.順序 結(jié)構(gòu)二.鏈式 結(jié)構(gòu)10115.3

二叉樹遍歷DLR前序(根)遍歷

LDR中序(根)遍歷

LRD后序(根)遍歷層次遍歷如何由遍歷序列恢復(fù)二叉樹？規(guī)律(

前,

中):

規(guī)律(

中,

后):序序列中找根;到中序序列中分左右。在后序序列中找根;到中序序列中分左右。125.4二叉樹的其它運算初始化二叉樹建立二叉樹判斷一棵二叉樹是否為空樹求二叉樹的深度查找二叉樹中值為x的結(jié)點輸出二叉樹清除二叉樹,使之變?yōu)橐豢每諛?35.5

樹的

結(jié)構(gòu)和運算樹的順序

結(jié)構(gòu)樹的

結(jié)構(gòu)1、標準形式2、廣義標準形式3、二叉樹表示形式14156.1二叉排序/搜索樹6.1.1

二叉排序/搜索樹的定義二叉排序樹Binary

Sort

Tree：或者為一棵空樹，或者為具有下列特性的非空樹：1、若其左子樹非空，則左子樹上的所有結(jié)點的關(guān)鍵字值均小于根結(jié)點關(guān)鍵字值；2、若其右子樹非空，則右子樹上的所有結(jié)點的關(guān)鍵字值均大于等于根結(jié)點關(guān)鍵字值；3、其左、右子樹分別為二叉排序樹。16對它進行中序遍歷：12，15，18，23，26，30，52，63，74得到有序序列17二叉搜索樹的建立(逐點

法)若二叉樹為空,則ki

作為該二叉樹的根結(jié)點；若二叉樹非空,

則將ki

與該二叉樹的根結(jié)點的值進行比較,

若ki

小于根結(jié)點的值,

則將ki到根結(jié)點的左子樹中;

否則,

將ki

到根結(jié)點的右子樹中。18例1

K

=

(

50,

35,

70,

40,

50,

65,

20,

80

)4070355050

50

5035

35

7040

507035506540

507035506520

40

507035506520

40

50

80703550193090^

100

^T50^10^70

^^

60

^p^80^p^80^item=80206.1.2

二叉搜索樹的抽象數(shù)據(jù)類型ADT

BinaryTreeData：一棵二叉搜索樹，結(jié)點的類型BTreeNode，指向二叉排序樹的樹根結(jié)點的指針為BSTOperations：查找、更新、

和刪除end

BinaryTreestruct

BTreeNode{ElemType

data;BTreeNode

*left,

*right;};21int

Find(BTreeNode*

BST,

ElemType&

item);//查找關(guān)鍵字值等于item.key的數(shù)據(jù)元素，成功返回真//并由item返回元素值。int

Update(BTreeNode*

BST,

cons emType&

item);//查找關(guān)鍵字值等于item.key的數(shù)據(jù)元素，成功返回真//并用item重寫數(shù)據(jù)元素值。void

Insert(BTreeNode*

&BST,

cons emType&

item);//根據(jù)關(guān)鍵字值item.key向二叉排序樹

數(shù)據(jù)元素。int

Delete(BTreeNode*

&BST,

cons emType&

item);//刪除關(guān)鍵字值為item.key的第一個數(shù)據(jù)元素。226.1.3

二叉搜索樹的運算1查找2更新34刪除23241二叉搜索樹的查找查找關(guān)鍵字值等于item.key的數(shù)據(jù)元素，成功返回真，并由item返回元素值。int

Find(BTreeNode*

BST,

ElemType&

item){//遞歸算法

if(BST==NULL)return

0;else

{if(item.key==BST->data.key){item=BST->data;return

1;

}else

if(item.key<BST->data.key)return

Find(BST->left,item);elsereturn

Find(BST->right,item);}}算法的空間和時間復(fù)雜度為O(log2n)~O(n)，平均為O(log2n)int

Find(BTreeNode*

BST,

ElemType&

item){//非遞歸算法while(BST!=NULL){if(item.key==BST->data.key){item=BST->data;return

1;}else

if(item.key<BST->data.key)BST=BST->left;elseBST=BST->right;}return

0;}算法的時間復(fù)雜度同遞歸算法O(log2n)~O(n)，空間復(fù)雜度為O(1)。25262二叉搜索樹的更新查找關(guān)鍵字值等于item.key的數(shù)據(jù)元素，成功返回真，并用item重寫數(shù)據(jù)元素值。int

Update(BTreeNode*

BST,

cons{if(BST==NULL)

return

0;else

{emType

item)if(item.key==BST->data.key){BST->data=item; return

1;}else

if(item.key<BST->data.key)return

Update(BST->left,item);elsereturn

Update(BST->right,item);

}}3

二叉搜索樹的根據(jù)關(guān)鍵字值item.key向二叉排序樹 數(shù)據(jù)元素。void

Insert(BTreeNode*&

BST,

cons{if(BST==NULL){emType&

item)BTreeNode*

p=new

BTreeNode;p->data=item;p->left=p->right=NULL;BST=p;}else

if(item.key<BST->data.key)Insert(BST->left,item);elseInsert(BST->right,item);}算法的時間復(fù)雜度同查找操作。27void

Insert(BTreeNode*&

BST,

cons emType&

item){ //非遞歸算法BTreeNode*

t=BST,*parent=NULL;//指針t指向待比較的結(jié)點while(t!=NULL){ //指針parent為t的雙親結(jié)點parent=t;if(item.key<t->data.key)t=t->left;elset=t->right;}//建立新結(jié)點pBTreeNode*

p=new

BTreeNode;p->data=item;p->left=p->right=NULL;if(parent==NULL)BST=p;else

if(item.key<parent->data.key)parent->left=p;elseparent->right=p;28}29生成一棵具有n個結(jié)點的二叉搜索樹的算法void

CreateBSTree(BSTree

*&

BST,

ElemType

a[],

int

n){BST=NULL;for

(inti=0;

i<n;

i++)Insert(BST,

a[i]);}一般而言，時間復(fù)雜度為O(n*log2

n)4

二叉搜索樹的刪除(本小節(jié)作為 內(nèi)容)1、刪除的結(jié)點為葉子結(jié)點；2、刪除的結(jié)點為單支結(jié)點；3、刪除的結(jié)點為雙支結(jié)點：查找待刪除結(jié)點的中序前驅(qū)結(jié)點；將前驅(qū)結(jié)點的值賦予待刪除結(jié)點；用前驅(qū)結(jié)點的左子樹根結(jié)點代替前驅(qū)結(jié)點。30調(diào)用二叉搜索樹算法的程序舉例void

main(){student

a[8]={{30,50},{20,70},{25,80},{23,40},{28,50},{15,90},{60,12},{48,60}};BTreeNode*

bst=NULL;student

x={28};student

y={20,37};CreateBSTree(bst,a,8);cout<<"中序遍歷："<<endl;Inorder(bst);cout<<endl;cout<<"深度為："<<BTreeDepth(bst)<<endl;if(Find1(bst,x))cout<<“查找成功！得到x為：(”<<x.key<<",“;cout<<x.rest<<')'<<endl;31if(Update1(bst,y)){cout<<"更新成功！"<<endl;Inorder(bst);cout<<endl;}Delete(bst,x);Delete(bst,y);cout<<“刪除關(guān)鍵字為28和20的元素后中序遍歷為：

”;cout<<endl;Inorder(bst);cout<<endl;cout<<"刪除后深度為："<<BTreeDepth(bst)<<endl;}326.2

堆堆（heap）分為小根堆和大根堆兩種，對于小根堆，它是具有如下特性的一顆完全二叉樹：1、若樹根存在左孩子，則根節(jié)點的值小于等于左孩子結(jié)點的值；2、若樹根存在右孩子，則根節(jié)點的值小于等于右孩子結(jié)點的值；3、以左、右孩子為根的子樹又各是一個堆。331826357348

607453422536

352018221、宜采用順序2、查找最大值或最小值最為方便3、

或刪除一個結(jié)點的時間復(fù)雜度為O(lbn)小根堆大根堆346.3

樹6.3.1

基本術(shù)語1、結(jié)點之間的路徑和路徑長度從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑，路徑上的分支的數(shù)目即稱作這兩個結(jié)點之間路徑長度。2、結(jié)點的權(quán)和帶權(quán)路徑長度從根結(jié)點到結(jié)點的路徑長度與結(jié)點的權(quán)的乘積。3、樹的帶權(quán)路徑長度樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，記作nWP

L

wi

lii

135LWPSGAMDF36圖6-8

三棵不同的帶權(quán)二叉樹37帶權(quán)路徑長度分別為（a）

WPL

=

7x2+

5x2+2x2

+

4x2=

36（b）

WPL

=

7x3

+

5x3

+2x1

+

4x2=

46（c）

WPL

=

7x1+

5x2+2x3+

4x3=

35可以驗證c為 樹。384、

樹（Huffman）樹，又稱最優(yōu)樹，是一種帶權(quán)路徑長度WPL最小的二叉樹。利用

樹可以得到最佳判定算法，例如編制一個將學(xué)生成績百分制轉(zhuǎn)換成五級分制的程序：分數(shù)0-5960-6970-7980-8990-100比例數(shù)0.050.150.400.300.10假設(shè)以5，15，40，30和10為權(quán)，構(gòu)造一棵帶有五個葉子結(jié)點的

樹，則得到圖

(b)所示判定過程。39(b)所示判定過程可使大部分數(shù)據(jù)經(jīng)過較少的比較次數(shù)即可得到結(jié)果。406.3.2

構(gòu)造

樹1、根據(jù)給定的n個權(quán)值{w1，w2，…，wn}，構(gòu)成n棵二叉樹的集合F={T1，T2，…，Tn}，其中每棵二叉樹Ti中只有一個帶權(quán)為wi的根結(jié)點，其左右子樹均為空；2、在F中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹構(gòu)成一棵新的二叉樹，且設(shè)新的二叉樹的根結(jié)點的權(quán)值為其左右子樹上根結(jié)點的權(quán)值之和；3、在F中刪除這兩棵樹，同時將新得到的二叉樹加入到F中；4、重復(fù)步驟2、3，直到F中只含一棵樹為止。此即為樹。41426.3.3

編碼從根結(jié)點到葉子結(jié)點所經(jīng)分支的

0、1編碼序列，代表葉子結(jié)點字符的編碼。等長編碼：任一字符的編碼長度相同無前綴編碼：任一字符的編碼都不是其它字符編碼的前綴所有的編碼都是無前綴編碼43樹構(gòu)造的用于通信的二進制編碼：利用編碼。編碼稱為用編碼傳送的電文長度最短：L為電文中字符總個數(shù)，wk某一字符在電文中出現(xiàn)次數(shù)，lk字符編碼長度。nL

WPL

k

1wklk44例、已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其概率分別為0.05,

0.29,

0.07,

0.08,

0.14,

0.23,

0.03,

0.11設(shè)計

編碼。設(shè)w=(5,29,7,8,14,23,3,11),n=845設(shè)w=(5,29,7,8,14,23,3,11),

n=846編碼特點1、無前綴編碼2、對應(yīng)的 樹不存在度數(shù)為1的結(jié)點476.44849中序序列：D,

B,

J,

E,

A,

H,F,

I,

C,

G按照某種遍歷順序遍歷一棵二叉樹，得到的序列可以看作一個線性表。表中結(jié)點有確定的前驅(qū)和后繼，如中序遍歷序列中，一個結(jié)點有其中序前驅(qū)結(jié)點，中序后繼結(jié)點。一.線索二叉樹利用二叉鏈表中空的指針域

結(jié)點在遍歷序列中的直接前驅(qū)和直接后繼;

這些指向前驅(qū)和后繼的指針稱為線索,

加了線索的二叉樹稱為線索二叉樹.二.線索二叉樹的構(gòu)造利用鏈結(jié)點的空的左指針域存放該結(jié)點的直接前驅(qū)的地址,空的右指針域存放該結(jié)點直接后繼的地址;

而非空的指針域仍然存放結(jié)點的左孩子或右孩子的地址.50ABCDEFJITGHABCDEFJITGH中序