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 ) { }
};

// ------------------------------------------------------------------
// BinarySearchTre e class
// ------------------------------------------------------------------
class BinarySearchTre e
{
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
BinarySearchTre e( ) : 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 BinarySearchTre e::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 counterclockwis e to show
structure.
void BinarySearchTre e::Print( 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 BinarySearchTre e::PrintInorder ( 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 BinarySearchTre e class: main() function
int main( )
{
BinarySearchTre e 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(ite m);
} 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.PrintInord er( );

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

cout<<"Goodbye" <<endl;

return EXIT_SUCCESS;
}
again thanks for the help

[John Harrison]

On 26 Jul 2004 18:08:19 -0700, Henry Jordon <bu*******@hotm ail.com> wrote:

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]

In message <opsbr7wzkp2123 31@andronicus>, John Harrison
<jo************ *@hotmail.com> writes

On 26 Jul 2004 18:08:19 -0700, Henry Jordon <bu*******@hotm ail.com> wrote:

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.

A possible explanation of your confusion may be found here:

http://www.hpcnet.org/upload/directo...31027093651.cc

;-)

--
Richard Herring

[Mark R Rivet]

On 26 Jul 2004 18:08:19 -0700, bu*******@hotma il.com (Henry Jordon)
wrote:

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.
***********) : right here. should be ); *********** data( d ), left( l ), right( r ) { }
};

// ------------------------------------------------------------------
// BinarySearchTre e class
// ------------------------------------------------------------------
class BinarySearchTre e
{
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
BinarySearchTre e( ) : 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 BinarySearchTre e::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 counterclockwis e to show
structure.
void BinarySearchTre e::Print( 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 BinarySearchTre e::PrintInorder ( 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 BinarySearchTre e class: main() function
int main( )
{
BinarySearchTre e 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(ite m);
} 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.PrintInord er( );

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

cout<<"Goodbye" <<endl;

return EXIT_SUCCESS;
}
again thanks for the help

[Richard Herring]

In message <aj************ *************** *****@4ax.com>, Mark R Rivet
<ma********@ver izon.net> writes

On 26 Jul 2004 18:08:19 -0700, bu*******@hotma il.com (Henry Jordon)
wrote:

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.
***********

) : right here. should be );

***********

data( d ), left( l ), right( r ) { }

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

John M Weiss's code
(http://www.hpcnet.org/upload/directo...31027093651.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.

--
Richard Herring