第三學期-2課件數(shù)據(jù)結構7-chap

1第五章樹5.1

樹的概念5.2

二叉樹5.3二叉樹的遍歷5.4二叉樹其它運算5.7樹的 結構和運算退出5.1樹的概念5.1.1

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

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

F

GA的第1棵子樹CHI

JA的第3棵子樹

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

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

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

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

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

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

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

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

的非空二叉樹最多有2h

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

有n2個度為2的結點,則

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

,

則 為i

的結點具有以下性質:(1)

若 為i的結點有左孩子,則左孩子結點的若 為i

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

≦

n

,

則

為i

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

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

BinaryTreeData：

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

InitBTree(BTreeType

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

CreateBTree(BTreeType&

BT,

char*

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

BTreeEmpty(BTreeType

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

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

BTreeDepth(BTreeType

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

PrintBTree(BTreeType

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

ClearBTree(BTreeType&

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

BinaryTree5.2.4二叉樹的 結構一.順序 結構二.鏈式 結構10115.3

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

LDR中序(根)遍歷

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

前,

中):

規(guī)律(

中,

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

樹的

結構和運算樹的順序

結構樹的

結構1、標準形式2、廣義標準形式3、二叉樹表示形式14156.1二叉排序/搜索樹6.1.1

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

Sort

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

法)若二叉樹為空,則ki

作為該二叉樹的根結點；若二叉樹非空,

則將ki

與該二叉樹的根結點的值進行比較,

若ki

小于根結點的值,

則將ki到根結點的左子樹中;

否則,

將ki

到根結點的右子樹中。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：一棵二叉搜索樹，結點的類型BTreeNode，指向二叉排序樹的樹根結點的指針為BSTOperations：查找、更新、

和刪除end

BinaryTreestruct

BTreeNode{ElemType

data;BTreeNode

*left,

*right;};21int

Find(BTreeNode*

BST,

ElemType&

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

Update(BTreeNode*

BST,

cons emType&

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

Insert(BTreeNode*

&BST,

cons emType&

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

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

Delete(BTreeNode*

&BST,

cons emType&

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

二叉搜索樹的運算1查找2更新34刪除23241二叉搜索樹的查找查找關鍵字值等于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);}}算法的空間和時間復雜度為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;}算法的時間復雜度同遞歸算法O(log2n)~O(n)，空間復雜度為O(1)。25262二叉搜索樹的更新查找關鍵字值等于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ù)關鍵字值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);}算法的時間復雜度同查找操作。27void

Insert(BTreeNode*&

BST,

cons emType&

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

t=BST,*parent=NULL;//指針t指向待比較的結點while(t!=NULL){ //指針parent為t的雙親結點parent=t;if(item.key<t->data.key)t=t->left;elset=t->right;}//建立新結點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個結點的二叉搜索樹的算法void

CreateBSTree(BSTree

*&

BST,

ElemType

a[],

int

n){BST=NULL;for

(inti=0;

i<n;

i++)Insert(BST,

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

n)4

二叉搜索樹的刪除(本小節(jié)作為 內容)1、刪除的結點為葉子結點；2、刪除的結點為單支結點；3、刪除的結點為雙支結點：查找待刪除結點的中序前驅結點；將前驅結點的值賦予待刪除結點；用前驅結點的左子樹根結點代替前驅結點。30調用二叉搜索樹算法的程序舉例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<<“刪除關鍵字為28和20的元素后中序遍歷為：

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

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

607453422536

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

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

樹6.3.1

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

L

wi

lii

135LWPSGAMDF36圖6-8

三棵不同的帶權二叉樹37帶權路徑長度分別為（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)樹，是一種帶權路徑長度WPL最小的二叉樹。利用

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

樹，則得到圖

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

構造

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

編碼從根結點到葉子結點所經分支的

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

WPL

k

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

0.29,

0.07,

0.08,

0.14,

0.23,

0.03,

0.11設計

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

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

B,

J,

E,

A,

H,F,

I,

C,

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

結點在遍歷序列中的直接前驅和直接后繼;

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

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

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