動(dòng)態(tài)查找(共16張PPT)

7.3

動(dòng)態(tài)查找↓

7.3.1

二叉排序樹二叉排序樹是一種常用的動(dòng)態(tài)查找表，下面首先給出它的非遞歸形式。二叉排序樹是一棵二叉樹，它或者為資，或者具有如下性質(zhì)：(1)任一非終端結(jié)點(diǎn)若有左孩子，則該結(jié)點(diǎn)的關(guān)鍵字值大于其左孩子結(jié)點(diǎn)的關(guān)鍵字值。(2)任一非終端結(jié)點(diǎn)若有右孩子，則該結(jié)點(diǎn)的關(guān)鍵字值小于其右孩子結(jié)點(diǎn)的關(guān)鍵字值。二叉排序樹也可以用遞歸的形式定義，即二叉排序樹是一棵樹，它或者為空，或者具有如下性質(zhì)：(1)若它的左子樹非空，則其左子樹所有結(jié)點(diǎn)的關(guān)鍵字值均小于其根結(jié)點(diǎn)的關(guān)鍵字值。(2)若它的右子樹非空，則其右子樹所有結(jié)點(diǎn)的關(guān)鍵字值均大于其根結(jié)點(diǎn)的關(guān)鍵字值。(3)它的左右子樹都是二叉排序樹。

例如，由關(guān)鍵字值序列(62,15,68,46,65,12,57,79,35)構(gòu)成的一

棵排序樹如圖7-4所示?！?/p>

圖7-4如果對(duì)上述二叉排序樹進(jìn)行中根遍歷可以得到一個(gè)關(guān)鍵字有序序列(12815,35,46,57,62,65,68,79),這是十叉排序樹的一個(gè)重要特征，也正是由此將其稱為

“上叉排序樹”?！?/p>

7.3.2二叉排序樹的查找二叉排序樹的結(jié)構(gòu)定義中可看到：

一棵非空二叉排序樹中根結(jié)點(diǎn)的關(guān)鍵字值大于其左子樹上所有結(jié)

點(diǎn)的關(guān)鍵字值，而小于其右子樹上所有結(jié)點(diǎn)的關(guān)鍵字值，所以在二叉排序樹中查找一個(gè)關(guān)鍵字值為k

的結(jié)點(diǎn)的基本思想是：用給定值k

與根結(jié)點(diǎn)關(guān)鍵字值比較，

如果k小于根結(jié)點(diǎn)的值，則要找的結(jié)點(diǎn)只可能在左子樹中，所以繼續(xù)在左子樹中查找，否則將繼續(xù)在右子樹中查找，依此方法，查找下去，至直查找成功或查找失敗為止。二叉排序樹查找的過程描述如下：(1)若二叉樹為空樹，則查找失敗，(2)將給定值k

與根結(jié)點(diǎn)的關(guān)鍵字值比較，若相等，則查找成功，(3)若根結(jié)點(diǎn)的關(guān)鍵字值小于給定值k,

則在左子樹中繼續(xù)搜索，(4)否則，在右子樹中繼續(xù)查找。假定二叉排序樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的類型定義如下：typedef

struct

node

{keytype

key;↓

anytype

otheritem;u

struct

node

*|child;u

struct

node

*rchild;↓}Bin

Sort

Tree

Node

,*Bin

Sort

Tree二叉排序樹查找過程的描述是一個(gè)遞歸過程，若用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)，其查找操作的遞歸算法如下所示：Bi

n

Sort

Tree

Node

*bt

search(Bin

Sort

Tree

bt,keytype

k)」

{//在根指針為bt

的二叉排序樹上查找一個(gè)關(guān)鍵字值為k的結(jié)點(diǎn)，↓

//若查找成功返回指向該結(jié)點(diǎn)的指針，否則返回空指針if

(bt=NULL)l|(bt-key

==k)return

bt;↓

e

lse

if(k<

bt->

key)return

bt

search(bt->Ichild,k);

//在左子樹中搜索else

return

bt

search(bt->

rchild,k);//在右子樹中搜索這個(gè)過程也可以用非遞歸算法實(shí)現(xiàn)，算法描述如下：Bin

Sort

Tree

Node_

_

_*bt

search1(Bin

Sort

Tree

bt,

keytypek)」{p=

bt;

//指針p

損向根結(jié)點(diǎn)，搜索從根結(jié)點(diǎn)開始while(p!=

NULL&&/p}>key!=k

){if(k<p->key)p=p->Ichild;

else

p=

p->rchild;}return(p);

}

