Linked Data Structures - Absolute Java - page 883

EXAMPLE: (continued)

Note that the method insertInSubtree searches the tree just as the method
isInSubtree does, but it does not stop if it finds item ; instead, it searches until it
reaches a leaf node—that is, a node containing null . This null is where the item
belongs in the tree, so it replaces null with a new subtree containing a single node
that contains item . You may need to think about the method insertInSubtree
a bit to see that it works correctly; allow yourself some time to study the method
insertInSubtree and be sure you are convinced that after the addition, like the
following,

subTreeRoot = insertInSubtree(item, subTreeRoot);
the tree with root node subTreeRoot still satisfies the Binary Search Tree
Storage Rule.
The rest of the definition of the class IntTree is routine.

Display 15.40 A Binary Search Tree for Integers (part 1 of 2)

1 /**
2 Class invariant: The tree satisfies the binary search tree storage rule.
3 */
4 public class IntTree
5 {
6 private static class IntTreeNode
7 {
8

The only reason this inner
class is static is that it is
used in the static methods
insertInSubtree ,
isInSubtree , and
showElementsInSubtree .

private int data;

9 private IntTreeNode leftLink;

10 private IntTreeNode rightLink;

11
12 public IntTreeNode( int newData, IntTreeNode newLeftLink,
13 IntTreeNode newRightLink)
14 {
15 data = newData;
16 leftLink = newLeftLink;
17 rightLink = newRightLink;
18 }
19 } //End of IntTreeNode inner class

20 private IntTreeNode root;

This class should have more methods.
This is just a sample of possible methods.

21 public IntTree( )
22 {
23 root = null ;

24 }

25 public void add( int item)
26 {
27 root = insertInSubtree(item, root);
28 }

(continued)