Binary Search Tree(Help)

[master797]

I am unable to implement the insert function properly,everytime i run the program i just get the first value and name,i am not getting other Id's and name.Please help!Thanks

"(Header File)"

#include <iostream>
#include <string>
using namespace std;


class node{
public:
int ID;
string name;
class node *left, *right, *parent;
node (string StudentName, int IDNumber) {
name = StudentName;
ID = IDNumber; // key value
left = NULL;
right = NULL;
parent = NULL;
}
}; // end class node

class bst {
class node *root; // root of the tree

// print in ascending order of IDs
void printInOrder(class node *n) {
if (n == NULL) {
//nothing to print
return;
}
// recursively print left sub-tree
printInOrder(n->left);
// print this node;
cout << "<" << n->ID << ", " << n->name << ">" << endl;
// recursively print right subtree
printInOrder(n->right);
}

public:
bst() {
root = NULL;
}
void print() {
printInOrder(root);
}

bool insert(string StudentName, int IDNumber); 

// returns true if successfully inserted 
// otherwise returns false (if matching ID exists in BST)

};



"(Main file)"


#include "bst.h"

int main() {
class bst *tree = new bst();

while (1) {
int choice; 
// 1 to insert a record, 2 to remove a record, 3 to print records in ascending order of IDs, 0 to exit
int StudentID;
string StudentName;
cout << endl << "Enter choice (1 to insert a record, 2 to remove a record, 3 to print records, 0 to exit): ";
cin >> choice;
if (choice == 0) {
break;
}
else if (choice == 1) {
cout << endl << "Enter new student ID: ";
cin >> StudentID;
cout << "Enter new student name: ";
cin >> StudentName;
if (tree->insert(StudentName, StudentID))
cout << "New student record inserted in BST" << endl;
else
cout << "Failed to add new student record in BST - matching ID exists" << endl;
}
if (choice == 3) {
cout << "Printing student records in ascending order of IDs" << endl;
tree->print();
}
}
system("pause");
}

"BST File(Implementation file)"

#include "bst.h"

using namespace std;

bool bst::insert(string StudentName, int IDNumber) {

class node *n1=new node("Master",10);
class node * parent=NULL;


if(root==NULL)
root=n1;
else
{
node*temp=root;
while(temp)
{

parent=temp;
if(n1->ID > temp->ID)
{
temp=temp->right;
return true;
}
else
{
temp=temp->left;
return true;
}
if(n1->ID < parent->ID)

{
parent->left=n1;
return true;
}
else
{
parent->right=n1;
return true;
}
}
}




//implement the function here
// you will need to create a new node with given student name and ID
// then traverse the tree (starting at the root) to find the right
// place to insert the node

// if a node with matching ID is found, return false to indicate failure

// if given ID is less than the ID of the node you are inspecting, move 
// to the left subtree. If the given ID is greater, move to the right subtree

// end insert

[ne555]

!indentation
<nolyc> indentation is optional whitespace. see also: !vowel
!vowel
<nolyc> vwls r bt s sfl s whtspc, spclly n vrbl nms. s ls: !ndnttn
!ndnttn
<nolyc> indentation is optional whitespace. see also: !vowel

bool bst::insert(string StudentName, int IDNumber) {
	class node *n1=new node("Master",10); //consider using the parameters
	class node * parent=NULL;

	if(root==NULL)
		root=n1;
	else
	{
		node*temp=root;
		while(temp)
		{
			parent=temp;
			if(n1->ID > temp->ID)
			{
				temp=temp->right;
				return true;
			}
			else
			{
				temp=temp->left;
				return true;
			}
//it is impossible that anything that follow would ever execute 

[master797]

What can i do to have other ids and names printed in ascending order?

[master797]

The only problem i am having is that its not been printed but when i debug the program and print the current and root note,it shows everything correct.Please point out where i am doing the mistake!thanks

bool bst::insert(string StudentName, int IDNumber) 
{
	
	
	class node * n= new node(StudentName,IDNumber);
	class node * current, *temp = NULL;
	current = root;

	if(root == NULL)
	{
		root = n;
		return 1;
	}
	else if(root->ID == n->ID)
		return 0;
	else if(root->ID > n->ID) //for Left Subtree 
	{		
		current = current->left;
		if(current == NULL)
		{
				current = n;
				current->parent = root;
				

				return 1;
		}
		else
		{
			while( !(current->left == NULL && current->right == NULL) )
			{		
				if(current->ID == n->ID)
					return 0;
				else if(current->ID > n->ID)
					current = current->right ;
				else
				{
					current = current->left;
				}

			}
			if(current->ID > n->ID)
			{	
				current->left = n;
				n->parent = current;
				

				return 1;
			}
			else
			{
				current->right = n;
				n->parent = current;
				

				return 1;
			}
	 
		}  
	}
	else
	{		
		current = current->right;
		if(current == NULL)
		{
				current = n;
				current->parent = root;
				return 1;
		}
		else
		{
			while( !(current->left == NULL && current->right == NULL) )
			{		
				if(current->ID == n->ID)
					return 0;
				else if(current->ID > n->ID)
					current = current->right ;
				else
				{
					current = current->left;
				}

			}
			if(current->ID > n->ID)
			{	
				current->left = n;
				n->parent = current;
				return 1;
			}
			else
			{
				current->right = n;
				n->parent = current;
				return 1;
			}
	 
		}  
	}
}

[ne555]

		current = current->left; //same in line 62 current->right
		if(current == NULL)
		{
				current = n;
				current->parent = root;
				

				return 1;
		}

You are not linking `root' there. You only set the parent, but `root->left' (or right) remains NULL.

You should note that the code from 29-56 is the same than 71-94. There is no point to the if-else.

bool bst::insert(string StudentName, int IDNumber) 
{
	class node * n= new node(StudentName,IDNumber);
	class node * current, *temp = NULL;
	current = root;
	if(root == NULL) //empty tree
	{
		root = n;
		return true;
	}

	//go to a leaf
	while( !(current->left == NULL && current->right == NULL) )
	{		
		if(current->ID == n->ID) //the value was already in the tree
			return false;
		else if(current->ID > n->ID)
			current = current->right ;
		else
			current = current->left;
	}
	//here we are in a leaf, and the value was not present in the three

	//linking the nodes
	if(current->ID > n->ID)
		current->left = n;
	else
		current->right = n;

	//avoid duplicated code
	n->parent = current;
	return true;
}

However that's still wrong, because you do not need to `go to a leaf', were both sons are missing.