Home Articles FAQs XREF Games Software Instant Books BBS About FOLDOC RFCs Feedback Sitemap
irt.Org

traversal

You are here: irt.org | FOLDOC | 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 "pre-order traversal", a node is visited __before__ its children. In "post-order" traversal, a node is visited __after__ its children. The more rarely used "in-order" 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 pre-order traversal visits the nodes in the order T I D E S. A post-order traversal visits them in the order D E I S T. An in-order traversal visits them in the order D I E T S.

(2001-10-01)

Nearby terms: traveling salesman problem « travelling salesman « travelling salesman problem « traversal » traverse » trawl » tree

FOLDOC, Topics, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, ?, ALL

©2018 Martin Webb