FUNDAMENTALS OF ALGORITHMS.
Graph-Traversal
Graph-traversal is the process of visiting each vertex in a graph. There are
two algorithms in this section - depth-first and breadth-first graph-
traversals. In a depth-first search, a branch is fully explored before
backtracking, whereas in a breadth-first search a node is fully explored
before venturing on to the next node.
Depth-first traversal uses a stack. Depth-first traversal is used for
navigating a maze. The following example uses a tree, but a depth-first
algorithm can be performed on any connected graph.
Tree-Traversal
Tree-traversal is the process of visiting/updating/outputting each node in a
tree - it is a form of algorithm. Unlike a graph-traversal, tree-traversals are
unique to trees and must start at the root. From the root, they travel left,
down the tree. There are three types of tree-traversals; pre-order, in-order
and post-order. Pre-order and post-order tree-traversal can be performed
on any tree including binary trees but an in-order traversal is only well
defined for binary trees.
Pre-order traversal is used for copying a tree. It can be performed on
any tree.
In-order traversal is useful for a binary search tree and because it
will output the contents of a binary search tree in ascending order. It
can only be performed on binary trees.
Post-order traversals can be performed on any tree. They are useful
for Infix to RPN (Reverse Polish Notation) conversions, producing a
postfix expression from an expression tree and emptying a tree.
Infix to Postfix; as mentioned above, postorder traversal can be
used to make infix to RPN conversions and make postfix expressions
from expression trees. Technically, these two uses are the same. The
difference is that Infix to RPN would involve the making of and then
traversing of a binary tree, whereas in the latter it can be assumed
the expression tree has already been formed.
Reverse Polish
Humans prefer to use in-fix order of notation. This means that the operand
is either side of the opcode. However, longer equations can cause
confusion over the order of execution.
Graph-Traversal
Graph-traversal is the process of visiting each vertex in a graph. There are
two algorithms in this section - depth-first and breadth-first graph-
traversals. In a depth-first search, a branch is fully explored before
backtracking, whereas in a breadth-first search a node is fully explored
before venturing on to the next node.
Depth-first traversal uses a stack. Depth-first traversal is used for
navigating a maze. The following example uses a tree, but a depth-first
algorithm can be performed on any connected graph.
Tree-Traversal
Tree-traversal is the process of visiting/updating/outputting each node in a
tree - it is a form of algorithm. Unlike a graph-traversal, tree-traversals are
unique to trees and must start at the root. From the root, they travel left,
down the tree. There are three types of tree-traversals; pre-order, in-order
and post-order. Pre-order and post-order tree-traversal can be performed
on any tree including binary trees but an in-order traversal is only well
defined for binary trees.
Pre-order traversal is used for copying a tree. It can be performed on
any tree.
In-order traversal is useful for a binary search tree and because it
will output the contents of a binary search tree in ascending order. It
can only be performed on binary trees.
Post-order traversals can be performed on any tree. They are useful
for Infix to RPN (Reverse Polish Notation) conversions, producing a
postfix expression from an expression tree and emptying a tree.
Infix to Postfix; as mentioned above, postorder traversal can be
used to make infix to RPN conversions and make postfix expressions
from expression trees. Technically, these two uses are the same. The
difference is that Infix to RPN would involve the making of and then
traversing of a binary tree, whereas in the latter it can be assumed
the expression tree has already been formed.
Reverse Polish
Humans prefer to use in-fix order of notation. This means that the operand
is either side of the opcode. However, longer equations can cause
confusion over the order of execution.
