<![CDATA[
CSE143 Binary Search Tree Code handout #25
Client Program IntSearchTreeClient.java
---------------------------------------
// This program tests the IntSearchTree class by constructing a
// binary search tree of integers and printing its contents as
// well as its structure.
import java.util.*;
public class IntSearchTreeClient {
public static void main(String[] args) {
Scanner console = new Scanner(System.in);
IntTree numbers = new IntTree();
System.out.print("Next int (0 to quit)? ");
int number = console.nextInt();
while (number != 0) {
numbers.add(number);
System.out.print("Next int (0 to quit)? ");
number = console.nextInt();
}
System.out.println();
System.out.println("Tree Structure:");
numbers.printSideways();
System.out.println("Sorted list:");
numbers.print();
}
}
Sample Execution of IntSearchTreeClient
---------------------------------------
Next int (0 to quit)? 20
Next int (0 to quit)? 8
Next int (0 to quit)? 93
Next int (0 to quit)? 7
Next int (0 to quit)? 5
Next int (0 to quit)? 14
Next int (0 to quit)? 42
Next int (0 to quit)? 92
Next int (0 to quit)? 25
Next int (0 to quit)? 12
Next int (0 to quit)? 0
Tree Structure:
93
92
42
25
20
14
12
8
7
5
Sorted list:
inorder: 5 7 8 12 14 20 25 42 92 93
New Code for IntTree
--------------------
The client program requires a new constructor for making an empty tree:
// post: constructs an empty tree
public IntTree() {
overallRoot = null;
}
And we need a new add method:
// post: value is added to overall tree so as to preserve the
// binary search tree property
public void add(int value) {
overallRoot = add(overallRoot, value);
}
// post: value is added to given tree so as to preserve the
// binary search tree property
private IntTreeNode add(IntTreeNode root, int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value <= root.data) {
root.left = add(root.left, value);
} else {
root.right = add(root.right, value);
}
return root;
}
Below is a contains method that efficiently searches for a value taking
advantage of the binary search tree property:
// post: returns true if overall tree contains value
public boolean contains(int value) {
return contains(overallRoot, value);
}
// post: returns true if given tree contains value
private boolean contains(IntTreeNode root, int value) {
if (root == null) {
return false;
} else if (value == root.data) {
return true;
} else if (value < root.data) {
return contains(root.left, value);
} else { // value > root.data
return contains(root.right, value);
}
}
]]>