Data Structure(C++) Slides-ENG 数据结构课件 第5-8章 Tree-and-Binary-Tree-EN-final-Sorting-English

DataStructuresChapter5TreesandBinaryTreesIntroduction5.15.1IntroductiontoTreesFunctionNavigationDataelement:functionnameDataStructuresChapter5TreesandBinaryTrees5.1Dataelement:surnameIntroductiontoTreesEvolutionofSurnameOriginsTreesandTreeStorageStructures5.25.2DefinitionofaTreeRecursiveDefinitionofaTreeAtreeisafinitesetofn(n≥0)nodes.Whenn=0,itiscalledanemptytree.Anynon-emptytreesatisfiesthefollowingconditions:Thereisoneandonlyonespecificnodecalledtheroot.Whenn>1,theremainingnodesexcepttherootaredividedintom(m>0)disjointfinitesetsT1,T2,...,Tm.Eachsetisalsoatreeandiscalledasubtreeoftheroot.Atreeconsistsofarootnodeandseveralsubtrees.5.2DefinitionofaTreeDefinitionofaTreeAtreehasoneandonlyoneroot;theroothasnopredecessor.Exceptfortheroot,eachnodeinatreehasoneandonlyonepredecessor.However,eachnodeinatreemayhavemultiplesuccessors.5.2DefinitionofaTree(a)atreestructure

(b)anon-treestructure

(c)anon-treestructureACBGFEDHIACBGFDACBGFDE5.2LogicalStructureofTreesBasicConceptsofTreesDegreeofanode:thenumberofsubtreesanodehas.Degreeofatree:themaximumdegreeamongallnodesinthetree.CGBDEFKLHMIJAThedegreeofthetreeis35.2BasicConceptsofTreesLeafnode:anodewithdegree0,alsocalledaterminalnode.Branchnode:anodewithnonzerodegree,alsocalledanon-terminalnode.CGBDEFKLHMIJALogicalStructureofTrees5.2BasicConceptsofTreesChild:therootofasubtreeofanodeiscalledthechildofthatnode(correspondingtosuccessor).Parent:thatnodeiscalledtheparentofitschild(correspondingtopredecessor).Sibling:childrenwiththesameparentarecalledsiblings.CGBDEFKLHMIJAAofchildnodeisB,C,DHofparentnodeDHofsiblingnodeI,JLogicalStructureofTrees5.2BasicConceptsofTreesPath:ifasequenceofnodesn1,n2,...,nkinatreesatisfiesthatnodeniistheparentofni+1(1≤i<k),thenn1,n2,...,nkiscalledapathfromn1tonk.Thenumberofedgesonthepathiscalledthepathlength.CGBDEFKLHMIJALogicalStructureofTrees5.2BasicConceptsofTreesAncestoranddescendant:inatree,ifthereisapathfromnodextonodey,thenxiscalledanancestorofy,andyiscalledadescendantofx.CGBDEFKLHMIJALogicalStructureofTrees5.2BasicConceptsofTreesLevelofanode:therootnodeisatlevel1.Foranyothernode,ifanodeisatlevelk,itschildrenareatlevelk+1.Depthofatree:themaximumlevelnumberamongallnodesinthetree,alsocalledheight.

1level

2level

4level

3levelheight=4CGBDEFKLHMIJALogicalStructureofTrees5.2BasicConceptsofTreesLevel-ordernumbering:numberthenodesofatreewithconsecutivenaturalnumbersstartingfrom1,orderedfromupperlevelstolowerlevelsandfromlefttorightwithinthesamelevel.CGBDEFKLHMIJALogicalStructureofTrees5.2BasicConceptsofTreesOrderedtreeandunorderedtree:ifthesubtreesofeachnodeinatreeareorderedfromlefttoright,thetreeiscalledanorderedtree;otherwise,itiscalledanunorderedtree.Foranorderedtree,exchangingtherelativepositionsofsubtreesproducesadifferenttree.Foranunorderedtree,thetreeremainsthesameaftersuchanexchange.ACBGFEDACBGFEDIndatastructures,thetreesdiscussedaregenerallyorderedtrees.LogicalStructureofTrees5.2BasicConceptsofTreesForest:asetofm(m≥0)disjointtrees.CBDEFKLHJALogicalStructureofTrees5.2ComparisonbetweenTreeStructuresandLinearStructuresStartingnode(onlyone):nopredecessorRootnode(onlyone):noparentTerminalnode(onlyone):nosuccessorLeafnodes(maybemultiple):nochildrenotherelements:onepredecessorandonesuccessorothernodes:oneparentand

