A Binary Search Tree of Classes

BossArky

Hello,
I'm trying to compile this program and get errors..that I cannot convert from one type to another. Anyone know why? I'm attempting to add some functionality to it once it compiles..so that I can insert names & number into a phonebook, browse, delete and list.
Any suggestions welcome.




#include <iostream.h>

//#include <string.h>
//#include <ctype.h>
#include <conio.h>

#include <time.h>
#include <stdlib.h>


//from here

#define SequenceLength 80
#define MaxNumber 100

//to here

/*
#define LONGEST_MENU_ENTRY 20
#define MaxMenuSize 10

bool Member(char , const char []) ;
char ShowMenu(const char Menu[][LONGEST_MENU_ENTRY+1 ], int ) ;
*/

// class stuff


template <class UserType> class BST;

template <class UserType>
class BSTNode
{
friend BST<UserType>;
protected : //private
UserType Data; //The data in the node
BSTNode *Left; //Left Child
BSTNode *Right; //Right Child
public :
/*NOTE : All of the activity in relation to Nodes is handled by constructors*/
BSTNode( ) : Left( NULL ), Right( NULL ) {}
BSTNode( const UserType & DataValue ) : Data( DataValue ), Left( NULL ), Right ( NULL ) {}
BSTNode( const UserType & DataValue, BSTNode *L, BSTNode *R ) :
Data ( DataValue ), Left(L), Right(R) {}
};

template <class UserType>
class BST
{
private :
BSTNode<UserType> *Root;
void DeleteTree( BSTNode<UserType> *t ) ;
void List( const BSTNode<UserType> *t) ;
public :
BST( ) : Root( NULL ) { }
~BST( ) ;
void Insert( const UserType & X ) ;
void List(void) { List(Root) ; }
};

template <class UserType>
BST<UserType>::~BST( )
{
if( Root != NULL )
{
DeleteTree( Root );
}
}

template <class UserType>
void
BST<UserType>::DeleteTree( BSTNode<UserType> *t )
{
if( t != NULL )
{
DeleteTree( t->Left );
DeleteTree( t->Right );
delete t;
}
}

template <class UserType>
void
BST<UserType>::Insert( const UserType & X )
{
BST<UserType> *t, *p;
if(Root == NULL)
{
Root = new BSTNode<UserType>( X );
}
else
{
p = t = Root;
while( t != NULL && X != t->Data )
{
p = t;
if(X < t->Data)
{
t = t->Left;
}
else
{
t = t->Right;
}
}
if (t == NULL)
{
t = new BSTNode<UserType>( X );
if( X < p->Data )
{
p->Left = t;
}
else
{
p->Right = t;
}
}
}
}


template <class UserType>
void
BST<UserType>::List( const BSTNode<UserType> *t )
{
if( t->Left != NULL )
{
List(t->Left);
}
cout<<t->Data<<'\t';
if( t-> Right != NULL )
{
List(t->Right);
}
}


main()
{
BST<int> Tree;
int i, N;
time_t t;
srand((unsigned) time(&t));
cout<<"Randomly generated list";
for(i=0; i< SequenceLength; i++)
{
N = rand() % MaxNumber + 1;
cout << N << '\t' ;
Tree.Insert(N);
}
cout<<endl<<endl;
cout<<"INORDER traversal generates list ";
<<endl <<endl;
Tree.List() ;
cout <<endl;
getch();
}



