Trees are a form of graph. Decision trees consist of a series of branches that represent different choices that can be made. The "root" is at the top of the tree diagram and the "children" are below. Nodes that have branches and nodes below them are known as parent nodes. The connections between nodes in a tree are known as "arcs" or "branches".

The "degree" of a tree is the maximum number of nodes that can exist below it. For example, binary trees are of degree 2. A Unary tree (or sequence) is a single line of nodes with no branches. Subtrees are any collection of branches and nodes within the overall tree.

Traversing a tree involves visiting the nodes within a tree in a certain way. For simplicity, the definitions below refer to traversing a binary tree. The example binary tree below is used to help show how the nodes are returned for each traversal method. The lettering of the nodes does not bear any relationship to how they were arranged in the tree initially but is purely for referencing.

      A
     / \
    B   H
   / \
  C   E
 /   / \
D   F   G

Post-order traversal of a tree involves the traversal of the left subtree first from the bottom up, then the right subtree, then the root node. When traversing each subtree, the left-most node at the bottom of the tree diagram is visited first. Post-order traversal of the binary tree shown above would return the nodes in the order "D C F G E B H A".

In-order traversal of a tree is generally only used to traverse binary trees whereas Pre-order and Post-order traversal are quite normally used on trees other than binary trees. In-order traversal is where each node in the tree has its left child visited first, the node itself visited next, then its right child is visited. In-order traversal of the binary tree shown above would return the nodes in the order "D C B F E G A H"

Search for "Trees and Traversal" on: Google | Kelkoo | Amazon | eBay (UK) | eBay (US)

Search for "Trees and Traversal" on the rest of Computing Students: Trees and Traversal