multiplechildrenone-to-one

one-to-manyACBGFEDHIa1ana2ai-1ailinearstructuretreestructure5.2AbstractDataTypeofTreesADTTreeDataModelAtreeconsistsofarootnodeandseveralsubtrees;thenodesinthetreehavehierarchicalrelationships.OperationInitTree:initializeatree.DestroyTree:destroyatree.PreOrder:preordertraversalofthetree.PostOrder:postordertraversalofthetree.LevelOrder:level-ordertraversalofthetree.endADT5.2PreorderTraversalofTreesTreetraversaloperationsTreetraversal:startingfromtheroot,visiteverynodeinaspecifiedordersothateachnodeisvisitedexactlyonce.Visit:anabstractoperationthatmayperformvariousprocessingonanode;hereitissimplifiedasoutputtingthenodedata.Aftertraversal,thetreestructure(nonlinearstructure)→linearstructure.Order:treesusuallysupportpreorder(root)traversal,postorder(root)traversal,andlevel-ordertraversal.5.2Thepreordertraversaloperationofatreeisdefinedasfollows:

Ifthetreeisempty,performnooperationandreturn;otherwise:Visittherootnode;Traverseeverysubtreeoftherootinpreorderfromlefttoright.Preordertraversalsequence:ACBGFEDHIPreorderTraversalofTrees5.2Thepostordertraversaloperationofatreeisdefinedasfollows:Ifthetreeisempty,performnooperationandreturn;otherwise:Traverseeverysubtreeoftherootinpostorderfromlefttoright;Visittherootnode.Postordertraversalsequence:ACBGFEDHIPreorderTraversalofTrees5.2Level-orderTraversalofTreesLevel-ordertraversalofatreestartsfromthefirstlevel(therootnode),traverseslevelbylevelfromtoptobottom,andvisitsnodesonthesamelevelfromlefttoright.Level-ordertraversalsequence:ACBGFEDHI5.2ATypicalTypeofProblemSupposeinatreeofdegreem,thenumberofnodesofdegree1isn1,thenumberofnodesofdegree2isn2,...,andthenumberofnodesofdegreemisnm.Findthenumberofleafnodes.Hint:totalnumberofnodesinthetree=CGBDEFKLHMIJAWhatisthenumberofleafnodes?Whatelseisthetotalnumberofnodesinatreeequalto?Takethetreeontherightasanexample:ThedegreeofAis3,soAhas3childnodes.ThedegreeofBis2,soBhas2childnodes.Summarypoints=5.2StorageStructureofTreesWhatisthekeytoimplementingthestoragestructureofatree?Whatisastoragestructure?Whatisthelogicalrelationshipbetweennodesinatree?Startingpoint:howtorepresenttheparent-childrelationshipofnodes.Sincethisrelationshipisdifficulttoreflectthroughstoragepositions,treesgenerallydonotusesequentialstoragestructures.Howtorepresentthelogicalrelationshipbetweennodesinatree.Therepresentationofdataelementsandtheirlogicalrelationshipsinmemory.5.2ParentRepresentationofTreesBasicidea:useaone-dimensionalarraytostoreallnodesofthetree(usuallyinlevelorder).Eacharrayelementcorrespondstoanodeandcontainsthenodedataandtheindexofitsparentinthearray.

