A tree is another of our basic data structures.
A tree has a root node. The root node has 0, 1, 2, or more child nodes. Each of the child nodes has 0, 1, or more child nodes of its own. And etc.
A binary tree has nodes that have 0, 1, or two children each.
In a full binary tree, every node has two children.
In a complete binary tree, every node above the bottom level has two children, and all of the nodes on the lowest level are farthest to the left of the tree.
Here is the definition of a tree class (in tree.h):
#ifndef TREENODE_H
#define TREENODE_H
#include <string>
using namespace std;
typedef string treeData;
class tree
{
public:
//Constructor for a one node tree
tree (const treeData d);
//Constructor for a tree with two one node
// child subtrees.
tree (const treeData, const treeData, const treeData);
~tree ();
//Function to change the data in the tree root.
void setRootData (const treeData);
//Functions to change the left and right subtree pointers.
void setLeft (tree*);
void setRight (tree*);
//Functions to return the left and right subtree pointers and the
// data in the root.
tree* getLeft () const;
tree* getRight () const;
treeData getRootData () const;
//Function to tell if this tree is a leaf. (Leaf means no children.)
bool isLeaf () const;
private:
treeData theData;
tree* lChild; //Left child subtree
tree* rChild; //Right child subtree
};
#endif
And here is are the member functions of the tree class:
#include "tree.h"
tree::tree (const treeData d)
{
theData = d;
lChild = NULL;
rChild = NULL;
}
tree::tree (const treeData d, const treeData L, const treeData R)
{
theData = d;
lChild = new tree (L);
rChild = new tree (R);
}
tree::~tree ()
{
delete lChild;
delete rChild;
}
void tree::setRootData (const treeData d)
{
theData = d;
}
treeData tree::getRootData () const
{
return theData;
}
void tree::setLeft (tree* aTree)
{
lChild = aTree;
}
void tree::setRight (tree* aTree)
{
rChild = aTree;
}
tree* tree::getLeft () const
{
return lChild;
}
tree* tree::getRight () const
{
return rChild;
}
bool tree::isLeaf () const
{
bool returnVal = false;
//Return a true value only if there are
// no children.
if (lChild == NULL && rChild == NULL)
returnVal = true;
return returnVal;
}
We program a children's animal guessing game. First the user must think of an animal.
We will set up a binary tree that will hold a series of yes/no questions about animals, and, in the leaves of the tree, the names of the animals. As a picture the tree might look like this:
--- 1) Is it a mammal? ---
| |
--- 2) Does it hop? -- -- 3) Does it swim? ---
| | | |
4) kangaroo 5) dog 6) fish 7) lizard
First the program poses the question: Is it a mammal?
If the user answers yes, then the program moves to the left child and poses the question at that node: Does it hop?
If the user answers yes, then the program asks, Is it a kangaroo.
If the user says yes (his/her animal is a kangaroo), then the program wins the game. If not, then the user wins.
If the user wins, then the program asks the user for his/her animal and for a question that has a yes answer for that animal. (For example, if the animal was a snake, the question might be: Does it have legs?)
The program then puts the question where the wrong animal was, makes the user's animal the left child, and the wrong animal the right child.
For example, after an exchange of:
Is it a mammal? NO Does it swim? NO Is it a lizard? NO What is your animal? SNAKE What is a question about your animal that has a yes answer? DOES IT SLITHER?
the tree will look like:
--- 1) Is it a mammal? ---
| |
--- 2) Does it hop? -- -- 3) Does it swim? ---
| | | |
4) kangaroo 5) dog 6) fish --7) Does it slither?--
| |
snake lizard
The following implementation of the animal guessing game consists of a game object to communicate with the user, and a game mechanism object to manage the operations with the tree.
Why not program the game with the tree class and just one game class that will do everything? Because the division of labor simplifies and organizes the code. The program will be easier to code, bugs will be easier to trace, and the program will be easier to modify later as needed.
Here is the game and game mechanism classes:
#ifndef ANIMAL_GAME
#define ANIMAL_GAME
#include <string>
#include "tree.h"
using namespace std;
class gameMechanism
{
public:
//The constructor starts up a tree structure with a question in
// the root of the tree, and two animals in the child nodes.
gameMechanism (string& Q, string& A1, string& A2);
~gameMechanism ();
//Makes the cursor point to the root of the tree.
void reset ();
//Makes the data of the current node a question, q, and makes the
// animal that was in the current node and the new animal a the data
// in the children. There weren't any children for this node before.
void newQuestionAndAnimal (string& q, string& a);
//Tells whether the cursor is presently on a leaf (which stores an animal).
bool isCursorOnAnimal ();
//Returns the string that is in the node the cursor points to.
string getStringAtCursor ();
//Takes a yes or no answer and move to the left child of the cursor
// on yes and to the right child on no.
void moveWithAnswer (string& answer);
private:
tree* theTree; //The tree structure to hold questions and animals
tree* cursor; //The current node.
};
//The game class communicates with the user of the game and uses the answers
// to direct the game mechanism .
class game
{
public:
//The constructor starts up the game mechanism with a question
// and two animals
game (string& Q, string& A1, string& A2);
~game ();
void play ();
private:
gameMechanism *theGuts;
//Helper functions
void playRound ();
void doQuestionAnswerSession();
void addAnimalAndQuestion ();
bool isPlayerAnimal ();
bool isPlayAgain ();
bool isYesAnswer (string&);
string getQuestion ();
string getAnimal ();
};
#endif
Here is the code for the member functions:
#include <iostream>
#include <string>
#include "AnimalGame.h"
using namespace std;
game::game (string& question,
string& animal1,
string& animal2)
{
//Starts the game off by storing a question and two animals.
// The game mechanism (which sets up and manages the tree)
// is created using the question and the animals.
#include <iostream>
#include <string>
#include "AnimalGame.h"
using namespace std;
game::game (string& question,
string& animal1,
string& animal2)
{
//Starts the game off by storing a question and two animals.
// The game mechanism (which sets up and manages the tree)
// is created using the question and the animals.
theGuts = new gameMechanism (question, animal1, animal2);
}
game::~game ()
{
//What is created must be deleted.
delete theGuts;
}
void game::play ()
{
//Plays the game.
bool isPlay = true;
while (isPlay)
{
theGuts->reset ();
playRound ();
isPlay = isPlayAgain ();
}
}
void game::playRound ()
{
//Plays one round of the game.
//Ask yes/no questions until there are none left.
doQuestionAnswerSession ();
//Then see get the player's animal and see if it matches
// the program's animal.
if (isPlayerAnimal ())
cout << "I win!\n\n\n";
else
//If no match, then get the user's animal and a
// matching question to add into the game.
addAnimalAndQuestion ();
}
void game::doQuestionAnswerSession ()
{
//Asks questions until the no questions are left to ask.
while (!theGuts->isCursorOnAnimal ())
{
//Get the next question from the game mechanism.
cout << theGuts->getStringAtCursor ();
string answer;
//Get the user's yes/no question to the question.
cin >> answer;
//Pass the answer to the game mechanism for action.
theGuts->moveWithAnswer (answer);
}
}
void game::addAnimalAndQuestion ()
{
string question, animal1, animal2;
//At this point there are no more questions to ask
// and the program has guessed the user's animal
// wrong.
//So get the user's animal, get a quesion for the
// animal, and pass these to the game mechanism
// to incorporate into the game.
animal1 = getAnimal ();
question = getQuestion ();
theGuts->newQuestionAndAnimal (question, animal1);
}
bool game::isPlayerAnimal ()
{
//Guess's the user's animal. If right return true,
// but if wrong, then return false.
cout << "Is it a " << theGuts->getStringAtCursor () << '?';
string answer;
cin >> answer;
cout << endl;
return isYesAnswer (answer);
}
bool game::isPlayAgain ()
{
//Returns true if the user wants to play again, false
// if not.
cout << "Want to play again?";
string answer;
cin >> answer;
bool returnVal = false;
if (answer == "Yes" || answer == "yes" ||
answer == "Y" || answer == "y")
returnVal = true;
return returnVal;
}
string game::getAnimal ()
{
//Get's the user's animal and returns it.
cout << "What is your animal? ";
string animal;
cin >> animal;
cout << endl;
return animal;
}
string game::getQuestion ()
{
//Gets a question to correspond to the user's animal
// and returns it.
cout << "Please give me a question about your animal "
<< "that someone would answer with yes."
<< endl << endl;
//Ignore the next character if it is a return char.
if (cin.peek () == '\n')
cin.ignore ();
string question;
//Get the question as an entire line of text.
getline (cin, question);
cout << endl;
return question;
}
bool game::isYesAnswer (string& answer)
{
//Returns true if answer is Yes or equivalent, false if not.
return (answer == "Yes" || answer == "yes" ||
answer == "Y" || answer == "y");
}
gameMechanism::gameMechanism (string& question,
string& animal1,
string& animal2)
{
//Sets up the game storage tree with a question at the
// root and two animals as leaves.
theTree = new tree (question, animal1, animal2);
//Sets the cursor to point to the root of the tree.
cursor = theTree;
}
gameMechanism::~gameMechanism ()
{
delete theTree;
}
bool gameMechanism::isCursorOnAnimal ()
{
//The animals are in the leaves of the tree. (The other
// nodes hold questions.)
//So return true if we are on a leaf, false if not.
return cursor -> isLeaf ();
}
string gameMechanism::getStringAtCursor ()
{
//Return the string in the node that the cursor points at.
return cursor -> getRootData ();
}
void gameMechanism::reset ()
{
//Reset the cursor so it points to the root of the tree.
// This resets the game.
cursor = theTree;
}
void gameMechanism::moveWithAnswer (string& answer)
{
//Recall that the game asks questions until it reaches the
// leaves of the storage tree.
//If the user's answer to the question is Yes, then move
// from the current node to the left child. Otherwise
// move from the current node to the right child.
if (answer == "Yes" || answer == "yes" ||
answer == "Y" || answer== "y")
cursor = cursor -> getLeft ();
else
cursor = cursor -> getRight ();
}
void gameMechanism::newQuestionAndAnimal (string& question,
string& animal1)
{
//At this point the game has run out of questions, has
// guessed the user's animal, and the guess is wrong.
// animal1 is the user's animal, and question is the user's
// question about the animal (that has a yes answer for
// that animal).
//The question is stored in the tree lead we are on, and
// the animal that was there, and the user's animal are
// stored in the leaves. The user's animal must go in
// the left leaf.
string animal2;
if (cursor->isLeaf ())
{
animal2 = cursor->getRootData ();
cursor->setRootData (question);
cursor->setLeft (new tree (animal1));
cursor->setRight(new tree (animal2));
}
}
theGuts = new gameMechanism (question, animal1, animal2);
}
game::~game ()
{
//What is created must be deleted.
delete theGuts;
}
void game::play ()
{
//Plays the game.
bool isPlay = true;
while (isPlay)
{
theGuts->reset ();
playRound ();
isPlay = isPlayAgain ();
}
}
void game::playRound ()
{
//Plays one round of the game.
//Ask yes/no questions until there are none left.
doQuestionAnswerSession ();
//Then see get the player's animal and see if it matches
// the program's animal.
if (isPlayerAnimal ())
cout << "I win!\n\n\n";
else
//If no match, then get the user's animal and a
// matching question to add into the game.
addAnimalAndQuestion ();
}
void game::doQuestionAnswerSession ()
{
//Asks questions until the no questions are left to ask.
while (!theGuts->isCursorOnAnimal ())
{
//Get the next question from the game mechanism.
cout << theGuts->getStringAtCursor ();
string answer;
//Get the user's yes/no question to the question.
cin >> answer;
//Pass the answer to the game mechanism for action.
theGuts->moveWithAnswer (answer);
}
}
void game::addAnimalAndQuestion ()
{
string question, animal1, animal2;
//At this point there are no more questions to ask
// and the program has guessed the user's animal
// wrong.
//So get the user's animal, get a quesion for the
// animal, and pass these to the game mechanism
// to incorporate into the game.
animal1 = getAnimal ();
question = getQuestion ();
theGuts->newQuestionAndAnimal (question, animal1);
}
bool game::isPlayerAnimal ()
{
//Guess's the user's animal. If right return true,
// but if wrong, then return false.
cout << "Is it a " << theGuts->getStringAtCursor () << '?';
string answer;
cin >> answer;
cout << endl;
return isYesAnswer (answer);
}
bool game::isPlayAgain ()
{
//Returns true if the user wants to play again, false
// if not.
cout << "Want to play again?";
string answer;
cin >> answer;
bool returnVal = false;
if (answer == "Yes" || answer == "yes" ||
answer == "Y" || answer == "y")
returnVal = true;
return returnVal;
}
string game::getAnimal ()
{
//Get's the user's animal and returns it.
cout << "What is your animal? ";
string animal;
cin >> animal;
cout << endl;
return animal;
}
string game::getQuestion ()
{
//Gets a question to correspond to the user's animal
// and returns it.
cout << "Please give me a question about your animal "
<< "that someone would answer with yes."
<< endl << endl;
//Ignore the next character if it is a return char.
if (cin.peek () == '\n')
cin.ignore ();
string question;
//Get the question as an entire line of text.
getline (cin, question);
cout << endl;
return question;
}
bool game::isYesAnswer (string& answer)
{
//Returns true if answer is Yes or equivalent, false if not.
return (answer == "Yes" || answer == "yes" ||
answer == "Y" || answer == "y");
}
gameMechanism::gameMechanism (string& question,
string& animal1,
string& animal2)
{
//Sets up the game storage tree with a question at the
// root and two animals as leaves.
theTree = new tree (question, animal1, animal2);
//Sets the cursor to point to the root of the tree.
cursor = theTree;
}
gameMechanism::~gameMechanism ()
{
delete theTree;
}
bool gameMechanism::isCursorOnAnimal ()
{
//The animals are in the leaves of the tree. (The other
// nodes hold questions.)
//So return true if we are on a leaf, false if not.
return cursor -> isLeaf ();
}
string gameMechanism::getStringAtCursor ()
{
//Return the string in the node that the cursor points at.
return cursor -> getRootData ();
}
void gameMechanism::reset ()
{
//Reset the cursor so it points to the root of the tree.
// This resets the game.
cursor = theTree;
}
void gameMechanism::moveWithAnswer (string& answer)
{
//Recall that the game asks questions until it reaches the
// leaves of the storage tree.
//If the user's answer to the question is Yes, then move
// from the current node to the left child. Otherwise
// move from the current node to the right child.
if (answer == "Yes" || answer == "yes" ||
answer == "Y" || answer== "y")
cursor = cursor -> getLeft ();
else
cursor = cursor -> getRight ();
}
void gameMechanism::newQuestionAndAnimal (string& question,
string& animal1)
{
//At this point the game has run out of questions, has
// guessed the user's animal, and the guess is wrong.
// animal1 is the user's animal, and question is the user's
// question about the animal (that has a yes answer for
// that animal).
//The question is stored in the tree lead we are on, and
// the animal that was there, and the user's animal are
// stored in the leaves. The user's animal must go in
// the left leaf.
string animal2;
if (cursor->isLeaf ())
{
animal2 = cursor->getRootData ();
cursor->setRootData (question);
cursor->setLeft (new tree (animal1));
cursor->setRight(new tree (animal2));
}
}