BST and BT Survivor Game

The Assignment

In this assignment you will be Jeff Probst. Your job, Jeff, is to implement a game of Survivor. Our version of survivor gathers several castaways together in a wilderness. At first, they're split into two tribes. After a brief initial challenge, one tribe will be declared the initial winner.

Then there's a second round, where members of the winning tribe compete against one another. Two people go head-to-head in a fierce competition. The loser of each challenge gets voted off the island, and the other one stays. The season is over when there is one single castaway left in the tribe. That person is then declared the overall winners and gets a big fat cash prize.

You're going to make this all work using trees. The heart of your code will be a BinarySearchTree class that inherits from the Binary Tree class provided in the starter code. (Youll need to add more to the Binary Tree class as well.)

BinaryTree Class -- Starter Code

In Tree.h, we've defined a BinaryNode struct. It has three attributes: a TreeItem, a left pointer and a right pointer. Whats a TreeItem? Well, in this case it should be a Survivor object. You can use "typedef" so that anytime a TreeItem is referred to in your code its tied to Survivor. (Jays Note: need to understand what typedef is and the proper usage.)

The starter code includes the following member functions. Most of them have corresponding non-member wrapper functions to handle the recursion, as we saw in class.

• Constructor and destructor
• int get_length() const. Returns the total number of nodes in the tree.
• TreeItem get_leftmost() const. Returns the item in the deepest left node (i.e., the item that would be printed first in an in-order traversal). Throws an exception if the tree is empty.
• void inorder(ostream &) const; Prints an in-order traversal (left, root, right)
• void preorder(ostream &) const; Prints a pre-order traversal (root, left, right)
• void postorder(ostream &) const; Prints a post-order traversal (left, right, root)
• virtual void insert_item(TreeItem); Inserts the given item into the next open slot
• virtual void find_item(TreeItem &, bool &) const; Finds the given item and updates the bool and TreeItem reference parameters
• virtual void remove_item(TreeItem); Removes the given item from the tree, replaces it with deepest node

The Binary Tree class uses a Queue as an auxiliary data structure for some of its operations. This is only in the starter code and not for anything you'll need to write. The BST class doesnt need an auxiliary data structure at all, thanks to its invariant of keeping smaller things to the left and larger things to the right. Put the queues out of your mind entirely while youre working on the project, and well revisit them later in lecture.

BinaryTree Class -- Your Code

You will need to modify the given BinaryTree class to include the following functions. Write wrapper functions to handle recursion whenever necessary. Any member function that does not modify the attributes of the tree object should be declared const.

• Copy constructor and assignment operator.
• A function to determine whether the tree is full. Use a try-block to attempt to allocate a new Binary Node. Return true if the attempt failed and the tree is full; false otherwise.
• A function to determine whether the tree is empty. Returns true if root is NULL, false otherwise.
• A function to calculate and return the number of leaves in the tree.
• A function to calculate and return the height of the tree. Returns the depth of the deepest node in the tree. The height of a one-node tree is zero; the height of a zero-node tree is -1.
• A function to calculate and return the average age of all castaways in the tree.
• A function to find and return the TreeItem in the rightmost node, i.e., the item that would be visited last in an in-order traversal.
  • This function should throw an exception if there is no TreeItem to return (e.g., because the tree is empty)
