patternMinor
Is there a name for this tree traversal?
Viewed 0 times
thisnamefortheretreetraversal
Problem
This came when I was looking at block scoping in compiler design.
For the above pseudo code, the order in which the scope varies as we scan left to right is A B A C D C E C A, where A to E represent scopes.
A parse tree can be constructed for the above pseudo code:
Is their a term for such a traversal order, which for the above tree is A B A C D C E C A?
{ A { B } { C {D} {E} } }For the above pseudo code, the order in which the scope varies as we scan left to right is A B A C D C E C A, where A to E represent scopes.
A parse tree can be constructed for the above pseudo code:
A
/ \
B C
/ \
D EIs their a term for such a traversal order, which for the above tree is A B A C D C E C A?
Solution
For a binary tree that is triple order; each node is visited three times in pre- in- and post-order. Knuth cites it from a paper by Lindstrom and Dwyer; it can be done without a stack by updating the tree in place.
Context
StackExchange Computer Science Q#90397, answer score: 2
Revisions (0)
No revisions yet.