java

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 commands

E 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; i