Java Reference
In-Depth Information
20
50
40
75
20 TO 40
Figure5.6
To be a binary search tree, the left child of the node with value 40
must have a value between 20 and 40.
Another problem that occurs when recursively processing data collections is
controlling which members of the collection will be visited. For example, some
tree “traversals” might in fact visit only some tree nodes, while avoiding processing
of others. Exercise 5.20 must solve exactly this problem in the context of a binary
search tree. It must visit only those children of a given node that might possibly
fall within a given range of values. Fortunately, it requires only a simple local
calculation to determine which child(ren) to visit.
A more difficult situation is illustrated by the following problem. Given an
arbitrary binary tree we wish to determine if, for every node A, are all nodes in A's
left subtree less than the value of A, and are all nodes in A's right subtree greater
than the value of A? (This happens to be the definition for a binary search tree,
described in Section 5.4.) Unfortunately, to make this decision we need to know
some context that is not available just by looking at the node's parent or children.
As shown by Figure 5.6, it is not enough to verify that A's left child has a value
less than that of A, and that A's right child has a greater value. Nor is it enough to
verify that A has a value consistent with that of its parent. In fact, we need to know
information about what range of values is legal for a given node. That information
might come from any of the node's ancestors. Thus, relevant range information
must be passed down the tree. We can implement this function as follows.
booleancheckBST(BinNode<Integer>rt,
intlow,inthigh){
if(rt==null)returntrue;//Emptysubtree
introotkey=rt.element();
if((rootkey<low)||(rootkey>high))
returnfalse;//Outofrange
if(!checkBST(rt.left(),low,rootkey))
returnfalse;//Leftsidefailed
returncheckBST(rt.right(),rootkey,high);
}
