|
I am writing a simple binary search tree (nodes are int nodes) with a BSTNode class and a BST class. I have followed the instructions from my C++ book, and now I am trying to get a remove method working. But before I get to the remove, I need to get my find method working. Basically, I am trying to get a "find" method working that will search for a giving int value, and return the node with that value. I have designed my current find with the help of my book, but for some off reason, when I run my program and try to find the values I do, it returns "10" (the root) everytime, and will not complete when I try to find a number thats not in the tree. Any help would be great! -
#include <iostream>
-
using std::cout;
-
using std::endl;
-
-
class BSTNode
-
{
-
friend class BST;
-
public:
-
BSTNode(int);
-
int getValue();
-
void print();
-
-
private:
-
int value;
-
BSTNode *leftPtr;
-
BSTNode *rightPtr;
-
};
-
-
class BST
-
{
-
public:
-
BST();
-
void insertNode(const int &);
-
BSTNode find(const int);
-
-
private:
-
BSTNode *rootPtr;
-
-
void insertNodeHelper(BSTNode**, const int &);
-
BSTNode findHelper(BSTNode**, const int);
-
};
-
-
/****
-
MAIN
-
*****/
-
int main(void)
-
{
-
cout << "TESTING MY BSTNode CLASS:" << endl
-
<< "creating nodes with values 3, 4, and 5" << endl << endl;
-
BSTNode node1 = BSTNode(3);
-
cout << "node1 has value of: " << node1.getValue() << endl;
-
BSTNode node2 = BSTNode(4);
-
cout << "node2 has value of: " << node2.getValue() << endl;
-
BSTNode node3 = BSTNode(5);
-
cout << "node3 has value of: " << node3.getValue() << endl;
-
-
cout << endl << "Using the print method, the values are:" << endl;
-
node1.print();
-
node2.print();
-
node3.print();
-
-
cout << endl << endl << "TESTING MY BST CLASS:" << endl
-
<< "adding 10, 5, 15, 20, 8, and 10 to the tree" << endl;
-
//Binary Search Tree
-
BST tree = BST();
-
tree.insertNode(10);
-
tree.insertNode(5);
-
tree.insertNode(15);
-
tree.insertNode(20);
-
tree.insertNode(8);
-
tree.insertNode(10);
-
-
cout << endl << "testing the find method" << endl;
-
cout << tree.find(10).getValue() << " ";
-
tree.find(5).print();
-
tree.find(15).print();
-
tree.find(20).print();
-
-
return 0;
-
}
-
-
/***************
-
BSTNode Methods
-
****************/
-
-
//CONSTRUCTOR
-
BSTNode::BSTNode(int d)
-
: value(d),
-
leftPtr(NULL),
-
rightPtr(NULL)
-
{}
-
-
//METHODS
-
int BSTNode::getValue()
-
{return value;}
-
void BSTNode::print()
-
{cout << value << " ";}
-
-
/***********
-
BST Methods
-
************/
-
-
//CONSTRUCTOR
-
BST::BST()
-
{rootPtr = NULL;}
-
-
//INSERT METHOD
-
void BST::insertNode(const int &value)
-
{insertNodeHelper(&rootPtr, value);}
-
void BST::insertNodeHelper(BSTNode **ptr, const int &value)
-
{
-
if (*ptr == NULL)
-
*ptr = new BSTNode(value);
-
else
-
{
-
if (value < (*ptr)->value)
-
insertNodeHelper(&((*ptr)->leftPtr), value);
-
else
-
{
-
-
if (value > (*ptr)->value)
-
insertNodeHelper(&((*ptr)->rightPtr), value);
-
else //SKIPS DUPLICATE NUMBERS
-
cout << " " << value << " already exists in the tree... no duplicates will be added" << endl;
-
}
-
}
-
}
-
-
//FIND METHOD FOR USE WITH REMOVE
-
BSTNode BST::find(const int value)
-
{return findHelper(&rootPtr, value);}
-
BSTNode BST::findHelper(BSTNode **ptr, const int value)
-
{
-
if (value == (*ptr)->value)
-
return **ptr;
-
else
-
{
-
if ((*ptr)->value > value)
-
findHelper(&((*ptr)->leftPtr), value);
-
-
else
-
{
-
if ((*ptr)->value < value)
-
findHelper(&((*ptr)->rightPtr), value);
-
-
else
-
{cout << "node not found"; return BSTNode(-1);}
-
}
-
}
-
}
-
| |
Share:
Expert 2GB |
Try using (*ptr)->getValue() rather than (*ptr)->value. I suspect this is messing things up.
| | |
Try using (*ptr)->getValue() rather than (*ptr)->value. I suspect this is messing things up.
that is a very great idea, however it did not change the output. Any other suggestions?
| | Expert 2GB |
Ah-hah!
In your first condition, if the value you're searching for is the root's value, then you return the root. But look at your next two conditions. If the value is less, then you call findHelper again - but you don't return the value! The only case where you return something is if the root is the search value or if the search value doesn't exist in the tree. Change these findHelper calls to return findHelper and see if it works.
| | |
Ah-hah!
In your first condition, if the value you're searching for is the root's value, then you return the root. But look at your next two conditions. If the value is less, then you call findHelper again - but you don't return the value! The only case where you return something is if the root is the search value or if the search value doesn't exist in the tree. Change these findHelper calls to return findHelper and see if it works.
HAHA, yeah i actually JUST noticed this right before I read this comment. Dumbest mistake ever lol. But I did this, the find works great... EXCEPT when the value i search for is not found... The problem now seems in returning a NULL pointer im guessing, perhaps I'm making another stupid mistake. I have changed my entire code to as follows: -
#include <iostream>
-
using std::cout;
-
using std::endl;
-
-
class BSTNode
-
{
-
friend class BST;
-
public:
-
BSTNode(int);
-
int getValue();
-
void print();
-
-
private:
-
int value;
-
BSTNode *leftPtr;
-
BSTNode *rightPtr;
-
};
-
-
class BST
-
{
-
public:
-
BST();
-
void insertNode(const int &);
-
BSTNode* find(const int &);
-
-
private:
-
BSTNode *rootPtr;
-
-
void insertNodeHelper(BSTNode**, const int &);
-
BSTNode* findHelper(BSTNode*, const int &);
-
};
-
-
/****
-
MAIN
-
*****/
-
int main(void)
-
{
-
cout << "TESTING MY BSTNode CLASS:" << endl
-
<< "creating nodes with values 3, 4, and 5" << endl << endl;
-
BSTNode node1 = BSTNode(3);
-
cout << "node1 has value of: " << node1.getValue() << endl;
-
BSTNode node2 = BSTNode(4);
-
cout << "node2 has value of: " << node2.getValue() << endl;
-
BSTNode node3 = BSTNode(5);
-
cout << "node3 has value of: " << node3.getValue() << endl;
-
-
cout << endl << "Using the print method, the values are:" << endl;
-
node1.print();
-
node2.print();
-
node3.print();
-
-
cout << endl << endl << "TESTING MY BST CLASS:" << endl
-
<< "adding 3, 2, 5, 1, 4, 6, and 4 to the tree" << endl;
-
//Binary Search Tree
-
BST tree = BST();
-
tree.insertNode(3);
-
tree.insertNode(2);
-
tree.insertNode(5);
-
tree.insertNode(1);
-
tree.insertNode(4);
-
tree.insertNode(6);
-
tree.insertNode(4);
-
-
cout << endl << "testing the find method" << endl;
-
for(int i = 1; i <= 6; i++)
-
{
-
if(tree.find(i) == NULL)
-
cout << i << " was not found!" << endl;
-
else
-
(tree.find(i))->print();
-
}
-
-
return 0;
-
}
-
-
/***************
-
BSTNode Methods
-
****************/
-
-
//CONSTRUCTOR
-
BSTNode::BSTNode(int d)
-
: value(d),
-
leftPtr(NULL),
-
rightPtr(NULL)
-
{}
-
-
//METHODS
-
int BSTNode::getValue()
-
{return value;}
-
void BSTNode::print()
-
{cout << value << " ";}
-
-
/***********
-
BST Methods
-
************/
-
-
//CONSTRUCTOR
-
BST::BST()
-
{rootPtr = NULL;}
-
-
//INSERT METHOD
-
void BST::insertNode(const int &value)
-
{insertNodeHelper(&rootPtr, value);}
-
void BST::insertNodeHelper(BSTNode **ptr, const int &value)
-
{
-
if (*ptr == NULL)
-
*ptr = new BSTNode(value);
-
else
-
{
-
if (value < (*ptr)->getValue())
-
insertNodeHelper(&((*ptr)->leftPtr), value);
-
else
-
{
-
-
if (value > (*ptr)->getValue())
-
insertNodeHelper(&((*ptr)->rightPtr), value);
-
else //SKIPS DUPLICATE NUMBERS
-
cout << " " << value << " already exists in the tree... no duplicates will be added" << endl;
-
}
-
}
-
}
-
-
//BEGINNING OF REMOVE
-
//FIND METHOD FOR USE WITH REMOVE
-
BSTNode* BST::find(const int &value)
-
{return findHelper(rootPtr, value);}
-
BSTNode* BST::findHelper(BSTNode *ptr, const int &value)
-
{
-
while (ptr!=NULL || (ptr)->getValue() == value)
-
{
-
if ((ptr)->getValue() > value)
-
ptr = (ptr)->leftPtr;
-
else if ((ptr)->getValue() < value)
-
ptr = (ptr)->rightPtr;
-
else if ((ptr)->getValue() == value)
-
break;
-
}
-
-
if (!ptr)
-
return NULL;
-
else
-
return ptr;
-
}
-
| | |
nevermind!!!! I figured it out, thanks so much for you help though..
instead of checking -
if(!tree.find(value))
-
{
-
not found code
-
}
-
else
-
{
-
found code
-
}
-
i needed to do it this way -
if(tree.find(value))
-
{
-
found code
-
}
-
else
-
{
-
not found code
-
}
-
| | Post your reply Sign in to post your reply or Sign up for a free account.
Similar topics
8 posts
views
Thread by Jerry Khoo |
last post: by
|
11 posts
views
Thread by jova |
last post: by
|
reply
views
Thread by j |
last post: by
|
4 posts
views
Thread by Tarique Jawed |
last post: by
|
15 posts
views
Thread by Foodbank |
last post: by
|
1 post
views
Thread by hn.ft.pris@gmail.com |
last post: by
|
4 posts
views
Thread by whitehatmiracle@gmail.com |
last post: by
|
11 posts
views
Thread by Defected |
last post: by
|
7 posts
views
Thread by Vinodh |
last post: by
| | | | | | | | | | |