数据结构课件-cs01版

CHAPTER5TREES§1Introduction1.TerminologyLinealTreePedigreeTree(binarytree)§1Introduction【Definition】Atreeisafinitesetofoneormorenodessuchthat:(1)Thereisaspeciallydesignednodecalledtheroot.(2)Theremainingnodesarepartitionedinton

0disjoint

setsT1,,Tn,whereeachofthesesetsisatree.Wecall

T1,,Tnthesubtreesoftheroot.Note:Subtreesmustnotconnecttogether.Thereforeeverynodeinthetreeistherootofsomesubtree.Normallytherootisdrawnatthetop.§1IntroductionACBDGFEHIJMLK3421Leveldegreeofanode::=numberofsubtreesofthenode.Forexample,degree(A)=3,degree(F)=0.degreeofatree::=

Forexample,degreeofthistree=3.leaf(terminalnode)::=anodewithdegree0.parent::=anodethathassubtrees.children::=therootsofthesubtreesofaparent.siblings::=childrenofthesameparent.ancestorsofanode::=allthenodesalongthepathfromthenodeuptotheroot.descendantsofanode::=allthenodesinitssubtrees.level::=level(parent)+1;level(root)=1.height(depth)::=max{levels}.§1Introduction2.RepresentationListRepresentationACBDGFEHIJMLK(A)(A(B,C,D))(A(B(E,F),C(G),D(H,I,J)))(A(B(E(K,L),F),C(G),D(H(M),I,J)))ABCDEFGHIJKLMSothesizeofeachnodedependsonthenumberofbranches.Hmmm...That’snotgood.§1IntroductionLeftChild-RightSiblingRepresentationleftchildrightsiblingdataACBDGFEHIJMLKNACBNDENKNNFNNGHNINNJNNLNNMNote:Therepresentationisnotuniquesincethechildreninatreecanbeofanyorder.§1IntroductionRepresentationasaDegree2Tree:Rotatetheleftchild-rightsiblingtreeclockwiseby45.NACBNDENKNNFNNGHNINNJNNLNNMNACBNDENKNNFNNGHNINNJNNLNNM45leftchildrightchilddataleftchildrightchildItsrightchildisalwaysemptyABinaryTree§2BinaryTrees1.ADTDefinitionstructure

Binary_Tree

isobjects:

Afinitesetofnodeseitheremptyorconsistingofarootnode,leftBinary_Tree,andrightBinary_Tree.functions:

forallbt,bt1,bt2

Binary_Tree,itemelementBinary_TreeCreate(

)

::=createsanemptybinarytreeBooleanIsEmpty(bt)::=

if

(bt==emptybinarytree)

return

TRUE

elsereturn

FALSE

Binary_TreeMakeBT

(bt1,item,bt2)::=

return

abinarytreewhoseleftsubtreeisbt1,whoserightsubtreeisbt2,andwhoserootnodecontainsthedataitem.structure

Binary_Tree

is(continued)functions:

Binary_TreeLchild(bt)::=

if

(IsEmpty(bt))

return

error

elsereturn

theleftsubtreeofbt.ElementData(bt)::=

if

(IsEmpty(bt))

return

error

elsereturn

thedataintherootnodeofbt.Binary_TreeRchild(bt)::=

if

(IsEmpty(bt))

return

error

elsereturn

therightsubtreeofbt.end

Binary_Tree§2BinaryTreesNote:Abinarytreecanbeempty,butatreemusthaveatleastonenode.Inatree,theorderofchildrendoesnotmatter.Butinabinarytree,leftchildandrightchildaredifferent.ABABandaretwodifferentbinarytrees.§2BinaryTreesSkewedBinaryTreesABCDABCDSkewedtotheleftSkewedtotherightCompleteBinaryTreesACGBDHEFIAlltheleafnodesareontwoadjacentlevels2.PropertiesofBinaryTreesThemaximumnumberofnodesonleveliis2i1,i1.Themaximumnumberofnodesinabinarytreeofdepthkis

2k1,k1.Proof:Byinduction.§2BinaryTreesForanynonemptybinarytree,n0=n2+1wheren0isthenumberofleafnodesandn2thenumberofnodesofdegree2.Proof:

Let

n1bethenumberofnodesofdegree1,andnthetotalnumberofnodes.Then

n=Let

Bbethenumberofbranches.Thenn~B?n=B+1.Sinceallbranchescomeoutofnodesofdegree1or2,wehaveB~n1

&n2

?B=n1

+

2n2.

123n0=n2+1

Afullbinarytreeofdepthkisabinarytreeofdepthkhaving2k1

nodes,k0.Abinarytreewithnnodesanddepthkiscompleteiffitsnodescorrespondtothenodesnumberedfrom1toninthefullbinarytreeofdepthk.489510116121371415231§2BinaryTrees3.BinaryTreeRepresentationsArrayRepresentation:BT[n+1](BT[0]isnotused)【Lemma】Ifacompletebinarytreewithnnodes(depth=log2

n+1)isrepresentedsequentially,thenforanynodewithindexi,1in,wehave:Proof:Byinduction.Oops!Herecomesthepickyguy.What’swrongwiththisrepresentationeh?Tellme,howlargemustthearraybetostoreaBTofdepth10?1024.WhatiftheBTisskewed?Gee