Java Reference
In-Depth Information
tends to be error prone. While
preorder2
insures that no recursive calls will
be made on empty subtrees, it will fail if the initial call passes in a
null
pointer.
This would occur if the original tree is empty. To avoid the bug, either
preorder2
needs an additional test for a
null
pointer at the beginning (making the subsequent
tests redundant after all), or the caller of
preorder2
has a hidden obligation to
pass in a non-empty tree, which is unreliable design. The net result is that many
programmers forget to test for the possibility that the empty tree is being traversed.
By using the first design, which explicitly supports processing of empty subtrees,
the problem is avoided.
Another issue to consider when designing a traversal is how to define the visitor
function that is to be executed on every node. One approach is simply to write a
new version of the traversal for each such visitor function as needed. The disad-
vantage to this is that whatever function does the traversal must have access to the
BinNode
class. It is probably better design to permit only the tree class to have
access to the
BinNode
class.
Another approach is for the tree class to supply a generic traversal function
which takes the visitor as a function parameter. This is known as the visitor design
pattern. A major constraint on this approach is that the signature for all visitor
functions, that is, their return type and parameters, must be fixed in advance. Thus,
the designer of the generic traversal function must be able to adequately judge what
parameters and return type will likely be needed by potential visitor functions.
Handling information flow between parts of a program can be a significant
design challenge, especially when dealing with recursive functions such as tree
traversals. In general, we can run into trouble either with passing in the correct
information needed by the function to do its work, or with returning information
to the recursive function's caller. We will see many examples throughout the topic
that illustrate methods for passing information in and out of recursive functions as
they traverse a tree structure. Here are a few simple examples.
First we consider the simple case where a computation requires that we com-
municate information back up the tree to the end user.
Example5.4
We wish to count the number of nodes in a binary tree. The
key insight is that the total count for any (non-empty) subtree is one for the
root plus the counts for the left and right subtrees. Where do left and right
subtree counts come from? Calls to function
count
on the subtrees will
compute this for us. Thus, we can implement
count
as follows.
intcount(BinNodert){
if(rt==null)return0;//Nothingtocount
return1+count(rt.left())+count(rt.right());
}
