I have some doubts about the course taken by this binary tree:
Could you classify it as binary? Since it has knots with 3 sheets?
T=(35,(80,(7,(11,(12)),(15,(6,(0),(1),(2)),(9))),(3,(18),(8))),(73,(13),(27),(61)))
Would it be correct to say that the paths are these?
Pre-Order:
35,80,7,11,12,15,6,0,1,2,9,3,18,8,73,13,27,71
In-Order:
12,11,0,1,2,6,9,15,7,18,8,3,80,35,13,27,71,73
In this notation, a string of type (A,(B),(C)) means that A is a node that has children as subtrees B and C .
Let's draw this tree:
Inabinarytree,nonodecanhavemorethantwochildren.The(6,(0),(1),(2))and(73,(13),(27),(61))thatarethereinthemiddleclearlyareviolationsofthis,sincetheyrepresentnodeswiththreechildren.Node11hasnorightchild,justtheleft.
Preordersearchconsistsofvisitingeachnode,firstvisitingthenumberitcontains,thentheleftsubtreeandthelastoneontheright.Recursively.Iftherearemorethantwochildren,theyshouldbevisitedfromlefttoright.Thenotationgiven(A,(B),(C))willalreadyrepresentthetreeinpreorder,andthereforetheresultofthevisitofthenodeswillbethesamesequenceinwhichtheyappearinthatnotation,nomatterwheretheyareinthetree.Sotheresultisthen:35,80,7,11,12,15,6,0,1,2,9,3,18,8,73,13,27and61.Youranswerisalmostcorrect,theonlydetailisthatthelastnumberis61insteadof71.
In-ordersearchconsistsofvisitingeachnode,firstvisitingtheleftchild,thenthenodeitselfandthentherightchild.Recursively.Itconsistsofreplacing(A,(B),(C))with((B),A,(C)).
Inthecaseofa(A,(B),(C),(D))nodethathasmorethantwochildren,itisunclearwhatshouldbedone,sincethein-ordervisitisonlydefinedforcaseswheretherearenomorethantwochildren.Therearetwopossibilitieshere:replace(A,(B),(C),(D))with((B),A,(C),(D))or((B),(C),A,(D)).Thismeansthatthe(6,(0),(1),(2))couldbevisitedas0,6,1,2oras0,1,6,2.
((B),A,(C),(D))or((B),(C),A,(D)).Whatyouseemtobewantingisthepost-orderviewthatistovisitthenodeonlyafterthechildrenhavebeenvisited.Theyconsistofchanging(A,(B),(C))by((B),(C),A).Thisorderingproducesaresultsimilartowhatyouproposed,withonly35attheendand61insteadof71.Thepost-ordervisitwouldbe12,11,0,1,2,6,9,15,7,18,8,3,80,13,27,61,73and35.
Onewaytounderstandorderingistoseetheschemebelow:
Visits occur in the path of the sequence indicated by the arrows, bypassing the tree. In this route, each node can be visited by the left, the bottom or the right. The arrows that arrive in the knots by the left are the green ones, the ones that arrive underneath are the yellow ones and those that arrive by the right are the red ones.
If you consider only the green arrows, you will be making a pre-order visit. If he considers only the yellow ones, he will be making the visit in-order. If you only consider red ones, you'll be doing post-order.
Note that in the case of the in-order visit, a same node is accessed more than once below if there are more than two children (in this case, 6 and 73), since this situation is ambiguous in this circumstance .