Tree traversal: Difference between revisions

Revision as of 08:06, 18 May 2023

Revision as of 07:10, 24 May 2023

Line 26:

# Execute the following three operations in a certain order:<ref>L before R means the (standard) counter-clockwise traversal—as in the figure.<br />The execution of N before, between, or after L and R determines one of the described methods.<br />If the traversal is taken the other way around (clockwise) then the traversal is called reversed. This is described in particular for [[#Reverse in-order|reverse in-order]], when the data are to be retrieved in descending order.</ref>

#: N: Visit the current node.

#: L: Recursively traversetraverses the current node's left subtree.

#: R: Recursively traversetraverses the current node's right subtree.

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>