数据结构-查找树

Chapter8searchtrees17

1722

19

6

11(a)

(b)6

9

615

3(c)

(d)Figure8-3invalidbinarysearchtreesAssume:TofindT,ComparingTwithroot,T<root

goleftT>root

go

rightAlgorithm

searchBST(val

root

<pointer>,val

argument<key>)Search

a

binary

search

tree

for

a

given

value

Preroot

is

the

root

to

a

binary

tree

orsubtree

argument

is

the

key

value

requested

Return

thenode

addressif

thevalue

isfoundNullif

thenode

isnot

in

the

tree1

if(root

is

null)1

return

null2end

if3

if

(argument<root->key)1return

searchBST(root->left,argument)4

else

if(argument>root->key)1

return

searchBST

(root->right,argument)

5

else1

return

root6

end

ifOperationsonbinarysearchtree

traversalsAlgorithms

areidentical

to

theones

in

chapter

7binary

search

treesearchalgorithmsFind

smallest

nodeFind

largest

nodeFind

requested

node●Insert

nodeSteps:1.Follow

the

branches

to

an

empty

subtree2.Insert

the

new

nodeAll

inserts

take

place

ata

leaf

or

aleaflike

node

thathas

onlyone

null

branchAfterinserting23238

44

1②

20358238)

44

12

2①

35Afterinserting

192318

4

1②

20

35Afterinserting.3819Note:node

withequalvaluesarefoundinthe

right

subtree52525②1

if(root

is

null)1

root

=new2

1else

pwalk

=root2

io

p(

k

a

ull)2

1

i

pl

key)3

else4end

P*alk=pwalk>isht3

end

loopLocationfornewnodefound4

if1

(n

k->el

f

pa

>key)5

el1s

->right

=new

6end

if3

end

if4returnwt-ent<nt>e-pareweftk->llk-wpwaey<lkw-aepwf(nlknwtpotlnaparepw1oAlgorithminsertBST(ref

root<pointer>,val

new

<pointer>)Insertnodecontainingnewdata

into

BSTusing

iterationPrerootisaddressof

firstnode

in

aBSTnewisaddressof

node

containingdatatobeinsertedPostnewnodeinsertedintothe

tree23Iterativeinsert(algorithm)end

insertBSTAlgorithm

8-4

iterativebinary

search

tree

insertwalk20parent

nul812new

一

19Finalpositionwhen

pwalk

nulRecursive

insertnode(algorithm)Algorithm

addBST(refroot

<pointer>,val

new

<pointer>)InsertnodecontainingnewdataintoBSTusingrecursionPrerootisaddressof

currentnodein

a

BSTnewisaddressof

nodecontainingdatatobe

insertedPostnewnodeinsertedintothetree1

if(root

is

null)i

root=new2

elselocate

null

subtreeforinsertion1

if(new->key<root->key)1

addBST(root->left,new)2

else1

addBST(root->right,new)3

end

if3end

if4returnend

insertBSTalgorithm8-5addnodeto

BST

recursivelyDelete

node1.locate

it●

2.delete:thereare4

possible

cases-The

node

has

no

children:set

the

delete

node's

parent

to

null,recycle

itsmemory,and

return-Has

only

a

right

subtree:attach

the

right

subtree

to

the

delete

node'sparent

and

recycle

its

memory.—Has

only

a

left

subtree:attach

the

left

subtree

to

the

delete

node's

parentand

recycle

its

memory.—Has

two

subtree:to

delete

a

node

from

the

middle

of

a

tree,to

keep

thebalance,we

must

find

a

node,...,two

ways:·Find

the

largest

node

in

the

deleted

node's

left

subtree,move

its

data

toreplace

the

deleted

node's

data·Find

the

smallest

node

in

the

deleted

node's

right

subtree,move

its

data

toreplace

the

deleted

node's

data—Regardless

of

which

logic

we

use,we

will

be

moving

data

from

a

leaf

orleaflike

node

that

can

be

deleted.(a)Deletenode(44)thathasnochildrenbefore

23

dltpt(44(12

152

12(b)Delete

node(44)with

no

left

childbefore

dltpt

|231441252(c)Delete

node(18)with

no

left

childtree

dltptr12

44

~8

区4区

区2江(d)Deletenode(23)withtwochildrenafterafterafter52afterdltptr23i44beforebefore1if

(root

is

null)1

return

false

Base

case

12endif

Nodenot

find3if(ditkey<root->data.key)1return

deleteBST

(root->left,dltkey)

4

elseif(dltkey

>root->data.key)1return

deleteBST

(root->right,dltkey)5

else//deletenodefound—testforleafnode1

if(root->left

null)3recycle(dltptr)4return

true2

1el

(t

o

ght

nuI)

Base

case

2tiroo->rti

ro

cy=crloe-l

rf)t

After

node

deleted4

return

true3

elsel/

odi

f

ot

a

leaf

(or

leaflike),find

largest

node

on

left

subtree

lo)de

found,move

data

and

delete

leafnode4re