traversal
<data> Processing nodes in a graph one at a time, usually in some
specified order. Traversal of a tree is recursively defined to mean visiting the
root node and traversing its children. Visiting a node usually involves
transforming it in some way or collecting data from it.
In "preorder traversal", a node is visited _before_ its children. In
"postorder" traversal, a node is visited _after_ its children. The more rarely
used "inorder" traversal is generally applicable only to binary trees, and is
where you visit first a node's left child, then the node itself, and then its
right child.
For the binary tree:
T
/ \
I S
/ \
D E
A preorder traversal visits the nodes in the order T I D E S. A
postorder traversal visits them in the order D E I
S T. An inorder traversal visits them in the order
D I E T S.
(20011001)
Nearby terms:
Trash80 « traveling salesman problem « travelling
salesman problem « traversal » traverse »
trawl » tree
