Binary Search Tree Input Problem

[Henry Jordon]

I have everything pretty much done but I need to fix something in my
coding. I want to be able to enter strings such as "love", "hate",
"the", etc. but am unable to figure how to do this. I have put my .cpp
and my .h code below. Please help and thank you very much.

// include files
#ifndef BINTREE_H
#define BINTREE_H
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
using namespace std;

// data types
typedef char DataType;

// TreeNode struct (includes constructor)
struct TreeNode
{
DataType data;
TreeNode *left, *right;

// constructor
TreeNode( DataType d = 0, TreeNode * l = NULL, TreeNode * r = NULL
) :
data( d ), left( l ), right( r ) { }
};

// ------------------------------------------------------------------
// BinarySearchTree class
// ------------------------------------------------------------------
class BinarySearchTree
{
private:

// private data members
TreeNode* root;
int level; // class variable to help format printing

// private member functions
void FreeTree( TreeNode* & );
TreeNode* Search( DataType, TreeNode* ) const;
void Insert( DataType, TreeNode* & );
void Delete( DataType, TreeNode* & );
void Print( TreeNode* );
void PrintInorder( TreeNode* ) const;

public:

// public member functions

// constructor
BinarySearchTree( ) : root( NULL ) { }

// call recursive insert method
void Insert( DataType item ) { Insert( item, root ); }

// print the tree on its side, showing structure
void Print( ) { level = 0; Print( root ); }

// call recursive print method
void PrintInorder( ) const { PrintInorder( root ); }
};

#endif


// include files
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include "bst.h"
using namespace std;

// Recursively insert an item in the tree, if not already present.
// Note that we pass root by reference.
void BinarySearchTree::Insert( DataType item, TreeNode* & root )
{
if ( root == NULL ) // hit NULL pointer, insert here
{
root = new TreeNode( item );
if ( root == NULL )
cerr << "Error: cannot allocate memory for TreeNode in
Insert()!\n";
}

else if ( item < root->data ) // insert in left subtree
Insert( item, root->left );

else if ( item > root->data ) // insert in right subtree
Insert( item, root->right );
}

// Recursive inorder tree traversal (called by Print function).
// Print the tree on its side, rotated counterclockwise to show
structure.
void BinarySearchTree:rint( TreeNode* nodeptr )
{
int i;

if ( nodeptr )
{
level++;

for ( i = 0; i < level; i++ )
cout << setw( 3 ) << ' ';
Print( nodeptr->right );

cout << '\r';
for ( i = 0; i < level - 1; i++ )
cout << setw( 3 ) << ' ';
cout << nodeptr->data << endl;

for ( i = 0; i < level; i++ )
cout << setw( 3 ) << ' ';
Print( nodeptr->left );

level--;
}
}

// Recursive tree traversals (called by Print routines).
// Print tree items inorder.
void BinarySearchTree:rintInorder( TreeNode* nodeptr ) const
{
if ( nodeptr != NULL )
{
PrintInorder( nodeptr->left ); // print left subtree
cout << nodeptr->data << ' '; // print root
PrintInorder( nodeptr->right ); // print right subtree
}
}

// Program to test BinarySearchTree class: main() function
int main( )
{
BinarySearchTree tree;
DataType item;
int n = 20;
char answer;
cout<<"Would you like to enter the numbers or have the system
generate";
cout<<"them randomly. R for random and U for user input."<<endl;
cin>>answer;
if(answer == 'R' || answer =='r')
{
// generate a BST of random int values
srand( time( NULL ) ); // init random number generator
cout << "Inserting " << n << " items in the BST:";
for ( int i = 0; i < n; i++ )
{
item = rand() % n; // generate a random int between 0 and n-1
tree.Insert( item ); // insert it in the BST
if ( i % 10 == 0 ) cout << endl;
cout << setw( 7 ) << item;
}
}
else if(answer == 'U' || answer =='u')
{
cout<<"Enter data with spaces in between. # terminates the
input"<<endl;
do
{
cin>>item;
if(item != '#')
tree.Insert(item);
} while(item != '#');
}
else
cout<<"Wrong input."<<endl;

// print the tree
cout <<endl;
cout <<"Duplicates will not be shown"<<endl;
cout << "\n\nBST contents:\n";
tree.PrintInorder( );

cout << "\n\nBST structure:\n";
tree.Print( );
cout<<endl;

cout<<"Goodbye"<<endl;

return EXIT_SUCCESS;
}
again thanks for the help

 

[John Harrison]

I have everything pretty much done but I need to fix something in my
coding. I want to be able to enter strings such as "love", "hate",
"the", etc. but am unable to figure how to do this. I have put my .cpp
and my .h code below. Please help and thank you very much.

It seems very unlikely that you could write all that code and yet not do
this seemingly simple task. What exactly is confusing you? What did you
attempt?

Here's a start

Add this.

#include <string>

Replace this

typedef char DataType;

with this.

typedef std::string DataType;

I think you'll have one or two more changes to make, but if you have any
understanding at all of the code you are working with I don't think you'll
find it too difficult.

john

 

[Richard Herring]

It seems very unlikely that you could write all that code and yet not
do this seemingly simple task.

A possible explanation of your confusion may be found here:

http://www.hpcnet.org/upload/directory/materials/1079_20031027093651.cc

;-)

 

[Mark R Rivet]

I have everything pretty much done but I need to fix something in my
coding. I want to be able to enter strings such as "love", "hate",
"the", etc. but am unable to figure how to do this. I have put my .cpp
and my .h code below. Please help and thank you very much.

// include files
#ifndef BINTREE_H
#define BINTREE_H
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
using namespace std;

// data types
typedef char DataType;

// TreeNode struct (includes constructor)
struct TreeNode
{
DataType data;
TreeNode *left, *right;

// constructor
TreeNode( DataType d = 0, TreeNode * l = NULL, TreeNode * r = NULL

You have a semi-colon here. It should be a colon or whatever you call
it, I always get them mixed up but you know what I mean, you have the
wrong line terminator right below my comments.
***********

 

[Richard Herring]

You have a semi-colon here. It should be a colon or whatever you call
it, I always get them mixed up but you know what I mean, you have the
wrong line terminator right below my comments.
***********

Wrong. That's a constructor definition and the colon introduces an
initializer list.

John M Weiss's code
(http://www.hpcnet.org/upload/directory/materials/1079_20031027093651.cc)
is fine, even if Mr Jordan did fail to acknowledge his authorship.
Somehow I don't think he's going to get full marks for this piece of
homework.