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. The following diagram 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 says what the maximum number of children a node can have is. 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...