dataparentdata:storesthedatainformationofanodeinthetree.parent:storestheindexofthenode'sparentinthearray.template<classDataType>structPNode{DataTypedata;//datafieldintparent;//indexoftheparentinthearray};5.2ACBHFEDGITheparentrepresentationofatreeisessentiallyastaticlinkedlist.indexdataparent012345678ParentRepresentationofTrees5.2indexdataparent012345678ACBHFEDGIHowtofindtheparentnode?Timeperformance?ParentRepresentationofTrees5.2index

data

parent012345678ACBHFEDGIHowtofindchildnodes?Timeperformance?Ifweneedtofindthefirstchild,howshoulditbeimplemented?firstchild136-18-1-1-1-1ParentRepresentationofTrees5.2index

data

parent012345678ACBHFEDGIHowtofindsiblingnodes?Timeperformance?Ifweneedtofindtheimmediaterightsibling,howshoulditbeimplemented?rightsib-12-145-17-1-1ParentRepresentationofTrees5.2ChildRepresentationofTreesMultiplelinked-listrepresentationBasicidea:eachnodeinthelinkedlistcontainsonedatafieldandmultiplepointerfields;eachpointerfieldpointstoonechildofthenode.Keyquestion:howmanypointerfieldsdshouldbeset?Scheme1:thenumberofpointerfieldsequalsthedegreeofthetree.datachild1child2……childdwheredataisthedatafieldstoringthenode'sdata;child1~childdarepointerfieldspointingtothenode'schildren.5.2∧Disadvantage:manynullpointerfieldsexist,wastingmemoryspace.ACBHFEDGIA∧BC∧E∧∧D∧∧∧F∧∧∧G∧∧∧H∧∧∧I∧∧multiplelinked-listrepresentationChildRepresentationofTrees5.2Multiplelinked-listrepresentationBasicidea:eachnodeinthelinkedlistcontainsonedatafieldandmultiplepointerfields;eachpointerfieldpointstoonechildofthenode.Keyquestion:howmanypointerfieldsdshouldbeset?Scheme2:thenumberofpointerfieldsequalsthedegreeofthatnode.data

degree

child1

child2

……

childdwheredataisthedatafieldstoringthenode'sdata;degreeisthedegreefieldstoringthedegreeofthenode;child1~childdarepointerfieldspointingtothenode'schildren.ChildRepresentationofTrees5.2Disadvantage:nodestructuresareinconsistent,manyoperationsaredifficulttoimplement,andtheamountofcomputationislarge.A2C2D0B3F0E1I0G0H0ACBHFEDGIChildRepresentationofTrees5.2Childlinked-listrepresentationBasicidea:linkedlist+array.Arrangethechildrenofeachnodeasalinearlistandstoreitasasinglylinkedlist;thisiscalledachildlinkedlist.childnextchildnodeACBChildRepresentationofTrees5.2Childlinked-listrepresentationBasicidea:linkedlist+array.Arrangethechildrenofeachnodeasalinearlistandstoreitasasinglylinkedlist;thisiscalledachildlinkedlist.Treatthedataofallnodesasalinearlistandstoreitinanarray;thisiscalledthehead-nodearray.Connecttheheadpointerofeachnode'schildlinkedlisttothecorrespondingelementinthehead-nodearray.childnextchildnodedatafirstchildheadnodeACBChildRepresentationofTrees5.2Childlinked-listrepresentationDefinitionofnodesstructCTNode{intchild;CTNode*next;};template<classT>structCBNode{Tdata;CTNode*firstchild;};childnextchildnodedatafirstchildheadnodeWhyischildanintegerratherthantypeT?ChildRepresentationofTreesBC5.2ChildLinked-listRepresentationofTreesACBHFEDGIWhyischildanintegerratherthantypeT?Howtofindchildnodes?Howtofindtheparentnode?index5.2Parent-childRepresentationofTreesparentrepresentation

dataparentchildlinked-listrepresentation

