<![CDATA[
CSE143 Sample Program handout #22
Log of execution of testing program
-----------------------------------
Name (blank to quit)? Goofy
Name (blank to quit)? Daffy Duck
Name (blank to quit)? Superman
Name (blank to quit)? Wonder Woman
Name (blank to quit)? Cinderella
Name (blank to quit)? Batman
Name (blank to quit)? Robin
Name (blank to quit)? Batgirl
Name (blank to quit)? Cat Woman
Name (blank to quit)? Bugs Bunny
Name (blank to quit)? Road Runner
Name (blank to quit)? Wiley Coyote
Name (blank to quit)? Rocky
Name (blank to quit)? Bullwinkle
Name (blank to quit)?
Alphabetized list:
Batgirl
Batman
Bugs Bunny
Bullwinkle
Cat Woman
Cinderella
Daffy Duck
Goofy
Road Runner
Robin
Rocky
Superman
Wiley Coyote
Wonder Woman
Next int (0 to quit)? 12
Next int (0 to quit)? 8
Next int (0 to quit)? 7
Next int (0 to quit)? 15
Next int (0 to quit)? 29
Next int (0 to quit)? 3
Next int (0 to quit)? 48
Next int (0 to quit)? 8
Next int (0 to quit)? 6
Next int (0 to quit)? 92
Next int (0 to quit)? -8
Next int (0 to quit)? 23
Next int (0 to quit)? 105
Next int (0 to quit)? 0
Sorted list:
-8
3
6
7
8
8
12
15
23
29
48
92
105
Testing program
---------------
// Stuart Reges
// 5/13/05
//
// This program tests the SearchTree class by constructing a binary search tree
// of strings and a binary search tree of integers and printing out each.
public class SearchTreeTest {
public static void main(String[] args) {
Scanner console = new Scanner(System.in);
SearchTree names = new SearchTree();
for(;;) {
System.out.print("Name (blank to quit)? ");
String name = console.nextLine();
if (name.length() == 0)
break;
names.insert(name);
}
System.out.println();
System.out.println("Alphabetized list:");
names.print();
System.out.println();
SearchTree numbers = new SearchTree();
for(;;) {
System.out.print("Next int (0 to quit)? ");
int number = console.nextInt();
if (number == 0)
break;
numbers.insert(new Integer(number));
}
System.out.println();
System.out.println("Sorted list:");
numbers.print();
}
}
SearchTreeNode class
--------------------
// Class SearchTreeNode is used to build binary search trees.
public class SearchTreeNode {
public Comparable data; // data stored in this node
public SearchTreeNode left; // reference to left subtree
public SearchTreeNode right; // reference to right subtree
// post: constructs a SearchTreeNode as a leaf with given data
public SearchTreeNode(Object data) {
this(data, null, null);
}
// post: constructs a SearchTreeNode with the given data and links
public SearchTreeNode(Object data, SearchTreeNode left,
SearchTreeNode right) {
this.data = (Comparable)data;
this.left = left;
this.right = right;
}
}
SearchTree Class
----------------
// Class SearchTree stores and prints a binary search tree of Comparable
// objects. It has the following public methods:
//
// public SearchTree()
// constructs an empty search tree
// public void insert(Object next)
// insert the given data into the tree
// public void print()
// print the tree in sorted order
public class SearchTree {
private SearchTreeNode root; // root of overall tree
// post: constructs an empty search tree
public SearchTree() {
root = null;
}
// post: next added to tree so as to preserve binary search tree
public void insert(Object next) {
root = insert(next, root);
}
// pre : node refers to a binary search tree
// post: next added to tree so as to preserve binary search tree
private SearchTreeNode insert(Object next, SearchTreeNode node) {
if (node == null)
node = new SearchTreeNode(next);
else if (node.data.compareTo(next) >= 0)
node.left = insert(next, node.left);
else
node.right = insert(next, node.right);
return node;
}
// post: prints the data fields of the tree, one per line
public void print() {
printInorder(root);
}
// pre : root points to a binary search tree
// post: prints the data fields of the tree using an inorder traversal
private void printInorder(SearchTreeNode node) {
if (node != null) {
printInorder(node.left);
System.out.println(node.data);
printInorder(node.right);
}
}
}
]]>