/*
* This is a really trivial example of class than can be organized
* using the BinarySearchTree. You should not use this. Instead,
* you should implement your own -- something that is interesting
* to you -- a databse of receipes, baseball players, cars, inventory
* record, &c.
*/
class Food implements Comparable
{
private String name; // This is the primary key: compareTo looks at it
private String color; // This is just an attribute. It doesn't affect order
/*
* It is perfectly legal to have secondary and tertiary keys, such
* as last name, then firstname, then middle initial. If you want to
* do this, then the compareTo() method needs to handle them appropriately.
*/
/*
* This should print out your whole record in a nice, readbale way
*/
public String toString()
{
return name + ": " + color;
}
/*
* You might want to have one or more constructors for your
* class -- usual reasons
*/
public Food (String name, String color)
{
this.name = name;
this.color = color;
}
/*
* This is enables the database to keep things in order
* it actually does the comparison...
*/
public int compareTo (Object f)
{
return name.compareTo(((Food)f).name);
}
/*
* This is just an example of a mutator method for the database
* record -- it changes the color of the food.
*/
public void changeColor(String newColor)
{
color=newColor;
}
}
-----------------------------------------------
/*
* This class implements a binary search tree. It stores a reference to
* the root node as its data
*
* This class also contains a private subclass which is used to represent
* the internal nodes of the tree
*/
public class BinarySearchTree
{
/*
* class to represent an internal node of the binary tree
*/
private class BinaryNode
{
/*
* Declare instance variables for the BinaryNode class here
* Hint: The user's record should be of type Comparable
*/
/*
* A constructor for the BinaryNode class, takes in only the data
* to be stored and sets the left child and the right child to
* null
*/
public BinaryNode(Comparable data)
{
/*
* Insert you code here
*/
}
/*
* Another constructor for the BinaryNode class, takes in the data
* to be stored, a reference to the left child, and a reference to
* the right child
*/
public BinaryNode(Comparable data, BinaryNode left, BinaryNode right)
{
/*
* Insert you code here
*/
}
/*
* Returns a reference to the user's record
*/
private Comparable getData()
{
/*
* Insert you code here
*/
}
/*
* Returns a reference to the left child
*/
private BinaryNode getLeft()
{
/*
* Insert you code here
*/
}
/*
* Returns a reference to the right child
*/
private BinaryNode getRight()
{
/*
* Insert you code here
*/
}
/*
* Changes the left child of the node
*/
private void setLeft(BinaryNode left)
{
/*
* Insert you code here
*/
}
/*
* Changes the right child of the node
*/
private void setRight(BinaryNode right)
{
/*
* Insert you code here
*/
}
/*
* Returns true if this node has no children,
* false otherwise
*/
private boolean isLeaf()
{
/*
* Insert you code here
*/
}
}
/*
* declare instance variables for the BinarySearchTree class here
*/
/*
* Constructor for the BinarySearchTree class
*/
public BinarySearchTree()
{
/*
* Insert you code here
*/
}
/*
* Inserts a new record into the right place within tree.
* It should simply check parameters and wrap the recursive method.
*/
public void insert(Comparable data)
{
/*
* Insert you code here
*/
}
/*
* Recursive method which inserts a new element
* into the tree. The tree must stay ordered after
* the new element has been added
*/
private BinaryNode insert(BinaryNode root, Comparable data)
{
/*
* Insert you code here
*/
}
/*
* User method for finding an element in the tree.
* It returns null if the data isn't found, or a reference
* back to the data if it is found.
*/
public Comparable find(Comparable data)
{
/*
* Insert you code here
*/
}
/*
* Recursive method which traverses the tree until
* it either finds the data it is looking for, in which
* case it returns a reference to that data, or hits the
* end of a path, in which case it returns null.
*/
private Comparable find(BinaryNode root, Comparable data)
{
/*
* Insert you code here
*/
}
/*
* This should check paramters and then call the recursive method
* to handle the delete
*/
public void delete(Comparable data)
{
/*
* Insert you code here
*/
}
/*
* Recursive method which removes an element
* from the tree. The tree must stay ordered after
* the element has been removed
*/
private BinaryNode delete(BinaryNode root, Comparable data)
{
/*
* Insert you code here
*/
}
/*
* Hint: You may want to think about writing one or more helper
* methods for your delete. This would be a good place to put
* them, if you do.
*/
/*
* This should print the content of the database in sorted order.
* It should really be a wrapper for the recursive method below.
*/
public void printInOrder()
{
/*
* Insert you code here
*/
}
/*
* Recursive method which performs an in-order
* traversal of the tree. It should display the
* tree's contents on the console
*/
private void printInOrder(BinaryNode root)
{
/*
* Insert you code here
*/
}
/*
* This should print the content of the database in reverse sorted order.
* It should really be a wrapper for the recursive method below.
*/
public void printInOrderBackwards()
{
/*
* Insert you code here
*/
}
/*
* Recursive method which performs the opposite of an in-order
* traversal of the tree. It should display the
* tree's contents on the console in the opposite order as printInOrder()
*/
private void printInOrderBackwards(BinaryNode root)
{
/*
* Insert you code here
*/
}
}
}
---------------------------------------------------------
class Database
{
public static void main (String []args)
{
/*
* This should be your database's user interface. It should
* let the user add, delete, and find items. It should also
* let the user do other things specific to your record type,
* such as change certain values.
*
* It should also let the user print the whole database in
* sorted order
*/
}
}