Recursive Binary-Tree Algorithms
The tree-traversal algorithms that we considered in 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 5.17 comprises recursive methods for computing the number of nodes in and the height of a given tree. The methods follow immediately from Definition 5.6. Neither of these methods 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 (see Exercises 5.88 through 5.90).
Computation of tree parameters
We can use simple recursive methods such as these to learn basic structural properties of trees.
private static int count(Node h) { if (h == null) return 0; return count(h.l) + count(h.r) + 1; } int count() { return count(root); } private static int height(Node h) { if (h == null) return -1; int u = height(h.l), v = height(h.r); if (u > v) return u+1; else return v+1; } int height() { return height(root); }
Another method that is useful whenever we write programs that process trees is one that prints out or draws the tree. For example, Program 5.18 is a recursive procedure that prints out a tree in the format illustrated in Screenshot. 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 tutorial (see Exercise 5.85).
Screenshot Printing a tree (inorder and preorder)
The output at the left results from using Program 5.18 on the sample tree in Screenshot 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 5.18 is an inorder traversal-if we print the item before the recursive calls, we get a preorder traversal, which is also illustrated in Screenshot. 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 Screenshot gives a version of the table of contents of this tutorial.
Quick tree-print method
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 programs (see Screenshot). It assumes that items in nodes are of type Item.
static void printnode(Item x, int h) {
for (int i = 0;i<h;i++)
Out.print(" ");
Out.println("[" + x + "]"); } private static void showR(Node t, int h) { if (t == null) { printnode(null, h); return; } showR(t.r, h+1); printnode(t.item, h); showR(t.l, h+1); } void show() { showR(root, 0); }
Construction of a tournament
This recursive method divides an array 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 array by setting links in a new node to the recursively built tournaments and setting its value to the larger of the values in the roots of the two recursively built tournaments.
static class Node { double val; Node l; Node r; Node(double v, Node l, Node r) { this.val = v; this.l = l; this.r = r; } } static Node max(double a[], int l, int r) { int m = (l+r)/2; Node x = new Node(a[m], null, null); if (l == r) return x; x.l = max(a, l, m); x.r = max(a, m+1, r); double u = x.l.val, v = x.r.val; if (u > v) x.val = u; else x.val = v; return x; }
Our first example of a program that builds an explicit binary tree structure is associated with the find-the-maximum app that we considered in . 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 5.19 is a recursive program that builds a tournament from the items in an array. A modification of Program 5.6, 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.
Screenshot is an example of an explicit tree structure that might be built by Program 5.19. 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 5.6, 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. We shall not consider such operations in any further detail here because similar data structures with this flexibility are the topic of .
Screenshot Explicit tree for finding the maximum (tournament)
This figure depicts the explicit tree structure that is constructed by Program 5.19 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; by induction, the largest item is at the root.
Indeed, tree-based implementations for several of the generalized queue ADTs that we discussed in are a primary topic of discussion for much of this tutorial. In particular, many of the algorithms in Chapters 12 through 15 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 Screenshot and the recursive find-the-maximum algorithm (see Screenshot). The challenge in implementing and using such structures is to ensure that our algorithms remain efficient after a long sequence of insert, remove, 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 5.4) to construct a tree representing a prefix expression, instead of just evaluating it (see Screenshot). Program 5.20 uses the same recursive scheme as Program 5.4, but the recursive method 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.
Screenshot Parse tree
This tree is constructed by Program 5.20 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.
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. However, we shall defer consideration of tree-processing programs in further detail until , because we use trees primarily for descriptive purposes in Chapters 7 through 11. We return to explicit tree implementations in because they form the basis of numerous algorithms that we consider in Chapters 12 through 15.
Exercises
Modify Program 5.18 to output a PostScript program that draws the tree, in a format like that used in Screenshot, but without the small boxes to represent the external nodes. Use moveto and lineto to draw lines, and the user-defined operator
/node { newpath moveto currentpoint 4 0 360 arc fill} defto draw nodes. After this definition, the call node draws a black dot at the coordinates on the stack (see ).
5.86 Write a program that counts the leaves in a binary tree.
Construction of a parse tree
To build a parse tree instead of just evaluating a prefix expression, we could use this recursive method instead of the eval method in Program 5.4. For simplicity, this code assumes that operands are single characters and that a Node class is defined like the one in Program 5.19, but with a char field for its data. Each call of the recursive method 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.
static Node parse() { char t = a[i++]; Node x = new Node(t); if ((t == '+') || (t == '*')) { x.l = parse(); x.r = parse(); } return x; }Determine the number of method invocations made by your program when it is computing the internal path length of a binary tree. Prove your answer by induction.
5.90 Write a recursive program that computes the internal path length of a binary tree in time proportional to the number of nodes in the tree.