Tree traversal
From Wikipedia, the free encyclopedia
In computer science, tree traversal is the process of visiting each node in a tree data structure. Tree traversal, also called tree walking, provides for sequential processing of each node in what is, by nature, a non-sequential data structure. Such traversals are classified by the order in which the nodes are visited.
If nodes are visited before any of their children, the traversal is called a preorder traversal (or prefix). If they are visited after any of their children, the traversal is called a postorder traversal (or postfix). If all nodes of a level are visited before any node of the following level, the traversal is called a level-order traversal. In the special case of a binary tree, if a node is visited after it's first child and before it's second child, the traversal is called an in-order traversal (or infix).
The prefix, postfix and infix names come from the fact that when visiting a node is writing it's content, the preorder, postorder and in-order traversals respectively produce a prefix, postfix and infix notation of the tree.
In the terminology of graph algorithms, pre, post and in-order traversal are depth-first traversals while level-order is breadth-first.
[edit] Example
For example, with the following tree representing an algebrical expression:
*
/ \
+ -
/ \ / \
4 2 3 5
The prefix notation is:
* + 4 2 - 3 5
Which is the reverse polish notation of the expression, as used on some HP calculators. With parentheses, it is also the expression in the syntax of LISP:
(* (+ 4 2) (- 3 5))
The postfix notation is:
4 2 + 3 5 - *
Compilers typically produce a postfix notation of the parsed source code.
The infix notation is the one we are used to:
4 + 2 * 3 - 5
With parentheses to avoid possible interference of mathematical operators precedence, it would be:
((4 + 2) * (3 - 5))
The level-order traversal of the tree would have no sense in the case of an algebrical expression, but would yield:
* + - 4 2 3 5
[edit] References
- Mastering Algorithms with C, by Kyle Loudon {ISBN 1-56592-453-3}. O'Reilly 1999
