-
November 19th, 2013, 12:32 AM
#1
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
-
November 19th, 2013, 05:40 AM
#2
Re: Binary Search tree
Originally Posted by talhakhan797
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
-
November 19th, 2013, 06:47 AM
#3
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)
-
November 19th, 2013, 11:19 PM
#4
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;
}
}
}
}
-
November 20th, 2013, 05:26 AM
#5
Re: Binary Search tree
Originally Posted by talhakhan797
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|