Java Reference
In-Depth Information
IntTreeNode left = buildTree(2 * n, max);
IntTreeNode right = buildTree(2 * n + 1, max);
return new IntTreeNode(n, left, right);
}
}
The preceding code works and is very clear in terms of the steps performed. In the
recursive case (the
else
branch), you can see that you construct a left subtree, then
construct a right subtree, and finally put these pieces together into a new
IntTreeNode
that is returned by the method. Although this code is clear, many people
prefer to write it even more concisely to eliminate the local variables. You can rewrite
the method above as follows:
private IntTreeNode buildTree(int n, int max) {
if (n > max) {
return null;
} else {
return new IntTreeNode(n, buildTree(2 * n, max),
buildTree(2 * n + 1, max));
}
}
Even though this tree ends up having a very predictable structure, it is helpful to
develop a method that shows the structure more clearly. Some programming environ-
ments like jGRASP have “structure viewers” that allow you to see a visual represen-
tation of a binary tree. If you don't have access to such a program, you might want to
take a simplified approach to viewing the structure of the tree.
You can accomplish this by writing a simple variation of your inorder traversal.
Instead of printing values all on a line, you will print them one per line and use
indentation to indicate the level of the tree. For example, consider the following
simple tree:
7
6
5
You'd want your program to produce output like this:
5
7
6
Search WWH ::
Custom Search