Description
The director of Camp Posanivee is frustrated. Campers are enrolling and withdrawing from camp faster than her primitive filing system can handle, and she has turned to you. You have been offered free meals at the mess hall in return for a program that will help her keep track of who is enrolled for the two-week summer camp.
Your program will use a binary search tree to maintain the set of campers enrolled in Camp Posanivee. Your program should not be case-sensitive.
Your program will consist of a loop to process commands. The commands should come from a text file (say, "camp.txt"). The program quits when the command 'Q' is given. Below is a list of commands your program should support:
H / Help: print a list of commandsE name age gender / Enroll a new camper (insert)
W name / Withdraw a camper (delete)
D name / Display the age and gender of a camper
A / Print the average age of the campers
L / List all campers names in alphabetical order
S / Print the number of boy and girl campers
P / List all campers names in preorder
Q / Quit
Here name is a string of at most 20 non-blank characters, age is an integer, and gender is either M or F. You may assume command arguments are separated by one or more spaces.
Be sure to echo the input, especially for commands that give no output (like E or W), and handle special cases in a clean way (for example, computing the average age of an empty tree should not crash your program).
Notes
1. Before you begin programming, sketch a high level design of what you want to implement using the UML notation. At the very least, you should have a use case diagram, class diagram and a sequence diagram.
2. Remember to include comments at the top of your program and 1-2 lines for each function (including pre- and post-conditions). Use javadoc compatible comments.
3. Hint: Use the sample BST.java files included with this assignment.
Example
Here is a sample input file:
A
E Kanga 26 F
E Tigger 28 M
E Pooh 31 M
L
D Tigger
E Rabbit 30 M
A
S
E Eeyore 36 M
W Kanga
P
Q
Here is the output that corresponds:
Welcome to Camp Posanivee!!
Command: A
There are no campers.
Command: E Kanga 26 F
New camper added.
Command: E Tigger 28 M
New camper added.
Command: E Pooh 31 M
New camper added.
Command: L
Alphabetical List of Campers:
Kanga
Pooh
Tigger
Command: D Tigger
Name: Tigger
Age: 28
Gender: M
Command: E Rabbit 30 M
New camper added.
Command: A
Average age = 28.75
Command: S
Camper count by gender:
boys = 3
girls = 1
Command: E Eeyore 36 M
New camper added.
Command: W Kanga
Camper withdrawn.
Command: P
Preorder Traversal:
Eeyore
Tigger
Pooh
Rabbit
Command: Q
End of program.
Bring plenty of calomine lotion!
Sample: BST.JAVA
public class BST
{
private class treenode
{
Comparable item;
treenode left, right;
}
treenode root;
int count;
private Queue Q;
public static final int PREORDER=0;
public static final int INORDER=1;
public static final int POSTORDER=2;
public BST()
{
root=null; count=0; Q=new QueueLL();
}
public void makeEmpty()
{ root=null; count=0; Q.makeEmpty(); }
public boolean isEmpty()
{ return root==null; }
public int size() { return count; }
public Comparable lookup(Comparable x)
{ return lookup(root,x); }
private Comparable lookup(treenode r, Comparable x)
{ // base cases
if(r==null) return null;
if(r.item.compareTo(x)==0) return r.item;
// recursive case
if(x.compareTo(r.item)<0) return lookup(r.left,x);
else return lookup(r.right,x);
}
public void insert(Comparable x)
{ root=insert(root,x); count++; }
// returns a reference to the root of the tree with x inserted
private treenode insert(treenode r, Comparable x)
{
// base case
if(r==null)
{
treenode t=new treenode();
t.item=x;
t.left=t.right=null;
return t;
}
// recursive case
if(x.compareTo(r.item)<0)
{ r.left=insert(r.left,x); return r; }
else
{ r.right=insert(r.right,x); return r; }
}
private Comparable todelete; // item that gets deleted
public Comparable delete(Comparable x)
// returns the item deleted, or null if not found
{
todelete=lookup(x);
if(todelete!=null) root=delete(root,x);
return todelete;
}
// returns a reference to the root of the modified tree
private treenode delete(treenode r, Comparable x)
{
// base case: all the work is here
if(r.item.compareTo(x)==0)
{
//code to handle 3 cases
// 0 children
if(r.left==null & r.right==null)
return null;
// 1 child
if(r.left==null) // we have only a right child
return r.right; // promote the right child
if(r.right==null)
return r.left;
// 2 children case
Comparable successor=min(r.right);
r.item=successor;
r.right=delete(r.right,successor);
return r;
}
// recursive case
if(x.compareTo(r.item)<0)
{ r.left=delete(r.left,x); return r; }
else
{ r.right=delete(r.right,x); return r; }
}
private Comparable min(treenode r)
{
// base cases
if(r==null) return null;
if(r.left==null) return r.item;
// recursive case
return min(r.left);
}
// Iterator functions
public void reset() { reset(INORDER); }
public void reset(int order)
{
Q.makeEmpty();
traverse(root,order);
}
private void traverse(treenode r, int order)
{
if(r==null) return;
if(order==PREORDER) Q.enqueue(r.item);
traverse(r.left,order);
if(order==INORDER) Q.enqueue(r.item);
traverse(r.right,order);
if(order==POSTORDER) Q.enqueue(r.item);
}
public Comparable getNext()
{ return (Comparable) Q.dequeue(); }
public boolean hasNext() { return !Q.isEmpty(); }
public void print() { print(root); }
private void print(treenode r) // inorder
{
// base case: empty tree
if(r==null) return;
// recursive case
print(r.left);
System.out.println(r.item);
print(r.right);
}
}
Sample: BST main.JAVA
import java.io.*;
import java.util.*;
class BSTmain
{
/**
* @return the average number of fins
* @param school the array of fish
*/
static double avgfins(Fish [] school)
{
double sum=0;
for(int i=0; ischool.length; i++)
sum += school[i].getNumFins();
if(school.length==0) return 0;
return sum/school.length;
}
static Comparable max(Comparable [] school)
{
if(school.length==0) return null;
Comparable maxsofar=school[0];
for(int i=1; ischool.length; i++)
{
if(maxsofar.compareTo(school[i])<0)
// if(maxsofar<school[i])
{
maxsofar=school[i];
}
}
return maxsofar;
}
public static void main(String [] args)
throws IOException
{
System.out.println("Count="+Fish.count);
Scanner file = new Scanner(
new FileReader("fishfile.txt"));
int n;
n=file.nextInt();
BST tree=new BST();
for(int i=0; i<n; i++)
{
Fish x = new Fish(file);
//System.out.println(x);
tree.insert(x);
}
//tree.print();
// preorder print
tree.reset(BST.PREORDER);
while(tree.hasNext())
System.out.println(tree.getNext());
Fish d=new Fish("","","",6);
Fish x;
x=(Fish)tree.delete(d);
if(x!=null)
{
System.out.println("We deleted "+x);
}
//tree.print();
tree.reset(BST.PREORDER);
while(tree.hasNext())
System.out.println(tree.getNext());
return;
}
}