Notes

//name: date:
import java.util.*;
import java.io.*;
public class BSTobject_shell
{
public static void main( String[] args ) throws Exception
{
//day one
BSTobject<Integer> tree = new BSTobject<Integer>(6);
tree.add(56);
tree.add(4);
tree.add(93);
tree.add(89);
System.out.println(tree);
System.out.println(tree.size());
System.out.println(tree.isEmpty());
System.out.println(tree.contains(900));
//day two
// Your assignment the second day is to finish the BSTobject class.
// Specifically, prompt the user for a string, put the characters into a BST,
// call toString on this tree, and print the size of the tree.
//
// Next, fill your BST with 57 Widget objects from widgets.txt. Display the tree.
// Then prompt the user to enter pounds and ounces. If the tree contains that
// Widget, delete it, of course restoring the BST order. Display the new tree
// and its size. If the tree does not contain that Widget, print "Not found".




//day three--AVL tree
}
}
////////////////////////////////
class BSTobject <E extends Comparable<E>> implements BSTinterface<E>
{
Node<E> root;
Node<E> currentNode;

// 2 constructors, one default and one one-arg
public BSTobject()
{
root=new Node<E>(null);
currentNode=root;
}
public BSTobject(E startroot )
{
root=new Node<E>(startroot);
currentNode=root;
}



public E add( E element )
{
Node<E> x=new Node<E>(element);
if(element.compareTo(currentNode.getValue())<0)
{
if(currentNode.getLeft()==null)
{
currentNode.setLeft(new Node<E>(element));
currentNode=root;
}
else
{x=currentNode;
currentNode=currentNode.getLeft();
add(element);
currentNode=x;
}
}
if(element.compareTo(currentNode.getValue())>0)
{
if(currentNode.getRight()==null)
{currentNode.setRight(new Node<E>(element));
currentNode=root;
}
else
{ x=currentNode;
currentNode=currentNode.getRight();
add(element);
currentNode=x;
}
}
if(element.compareTo(currentNode.getValue())==0)
return element;

return element;

} //returns the object
public boolean contains( E element )
{boolean po=false;
if(currentNode==null)
po=false;
else if(currentNode.getValue().compareTo(element)==0)
return true;
else if(currentNode.getValue().compareTo(element)>0)
{Node<E> x=currentNode;
currentNode=currentNode.getLeft();
po=contains(element);
currentNode=x;
}

else if(currentNode.getValue().compareTo(element)<0)
{Node<E> x=currentNode;
currentNode=currentNode.getRight();
po=contains(element);
currentNode=x;
}
else;
return po;
}
public boolean isEmpty()
{
if(root==null)
return true;
return false;
}

public E delete( E element )
{


} //returns the object, not a Node<E>.
public int size(){
int count=0;
if(currentNode==null)
return count;
else
count++;
if(currentNode.getLeft()==null&&currentNode.getRight()==null)
return count;
if(currentNode.getLeft()!=null)
{
Node<E> x=currentNode;
currentNode=currentNode.getLeft();
count+=size();
currentNode=x;
}
if(currentNode.getRight()!=null)
{
Node<E> x=currentNode;
currentNode=currentNode.getRight();
count+=size();
currentNode=x;
}

return count;
}
public String toString()
{

String s=toStringHelper();

return s;

}
public String toStringHelper()
{
String s="";

if(currentNode.getValue() == null)
return s;

if(currentNode.getLeft()!=null)
{Node<E> x=currentNode;
currentNode=currentNode.getLeft();
s+=toString();
currentNode=x;
}
System.out.print(currentNode.getValue()+" ");


if(currentNode.getRight()!=null)
{Node<E> x=currentNode;
currentNode=currentNode.getRight();
s+=toString();
currentNode=x;
}


return s;
}




/***************************private inner class **************/
private class Node<E>
{
// 3 fields
private E value;
private Node<E> left, right;

// 2 constructors, one-arg and three-arg
Node(E initValue)
{
value=initValue;
}
Node(E initValue, Node<E> initleft, Node<E> initright)
{
value=initValue;
left=initleft;
right=initright;

}
public E getValue()
{
return value;
}

public Node<E> getLeft()
{
return left;
}

public Node<E> getRight()
{
return right;
}

public void setValue(E theNewValue)
{
value = theNewValue;
}

public void setLeft(Node<E> theNewLeft)
{
left = theNewLeft;
}

public void setRight(Node<E> theNewRight)
{
right = theNewRight;
}





}
}
//////////////////////////////////
interface BSTinterface<E extends Comparable<E>>
{
public E add( E element ); //returns the object
public boolean contains( E element );
public boolean isEmpty();
public E delete( E element ); //returns the object, not a Node<E>.
public int size();
public String toString();


}
//////////////////////////////////