Binary Tree Assignment
Write a program that plays with the user the game commonly known as "Twenty Questions". However, in this version of the game, the program will not be limited to asking twenty questions. Instead, it may ask any number of questions. Also the program will learn and improve from playing each game.
At the start of each game, the program will ask the user to think of an object for the program to guess. Then, using its database, it will ask the user a number of yes/no questions one at a time. At the end of the question/answer session, it will display its guess for the user object. It will ask the user if its guess is correct. If the guess is correct, it will display a self praising sentence such as "I must say I am very smart". If the guess was wrong, for the purpose of improving its performance in the future, it will ask the user for the correct object. It will also ask the user to provide it with a question whose yes answer will be the user correct object and no answer will be the program's wrong guess. It will then update its database with the information received from the user for future use.
Then it will ask the user if he/she will like to play another game. If the user response affirmatively, it will repeat the procedure described above
in the last paragraph. Otherwise, the program will end.
Database
The program will use a flat file database for keeping questions and answers. It will use these questions and answers in interacting with the user. The flat database will be a text file named knowledge.txt. Initially the file will contain the three lines below: (Manually prepare this file using a text editor and save it in a folder accessible from the program).
Is it a non-living object?
Elephant
Stone
In the file, each line will contain either a question or an answer. Each question will be differentiable from the answer in that it will always end with a question mark "?". An answer will never end with a question mark. The above file contains one question component and two answer components.
The question and answer components are stored in the file in such a way that on reading the file, an in memory binary tree can be constructed with each node containing either the question or the answer component. An answer component will always be stored in a leaf node of the tree and a question component will be stored in a non-leaf node of the tree. For example, when the program reads the above file, it will construct the following binary tree:
Is it a non-living object?
| |
| |
Elephant Stone
Algorithm
• At the start of the program, the program will read the contents of the file and construct a binary tree containing the question and answer components of the file. It will use this tree to interact with the user.
• Once the user has thought of an object, the program will display to the user the contents of the root node as the first question and solicit user's yes/no answer.
• If the user's answer is "no", it will traverse the tree using the left link. Otherwise, it will traverse the tree using the right link.
• If the new node contains a question, it will present this question to the user and solicits a yes/no answer.
• Again if the answer is "no", it will traverse the tree using the left link. Otherwise, it will traverse the tree using right link.
• It will repeat this process, till it arrives at a leaf node.
• It will read the contents of the leaf node and present it to the user as its final guess. (A leaf node will always contain a guess/answer).
• If its guess is correct, it will print a self praising message such as "I must say I am very smart".
• If its guess is wrong, it will first ask the user to provide the correct answer and then it will ask the user to provide a question such that the "yes" answer to the question is user's correct object and "no" answer is program's wrong guess.
• It will update the tree to include the above information received from the user as below:
From the current leaf node that provided the program's guess, it will create two child nodes. It will copy the contents of the current node into its left child node; it will copy user's correct answer into its right child node; and it will copy the user supplied question in the current node.
• Then it will ask the user if the user would like to play another game.
• If the user responds affirmatively, it will repeat the above process.
• Otherwise, it will save the updated binary tree in the database file for future use and exit.
Storing/restoring Tree
//For using the method below, make sure that the last
//character in each question is a question mark i.e. ?
//For the methods below to work,
// the last character of every question must be a question mark.
//The methods below for storing a tree to a file is a modified pre-order traversal.
struct NodeType;
typedef NodeType * NodePtr;
struct NodeType
{
string item;
NodePtr llink;
NodePtr rlink;
};
void store()
{
//open a file object for output
ofstream outFile ("tree.txt", ios::out);
//assume root is the root of the tree;
rstore(root, outFile);
outFile.close ( );
}
void rstore(NodePtr nodep, ofstream & outFile)
{
//item below is a string being written to the file.
//For a question, the string ends with a question mark (?).
//For an answer,
//it ends with a non question mark, say with a period (.).
//use pre-order traversal to save the tree.
if (nodep!=NULL)
{
OutFileitem
rstore(nodep->llink,outFile);
rstore(nodep->rlink,outFile);
}
}
//The methods below can be used for restoring tree
//from a file prepared by the above methods. by using pre-order traversal.
void restore( )
{
//open a file object for input
ifstream inFile ("tree.txt", ios::in);
//assume root is the root of the tree. It may contain NULL at this time.
rrestore(root, inFile);
inFile.close ( );
}
rrestore(NodePtr &nodep, ofstream & inFile)
{
//use pre-order traversal for restoring the tree.
//After reading a line, and creating a node for it, ask if this is a question?
//If it is a question, make a recursive call to create and fill the next node.
//If it is not a question (i.e. it is an answer), do not make the recursive call
//because there is no node below it.
//read a line from the file.
char buf[120];
inFile.getline(buf,120);
//create a node.
//link this node to the node/root above it.
// The root or left/right link of the node above is passed to this method.
nodep = new NodeType;
//fill the node.
nodep->item = buf;
nodep->llink = NULL;
nodep->rlink = NULL:
//if this is a question, make the recursive call
//because there is still a node below it.
if (nodep->item[nodep->item.length( )-1]=='?')
{
rrestore(nodep->llink, inFile);
rrestore(nodep->rlink, inFile);
}
}
Testing
• Make your own data for testing.
• Keep testing till tree becomes at least 7 levels deep.
Submit
• Submit console input/output dialog for at least one correct and one incorrect answer.
• After the tree is at least 7 levels deep, submit a copy of the output file.