CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5
  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,449

    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
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    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. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  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,449

    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
  •  





Click Here to Expand Forum to Full Width

Featured