datafirstchildParentlookupiseasy,butchildlookupisdifficult.Childlookupiseasy,butparentlookupisdifficult.Parent-childrepresentationBasedonthechildlinked-listrepresentation,definechildnodesandheadnodes.Addaparentfieldtotheheadnode.childnextchildnodedataparentfirstchildheadnode5.2ACBHFEDGIHowtofindchildnodes?Howtofindtheparentnode?Parent-childRepresentationofTrees5.2Child-siblingRepresentationofTreesBasicideaofthechild-siblingrepresentation:foranynode,itsfirstchildisuniqueanditsrightsiblingisunique.Therefore,settwopointerspointingrespectivelytothenode'sfirstchildandrightsibling.nodestructurefirstchild

data

rightsibdata:datafield,storingthenode'sdatainformation;firstchild:pointerfield,pointingtothenode'sfirstchild;rightsib:pointerfield,pointingtothenode'srightsibling.ACBHFEDGI5.2ACBHFEDGIHowtofindchildnodes?Timeperformance?Howtofindsiblingnodes?Timeperformance?ABHFICDEGChild-siblingRepresentationofTreesLogicalStructureofBinaryTrees5.35.3DefinitionofBinaryTreesBinarytree:afinitesetofn(n≥0)nodes.Thesetiseitherempty(calledanemptybinarytree),orconsistsofarootnodeandtwodisjointbinarytreescalledtheleftsubtreeandtherightsubtreeoftheroot.Significanceofstudyingbinarytrees:problemtransformation.Treescanbeconvertedintobinarytrees,sotree-relatedproblemscanbesolvedusingbinarytrees.5.3Eachnodehasatmosttwosubtrees.Abinarytreeisordered,sotheordercannotbereversedarbitrarily.Evenifanodehasonlyonesubtree,wemustdistinguishwhetheritistheleftsubtreeortherightsubtree.Note:Thesearethesametree,butdifferentbinarytrees.Therefore,binarytreesandtreesaretwodifferenttreestructures;abinarytreeisnotasubsetoftrees.ABABDefinitionofBinaryTrees5.3SpecialBinaryTrees-SkewedTreesAbinarytreeinwhichallnodeshaveonlyleftsubtreesiscalledaleft-skewedtree;abinarytreeinwhichallnodeshaveonlyrightsubtreesiscalledaright-skewedtree;left-skewedandright-skewedtreesarecollectivelycalledskewedtrees.Inaskewedtree,eachlevelhasonlyonenode.Thenumberofnodesinaskewedtreeisthesameasitsdepth.Characteristicsofskewedtrees:ABCABC5.3SpecialBinaryTrees-FullBinaryTreesFullbinarytree:Inabinarytree,ifeverybranchnodehasbothaleftsubtreeandarightsubtree,andallleavesareonthesamelevel.Characteristicsoffullbinarytrees:Leavescanappearonlyonthelowestlevel.Thereareonlynodesofdegree0anddegree2.CDEFGHIJKLMNO11121314155.3Completebinarytree:Forabinarytreewithnnodesnumberedinlevelorder,ifthenodenumberedi(1≤i≤n)isinexactlythesamepositionasthenodenumberediinafullbinarytreeofthesamedepth.CDEFGHIJKLMNO1112131415CDEFGHIJLeafnodescanappearonlyonthelowesttwolevels,andleafnodesonthelowestlevelareconcentratedontheleftsideofthebinarytree.Ifacompletebinarytreehasanodeofdegree1,therecanbeonlyonesuchnode,andithasonlyaleftchild.Acompletebinarytreeofdepthkmustbefullonlevelk-1.Amongbinarytreeswiththesamenumberofnodes,acompletebinarytreehastheminimumdepth.Characteristicsofcompletebinarytrees:SpecialBinaryTrees-CompleteBinaryTrees5.3A152346789BCDEFHIJKLM101112ACBHFEDGABCDEFHIKGTheseareallincompletebinarytrees.A152346789BCDEFHJGSpecialBinaryTrees-CompleteBinaryTrees5.3BasicPropertiesofBinaryTreesProperty5-1:Thei-thlevelofabinarytreehasatmostnodes(i≥1).CDEFGHIJKLMNO11121314155.3Property5-2:Abinarytreeofdepthkhasatmost2^k-1nodesandatleastknodes.CDEFGHIJKLMNO1112131415Maximum:Minimum:A1234BDHBasicPropertiesofBinaryTrees5.3Property5-3:Inabinarytree,ifthenumberofleafnodesisn0andthenumberofnodesofdegree2isn2,thenn0=n2+1.CDEFGHIJKLO111215Letthenumberofnodesofdegree1ben1.Thenthetotalnumberofnodesninthebinarytreeis:Numberofleafnodes:Numberofnodesofdegree2:Besidesnodesofdegree0and2,whatothernodesexistinabinarytree?LetthenumberofbranchesinabinarytreebeB.Then:Nodesofdegree1produce

