7
$\begingroup$

To complement my earlier questions:

I would now like to ask: how to perform a depth-first in-order traversal?

Wikipedia gives this illustration of the depth-first in-order traversal:

enter image description here

The output is A, B, C, D, E, F, G, H, I.

I believe this traversal applies only to binary trees.

Here is an expression to experiment with, using Null for missing leaves.

tree = "F"["B"["A", "D"["C", "E"]], "G"[Null, "I"["H", Null]]];

I am interested in efficiency and elegance.

$\endgroup$
  • 1
    $\begingroup$ Can you define in-order traversal for a generic tree (not necessarily binary)? What would that mean? $\endgroup$ – Leonid Shifrin Mar 21 '17 at 19:03
  • $\begingroup$ @LeonidShifrin Good question. I cannot. I found the example in isolation interesting and wondered if there were already Mathematica functions that implement this, or other standard methods. The Wikipedia description applies to a binary tree, and I don't think this generalizes to an arbitrary number of leaves, as it visits the root node between left and right branches. $\endgroup$ – Mr.Wizard Mar 21 '17 at 19:34
  • 2
    $\begingroup$ For the GIH branch, how does one decide which is left and which is right? $\endgroup$ – wxffles Mar 21 '17 at 20:24
  • $\begingroup$ @wxffles It was a quick fix so I self-answered instead of deleting. $\endgroup$ – Mr.Wizard Mar 22 '17 at 0:03
  • $\begingroup$ @Mr.Wizard, as left and right branches have been assigned an order, why can't 3 or more branches be similarly ordered? $\endgroup$ – alancalvitti Apr 11 '18 at 17:04
6
$\begingroup$

Recursion

tree = "F"["B"["A", "D"["C", "E"]], "G"[Null, "I"["H", Null]]];

dfio[f_][Null | a_~r_~b_] := Scan[dfio[f], {a, r, b}]
dfio[f_][x_] := f[x]

dfio[Print][tree]

A

B

C

D

E

F

G

H

I

Stack

Daniel showed how to manually manage a stack. Applying his method to this traversal:

dfioStack[f_, expr_] :=
  Module[ {stack = {expr, {}}, el = expr},
    While[ stack =!= {},
      {el, stack} = stack;
      If[ Length@el === 2,
        Do[ stack = {el[[j]], stack}, {j, {2, 0, 1}}],
        If[ el =!= Null, f @ el]
      ]
    ]
  ]

dfioStack[Print, tree]  (* same output as above *)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.