Run with print stmts for just a few adds and
deletes
AddingBob 3.2
adding bob true
AddingBiff 1.2
adding biff true
AddingSally 2.9
adding sue true
AddingBob 3.2
adding bob false
removing bob true
contains bob false
package BinSearch;
public class BinTreeTester {
/**
* @param args
*/
public static void main(String[] args) {
boolean result;
BinarySearchTree
<Student>tree=new BinarySearchTree<Student>();
Student []students=new Student[20];
students[0]=new Student("Bob",3.2);
students[1]=new Student("Biff",1.2);
students[2]=new Student("Sally",2.9);
System.out.println("adding
bob "+ tree.add(students[0]));
System.out.println("adding
biff "+ tree.add(students[1]));
System.out.println("adding
sue "+ tree.add(students[2]));
System.out.println("adding
bob "+ tree.add(students[0]));
System.out.println("removing
bob "+ tree.remove(students[0]));
System.out.println("contains
bob "+ tree.contains(students[0]));
/*students[14]=new
Student("Sue",2.2);
students[15]=new
Student("Joe",3.0);
students[13]=new
Student("Sarah",4.0);
students[3]=new
Student("Jeff",3.6);
students[4]=new
Student("Steve",0.9);
students[5]=new
Student("Barry",1.2);
students[6]=new
Student("Jane",2.6);
students[7]=new
Student("Lou",3.4);
students[8]=new
Student("Phil",1.0);
students[9]=new
Student("Ralph",1.62);
students[10]=(new
Student("Mary",2.95));
students[11]=(new
Student("Mike",3.6));
students[12]=(new
Student("Larry",0.9));
for(int i=0;i<16;i++){
result=tree.add(students[i]);
System.out.println("adding "+students[i].toString()+" result is "+result);
}
for(int i=0;i<16;i++){
result=tree.add(students[i]);
System.out.println("adding "+students[i].toString()+" result is "+result);
}
for(int i=0;i<5;i++){
result=tree.remove(students[i]);
System.out.println("removing "+students[i].toString()+" result is "+result);
}
*/
}
}
package BinSearch;
public class Entry<E>
{
protected E data;
protected Entry<E> left,right,parent;
protected Entry(E data, Entry<E> parent) {
this.data = data;
this.left = null;
this.right = null;
this.parent = parent;
}
protected Entry() {
this.data=null;
this.left = null;
this.right = null;
this.parent = null;
}
protected Entry(E data) {
this.data=data;
this.left = null;
this.right = null;
this.parent = null;
}
}
package BinSearch;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Collections;
public class BinarySearchTree<E>
{
protected Entry<E> root;
private int size;
public BinarySearchTree() {
root = null;
size = 0;
}
public int size() {
return size;
}
public boolean contains(Object obj)
{
Entry<E>e=getEntry((E)obj);
if(e==null)return false;
return true;
}// contains
public boolean add(E element) {
System.out.println("Adding"+ element.toString());
if (root == null)// tree was
empty
{
root = new
Entry<E>(element, null);
size++;
return true;
} else // non-empty
tree
{
Entry temp = root;
int comp;
while (true) {
comp
= ((Comparable) element).compareTo(temp.data);
if (comp == 0)
return false;
if (comp < 0)
if (temp.left
!= null)
temp = temp.left;
else {
temp.left = new Entry<E>(element, null);
size++;
return true;
}// temp
left is null
else if (temp.right != null)
temp
= temp.right;
else {
temp.right = new Entry<E>(element, null);
size++;
return true;
}// temp
right null
}// while
}// not empty
}
public boolean remove(Object obj)
{
Entry<E>e=getEntry((E)obj);
if(e==null)return false;
deleteEntry(e);
return true;
}
protected Entry<E> deleteEntry(Entry<E> entry) {
size--;
if(entry.left!=null&&entry.right!=null)
{
Entry<E>s=successor(entry);
entry.data=s.data;
entry=s;
}//there were
two children
//now p has 1 or no children
Entry <E>replacement;
if(entry.left!=null)
replacement=entry.left;
else
replacement=entry.right;
if(replacement!=null)
{//link replacement to p's parent
replacement.parent=entry.parent;
if(entry.parent==null)root=replacement;
else if(entry==entry.parent.left)entry.parent.left=replacement;
else entry.parent.right=replacement;
}//one child
else if(entry.parent==null)root=null;
else
{
if(entry==entry.parent.left)
entry.parent.left=null;
else entry.parent.right=null;
}//no children
return entry;
}
protected Entry<E>
successor(Entry<E> entry) {
if(entry==null)return entry;
else if(entry.right!=null)
{
//successor is leftmost entry
in rt subtree
Entry<E>p=entry.right;
while(p.left!=null)p=p.left;
return p;
}
else
{
/*go up tree to the left as far
as possible, then go up to the right*/
Entry<E>p=entry.parent;
Entry<E>child=entry;
while(p!=null&&child==p.right)
{
child=p;
p=p.parent;
}//while
return p;
}//e has no right child
}
protected Entry<E> getEntry(Object obj) {
int comp;
Entry<E>e=root;
while(e!=null){
comp=((Comparable)obj).compareTo(e.data);
if(comp==0)return e;
else if(comp<0)
e=e.left;
else e=e.right;
}
return null;
}//method
}
///////////////added
to binary tree an iterator
public Iterator
iterator() {
return new TreeIterator<E>(root);
}
//////////////iterator subclass
public class TreeIterator<E> implements Iterator<E> {
protected Entry<E> lastReturned;
protected Entry<E> next;
int counter = 0;
protected TreeIterator(Entry<E> root) {
this.next = root;
lastReturned = null;
if (next != null)
while (next.left != null) {
next = next.left;
}
}
@Override
public boolean hasNext() {
counter++;
return next != null;
}
@Override
public E next() {
if (next == null)
throw new NoSuchElementException();
lastReturned = next;
next = successor(next);
return lastReturned.data;
}
protected Entry<E>
successor(Entry<E> entry) {
if (entry == null)
return entry;
else if (entry.right != null) {
// successor
is leftmost entry in rt
subtree
Entry<E> p = entry.right;
while (p.left
!= null) {
p = p.left;
}
return p;
} else {
/*
* go up tree to the left as far as possible,
then go up to the
* right
*/
Entry<E> p = entry.parent;
Entry<E> child =
entry;
while (p != null && child == p.right) {
child
= p;
p = p.parent;
}// while
return p;
}// e has no
right child
}
@Override
public void remove() {
/*
* if(lastReturned==null)throw new IllegalStateException();
* if(lastReturned.left!=null&&lastReturned.right!=null)
* next=lastReturned; deleteEntry((Entry<E>)
lastReturned);
* lastReturned=null;
*/
}
}
}
//output from tree iterator with all the students added from above
Barry 1.2
Biff 1.2
Bob 3.2
Jane 2.6
Jeff 3.6
Joe 3.0
Larry 0.9
Lou 3.4
Mary 2.95
Mike 3.6
Phil 1.0
Ralph 1.62
Sally 2.9
Sarah 4.0
Steve 0.9
Sue 2.2