<![CDATA[
CSE143 Binary Search Tree Code handout #25
Client Program IntTreeTest2.java
--------------------------------
// Stuart Reges
// 11/15/06
//
// This program tests the IntTree class by constructing a binary search tree
// of integers and printing it out.
import java.util.*;
public class IntTreeTest2 {
public static void main(String[] args) {
Scanner console = new Scanner(System.in);
IntTree numbers = new IntTree();
for(;;) {
System.out.print("Next int (0 to quit)? ");
int number = console.nextInt();
if (number == 0)
break;
numbers.add(number);
}
System.out.println();
System.out.println("Tree Structure:");
numbers.printStructure();
System.out.println("Sorted list:");
numbers.printInorder();
}
}
Sample Execution of IntTreeTest2
--------------------------------
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:
// pre : the tree satisfies the binary search tree property
// post: value is added so as to preserve the binary search tree property
public void add(int value) {
overallRoot = add(overallRoot, value);
}
// pre : the tree with given root satisfies the binary search tree property
// post: value is added 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;
}
]]>