程序设计与算法基础课件.ppt

《程序设计与算法基础课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、程序设计与算法基础(4)潘爱民2006/10/16OutlinetreetreeBinarysearchtreeTreetraversalInsertioninabinarytreeDeletinginabinarytreeBalancingatreeSplaytreeHeaptreesThetreeinrealworldleavesrootbranchesThetreeincomputersciencerootleavesarcsnodesHierarchicalstructuresinrea

2、lworldCorporationorganizationUniversityorganizationMaildispatchingInternetThedatastructuresThelineardatastructureArrayLinkedlistInessence,stackandqueueoperateonalinearstructureTreeisanon-lineardatastructureAformaldefinitionoftreeAtreeconsistsofnodesa

3、ndarcs1.Anemptystructureisanemptytree2.Ift1,…,tk,aredisjointtrees,thenthestructurewhoseroothasasitschildrentherootsoft1,...,tkisalsoatree.3.Onlystructuresgeneratedbyrules1and2aretrees.ExamplesoftreesThetermsinatreeRoot:thetopelementifnotanemptytreeCh

4、ildren,parentGrandparent,siblings,…Path(foranode):auniquesequenceofarcsfromroottoanodeLength(forapath):thenumberofarcsinapathLevel(foranode):thelengthofthepathfromtheroottothenodeplus1,i.e.thenumberofnodesinthepathHeight(foratree):themaximumlevelofan

5、odeinthetreeFortheemptytree,theheightis0Forthetreewithasinglenode,theheightis1levelsLevel4Level3Level2PresidentVP1VP2VP3Manager1Manager2ManagerManagerWorkerBeeLevel1NotesaboutlevelsSometextsstartlevelnumbersat0ratherthanat1Rootisatlevel1.Itschildrena

6、reatlevel2.Thegrandchildrenoftherootareatlevel3.Andsoon.height=depth=numberoflevelsNodeDegree=NumberOfChildrenPresidentVP1VP2VP3Manager1Manager2ManagerManagerWorkerBee321100100TreeDegree=MaxNodeDegreeDegreeoftree=3.PresidentVP1VP2VP3Manager1Manager

7、2ManagerManagerWorkerBee321100100AbinarytreeDefinitionAbinarytreeisatreewhosenodeshaveatmosttwochildren(possiblyempty)AndeachchildisdesignedaseitheraleftchildorarightchildPropertiesofabinarytreeMinimumnumberofnodesinabinarytreewhoseheightishishMaximu

8、mnumberofnodesinabinarytreewhoseheightishis2h-1Ifnisthenumberofnodesinabinarytreewhoseheightish,thenh<=n<=2h–1AcompletebinarytreeSatisfyingthecondition:AllthenodesatalllevelsexceptthelasthavetwochildrenFeaturesAllnon-terminalnodeshaveboththeirchildre