3 Replies - 4661 Views - Last Post: 26 May 2009 - 04:16 PM Rate Topic: -----

#1 korrupted   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 26-May 09

Binary Search Trees and Game

Posted 26 May 2009 - 08:45 AM

Hi There,

I have a question regarding Binary Search Trees implementation. This is sort of like a game based on yes or no answers. The game reads the data from a file with text asking questions and a yes or no and then another question till it has reached an answer.

I have managed to write a header and a cpp file with some code. I also have a text file for some testing purpose. Now from what I understand, I have to deal with a substr command. At the moment I am stuck as I don't have an idea on how to go about doing this.

/* 
  BSTNode.h
  Name: Vinod
  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


Here comes the second part of code

[code]
/*
BSTNode.cpp
Name: Vinod
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;
}
}[/code

Any help will be most appreciated. Tanks

Is This A Good Question/Topic? 0
  • +

Replies To: Binary Search Trees and Game

#2 Plus   User is offline

  • D.I.C Regular
  • member icon

Reputation: 41
  • View blog
  • Posts: 414
  • Joined: 24-November 08

Re: Binary Search Trees and Game

Posted 26 May 2009 - 11:35 AM

BST, ehh ...

well here is my BST declaration recursively ...

#ifndef BSTNODE_H
#define BSTNODE_H

struct TNode
{
			tree_node* left;
			tree_node* right;
			string data;
};

class BST
{
	private:
		TNode* root;

	public:
		BST()
		{
		   root = NULL;
		}
		bool isEmpty() const { return root==NULL; }
		void print_preorder();
		void preorder(TNode*);

		void insert(const string&);
		TNode* insert(TNode*,const string&);
};

void print_preorder()
{
	print_preorder(root);
}

void preorder(TNode* t)
{
   if(t!=NULL)
   {
		cout <<" "<< t->data;
		
		print_preorder(t->left);
		print_preorder(t->right);
   }
}

void insert(const string &s)
{
	root = (root, s);
}

TNode* insert(TNode* t,const string &s)
{
   if(t!=NULL)
   {
		if( strcmp(s,t->data)<2 )
			t = print_preorder(t->left);

		t = print_preorder(t->right);
   }
   else
		t = new TNode*(s);

   return t;
}



Was This Post Helpful? 0
  • +
  • -

#3 Elcric   User is offline

  • D.I.C Regular
  • member icon

Reputation: 102
  • View blog
  • Posts: 453
  • Joined: 02-May 09

Re: Binary Search Trees and Game

Posted 26 May 2009 - 03:01 PM

:D Hello everyone,

See if this site helps you any.

http://www.cplusplus...thms/code5.html
Was This Post Helpful? 0
  • +
  • -

#4 korrupted   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 26-May 09

Re: Binary Search Trees and Game

Posted 26 May 2009 - 04:16 PM

View PostPlus, on 26 May, 2009 - 10:35 AM, said:

BST, ehh ...

well here is my BST declaration recursively ...

#ifndef BSTNODE_H
#define BSTNODE_H

struct TNode
{
			tree_node* left;
			tree_node* right;
			string data;
};

class BST
{
	private:
		TNode* root;

	public:
		BST()
		{
		   root = NULL;
		}
		bool isEmpty() const { return root==NULL; }
		void print_preorder();
		void preorder(TNode*);

		void insert(const string&);
		TNode* insert(TNode*,const string&);
};

void print_preorder()
{
	print_preorder(root);
}

void preorder(TNode* t)
{
   if(t!=NULL)
   {
		cout <<" "<< t->data;
		
		print_preorder(t->left);
		print_preorder(t->right);
   }
}

void insert(const string &s)
{
	root = (root, s);
}

TNode* insert(TNode* t,const string &s)
{
   if(t!=NULL)
   {
		if( strcmp(s,t->data)<2 )
			t = print_preorder(t->left);

		t = print_preorder(t->right);
   }
   else
		t = new TNode*(s);

   return t;
}




That's great! So this should um...help to create the tree and insert the string based on a question? For example I read from a text file and ask "Is this a land dwelling animal? answer should be yes or no. If it no then the node inserts No at the left and then asks the next question. Can this animal fly? If yes then the node will insert yes at the right.

So this code basically takes the text file after opening and reading the contents and then does the above right? I assume based on this code if( strcmp(s,t->data)<2 ) that it is comparing the data less than 2. Pardon me but what is the s and t and the value of 2 in this context? Was it something to do with substr command?

It's a kind of a game I'm trying to develop just for a demo...

Thanks for your time.


View PostPlus, on 26 May, 2009 - 10:35 AM, said:

BST, ehh ...

well here is my BST declaration recursively ...

#ifndef BSTNODE_H
#define BSTNODE_H

struct TNode
{
			tree_node* left;
			tree_node* right;
			string data;
};

class BST
{
	private:
		TNode* root;

	public:
		BST()
		{
		   root = NULL;
		}
		bool isEmpty() const { return root==NULL; }
		void print_preorder();
		void preorder(TNode*);

		void insert(const string&);
		TNode* insert(TNode*,const string&);
};

void print_preorder()
{
	print_preorder(root);
}

void preorder(TNode* t)
{
   if(t!=NULL)
   {
		cout <<" "<< t->data;
		
		print_preorder(t->left);
		print_preorder(t->right);
   }
}

void insert(const string &s)
{
	root = (root, s);
}

TNode* insert(TNode* t,const string &s)
{
   if(t!=NULL)
   {
		if( strcmp(s,t->data)<2 )
			t = print_preorder(t->left);

		t = print_preorder(t->right);
   }
   else
		t = new TNode*(s);

   return t;
}




That's great! So this should um...help to create the tree and insert the string based on a question? For example I read from a text file and ask "Is this a land dwelling animal? answer should be yes or no. If it no then the node inserts No at the left and then asks the next question. Can this animal fly? If yes then the node will insert yes at the right.

So this code basically takes the text file after opening and reading the contents and then does the above right? I assume based on this code if( strcmp(s,t->data)<2 ) that it is comparing the data less than 2. Pardon me but what is the s and t and the value of 2 in this context? Was it something to do with substr command?

It's a kind of a game I'm trying to develop just for a demo...

Thanks for your time.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1