Binary Search Tree AI Game

[korrupted]

Hello All,

I have a question regarding binary trees. What I have to do is create a tree that plays a game and accepts yes or no as a answer to the question then goes on to the next. I have the question posted below.

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: <question from tree node> (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 <object> 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.

From here what I have done o attempted for the header file is as follows, see the code.

/* 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 ;
//not sure what else to put here.




    //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 

Is this sufficient to achieve what the question asks? Additional code for the cpp file is below.

/* 
  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;
    }
}

It can read the text file but doen't achieve what I am trying to do for the question, any help ith this is most welcome. I can't seem to get it to ask a question and then the usere respond to it yes or no. If no add the node to let and then ask andother question. If it is yes add the node to the right and try to guess the animal. Please do help me with this question.

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

and so on. Any help with this question will be verry much appreciated. Thanks!

[writetonsharma]

looks interesting..so where have you stuck??

because if you know how to add to bst than you should not be having any problem.

[Incubbus]

that looks like code ur lecturer gave u;)...

[korrupted]

Good try eh? I am stuck with the question ans answer section. Let's just say it reads the question then it waits for an answer based on yes or no.

// 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 ;
//not sure what else to put here.




    //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;
  }
}

So how does one get it to perform the qn'a part of the tree? Apart from the main program where I read the file? You can refer to the sample execution.