/*

main()
{ char Menu[][LONGEST_MENU_ENTRY+1] = {"Insert","List","Browse","Delete","Off"} ;
char MenuChoice ;
// stuff to create object instance of class

do {
MenuChoice = ShowMenu(Menu,5) ;
switch(MenuChoice) {
case 'I' :
case 'i' : //stuff to insert
break ;
case 'L' :
case 'l' : //stuff to List
break ;
case 'B' :
case 'b' : //stuff to Browse
break ;
case 'D' :
case 'd' : //stuff to Delete
break ;
}
} while(MenuChoice != 'O') ;
cout << endl << "Switching Off...Press any key" << endl ;
getch() ;
}



char ShowMenu(const char Menu[][LONGEST_MENU_ENTRY+1],int Size)
{ int i ;
char MenuInitialChars[MaxMenuSize+1], Choice ;

cout << endl ;
for(i = 0 ; i < Size ; i++) {
cout << Menu << endl ;
MenuInitialChars = toupper(Menu[0]) ;
}
// Insert an EOF (i.e. end of text) marker after the last menu char
MenuInitialChars = '\0' ;

cout << endl << endl << "Menu Choice? " << flush ;
do {
// NOTE, the user input is converted to uppercase for consistency
Choice = toupper(getch()) ;
// Search the initial chars array for the user input
} while(!Member(Choice,MenuInitialChars)) ;
return Choice ;
}

bool Member(char X, const char Str[])
{ int i ;
for(i=0; Str != '\0' && Str != X ; i++) ;
if(Str == X) {
return true ;
} else {
return false ;
}
}



*/

DeadBankClerk

can you clean that code up and post it again?
(and put it between [code] [/code] tags - it makes the code maintain it's formatting).
and take out the big commented-out chunk at the bottom.

From a quick read of your code:

1) You dont need to check that a pointer is not null before you delete it, calling delete on a null pointer is a valid operation in C++, and has no effect.

2) Your delete node code could be alot more elegant with proper destructors:

Node::~Node (void)
{
    // Nice elegant recursive delete
    delete this->left;
    delete this->right;
}

BST::~BST (void)
{ 
    delete this->root;
}

DeadBankClerk

What line of code is giving the syntax error?

DeadBankClerk

Also, your BST::list function has the line:

cout << t->Data << '\t';

This is probably the error. Data can be of any type, not just int, so cout wont like it. You should cast it to an int:

cout << (int)t->Data << '\t';



[php]
class BST
{
...
friend ostream& operator << (ostream& stream, const BST& tree)
{
stream << *left;
stream << *this;
stream << *right;
};
};

class BSTNode
{
...
friend ostream& operator << (ostream& stream, const BSTNode& node)
{
stream << (int)node.Data << '\t';
};
};
[/php]

Something like that is just nice it will allow you to:

BST Tree;

cout << Tree << endl;

BossArky

ok thanks, sorry for delay in replying..just working on something at the moment. Will post again when I figure out what I'm doing.

Talliesin

Originally posted by DeadBankClerk
Also, your BST::list function has the line:

cout << t->Data << '\t';

This is probably the error. Data can be of any type, not just int, so cout wont like it. You should cast it to an int:

cout << (int)t->Data << '\t';

You sure?

std::ostream (of which cout is an object) has << overloaded for all the built in types. If UserType (the type of Data) is a user-defined type then you can define an operator along the lines of:

std::ostream& operator<<(std::ostream& out, const SOMETYPE& x){
/*code here that writes x to the stream,
this will obviously depend on the layout and purpose of SOMETYPE */
return out;
}

You might like to do the same for std::wostream for good measure.

As such the code without the cast to int will work (at least that small bit of it) for all built-in types, and can be made to work for all user-defined types.
(Of course the rules of template instantiation mean that it won't matter if a user-defined type doesn't have << if you don't actually try to << the tree, so you could still use the tree class for something else if << wasn't needed).

With the (C-style) cast to int however there are a few possibilities, in order of disasterousness:

1. UserType is int, the cast gets compile away to nothing, so everything is grand.
2. UserType can't be cast to int. Code doesn't compile. Bug found and fixed.
3. UserType can be cast to int without loss of precision. The code works, but is less efficient, although that inefficiency might be optimised away.
4. UserType can be cast to int, but returns an address (e.g. casting c-style strings to int) results are gibberish.
5. UserType can be cast to int, but loses precision. Results are wrong, but testing may not reveal the bug.