I am trying to make a template class with a binary tree with functions | insert, remove, search, inorder, postorder, and print| I need some help with the main() part so i can test if i have the right code. please help.
Printable View
I am trying to make a template class with a binary tree with functions | insert, remove, search, inorder, postorder, and print| I need some help with the main() part so i can test if i have the right code. please help.
Code:#ifndef BST_H
#define BST_H
template < class S>
class BST
{
private:
typedef struct Node
{
Node* left;
Node* right;
int count;
};
Node* root;
public:
BST();
~BST();
bool Insert(const BST &i);
bool Remove(const BST &d);
Node*Search(const BST &s);
void InOrderTraverse(Node*);
void PostOrderTraverse(Node*);
void Print();
};
#endif
#include <iostream>
#include <cstdlib>
#include "bst.h"
using namespace std;
template <class S> void BST<S>::Print()
{
}
///////////////////////////////////////////////////////
template <class S> void BST<S>::PostOrderTraverse(Node* p)
{
if(p != NULL)
{
if(p->left) postorder(p->left);
if(p->right) postorder(p->right);
cout<<" "<<p->count<<" ";
PostOrderTraverse(root);
}
else return;
}
////////////////////////////////////////////////////////
template <class S> void BST<S>::InOrderTraverse(Node*)
{
if(p != NULL)
{
if(p->left) inorder(p->left);
cout<<" "<<p->count<<" ";
if(p->right) inorder(p->right);
InOrderTraverse(root);
}
else return;
}
////////////////////////////////////////////////////////
template <class S> bool BST<S>::Insert(const BST &i)
{
Node* t = new Node;
Node* parent;
t->count = i;
t->left = NULL;
t->right = NULL;
parent = NULL;
// is this a new tree?
if(isEmpty()) root = t;
else
{
//Note: ALL insertions are as leaf nodes
Node* curr;
curr = root;
// Find the Node's parent
while(curr)
{
parent = curr;
if(t->count > curr->count) curr = curr->right;
else curr = curr->left;
}
if(t->count < parent->count)
parent->left = t;
else
parent->right = t;
}
}
////////////////////////////////////////////////////////
template <class S> bool BST<S>::Remove(const BST &d)
{
//Locate the element
bool found = false;
if(isEmpty())
{
cout<<" This Tree is empty! "<<endl;
return;
}
Node* curr;
Node* parent;
curr = root;
while(curr != NULL)
{
if(curr->count == d)
{
found = true;
break;
}
else
{
parent = curr;
if(d>curr->count) curr = curr->right;
else curr = curr->left;
}
}
if(!found)
{
cout<<" count not found! "<<endl;
return;
}
// 3 cases :
// 1. We're removing a leaf node
// 2. We're removing a node with a single child
// 3. we're removing a node with 2 children
// Node with single child
if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
&& curr->right == NULL))
{
if(curr->left == NULL && curr->right != NULL)
{
if(parent->left == curr)
{
parent->left = curr->right;
delete curr;
}
else
{
parent->right = curr->right;
delete curr;
}
}
else // left child present, no right child
{
if(parent->left == curr)
{
parent->left = curr->left;
delete curr;
}
else
{
parent->right = curr->left;
delete curr;
}
}
return;
}
//We're looking at a leaf node
if( curr->left == NULL && curr->right == NULL)
{
if(parent->left == curr) parent->left = NULL;
else parent->right = NULL;
delete curr;
return;
}
//Node with 2 children
// replace node with smallest value in right subtree
if (curr->left != NULL && curr->right != NULL)
{
Node* chkr;
chkr = curr->right;
if((chkr->left == NULL) && (chkr->right == NULL))
{
curr = chkr;
delete chkr;
curr->right = NULL;
}
else // right child has children
{
//if the node's right child has a left child
// Move all the way down left to locate smallest element
if((curr->right)->left != NULL)
{
Node* lcurr;
Node* lcurrp;
lcurrp = curr->right;
lcurr = (curr->right)->left;
while(lcurr->left != NULL)
{
lcurrp = lcurr;
lcurr = lcurr->left;
}
curr->count = lcurr->count;
delete lcurr;
lcurrp->left = NULL;
}
else
{
Node* tmp;
tmp = curr->right;
curr->count = tmp->count;
curr->right = tmp->right;
delete tmp;
}
}
return;
}
}
//////////////////////////////////////////////////
/*template <class S>
BST<S>::Node*Search(const BST &s)
{
}*/
//////////////////////////////////////////////////
template <class S>
BST<S>::BST()
{
root = NULL;
count = 0;
}
template <class S>
BST<S>::~BST()
{
}
int main()
{
int ch,tmp,tmp1;
while(1)
{
cout<<endl<<endl;
cout<<" Binary Search Tree Operations "<<endl;
cout<<" ----------------------------- "<<endl;
cout<<" 1. Insertion/Creation "<<endl;
cout<<" 2. In-Order Traversal "<<endl;
cout<<" 3. Pre-Order Traversal "<<endl;
cout<<" 4. Post-Order Traversal "<<endl;
cout<<" 5. Removal "<<endl;
cout<<" 6. Exit "<<endl;
cout<<" Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1 : cout<<" Enter Number to be inserted : ";
cin>>tmp;
bool Insert(tmp)
break;
case 2 : cout<<endl;
cout<<" In-Order Traversal "<<endl;
cout<<" -------------------"<<endl;
void InOrderTraverse();
break;
case 3 : cout<<endl;
cout<<" Post-Order Traversal "<<endl;
cout<<" --------------------"<<endl;
void PostOrderTraverse();
break;
case 4 : cout<<" Enter count to be deleted : ";
cin>>tmp1;
//b.remove(tmp1);
break;
case 5 :
return 0;
}
}
}
I need help for this part
case 1 : cout<<" Enter Number to be inserted : ";
cin>>tmp;
b.Insert(tmp);
break;
i keep getting Reason: cannot convert from 'int' to 'const BST<S>'
1. Edit your posts adding Code tags around code snippet. Otherwise your code is impossible to read/understand.Quote:
Originally Posted by akballow
2. I cannot convert from 'int' to 'const BST<S>' too. Because I have no idea what 'const BST<S>' is. :cool:
what is it ?Code:bool Insert(tmp)
How can i do that, this site doesnt have the button. Please help
Oh, Something's bad.
In your BST class you have defined a method :
bool Insert(const BST &i);
But when you use it :
case 1 : cout<<" Enter Number to be inserted : ";
cin>>tmp;
bool Insert(tmp) // maybe it's b.Insert(tmp);
but tmp is not type of BST
so ... ?
In myopinion, maybe you will think about this method:
bool Insert(const BST &i);
and change it to:
bool Insert(const S &i);
Oh man, that jumped a boat load of errors. I just want a simple way to check that my insert member function works.
Announcement: Before you post....Quote:
Originally Posted by akballow
http://www.codeguru.com/forum/misc.php?do=bbcode
alright, so changing BST to S in that class made things work, but my insert member function is broke, it doesnt work correctly. Can someone help me with that.
Sorry i mean the remove member function does not work, the insert function works great.
What does it do incorrectly?Quote:
Originally Posted by akballow
Did you try to debug it to see where and why it fails?
the remove function breaks at | if(parent->left == curr) | which doesnt help me much. I am working for the solution atm as well as looking for any outside help.
The variable 'parent' is being used without being initialized. seems to be the problem
Define "breaks".Quote:
Originally Posted by akballow
Does the parent point to a valid object?
parent-> is Null here and its trying to become curr, but breaks(code crashes) here.
Code:template <class S> bool BST<S>::Remove(const S &d)
{
//Locate the element
bool found = false;
if(isEmpty())
{
cout<<" This Tree is empty! "<<endl;
return false;
}
Node* curr;
Node* parent;
curr = root;
while(curr != NULL)
{
if(curr->count == d)
{
found = true;
break;
}
else
{
parent = curr;
if(d>curr->count) curr = curr->right;
else curr = curr->left;
}
}
if(!found)
{
cout<<" count not found! "<<endl;
return false;
}
// 3 cases :
// 1. We're removing a leaf node
// 2. We're removing a node with a single child
// 3. we're removing a node with 2 children
// Node with single child
if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
&& curr->right == NULL))
{
if(curr->left == NULL && curr->right != NULL)
{
if(parent->left == curr) <--------------------------------------------Problem Area
{
parent->left = curr->right;
delete curr;
}
else
{
parent->right = curr->right;
delete curr;
}
}
else // left child present, no right child
{
if(parent->left == curr)
{
parent->left = curr->left;
delete curr;
}
else
{
parent->right = curr->left;
delete curr;
}
}
return true;
}
//We're looking at a leaf node
if( curr->left == NULL && curr->right == NULL)
{
if(parent->left == curr) parent->left = NULL;
else parent->right = NULL;
delete curr;
return true;
}
//Node with 2 children
// replace node with smallest value in right subtree
if (curr->left != NULL && curr->right != NULL)
{
Node* chkr;
chkr = curr->right;
if((chkr->left == NULL) && (chkr->right == NULL))
{
curr = chkr;
delete chkr;
curr->right = NULL;
}
else // right child has children
{
//if the node's right child has a left child
// Move all the way down left to locate smallest element
if((curr->right)->left != NULL)
{
Node* lcurr;
Node* lcurrp;
lcurrp = curr->right;
lcurr = (curr->right)->left;
while(lcurr->left != NULL)
{
lcurrp = lcurr;
lcurr = lcurr->left;
}
curr->count = lcurr->count;
delete lcurr;
lcurrp->left = NULL;
}
else
{
Node* tmp;
tmp = curr->right;
curr->count = tmp->count;
curr->right = tmp->right;
delete tmp;
}
}
return true;
}
}
A new problem other then my remove function not working is when i compile under KDE, runing command g++ -g *.cpp -o test
i get
in member function 'bool BST<S>::Insert(const S&)'
error: '->' cannot appear in a constant-expression
error: parse error in template argument list
for the line if( t->count < parent->count)
parent->left =t;