<![CDATA[
CSE143 Generic Binary Search Tree handout #28
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.
import java.util.*;
public class SearchTreeTest {
public static void main(String[] args) {
Scanner console = new Scanner(System.in);
SearchTree<String> names = new SearchTree<String>();
for(;;) {
System.out.print("Name (blank to quit)? ");
String name = console.nextLine();
if (name.length() == 0)
break;
names.add(name);
}
System.out.println();
System.out.println("Alphabetized list:");
names.print();
System.out.println();
SearchTree<Integer> numbers = new SearchTree<Integer>();
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("Sorted list:");
numbers.print();
}
}
SearchTreeNode class
--------------------
// Class SearchTreeNode is used to build binary search trees.
public class SearchTreeNode<E> {
public E data; // data stored in this node
public SearchTreeNode<E> left; // reference to left subtree
public SearchTreeNode<E> right; // reference to right subtree
// post: constructs a SearchTreeNode as a leaf with given data
public SearchTreeNode(E data) {
this(data, null, null);
}
// post: constructs a SearchTreeNode with the given data and links
public SearchTreeNode(E data, SearchTreeNode<E> left,
SearchTreeNode<E> right) {
this.data = data;
this.left = left;
this.right = right;
}
}
SearchTree Class
----------------
// Class SearchTree stores and prints a binary search tree of objects of
// type E. E must implement the Comparable<E> interface.
public class SearchTree<E extends Comparable<E>> {
private SearchTreeNode<E> overallRoot; // root of overall tree
// post: constructs an empty search tree
public SearchTree() {
overallRoot = null;
}
// post: next added to tree so as to preserve binary search tree
public void add(E next) {
overallRoot = add(next, overallRoot);
}
// post: next added to tree so as to preserve binary search tree
private SearchTreeNode<E> add(E next, SearchTreeNode<E> root) {
if (root == null)
root = new SearchTreeNode<E>(next);
else if (root.data.compareTo(next) >= 0)
root.left = add(next, root.left);
else
root.right = add(next, root.right);
return root;
}
// post: returns true if tree contains next, returns false otherwise
public boolean contains(E next) {
return contains(next, overallRoot);
}
// post: returns true if given tree contains next, returns false otherwise
private boolean contains(E next, SearchTreeNode<E> root) {
if (root == null)
return false;
else {
int compare = next.compareTo(root.data);
if (compare == 0)
return true;
else if (compare < 0)
return contains(next, root.left);
else
return contains(next, root.right);
}
}
// post: prints the data of the tree, one per line
public void print() {
printInorder(overallRoot);
}
// post: prints the data of the tree using an inorder traversal
private void printInorder(SearchTreeNode<E> root) {
if (root != null) {
printInorder(root.left);
System.out.println(root.data);
printInorder(root.right);
}
}
}
]]>