TREES

A tree is made up of nodes (data elements) with zero, one, or several references (or pointers) to other nodes. Each node has only one other node referencing it. The result is a data structure that looks like Figure 6-1.

FIGURE 6-1

As in a linked list, a node is represented by a structure or class, and trees can be implemented in any language that includes pointers or references. In object-oriented languages you usually define a class for the common parts of a node and one or more subclasses for the data held by a node. For example, the following are the C# classes you might use for a tree of integers:

public class Node {
    public Node[] children;
}

public class IntNode : Node {
    public int value;
}

In this definition, children is an array that keeps track of all the nodes that this node references. For simplicity, these classes expose the children as public data members, but this isn’t good coding practice. A proper class definition would make them private and...