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.

If there is an maximum number N of successors for a node, then the tree is called an N-ary tree. In particular a binary (2-ary) tree is a tree in which each node has either 0, 1, or 2 successors.

In the lectures we will always use binary trees. It turns out this is not a restriction at all because all trees, even general trees, can be represented using binary trees (see text, (section 7.3.3)).

The unique node with no predecessor is called the root of the tree. A node with no successors is called a leaf - there will usually be many leaves in a tree. The successors of a node are called its children; the unique predecessor of a node is called its parent. If two nodes have the same parent, they are called brothers orsiblings. In a binary tree the two children are called the left and right.