↓

7.3.3二叉排序樹的插入在一棵二叉排序樹中插入一個(gè)結(jié)點(diǎn)可以用一個(gè)遞歸的過程實(shí)現(xiàn)，即：若二叉排序樹為空，則新結(jié)點(diǎn)

作為二叉排序樹的根結(jié)點(diǎn)；杏則，若給定結(jié)點(diǎn)的關(guān)鍵

字值小于根結(jié)點(diǎn)關(guān)鍵字值，則插入在左子樹上；若給

定結(jié)點(diǎn)的關(guān)鍵字值大于根結(jié)點(diǎn)的值，則插入在右子樹上

。下面是二叉排序樹插入操作的遞歸算法。void

bt

insert1(Bin

Sort

Tree*bt,Bin

Sort

Tree

Node

*pn)」

{

/

/

在

以bt

為根的二叉排序樹上插入一個(gè)由指針pn

指向的新的結(jié)點(diǎn)↓

if(*bt

=NULL)*bt

=

pn;↓

else

if(*bt->

key>

pn->key)bt

insert1(&(*bt->Ichild),pn);else

if(*bt->

key<

pn->key)bt

insert1(&(*bt->

rchild),pn);□

這個(gè)算法也可以用非遞歸的形式實(shí)現(xiàn)，如下所示：void

bt

insert

2(Bin

Sort

Tree

*btBin

Sort

Tree

Node

*pn)」{↓

p=

bt;while(p!=

NULL&&p>key!=

pn-key)↓

{

q=p;u

if(p->key>pn-pkey)\p=p-chil

d;

else

p

=

p->

rchild;if(p=NULL){↓

if(q->key>pn->key)q->lchild

=

pn;↓

else

q->

rchild

=pn->key;利用二叉排序樹的插入算法，可以很容易地實(shí)現(xiàn)創(chuàng)建二叉排序樹的操作，其基本思想為：申一棵空二叉樹開始，經(jīng)過一系列的查找插入操作生成一棵二叉排序樹。例如，由結(jié)點(diǎn)關(guān)鍵字序列(62,15,68,46,65,12

,57,79,35)構(gòu)造二叉排序樹的過程為：從空二叉樹開始，依次將每個(gè)結(jié)點(diǎn)插入到二叉排序前審插入，在插入每個(gè)結(jié)點(diǎn)時(shí)都是從根結(jié)點(diǎn)開始搜索插入

位置，找到插入位置后，將新結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入，

經(jīng)過9次的查找和插入操作，/建成由這9個(gè)結(jié)點(diǎn)組成的二叉排序樹。創(chuàng)建二叉排序樹的算法如下：

B

in

Sort

Tree

Node/*bt

bulid

(Bin

Sort

Treea,

int

n)↓

{//在數(shù)組a

的a[1]~a[n]

單元中存放著將要構(gòu)成二

叉排序樹的n個(gè)結(jié)點(diǎn)內(nèi)容-

p->key

=a[l].key;p->

otheritem=

a[i].otheritem;;p->

Ichile

=

NULL;-

p->

rchile=

NUL;

bt_insert1(/&bt,

p);}return(bt);□

p=(Bin_Sort_Tree_Node)mallo

(siz

eof(Bin_Sort_Tree_Node));□

bt=NULL;for(i=1;i<={n;i++)c□

7.3.4二叉排序樹的刪除

下面分四種情況討論一下如何確保從二叉樹中

刪除一個(gè)結(jié)點(diǎn)后，不會(huì)影響二叉排序樹的性質(zhì)：

(1)若要?jiǎng)h除的結(jié)點(diǎn)為葉子結(jié)點(diǎn)，可以直接進(jìn)

行刪除。(2)若要?jiǎng)h除結(jié)點(diǎn)有右子樹，但