traversal

views updated May 21 2018

traversal A path through a graph in which every vertex is visited at least once. Traversals are usually discussed in connection with special kinds of graphs, namely trees. Examples include preorder traversal, postorder traversal, and symmetric order (or inorder) traversal. When parse trees for arithmetic expressions are traversed, these tree traversals lead to prefix (Polish notation), postfix (reverse Polish) notation, and infix notation respectively.

More From encyclopedia.com