Java Reference
In-Depth Information
This simple rearrangement of the three calls causes the code to print in an inorder
manner rather than a preorder manner.
You can create another set of methods for printing in postorder by again rearrang-
ing the three operations so that the two recursive calls are made before the print .
It is important to understand why this seemingly small change of moving the
print statement relative to the recursive calls generates such different behavior. It's
because each recursive call potentially processes a large amount of data (an entire
subtree). You'll find that this is a common property of binary tree code. A minor
change to the code can produce very different results.
Constructing and Viewing a Tree
It's difficult to know whether our traversal methods work unless we can construct a
tree and examine its structure. Most often we develop binary tree code with a specific
application in mind. We're trying to keep things simple initially, so for now, let's con-
struct a very specific tree that will allow us to test our code.
Using recursion, we can fairly easily construct a tree that has nodes numbered in a
sequential manner level by level, as in this tree of nine nodes:
1
2
3
4
5
6
7
8
9
Notice how the number 1 is on the first level, then 2 and 3 on the next level, then
4, 5, 6, and 7, and so on. In this structure, we will fill in every possible node up to
some maximum node number. Let's refer to this as a sequential tree to simplify our
discussion.
Assume that the constructor for the class will be passed the maximum node number
to include in the tree:
public IntTree(int max) {
...
}
This is another case in which you need to introduce a private method to do most of
the work for you. In our previous pattern, we wrote methods that take a parameter of
type IntTreeNode and our initial call passed the value of the field overallRoot to start
the ball rolling. In this case, there is no tree to traverse. The whole point of the method is
to construct the tree. Instead of passing overallRoot as a parameter, we want to use the
 
Search WWH ::




Custom Search