• A function to print the tree. Prints the root node (by calling the Survivor class's print function), the height of the tree, the number of nodes in the tree, and the number of leaves in the tree.
  • This function should accept an ostream reference as a parameter.
  • If you'd prefer, you can overload the << operator instead of writing a print function (not required, though, just for fun).
• A function to print just the root of the tree. This function should accept an ostream reference parameter, and print the Survivor at the root of the tree.

BinarySearchTree Class -- Starter Code

The starter code includes the following member functions. The starter code includes the following member functions.

• Constructor and destructor.
• void insert_item(TreeItem). Inserts the given TreeItem in the correct spot in the BST.

BinarySearchTree Class -- Your Code

You'll finish writing the class for a BinarySearchTree whose elements are TreeItems containing objects of the Survivor class. This will inherit from the BinaryTree class, so you are responsible for overwriting the find and remove functions inherited from the BinaryTree.

You will need to modify the given BinaryTree class to include the following functions. Write wrapper functions to handle recursion whenever necessary.

Any member function that does not modify the attributes of the tree object should be declared const.

• Copy constructor and assignment operator. These are not inherited from the base class.
• remove_item, inherited from Binary Tree. This function must have the same name, parameters, and return type as the version in the base class. Throw an exception if the tree is empty.
  • Case one: Remove a leaf. Update parent's pointer to NULL.
  • Case two: Remove a one-child parent. Replace parent with child.
  • Case three: Remove a two-child parent. Replace parent with child immediately preceding in in-order traversal. Think about writing a get_predecessor function to help.
• find_item, inherited from Binary tree. This function must have the same name, parameters, and return type as the version in the base class.

Survivor Class

This class will keep track of the Survivor contestants and is similar to the Pirate class from HW 1.

The Survivor class should keep track of the following with private member variables:

• First name, Last name (strings)
• Hometown, State (strings)
• Age (int)

Here are the functions you'll need to write. You can also add any other functions or attributes you need to make your program work.

• Constructor
• Parameterized Constructor accepting first name, last name, city, state, and age
• A print function that accepts an ostream reference as a parameter. Prints the data for the Survivor in the following format
  FirstName LastName
  hometown: city, state
  age: age

• A function to generate the next castaway from a file. Similar to generate_next_pirate() from HW 1, except we know more about a survivor than their name. Reads in the next survivor from an input file, populating all its values.

(Jay’s Note: below is the generate_next_pirate() function mentioned above)

// in the Pirate.h file:
class Pirate
{
public:
Pirate();
Pirate(string);
void print(ofstream &) const;
void generate_pirate_name(ifstream &, int);
void assign_pirate_id();

// Member function to add pirates in order.
void generate_next_pirate(ifstream &);

friend bool operator == (const Pirate &, const Pirate &);
private:
int pirate_id;
string name;
static int pirate_count;
};

// in the Pirate.cpp file:
void Pirate::generate_next_pirate(ifstream &infile)
{
string pname;
int count = 0;

infile.clear();
infile.seekg(0, ios::beg);
while (getline(infile, pname))
{
if (count == pirate_count - 1)
{
name = pname;
break;
}
count++;
}
}

// in the int main() file:
int all_pirates_smee(PirateMates hookbook[], Pirate smee)
{
int counter = 0;

// Make an ArrayList out of every Pirate in the txt file
ifstream infile;
infile.open(PIRATE_FILE.c_str());
if (!infile.is_open())
{
cerr << "Could not add pirates from filen";
return -1;
}

while (!infile.eof() && counter < ALL_PIRATES)
{
Pirate p;
p.generate_next_pirate(infile);
p.assign_pirate_id();
hookbook[counter].pirate = p;
hookbook[counter].mates.insert_pirate(smee);
counter++;
}
infile.close();
}

• void set_name(string, string). Sets the name of the Survivor to the given strings. This function prototype needs to match what we have here exactly in order for the test-drivers to work.
• You will also need to overload the ==, <, and > to determine equality of survivors as well as sort them in alphabetical order. Note that you only need to compare first and last name to determine equality.

Driver

You need to create a driver to run the logic of your game, survivor-driver.cpp. You'll have two input files to read, castaways.txt and stowaways.txt. One input file will become a Binary Tree and the other will become a BST (which is which, you ask? Well, thatll be randomly chosen).

This will run your game according to the following structure.

• Round One: Two competing tribes are created, one using a BinaryTree and one using a BinarySearchTree. Once the two trees are created and populated, determine which tree has the fewest leaves. This tribe wins and moves on to round two.
  • Populate the trees using the two input files given, but randomly choose which file populates the BinaryTree and which populates the BinarySearchTree.
  • Announce the winner by printing "ROUND ONE WINNER: BST" or ROUND ONE WINNER: BT. Then print the winning tree using the print function you wrote earlier.
  • If it's a tie, the BT wins.
• Round Two: Round Two consists of subrounds which repeat in the following manner until the sole survivor is determined
  • For each subround, determine the average age of castaways in the tree. Print that value.
  • Then find the player who is in the deepest left node and the player who is in the deepest right node. We've written get_leftmost() already; you need to write get_rightmost();
  • Of these two players, the player whose age is closest to the average age wins, and the other player is voted off the island.
  • Announce the one who got voted off.
  • When there is one castaway left, print "WINNING SURVIVOR" and print the Survivor's information using the print function you wrote for the survivor class.

You can add any functions you need to your driver to make this happen.

Makefile

You must submit a Makefile along with your source code and header files. You should be able to compile with the command "make survivor" and generate an executable called survivor. These names are important, because our grading scripts will use them.

Here's a sample output (please note the spacing, well use a script to check so be careful that it matches, also note that we ran this on a totally different input file than youll see in starter code!). We also arent expecting any kind of precision setting in doubles.

Loser had 9 leaves
ROUND ONE WINNER: BST
Maralyn Hershey
hometown: Wakefield, VA
age: 51

Height: 6
Number of nodes: 18
Number of leaves: 5

Average age this round 34.5
Voted off the island:
Tina Wesson
hometown: Knoxville, TN
age: 39

Average age this round 34.2353
Voted off the island:
Jeff Varner
hometown: NewYork, NY
age: 34

Average age this round 33.6
Voted off the island:
Michael Skupin
hometown: WhiteLake, MI
age: 38

WINNING SURVIVOR:
Rodger Bingham
hometown: Crittenden, KY
age: 53