【精品数据结构】Binary and other trees.ppt

《【精品数据结构】Binary and other trees.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter8BinaryandothertreesTwokindsofdatastructureLinear:list,stack,queue,stringNon-linear:tree,graph8.1Tree1.Definition:AtreeTisafinitenonemptysetofelements.Oneoftheseelementsiscalledtheroot,andtheremainingelements(ifany)arepartitionedintotreeswhicharecalledthesubtreesofT.8.1TreeexampleABCDEFGHIJK

2、LM8.1Tree2.TerminologyDegreeofanelememts:thenumberofchildrenithas.Degreeofatree:themaximumofitselementdegreesLeaf:elementwhosedegreeis0Branch:elementwhosedegreeisnot08.1TreeLevel:thelevelofrootis1thelevelofanelement=thelevelofitsparent+1Depthofatree:themaximumlevelofitselements8.2BinaryTrees1.Defin

3、ition:Abinarytreetisafinite(possiblyempty)collectionofelements.Whenthebinarytreeisnotempty:IthasarootelementTheremainingelements(ifany)arepartitionedintotwobinarytrees,whicharecalledtheleftandrightsubtreesoft.8.2BinaryTrees2.Theessentialdifferencesbetweenabinarytreeandatreeare:1)Abinarytreecanbeemp

4、ty,whereasatreecannot.2)Eachelementinabinarytreehasexactlytwosubtrees(oneorbothofthesesubtreesmaybeempty).Eachelementinatreecanhaveanynumberofsubtrees.8.2BinaryTrees3)Thesubtreesofeachelementinabinarytreeareordered.Thatis,wedistinguishbetweentheleftandtherightsubtrees.Thesubtreesinatreeareunordered

5、.8.2BinaryTreesExampleofabinarytree+*/abcd8.3PropertiesofbinarytreesProperty1.Thedrawingofeverybinarytreewithnelements,n>0,hasexactlyn-1edges.Property2.Thenumberofelementsatleveliisatmost2i-1(i>=1).8.3PropertiesofbinarytreesProperty3.Abinarytreeofheighth,h>=0,hasatleasthandatmost2h–1elementsinit.pr

6、oofofproperty3:2i-1=20+21+……+2h-1=1*(1-2h)/(1-2)=2h–1i-1h8.3PropertiesofbinarytreesProperty4.Theheightofabinarytreethatcontainsn,n>=0,elementisatmostnandatleastlog2(n+1)proof:Sincetheremustbeatleastoneelementateachlevel,theheightcannotexceedn.Fromproperty3,weknown<=2h-1,so,h>=log2(n+1),sincehisa

7、ninteger,wegeth>=log2(n+1)8.3PropertiesofbinarytreesProperty5.Ifnumberofleavesisn0,andthenumberofthe2degreeelementsisn2,thenn0=n2+1.8.3PropertiesofbinarytreesDefinitionofafullbinarytree:Abinarytreeofheigh