<![CDATA[
CSE143X Binary Search Tree Code handout #23
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
Class IntTreeNode.java
----------------------
// Class for storing a single node of a binary tree of ints
public class IntTreeNode {
public int data;
public IntTreeNode left;
public IntTreeNode right;
// constructs a leaf node with given data
public IntTreeNode(int data) {
this(data, null, null);
}
// constructs a branch node with given data, left subtree,
// right subtree
public IntTreeNode(int data, IntTreeNode left,
IntTreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}
Class IntTree.java
------------------
// Simple binary tree class that includes methods to build a binary search
// tree, to see whether it contains a value, to print the structure, and to
// print the data using a preorder, inorder or postorder traversal.
public class IntTree {
private IntTreeNode overallRoot;
// default constructor sets overallRoot to null to construct an empty tree
// 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;
}
// 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);
}
}
// post: prints the tree contents using a preorder traversal
public void printPreorder() {
System.out.print("preorder:");
printPreorder(overallRoot);
System.out.println();
}
// post: prints in preorder the tree with given root
private void printPreorder(IntTreeNode root) {
if (root != null) {
System.out.print(" " + root.data);
printPreorder(root.left);
printPreorder(root.right);
}
}
// post: prints the tree contents using an inorder traversal
public void printInorder() {
System.out.print("inorder:");
printInorder(overallRoot);
System.out.println();
}
// post: prints in inorder the tree with given root
private void printInorder(IntTreeNode root) {
if (root != null) {
printInorder(root.left);
System.out.print(" " + root.data);
printInorder(root.right);
}
}
// post: prints the tree contents using a postorder traversal
public void printPostorder() {
System.out.print("postorder:");
printPostorder(overallRoot);
System.out.println();
}
// post: prints in postorder the tree with given root
private void printPostorder(IntTreeNode root) {
if (root != null) {
printPostorder(root.left);
printPostorder(root.right);
System.out.print(" " + root.data);
}
}
// post: prints the tree contents, one per line, following an
// inorder traversal and using indentation to indicate
// node depth; prints right to left so that it looks
// correct when the output is rotated.
public void printSideways() {
printSideways(overallRoot, 0);
}
// post: prints in reversed preorder the tree with given
// root, indenting each line to the given level
private void printSideways(IntTreeNode root, int level) {
if (root != null) {
printSideways(root.right, level + 1);
for (int i = 0; i < level; i++) {
System.out.print(" ");
}
System.out.println(root.data);
printSideways(root.left, level + 1);
}
}
}
]]>