Code:
// Narendrav,
// Your program doesn't hang for me, but since it does have *undefined behavior* it might hang in some cases.
// Let's go through it.
// You need to include some files for declarations (just to get your code to compile):
#include <cstddef> // For NULL
#include <iostream> // for std::cout and std::cin
// All references to cout and cin need to have namespace specifications (std::) to get your code to compile.
template <class T>
struct node
{
struct node *left;
T info;
struct node *right;
// No parent node pointer? That is okay.
};
// As laserlight said, you don't want a global variable for this. Probably put this in bst?
node<int>* root;
template <class T>
class bst
{
public:
// Some doc here to explain what these parameters are would be good.
// Is the first parameter the root node? Probably better to make that a member.
// Is the second parameter the node to insert?
// Does the tree take ownership of the node?
// Does it make a copy?
// Documentation makes life better for you, for your code reviewers and for your library users.
// In this case it is critical to understanding the problems with your code. In your main() routine
// You are passing in a
void insert(node<T> *,node<T> *);
// I don't see this and it isn't clear what it would do.
void inorder(node<T> *);
};
template <class T>
void bst<T> :: insert(node<T> *tree,node<T> *newnode)
{
if(root == NULL)
{
// Since T is a templated type, how do you know it is a number? Could it be a string?
// Why are we creating a T anyway. This function is an insert function, so why is it doing this?
T num;
// Your type shouldn't be writing to std::cout in the middle of an insert. It make your type
// unusable in a lot of contexts and it isn't a logical requirement of an insert.
std::cout << "Enter element\n";
// Ditto with reading in the middle of an insert.
std::cin >> num;
// You are writing over the value in newnode. Why did you pass it in if you are just going to overwrite it?
// With the main() routine that you have below, you are passing in newnode as a pointer that is never initialized.
// Here you are dereferencing your uninitialized pointer. This is *undefined behavior* meaning that anything can
// happen, including hanging your machine.
newnode->info = num;
root = new node<int>;
root->info = newnode->info;
root->left = NULL;
root->right = NULL;
std::cout << "Root element has been added\n";
return;
// Were we supposed to take ownership of the pass in node? If so we just leaked it.
// If not we changed its value, but didn't use it which may be a surprise to the caller.
}
if(tree->info == newnode->info)
{
// Probably better to either throw or return an error. Writing to the console
// means that:
// Your library can't be used in a lot of contexts
// There is no way for the calling code to detect this issue.
std::cout << "Element already exists\n";
return;
}
if(newnode->info < tree->info)
{
if(tree->left != NULL)
insert(tree->left,newnode);
else
{
// This code has many of the same issues as the code above. In fact it should be refactored
// as a function called from both places.
std::cout << "Enter element\n";
std::cin >> newnode->info;
tree->left = newnode;
newnode->left = NULL;
newnode->right = NULL;
std::cout << "Element added to the left\n";
return;
}
}
else
{
if(tree->right != NULL)
insert(tree->right,newnode);
else
{
std::cout << "Enter element\n";
std::cin >> newnode->info;
tree->right = newnode;
newnode->left = NULL;
newnode->right = NULL;
std::cout << "Element added to the right\n";
return;
}
}
}
int main()
{
// "option" isn't used at all.
int option;
bst<int> B;
node<int> *temp;
B.insert(root,temp);
}
// Narendrav, Make another pass at this code thinking about the issues that laserlight and I have raised.
// Consider a main that might look like this:
int main()
{
bst<int> b;
b.insert(10); // root value
b.insert(15);
b.insert(5);
assert(b.contains(5) && b.contains(10) && b.contains(15));
}