Learning about trees

Mathematically, a tree is a kind of graph structure; it consists of nodes and edges that connect those nodes. All the nodes in a tree are connected. A single node at the top is called the root. Tree nodes can have zero or more children, and at most one parent. A tree node with zero children is called a leaf; most trees have a lot of leaves. A tree node that is not a leaf has one or more children and is called an internal node. Figure 5.1 shows an example tree with a root, two additional internal nodes, and five leaves:

Figure 5.1: A tree with a root, internal nodes, and leaves

Trees have a property called arity that specifies the maximum number of children that occur for any node in the tree. An arity of 1 would give you a linked list. Perhaps the most common kinds of trees are binary trees (arity = 2). The kind of trees we need has as many children as there are symbols on the right-hand side of the rules in our grammar; these are so-called n-ary...