Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Basics

The following is a mathematical definition of a tree:

Definition (Tree)  A tree  T is a finite, non-empty set of nodes ,

displaymath62541

with the following properties:

  1. A designated node of the set, r, is called the root  of the tree; and
  2. The remaining nodes are partitioned into tex2html_wrap_inline58277 subsets, tex2html_wrap_inline62549, tex2html_wrap_inline62551, ..., tex2html_wrap_inline62553, each of which is a tree.
For convenience, we shall use the notation tex2html_wrap_inline62555 to denote the tree T.

Notice that Definition gif is recursive--a tree is defined in terms of itself! Fortunately, we do not have a problem with infinite recursion because every tree has a finite number of of nodes and because in the base case a tree has n=0 subtrees.

It follows from Definition gif that the minimal tree is a tree comprised of a single root node. For example tex2html_wrap_inline62561 is such a tree. When there is more than one node, the remaining nodes are partitioned into subtrees. For example, the tex2html_wrap_inline62563 is a tree which is comprised of the root node B and the subtree tex2html_wrap_inline62567. Finally, the following is also a tree

  equation14196

How do tex2html_wrap_inline62569, tex2html_wrap_inline62571, and tex2html_wrap_inline62573 resemble their arboreal namesake? The similarity becomes apparent when we consider the graphical representation of these trees shown in Figure gif. To draw such a pictorial representation of a tree, tex2html_wrap_inline62555, the following recursive procedure is used: First, we first draw the root node r. Then, we draw each of the subtrees, tex2html_wrap_inline62549, tex2html_wrap_inline62551, ..., tex2html_wrap_inline62553, beside each other below the root. Finally, lines are drawn from r to the roots of each of the subtrees.

   figure14200
Figure: Examples of trees.

Of course, trees drawn in this fashion are upside down. Nevertheless, this is the conventional way in which tree data structures are drawn. In fact, it is understood that when we speak of ``up'' and ``down,'' we do so with respect to this pictorial representation. For example, when we move from a root to a subtree, we will say that we are moving down the tree.

The inverted pictorial representation of trees is probably due to the way that genealogical lineal charts are drawn. A lineal chart is a family tree that shows the descendants of some person. And it is from genealogy that much of the terminology associated with tree data structures is taken.




next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.