branchesintotal.Nodesofdegree2producebranchesintotal.CombiningtheequationsBasicPropertiesofBinaryTrees5.3Property5-4:ThedepthofacompletebinarytreewithnnodesisCDEFGHIJKL1112Thedepthofthebinarytreeis4.BasicPropertiesofBinaryTrees5.3Basicpropertyofcompletebinarytrees:Inacompletebinarytreewithnnodesnumberedfrom1inlevelorder,foranynodenumberedi(1≤i≤n),i.e.,nodei,wehave:CDEFGHIJKL1112If2i≤n,thenthenumberofnodei'sleftchildis2i;if2i>n,nodeihasnoleftchild.If2i+1≤n,thenthenumberofnodei'srightchildis2i+1;if2i+1>n,nodeihasnorightchild.Ifi>1,thenthenumberofnodei'sparentis____;ifi=1,nodeiistherootnodeandhasnoparent.BasicPropertiesofBinaryTrees5.3SpecialBinaryTrees-CompleteBinaryTreeoracompletebinarytreewithnnodesnumberedfrom1inlevelorder:theparentofnodeiisi/2;theleftchildofnodeiis2i;therightchildofnodeiis2i+1.Thispropertyshowsthatinacompletebinarytree,level-ordernumberingreflectsthelogicalrelationshipbetweennodes.5.3AbstractDataTypeofBinaryTreesADTBiTreeDataModelAbinarytreeconsistsofarootnodeandtwodisjointleftandrightsubtrees;thenodeshavehierarchicalrelationships.OperationInitBiTree:initializeanemptybinarytree.CreateBiTree:createabinarytree.DestroyBiTree:destroyabinarytree.PreOrder:preordertraversalofthebinarytree.InOrder:inordertraversalofthebinarytree.PostOrder:postordertraversalofthebinarytree.LevelOrder:level-ordertraversalofthebinarytree.endADT5.3TraversalOperationsofBinaryTreesTraversalofabinarytreemeansstartingfromtherootandvisitingallnodesinacertainordersothateachnodeisvisitedexactlyonce.Essentially,itlinearizesanonlinearstructure.PreordertraversalInordertraversalPostordertraversalLevel-ordertraversalPurposeoftraversal:nonlinearstructure→linearstructure5.3BinaryTreeTraversalPreorder:DLR(root-left-right)Inorder:LDR(left-root-right)Postorder:LRD(left-right-root)Level-ordertraversal:visitnodesaccordingtothelevel-ordernumberingofthebinarytree.TraversalOperationsofBinaryTrees5.3Preorder(root)TraversalPreorder(root)traversalIfthebinarytreeisempty,performnooperationandreturn;otherwise:Visittherootnode;Traversetheleftsubtreeoftherootinpreorder;Traversetherightsubtreeoftherootinpreorder.Preordertraversalsequence:ABCDEFG5.3Inorder(root)TraversalInorder(root)traversalIfthebinarytreeisempty,performnooperationandreturn;otherwise:Traversetheleftsubtreeoftherootininorder;Visittherootnode;Traversetherightsubtreeoftherootininorder.inordertraversalsequence:ABCDEFG5.3Postorder(root)TraversalDataStructuresandAlgorithmsChapter5TreesandBinaryTreesABCDEFGPostorder(root)traversalIfthebinarytreeisempty,performnooperationandreturn;otherwise:Traversetheleftsubtreeoftherootinpostorder;Traversetherightsubtreeoftherootinpostorder;Visittherootnode.Postordertraversalsequence:5.3level-ordertraversalABCDEFGLevel-ordertraversalLevel-ordertraversalofabinarytreestartsfromthefirstlevel(therootnode),traverseslevelbylevelfromtoptobottom,andvisitsnodesonthesamelevelfromlefttoright.Level-ordertraversalsequence:5.3BinaryTreeTraversalPracticepreordertraversal:inordertraversal:postordertraversal:level-ordertraversal5.3ClassParticipationforThisChapterClassparticipation(nextMonday)Usebinarytreestodescribeinfix,prefix,andpostfixexpressions,anduseastacktoconvertprefixexpressions.ThinkaboutthedifferencesbetweentheclassdefinitionsandcodeinthetextbookandthoseinthePPT;understandtheirpurposesandfunction-callmethods.Duration:2weeksPleasevolunteeryourselforrecommendtwostudents.Make-upClassScheduleThisWednesday(October29),periods9-10intheevening,location:WX4302NextSaturday(November8),periods3-4inthemorning,location:WX42015.4ChapterLabChapterlab(nextWednesday)Designabinarytreeyourselfandprogramthefunctionsdefinedintheclass.Itisrecommendedtodefinenodedataascharactertype.Othertypesrequireslightcodemodifications;trythemafterdebuggingthecharactertypesuccessfully.Optionalimprovements:Implementthefollowingfunctionsforthebinarytree:1.Searchbyvalue2.Computedepth3.OutputleafnodesNon-recursivetraversal5.3LogicalStructureofBinaryTreesUseabinarytreetoconvertaninfixexpressionintoprefixandpostfixexpressions.Theoperatorevaluatedlastintheinfixexpressionistherootnode.Theexpressionontheleftoftherootistheleftsubtree.Theexpressionontherightoftherootistherightsubtree.Repeattheprocessuntileverynodeinthebinarytreeiseitheranoperatororanoperand.Operandsareleafnodes.Binaryoperatorsarebranchnodes.Preordertraversalofthebinarytreegivestheprefixexpression.Postordertraversalgivesthepostfixexpression.5.3LogicalStructureofBinaryTreesUseabinarytreetoconvertaninfixexpressionintoprefixandpostfixexpressions.Example:a*(b+c)-dDrawthebinarytree.Preordertraversalgivestheprefixexpression:-*a+bcdPostordertraversalgivesthepostfixexpression:abc+*d-5.32003postgraduateexam:ThepostfixexpressionoftheinfixexpressionA*(B+C)/(D-E+F)is();ABC+*DE-F+/2012postgraduateexam:Whenconvertingtheinfixexpressiona+b-a*((c+d)/e-f)+gtoitsequivalentpostfixexpression(),astackisusedtostoreoperatorswhoseorderisnotyetdetermined.Ifthestackisinitiallyempty,themaximumnumberofoperatorsstoredinthestackatthesametimeduringconversionis().ab+acd+e/f-*-g+5LogicalStructureofBinaryTrees5.3Convertprefixorpostfixexpressionstoinfixexpressions.Useastackandcomputeaccordingtotheoperationrules.Consideraddingparenthesesforeveryoperation.Finallyremoveunnecessaryparenthesesfromtheresult.Evaluationrulesforprefixorpostfixexpressions:Forprefixexpressions,scancharactersfromrighttoleft;forpostfixexpressions,scanfromlefttoright.Ifthecharacterisanoperand,pushitontothestack.Ifthecharacterisanoperator,popthetoptwoelements,performtheoperation,andpushtheresultbackontothestack(prefix:thetopelementcomesbeforetheoperator;postfix:thetopelementcomesaftertheoperator).Continuescanningthenextcharacter.LogicalStructureofBinaryTrees5.3prefixexpression-*a+bcdpostfixexpressionabc+*d-LogicalStructureofBinaryTreesStorageStructuresofBinaryTrees5.45.4SequentialStorageStructureofBinaryTreesThesequentialstoragestructureofabinarytreeusesaone-dimensionalarraytostorethenodes,andthestoragepositions(indices)shouldreflectthelogicalparent-childrelationshipamongnodes.Inacompletebinarytree(includingafullbinarytree),nodenumberscanuniquelyreflectthelogicalrelationshipbetweennodes.5.4CDEFGHIJFindtheparentnode?SequentialStorageStructureofBinaryTrees5.4IncompletebinarytreeBasicidea:addemptynodestoformacompletebinarytree,thennumberthenodes.ABCDEGFABCDEGFΛΛΛΛΛΛSequentialStorageStructureofBinaryTrees5.4XABCDEFGABCDEFG1234567ABCDEΛ

