Linked Data Structures - Absolute Java - page 884

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

29 public boolean contains( int item)
30 {
31

return isInSubtree(item, root);

32 }
33 public void showElements( )
34 {
35 showElementsInSubtree(root);
36 }
37 /**
38 Returns the root node of a tree that is the tree with root node
39 subTreeRoot, but with a new node added that contains item.
40 */
41 private static IntTreeNode insertInSubtree( int item,
42 IntTreeNode subTreeRoot)
43 {
44 if (subTreeRoot == null )
45 return new IntTreeNode(item, null , null );
46 else if (item < subTreeRoot.data)
47 {
48

subTreeRoot.leftLink = insertInSubtree(item, subTreeRoot.
leftLink);

49 return subTreeRoot;

50 }
51 else //item >= subTreeRoot.data
52 {
53 subTreeRoot.rightLink = insertInSubtree(item, subTreeRoot.

rightLink);

54 return subTreeRoot;

55 }
56 }
57 private static boolean isInSubtree( int item, IntTreeNode
subTreeRoot)
58 {
59 if (subTreeRoot == null )

60 return false ;

61 else if (subTreeRoot.data == item)

62 return true ;

63 else if (item < subTreeRoot.data)

64 return isInSubtree(item, subTreeRoot.leftLink);

65 else //item >= link.data

66 return isInSubtree(item, subTreeRoot.rightLink);

67 }

68 private static void showElementsInSubtree(IntTreeNode subTreeRoot)
69 { //Uses inorder traversal.
70 if (subTreeRoot != null )
71 {
72 showElementsInSubtree(subTreeRoot.leftLink);
73 System.out.print(subTreeRoot.data + " ");
74 showElementsInSubtree(subTreeRoot.rightLink);
75 } //else do nothing. Empty tree has nothing to display.
76 }
77 }