<links snipped>
Hello I need some help with this question. I have attempted to write a segment of code for the Binary Search Trees in C++ code. Refer to the question below.
Design and implement a program in C++ to solve the following problem.
DESCRIPTION
This program, which learns by asking questions, is a classic artificial intelligence problem. The program uses a decision tree (a BST used for decision making) as its main data structure. The non-leaf nodes of the tree contain strings representing yes/no questions. The user must think of a single object and answer the questions based on that object.
The program starts by asking the user the question contained in the root node. If the user responds with a “no”, the program follows the left child branch to ask the question in the next node; with “yes” it follows the right child branch. The program repeats this process with each new node. The leaves of the tree contain objects corresponding to the sequence of answers that led from the root to the leaf. When the program reaches a leaf, it guesses that the user is thinking of that leaf’s object. It that leaf’s object matches the user’s object, the program wins. If the two objects do not match, the program learns by asking the user to specify a yes/no question that distinguishes the user’s object from the leaf’s object. The program then places this user question into the appropriate location in the tree. The user may continue to play this game for some period of time.
INPUT
User response to a program question, to a program guess, or to a play-again prompt is either a single ‘y’ or a single ‘n’ (either in uppercase or lowercase).
Input to an add-an-object prompt is the object that the user was thinking of while playing the current round of the game.
Input to an add-a-question prompt is a single-line question that has a “yes” answer for the user’s object and a “no” answer for the object guessed by the program.
OUTPUT
All program output is double-spaced. At the beginning of each game, the program begins with the following message:
You must think of a single object. Please answer the following questions about this object.
Each subsequent question comes from a node in the decision tree. The form is:
QUESTION: (Y or N):
The program continues to ask questions from the root of the tree down through the descendants that correspond to the user’s responses. When the program encounters a leaf node, it makes the following guess:
I guess that your object is a(n) <object>. (Y or N):
where is the object in the leaf node. If the user responds ‘Y’ or ‘y’, the program outputs the following:
Notice the superior intellect of the computer!
If the user responds ‘N’ or ‘n’, the program outputs an add-an-object prompt, followed by an add-a-question prompt, and then a play-again prompt. The add-an-object prompt is as follows:
What object were you thinking of?
The add-a-question prompt is as follows:
Please specify a question that has a yes answer for your object and a no answer for my guess:
The program then issues a play-again prompt:
Play again? (Y or N):
The program plays the game as many times the user continues to respond 'Y’ or ‘y’ to this prompt.
ERROR HANDLING
The program should deal with any unexpected user input in a useful and user-friendly manner.
EXAMPLE
Suppose that the initial tree is as follows:
Does it have two legs?
horse bird
Below is a sample execution with all input in italics:
You must think of a single object. Please answer the following questions about this object.
QUESTION: Does it have two legs? (Y or N): N
I guess that your object is a(n) horse. (Y or N): Y
Notice the superior intellect of the computer!
Play again? (Y or N): Y
You must think of a single object. Please answer the following questions about this object.
QUESTION: Does it have two legs? (Y or N): N
I guess that your object is a(n) horse. (Y or N): N
What object were you thinking of? tulip
Please specify a question that has a yes answer for your object and a no answer for my guess:
Is it a plant?
Play again? (Y or N): A
INCORRECT RESPONSE – Please type Y or N
Play again? (Y or N): Y
You must think of a single object. Please answer the following questions about this object.
QUESTION: Does it have two legs? (Y or N): N
QUESTION: Is it a plant? (Y or N): N
I have started to code the Header file with some operations. But hat essentially needs to be done is it should be able to handle strings with yes/no answers from a text file. If the answer is no add to the left side of the tree, if yes then add to the right side. Here's the code.
Help with Code Tags
/* BSTNode.h
Name: Vinod Shankar Menon
Description: This exercise is to show the implementation of a Binary Search Tree
The Header file contains the various operations that can be performed on the Tree.
BSTNode.h contains the declaration of class template BST.
Constructor: Constructs an empty BST
isEmpty: Checks if a BST is empty
insert: Inserts a value into a BST
remove: Removes a value from a BST
*/
#include <iostream>
#include <cstdlib>
using namespace std;
#ifndef BSTNODE_H
#define BSTNODE_H
class BinarySearchTree
{
private:
struct tree_node
{
tree_node* left;
tree_node* right;
string data;
};
tree_node* root;
public:
BinarySearchTree()
{
root = NULL;
}
bool isEmpty() const { return root==NULL; }
void print_preorder();
void preorder(tree_node*);
void insert(string);
};
// Smaller elements go left
// larger elements go right
void BinarySearchTree::insert(string d)
{
tree_node* t = new tree_node;
tree_node* parent;
t->data = d;
t->left = NULL;
t->right = NULL;
parent = NULL;
// is this a new tree?
if(isEmpty()) root = t;
else
{
d.substr() = no ;
//Note: ALL insertions are as leaf nodes
tree_node* curr;
curr = root;
// Find the Node's parent
while(curr)
{
parent = curr;
if(t->data > curr->data) curr = curr->right;
else curr = curr->left;
}
if(t->data < parent->data)
parent->left = t;
else
parent->right = t;
}
}
void BinarySearchTree::print_preorder()
{
preorder(root);
}
void BinarySearchTree::preorder(tree_node* p)
{
if(p != NULL)
{
cout<<" "<<p->data<<" ";
if(p->left) preorder(p->left);
if(p->right) preorder(p->right);
}
else return;
}
#endif/* BSTNode.h Name: Vinod Shankar Menon Description: This exercise is to show the implementation of a Binary Search Tree The Header file contains the various operations that can be performed on the Tree. BSTNode.h contains the declaration of class template BST. Constructor: Constructs an empty BST isEmpty: Checks if a BST is empty insert: Inserts a value into a BST remove: Removes a value from a BST */ #include <iostream> #include <cstdlib> using namespace std; #ifndef BSTNODE_H #define BSTNODE_H class BinarySearchTree { private: struct tree_node { tree_node* left; tree_node* right; string data; }; tree_node* root; public: BinarySearchTree() { root = NULL; } bool isEmpty() const { return root==NULL; } void print_preorder(); void preorder(tree_node*); void insert(string); }; // Smaller elements go left // larger elements go right void BinarySearchTree::insert(string d) { tree_node* t = new tree_node; tree_node* parent; t->data = d; t->left = NULL; t->right = NULL; parent = NULL; // is this a new tree? if(isEmpty()) root = t; else { d.substr() = no ; //Note: ALL insertions are as leaf nodes tree_node* curr; curr = root; // Find the Node's parent while(curr) { parent = curr; if(t->data > curr->data) curr = curr->right; else curr = curr->left; } if(t->data < parent->data) parent->left = t; else parent->right = t; } } void BinarySearchTree::print_preorder() { preorder(root); } void BinarySearchTree::preorder(tree_node* p) { if(p != NULL) { cout<<" "<<p->data<<" "; if(p->left) preorder(p->left); if(p->right) preorder(p->right); } else return; } #endifAfter having done that I have written code for the implementation of the binary search tree, still would require some work? In this part of the code we have to open the file, read the question ask it and based on answer perform the insertion of data to the appropriate part of the tree.
Help with Code Tags
/*
BSTNode.cpp
Name: Vinod Shankar Menon
Description: This exercise is to show the implementation of a Binary Search Tree
The Header file contains the various operations that can be performed on the Tree.
BSTNode.cpp contains the declaration of class template BST.
*/
#include <iostream>
#include <fstream>
#include <string>
#include "BSTree.h"
using namespace std;
int main()
{
BinarySearchTree b;
int ch;
string filename;
cout << "Enter filename: ";
getline (cin, filename);
ifstream fstr (filename.c_str());
// Is the ready state 0 (no errors)?
if (fstr.rdstate() == 0)
{
string line;
// prime the while loop
getline (fstr , line);
b.insert (line);
while (!fstr.eof())
{
cout << line << endl;
getline (fstr , line);
b.insert(line);
}
}
else
{
cerr << "Could not open file \"" << filename
<< "\" for reading." << endl;
}
return 0;
while(1)
{
cout<<endl<<endl;
cout<<" Binary Search Tree Operations "<<endl;
cout<<" ----------------------------- "<<endl;
cout<<" 1. Insertion/Creation "<<endl;
cout<<" 2. Pre-Order Traversal "<<endl;
cout<<" 3. Exit "<<endl;
cout<<" Enter your choice : ";
cin>>ch;
}
}
/* BSTNode.cpp Name: Vinod Shankar Menon Description: This exercise is to show the implementation of a Binary Search Tree The Header file contains the various operations that can be performed on the Tree. BSTNode.cpp contains the declaration of class template BST. */ #include <iostream> #include <fstream> #include <string> #include "BSTree.h" using namespace std; int main() { BinarySearchTree b; int ch; string filename; cout << "Enter filename: "; getline (cin, filename); ifstream fstr (filename.c_str()); // Is the ready state 0 (no errors)? if (fstr.rdstate() == 0) { string line; // prime the while loop getline (fstr , line); b.insert (line); while (!fstr.eof()) { cout << line << endl; getline (fstr , line); b.insert(line); } } else { cerr << "Could not open file \"" << filename << "\" for reading." << endl; } return 0; while(1) { cout<<endl<<endl; cout<<" Binary Search Tree Operations "<<endl; cout<<" ----------------------------- "<<endl; cout<<" 1. Insertion/Creation "<<endl; cout<<" 2. Pre-Order Traversal "<<endl; cout<<" 3. Exit "<<endl; cout<<" Enter your choice : "; cin>>ch; } }My question is what else can I do to the code, in order to just get it to read the file ask the question and create the tree, and ask player if he wants to play again yes or no question? Any help with the modification of code would be helpful. Thanks