Λ

Λ

ΛFG1234567891011Extremecase:abinarytreeofdepthkmayhaveonlyknodes,witheachnodehavingatmostonechild,suchasaskewedtree.Itrequiresaone-dimensionalarrayoflength2^k-1.Conclusion:Thesequentialstoragestructureofbinarytreesisgenerallyusedonlyforcompletebinarytreesandisnotsuitableforordinarybinarytrees.SequentialStorageStructureofBinaryTrees5.4BinaryLinked-listStorageStructureBasicidea:leteverynodeinabinarytreecorrespondtoalinked-listnode.Besidesstoringdatainformationrelatedtothebinary-treenode,thelinked-listnodealsostorespointerstotheleftandrightchildren.nodestructure:

lchild

data

rchildwheredataisthedatafieldstoringthenode'sdatainformation;lchildistheleftpointerfieldstoringapointertotheleftchild;rchildistherightpointerfieldstoringapointertotherightchild.Thecommonlyusedstoragestructureforbinarytreesisthebinarylinkedlist.5.4template<classDataType>struct

BiNode{

DataTypedata;

BiNode<T>*lchild,*rchild;};lchild

datarchildleftchildnoderightchildnodeABCDEFGGFEDBA∧∧∧∧∧∧∧∧CBinaryLinked-listStorageStructure5.4Howmanynullpointersarethereinabinarylinkedlistwithnnodes?BinaryLinked-listStorageStructure5.4binarylinkedlistofimplementationbinarylinkedlistofclassdeclarationtemplate<classT>classBiTree{public:BiTree()

{root=Creat(root);}~BiTree(){Release(root);};voidPreOrder(BiNode<T>*root);voidInOrder(BiNode<T>*root);voidPostOrder(BiNode<T>*root);voidLeverOrder();private:BiNode<T>*root;BiNode<T>*Creat(BiNode<T>*root);voidRelease(BiNode<T>*root);};5.4RecursiveImplementationofPreorderTraversaltemplate<classDataType>voidBiTree<DataType>::PreOrder(BiNode<DataType>*bt){if(bt==nullptr)return;//terminationconditionofrecursionelse{cout<<bt->data;//visitthedatafieldofrootnodebtPreOrder(bt->lchild);//recursivelypreorder-traversetheleftsubtreeofbtPreOrder(bt->rchild);//recursivelypreorder-traversetherightsubtreeofbt}}5.4template<classDataType>voidBiTree<DataType>::InOrder(BiNode<DataType>*bt){if(bt==nullptr)return;//terminationconditionofrecursionelse{InOrder(bt->lchild);//recursivelyinorder-traversetheleftsubtreeofbtcout<<bt->data;//visitthedatafieldofrootnodebtInOrder(bt->rchild);//recursivelyinorder-traversetherightsubtreeofbt}}RecursiveImplementationofPreorderTraversal5.4template<classDataType>voidBiTree<DataType>