Print a binary search tree
Greetings, here is my code:
import java.util.*;
class BinarySearchTreeSet
{
// Inner class defining a binary tree node
private class TreeNode
{
private TreeNode left;
private Comparable key;
private TreeNode right;
}
// instance variables
private TreeNode root, parent, child;
// Constructor
public BinarySearchTreeSet()
{
root = null;
}
// Inserts a key into the set
public void insert(Comparable key) throws DuplicateKey
{
TreeNode newNode;
if (search(key))
throw new DuplicateKey();
newNode = new TreeNode();
newNode.key = key;
newNode.left = null;
newNode.right = null;
if (parent == null)
root = newNode;
else if (parent.key.compareTo(key) > 0)
parent.left = newNode;
else
parent.right = newNode;
System.out.println("The name " + key + " was added");
}
// Removes a key from the set
public void remove(Comparable key) throws NotFound
{
if (!search(key))
throw new NotFound();
if (child == root)
root = deleteNode(root);
else if (parent.left == child)
parent.left = deleteNode(parent.left);
else
parent.right = deleteNode(parent.right);
System.out.println("The name " + key + " was deleted");
}
// Determines whether a key is in the set
public boolean contains(Comparable key)
{
if (!search(key))
return false;
return true;
}
// Private method that searches for a key
private boolean search(Comparable key)
{
parent = null;
child = root;
while (child != null)
{
if (child.key.equals(key))
return true;
parent = child;
if (child.key.compareTo(key) > 0)
child = child.left;
else
child = child.right;
}
return false;
}
// Private method that deletes a node
private TreeNode deleteNode(TreeNode node)
{
TreeNode inorderSuccessor, successorsParent;
if (node.right == null)
return node.left; // 0-1 Child
else if (node.left == null)
return node.right; // 1 Child
else
{ // 2 Children
successorsParent = node.left;
inorderSuccessor = successorsParent.right;
if (inorderSuccessor == null)
{
node.left = successorsParent.left;
node.key = successorsParent.key;
}
else
{
while (inorderSuccessor.right != null)
{
successorsParent = inorderSuccessor;
inorderSuccessor = inorderSuccessor.right;
}
successorsParent.right = inorderSuccessor.left;
node.key = inorderSuccessor.key;
}
}
return node;
}
// begin print code
// here is where I'm having problems
public void printTree() {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
System.out.println(root);
while(!queue.isEmpty()) {
TreeNode n = queue.poll();
System.out.println(n.left + " <- " + n + " -> " +
n.right);
if(n.left != null) queue.offer(n.left);
if(n.right != null) queue.offer(n.right);
}
}
// end print code
}
I get the following output when I call the printTree() method from my
driver:
BinarySearchTreeSet$TreeNode@1b67f74
// the following all on one line
BinarySearchTreeSet$TreeNode@69b332 <- BinarySearchTreeSet
$TreeNode@1b67f74 -> BinarySearchTreeSet$TreeNode@173a10f
// end of all on one line
null <- BinarySearchTreeSet$TreeNode@69b332 -> null
null <- BinarySearchTreeSet$TreeNode@173a10f -> null
This output is after adding "kevin", "billy", and "timmy" to the
tree. The add, contains, and remove methods all work fine. I just
need to get the tree printing to the console, and then I have to work
on file i/o.
Thanks in advance for any help...