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.

Path in a Tree

A path is any linear subset of a tree, e.g. A-B-E and C-F are paths. The length of a path could be counted as either the number of nodes or the number of edges on the path - in the lectures we will count the nodes; e.g. A-B-E has length 3. But be careful: there is no agreed definition! The textbook defines path length as the number of edges.

There is a unique path from the root to any node. Simple as this property seems, it is extremely important: all our algorithms for processing trees will depend upon it. The depth or level of a node is the length of this path. When you draw a tree, it is very useful if all the nodes in the same level are drawn as a neat horizontal row. Thedepth or height of a tree is the maximum depth of the nodes in the tree.

Ordered Trees

A tree is ordered if there is some significance to the order of the subtrees. For example, consider this tree:

       

If this is a family tree, there could be no significance to left and right. In this case the tree is unordered, and we could redraw the tree exchanging subtrees without affecting the meaning of the tree. On the other hand, there may be some significance to left and right - maybe the left child is younger than the right... or (as is the case here) maybe the left child has the name that is earlier in the alphabet. Then, the tree is ordered and we are not free to move around the subtrees.

For now we will restrict ourselves to ordered trees. Like lists, ordered N-ary trees have a nice recursive structural definition: