Breadth First Traversal

These three are certainly not the only possible traversal orders. Another very natural traversal order is ``level by level'' - the root is processed first, all its children are processed next, then all of their children, etc. down to the bottom level. This is called breadth first traversal. In the above example, it would process nodes in the order: A-B-C-D-E-F. It is not difficult to write a breadth-first traversal, but is not quite as simple as the traversal orders just described.

2. Tree Traversal

What I've just called ``scanning through'' a tree is actually called traversing a tree.

General Definition: to traverse a data structure is to process, however you like, every node in the data structure exactly once.

Note: You may ``pass through'' a node as many times as you like but you must only process the node once.

E.g. we can talk about ``traversing a list'', which means going through the list and processing every node once. We had a special name for this: map.

For a specific data structure, we talk about the different orders in which it might be traversed. For a list there are two common traversal orders: first-to-last (the most common) and last-to-first.

The general recursive pattern for traversing a (non-empty) binary tree is this: At node N you must do these three things:

Structural Definition of Binary Trees

A binary tree is either empty or it has 3 parts:

• a value
• a left subtree
• a right subtree

Whenever a data structure has a recursive definition like this, most of the `properties' of the data structure can be computed in a recursive manner which exactly mirrors the definition.

For example, here is a function to compute the number of nodes in a binary tree:

        int size(binary_tree *t)

        {

          return is_empty(t) ? 0 : 1 + size(t->left) + size(t->right);

        }

With lists we had an alternative to recursion - we could scan through a list as easily with normal loops (while, do ... while) as with recursion. This is not true for trees. It is possible to scan through a tree non-recursively, but it is not nearly as easy as scanning recursively.

Drawing Trees

Here is how we draw a tree:

The root is at the top; below it are its children. An arc connects a node to each of its children: we sometimes draw arrowheads on the arc, but they are optional because the direction parent->child is always top->bottom.

Then we continue in the same manner, the children of each node are drawn below the node.

For example, here is a binary tree:

       

In general, each child of a node is the root of a tree ``within the big tree''. For example, B is the root of a little tree (B,D,E), so is C. These inner trees are calledsubtrees. The subtrees of a node are the trees whose roots are the children of the node. e.g. the subtrees of A are the subtrees whose roots are B and C. In a binary tree we refer to the left subtree and the right subtree.

1. Introduction To Trees

We will now turn to tree structures, which is the subject of most of the rest of the course.

Definition of Trees

Trees are as common and important as lists. And like lists there are many variations - binary search trees, balanced trees, and heaps are the main ones we will look at.

Recall that a list is a collection of components in which

1.     each component (except one, the first) has exactly 1 predecessor.

2.     each component (except one, the last) has exactly 1 successor.

a tree is very similar: it has property (1) but (2) is slightly relaxed:

(2') each component has some number of successors.

If there is no limit on the number of successors that a node can have, the tree is called a general tree.