The tree-traversal algorithms that we considered in Recursion and Trees～ Mathematical Properties of Trees and Tree Traversal exemplify the basic fact that we are led to consider recursive algorithms for binary trees, because of these trees’ very nature as recursive structures. Many tasks admit direct recursive divide-and-conquer algorithms, which essentially generalize the traversal algorithms. We process a tree by processing the root node and (recursively) its subtrees; we can do computation before, between, or after the recursive calls (or possibly all three).
We frequently need to find the values of various structural parameters for a tree, given only a link to the tree. For example, Program 1 comprises recursive functions for computing the number of nodes in and the height of a given tree. The functions follow immediately from Definition 1 in Recursion and Trees～ Mathematical Properties of Trees and Tree Traversal. Neither of these functions depends on the order in which the recursive calls are processed: they process all the nodes in the tree and return the same answer if we, for example, exchange the recursive calls. Not all tree parameters are so easily computed: for example, a program to compute efficiently the internal path length of a binary tree is more challenging.
Another function that is useful whenever we write programs that process trees is one that prints out or draws the tree. For example, Program 2 is a recursive procedure that prints out a tree in the format illustrated in Figure 1. We can use the same basic recursive scheme to draw more elaborate representations of trees, such as those that we use in the figures in this series.
Program 1 Computation of tree parameters
We can use simple recursive procedures such as these to learn basic structural properties of trees.
Program 2 Quick-print function
This recursive program keeps track of the tree height and uses that information for indentation in printing out a representation of the tree that we can use to debug tree-processing program (see Figure 1). It assumes that items in nodes are characters.
Figure 1 Printing a tree (inorder and preorder)
The output at the left results from using Program 2 on the sample tree in Figure 3 in Recursion and Trees～ Mathematical Properties of Trees and Tree Traversal, and exhibits the tree structure in a manner similar to the graphical representation that we have been using, rotated 90 degrees. The output at the right is from the same program with the print statement moved to the beginning; it exhibits the tree structure in a familiar outline format.
Program 2 is an inorder traversal—if we print the item before the recursive calls, we get a preorder traversal, which is also illustrated in Figure 1. This format is a familiar one that we might use, for example, for a family tree, or to list files in a tree-based file system, or to make an outline of a printed document. For example, doing a preorder traversal of the tree in Figure 1 in Recursion and Trees～ Trees gives a version of the table of contents of this series.
Our first example of a program that builds an explicit binary tree structure is associated with the find-the-maximum application that we considered in Recursion and Trees～ Divide and Conquer. Our goal is to build a tournament: a binary tree where the item in every internal node is a copy of the larger of the items in its two children. In particular, the item at the root is a copy of the largest item in the tournament. The items in the leaves (nodes with no children) constitute the data of interest, and the rest of the tree is a data structure that allows us to find the largest of the items efficiently.
Program 3 is a recursive program that builds a tournament from the items in an array. A modification of Program 1 in Recursion and Trees～ Divide and Conquer, it thus uses a divide-and-conquer recursive strategy: To build a tournament for a single item, we create (and return) a leaf containing that item. To build a tournament for N > 1 items, we use the divide-and-conquer strategy: Divide the items in half, build tournaments for each half, and create a new node with links to the two tournaments and with an item that is a copy of the larger of the items in the roots of the two tournaments.
Figure 2 is an example of an explicit tree structure that might be built by Program 3. Building a recursive data structure such as this one is perhaps preferable in some situations to finding the maximum by scanning the data, as we did in Program 1 in Recursion and Trees～ Divide and Conquer, because the tree structure provides us with the flexibility to perform other operations. The very operation that we use to build the tournament is an important example: Given two tournaments, we can combine them into a single tournament in constant time, by creating a new node, making its left link point to one of the tournaments and its right link point to the other, and taking the larger of the two items (at the roots of the two given tournaments) as the largest item in the combined tournament. We also can consider algorithms for adding items, removing items, and performing other operations.
Program 3 Construction of a tournament
This recursive function divides a file a[ l ], …, a[ r ] into the two parts a[ l ], …, a[m] and a[m+1], …, a[ r ], builds tournaments for the two parts (recursively), and makes a tournament for the whole file by setting links in a new node to the recursively built tournaments and setting its item value to the larger of the items in the roots of the two recursively built tournaments.
Figure 2 Explicit tree for finding the maximum (tournament)
This figure depicts the explicit tree structure that is constructed by Program 3 from the input A M P L E. The data items are in the leaves. Each internal node has a copy of the larger of the items in its two children, so, by induction, the largest item is at the root.
Indeed, tree-based implementations for several of the generalized queue ADTs that we discussed in Abstract Data Types～Queues and Unique Items are a primary topic of discussion for much of this series. In particular, many of the algorithms in later series are based on binary search trees, which are explicit trees that correspond to binary search, in a relationship analogous to the relationship between the explicit structure of Figure 2 and the recursive find-the-maximum algorithm. The challenge in implementing and using such structures is to ensure that our algorithms remain efficient after a long sequence of insert, delete, and other operations.
Our second example of a program that builds a binary tree is a modification of our prefix-expression-evaluation program in Program 4 in Recursion and Trees～ Recursive Algorithms to construct a tree representing a prefix expression, instead of just evaluating it (see Figure 3). Program 4 uses the same recursive scheme as Program 4 in Recursion and Trees～ Recursive Algorithms, but the recursive function returns a link to a tree, rather than a value. We create a new tree node for each character in the expression: Nodes corresponding to operators have links to their operands, and the leaf nodes contain the variables (or constants) that are inputs to the expression.
Figure 3 Parse tree
This tree is constructed by Program 4 for the prefix expression * + a * * b c + d e f. It is a natural way to represent the expression: Each operand is in a leaf (which we draw here as an external node), and each operator is to be applied to the expressions represented by the left and right subtrees of the node containing the operator.
Program 4 Construction of a parse tree
Using the same strategy that we used to evaluate prefix expressions (see Program 4 in Recursion and Trees～ Recursive Algorithms), this program builds a parse tree from a prefix expression. For simplicity, we assume that operands are single characters. Each call of the recursive function creates a new node with the next character from the input as the token. If the token is an operand, we return the new node; if it is an operator, we set the left and right pointers to the tree built (recursively) for the two arguments.
Translation programs such as compilers often use such internal tree representations for programs, because the trees are useful for many purposes. For example, we might imagine operands corresponding to variables that take on values, and we could generate machine code to evaluate the expression represented by the tree with a postorder traversal. Or, we could use the tree to print out the expression in infix with an inorder traversal or in postfix with a postorder traversal.
We considered the few examples in this section to introduce the concept that we can build and process explicit linked tree structures with recursive programs. To do so effectively, we need to consider the performance of various algorithms, alternate representations, nonrecursive alternatives, and many other details.