Nov 2, 2014 at 3:56pm UTC
Once I create my binary search tree, there's a find function to find any number in the tree. However, When searching for a particular number, the program kicks back a large number. Here's the code:
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
struct node
{
int info;
struct node *left;
struct node *right;
}*root;
class BST
{
public:
void find(int, node *, node *);
void insert(node *, node *);
void del(int);
void case_a(node *,node *);
void case_b(node *,node *);
void case_c(node *,node *);
void preorder(node *);
void inorder(node *);
void postorder(node *);
void display(node *, int);
BST()
{
root = NULL;
}
};
# include "TRP Class.h"
# include <cstdlib>
using namespace std;
void BST::find(int item, node *loc, node *par)
{
node *ptr, *ptrsave;
if (root == NULL)
{
par = NULL;
loc = NULL;
cout<<item<<" is not found."<<endl;
return;
}
if (item == root->info)
{
loc = root;
par = NULL;
cout<<item<<" is found."<<endl;
return;
}
if (item < root->info)
ptr = root->left;
else
ptr = root->right;
ptrsave = root;
cout<<item<<" is not found."<<endl;
while (ptr != NULL)
{
if (item == ptr->info)
{
loc = ptr;
par = ptrsave;
cout<<item<<" is found."<<endl;
return;
}
ptrsave = ptr;
if (item < ptr->info)
ptr = ptr->left;
else
ptr = ptr->right;
//cout<<item<<" is not found."<<endl;
}
loc = NULL;
par = ptrsave;
}
// Inserting Element
void BST::insert(node *tree, node *newnode)
{
if (root == NULL)
{
root = new node;
root->info = newnode->info;
root->left = NULL;
root->right = NULL;
cout<<"Root Node is Added."<<endl;
return;
}
if (tree->info == newnode->info)
{
cout<<"It's already there, try again."<<endl;
return;
}
if (tree->info > newnode->info)
{
if (tree->left != NULL)
{
insert(tree->left, newnode);
}
else
{
tree->left = newnode;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
cout<<"Node Added To Left."<<endl;
return;
}
}
else
{
if (tree->right != NULL)
{
insert(tree->right, newnode);
}
else
{
tree->right = newnode;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
cout<<"Node Added To Right."<<endl;
return;
}
}
}
//Delete Element
void BST::del(int item)
{
node *parent, *location;
if (root == NULL)
{
cout<<"Tree empty."<<endl;
return;
}
find(item, parent, location);
if (location == NULL)
{
cout<<"Item not present in tree."<<endl;
return;
}
if (location->left == NULL && location->right == NULL)
case_a(parent, location);
if (location->left != NULL && location->right == NULL)
case_b(parent, location);
if (location->left == NULL && location->right != NULL)
case_b(parent, location);
if (location->left != NULL && location->right != NULL)
case_c(parent, location);
free(location);
}
// Case A
void BST::case_a(node *par, node *loc )
{
if (par == NULL)
{
root = NULL;
}
else
{
if (loc == par->left)
par->left = NULL;
else
par->right = NULL;
}
}
// Case B
void BST::case_b(node *par, node *loc)
{
node *child;
if (loc->left != NULL)
child = loc->left;
else
child = loc->right;
if (par == NULL)
{
root = child;
}
else
{
if (loc == par->left)
par->left = child;
else
par->right = child;
}
}
// Case C
void BST::case_c(node *par, node *loc)
{
node *ptr, *ptrsave, *suc, *parsuc;
ptrsave = loc;
ptr = loc->right;
while (ptr->left != NULL)
{
ptrsave = ptr;
ptr = ptr->left;
}
suc = ptr;
parsuc = ptrsave;
if (suc->left == NULL && suc->right == NULL)
case_a(parsuc, suc);
else
case_b(parsuc, suc);
if (par == NULL)
{
root = suc;
}
else
{
if (loc == par->left)
par->left = suc;
else
par->right = suc;
}
suc->left = loc->left;
suc->right = loc->right;
}
//Preorder
void BST::preorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty."<<endl;
return;
}
if (ptr != NULL)
{
cout<<ptr->info<<" ";
preorder(ptr->left);
preorder(ptr->right);
}
}
// Inorder Traversal
void BST::inorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty."<<endl;
return;
}
if (ptr != NULL)
{
inorder(ptr->left);
cout<<ptr->info<<" ";
inorder(ptr->right);
}
}
// Display
void BST::display(node *ptr, int level)
{
int i;
if (ptr != NULL)
{
display(ptr->right, level+1);
cout<<endl;
if (ptr == root)
cout<<"Root->: ";
else
{
for (i = 0;i < level;i++)
cout<<" ";
}
cout<<ptr->info;
display(ptr->left, level+1);
}
}
# include <iostream>
# include "TRP Class2.h"
# include <cstdlib>
using namespace std;
int main()
{
int choice, num;
BST bst;
node *temp, *find;
while (1)
{
cout<<endl;
cout<<"Binary Search Tree"<<endl;
cout<<endl;
cout<<"1. Display"<<endl;
cout<<"2. iNnsert"<<endl;
cout<<"3. Find"<<endl;
cout<<"4. Delete"<<endl;
cout<<"5. Inorder"<<endl;
cout<<"6. Preorder"<<endl;
cout<<"7. Quit"<<endl;
cout<<"Enter your choice : ";
cin>>choice;
cout<<endl;
switch(choice)
{
case 1:
cout<<endl;
cout<<"Display BST:"<<endl;
bst.display(root,1);
cout<<endl;
break;
case 2:
cout<<endl;
temp = new node;
cout<<"Enter the number.";
cin>>temp->info;
bst.insert(root, temp);
break;
case 3:
cout<<endl;
temp = new node;
cout<<"Which number?";
cin>>num;
num = temp->info;
bst.find(num, root, temp);
break;
case 4:
cout<<endl;
if (root == NULL)
{
cout<<"Tree is empty. Try again."<<endl;
continue;
}
cout<<"Which one?";
cin>>num;
bst.del(num);
break;
case 5:
cout<<endl;
cout<<"Inorder:"<<endl;
bst.inorder(root);
cout<<endl;
break;
case 6:
cout<<endl;
cout<<"Preorder:"<<endl;
bst.preorder(root);
cout<<endl;
break;
case 7:
exit(1);
default:
cout<<endl;
cout<<"No. Try again."<<endl;
}
}
}
I would insert the number, then try to find the same number. The number it would kick back is a giant one. For example, I would enter 5, then it would kick back "6497696 is not found." Am I pointing to the wrong node?