Binary Search tree
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5

Thread: Binary Search tree

  1. #1
    Join Date
    Nov 2013
    Posts
    6

    Question Binary Search tree

    I am unable to implement the insert function properly,every time i run the program i just get the first value and name,i am not getting other Id's and name.Please help!Thanks
    Code:
    "(Header File)" #include <iostream> #include <string> using namespace std; class node { public: int ID; 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 * n= new node(StudentName,IDNumber); class node * parent = NULL; if(root == NULL) root = n; else { // Need help here //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

  2. #2
    Join Date
    Apr 1999
    Posts
    27,424

    Re: Binary Search tree

    Quote Originally Posted by talhakhan797 View Post
    every time i run the program
    Programming is much more than just writing code and running it. What have you done to debug your program? When you debug your program, what line, function, variable, etc. goes against what you expected?

    Regards,

    Paul McKenzie

  3. #3
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,316

    Re: Binary Search tree

    Being able to debug programs is an essential skill of becoming a programmer. The basic steps for any program are
    design, code, test/debug.

    In this case, you haven't even attempted to code the missing functions, so no wonder the program doesn't work properly! As this is an assignment, we won't provide the code for you as that would be cheating. See http://forums.codeguru.com/showthrea...ork-assignment

    Your first step is to understand the provided code and then to design the required functions, then code them and then test/debug. If you are having trouble understanding binary search trees, an internet search provides plenty of information eg
    https://www.google.co.uk/search?q=bi...LciVhQexuoCQBQ
    http://en.wikipedia.org/wiki/Binary_search_tree
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  4. #4
    Join Date
    Nov 2013
    Posts
    6

    Question Re: Binary Search tree

    The only problem i am having now is that id's are not been printed except root node but when i debug the program and print the current and root note by inserting cout,it shows everything correct(correct root node and current node).Please point out where i am doing the mistake!thanks


    Code:
    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;
    			}
    	 
    		}  
    	}
    }

  5. #5
    Join Date
    Apr 1999
    Posts
    27,424

    Re: Binary Search tree

    Quote Originally Posted by talhakhan797 View Post
    but when i debug the program and print the current and root note by inserting cout,
    Run your code using the debugger, not by using cout. Step through the code in the debugger
    it shows everything correct
    Which proves that using "cout" is not enough. If you say it is "correct", then there is nothing wrong. If you now say there is something wrong, then it isn't "correct".
    Please point out where i am doing the mistake!
    Did you write the code? If so, then you're supposed to know exactly what every line, function, etc. is supposed to do. If the program doesn't do what you planned it to do, then you step through the program using the debugger to see where it goes against your plan. You don't write code randomly and not know what every single function, loop, line, etc. is supposed to do.

    Second, when dealing with trees, you should have written down on paper using boxes, arrows, etc. how linked lists are supposed to work in terms of insertion, deletion, etc. before writing a single line of code. If you did that first, then there should be no problem with writing the code that mimics the pictures drawn.

    Third, the code you posted has no "cout" statements. It also doesn't show us how you're calling this code, and you don't have a main() function that is testing this code. Just showing us a function doesn't tell us how you're using the function.

    Regards,

    Paul McKenzie

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center