【精品数据结构】binary trees

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

1、BinaryTreesAbinarytreeismadeupofafinitesetofnodesthatiseitheremptyorconsistsofanodecalledtheroottogetherwithtwobinarytrees,calledtheleftandrightsubtrees,whicharedisjointfromeachotherandfromtheroot.BinaryTreeExampleNotation:Node,children,edge,parent,ancestor,descendant,path,depth,height,

2、level,leafnode,internalnode,subtree.FullandCompleteBinaryTreesFullbinarytree:Eachnodeiseitheraleaforinternalnodewithexactlytwonon-emptychildren.Completebinarytree:Iftheheightofthetreeisd,thenallleavesexceptpossiblyleveldarecompletelyfull.Thebottomlevelhasallnodestotheleftside.FullBinary

3、TreeTheorem(1)Theorem:Thenumberofleavesinanon-emptyfullbinarytreeisonemorethanthenumberofinternalnodes.Proof(byMathematicalInduction):Basecase:Afullbinarytreewith1internalnodemusthavetwoleafnodes.InductionHypothesis:AssumeanyfullbinarytreeTcontainingn-1internalnodeshasnleaves.FullBinary

4、TreeTheorem(2)InductionStep:GiventreeTwithninternalnodes,pickinternalnodeIwithtwoleafchildren.RemoveI’schildren,callresultingtreeT’.Byinductionhypothesis,T’isafullbinarytreewithnleaves.RestoreI’stwochildren.Thenumberofinternalnodeshasnowgoneupby1toreachn.Thenumberofleaveshasalsogoneupby

5、1.FullBinaryTreeCorollaryTheorem:Thenumberofnullpointersinanon-emptytreeisonemorethanthenumberofnodesinthetree.Proof:Replaceallnullpointerswithapointertoanemptyleafnode.Thisisafullbinarytree.BinaryTreeNodeClass(1)//BinarytreenodeclasstemplateclassBinNodePtr:publicBinNode

6、>{private:Elemit;//Thenode'svalueBinNodePtrlc;//PointertoleftchildBinNodePtrrc;//Pointertorightchildpublic:BinNodePtr(){lc=rc=NULL;}BinNodePtr(Eleme,BinNodePtrl=NULL,BinNodePtrr=NULL){it=e;lc=l;rc=r;}BinaryTreeNodeClass(2)Elem&val(){returnit;}voidsetVal(constElem&e){it=e;}inlineBinNode<

7、Elem>left()const{returnlc;}voidsetLeft(BinNodeb){lc=(BinNodePtr)b;}inlineBinNoderight()const{returnrc;}voidsetRight(BinNodeb){rc=(BinNodePtr)b;}boolisLeaf(){return(lc==NULL)&&(rc==NULL);}};Traversals(1)Anyprocessforvisitingthenodesinsomeorderiscalledatraversal