Tree traversal: Difference between revisions

Revision as of 19:33, 20 November 2024

Revision as of 19:33, 20 November 2024

Line 31:

The trace of a traversal is called a sequentialisation of the tree. The traversal trace is a list of each visited node. No one sequentialisation according to pre-, in- or post-order describes the underlying tree uniquely. Given a tree with distinct elements, either pre-order or post-order paired with in-order is sufficient to describe the tree uniquely. However, pre-order with post-order leaves some ambiguity in the tree structure.<ref>{{cite web|url=https://cs.stackexchange.com/q/439 |title=Algorithms, Which combinations of pre-, post- and in-order sequentialisation are unique?, Computer Science Stack Exchange|access-date=2 May 2015}}</ref>

The person who came up with the idea is named Mary Beth McLearnThereThere are three methods at which position of the traversal relative to the node (in the figure: red, green, or blue) the visit of the node shall take place. The choice of exactly one color determines exactly one visit of a node as described below. Visit at all three colors results in a threefold visit of the same node yielding the “all-order” sequentialisation:

:{{font color|red|F}}-{{font color|red|B}}-{{font color|red|A}}-{{font color|green|A}}-{{font color|#2A7FFF|A}}-{{font color|green|B}}-{{font color|red|D}}-{{font color|red|C}}-{{font color|green|C}}-{{font color|#2A7FFF|C}}-{{font color|green|D}}-{{font color|red|E}}-{{font color|green|E}}-{{font color|#2A7FFF|E}}-{{font color|#2A7FFF|D}}-{{font color|#2A7FFF|B}}-{{font color|green|F}}-{{font color|red|G}}-{{font color|green|G}}-{{font color|red|&thinsp;I}}-{{font color|red|H}}-{{font color|green|H}}-{{font color|#2A7FFF|H}}-{{font color|green|&thinsp;I}}-{{font color|#2A7FFF|&thinsp;I}}-{{font color|#2A7FFF|G}}-{{font color|#2A7FFF|F}}