hello all, I am trying to make a menu driven program that uses a while loop and a switch in main. When i choose #1, the code seems to work. However when I type in #2, and enter data, the program goes into an infinite loop, because the menu is printed over and over.....
anyone know what I have done wrong in my code to cause that problem?
Thank!
/********************************************************************************************************
Devang N. Joshi *
CSCI 271 *
Assignment Four *
March 19th, 2011 *
Binary Search Tree *
*
The purpose of this assignment is to create a binary search tree with a menu driven interface *
/*******************************************************************************************************/
#include <iostream> //
#include <iomanip> //
#include <string.h> //
#include <fstream> //
#include <cstdlib> //
using namespace std; //
//
class BinarySearchTree //
{ //
private: //
//
struct tree_node //
{ //
tree_node* left; //
tree_node* right; //
char data; //
//
//
}; //
//
tree_node* root; //
//
public: //
//
BinarySearchTree() //
{ //
root = NULL; //
} //
bool isEmpty() const //
{ //
return root==NULL; //
} //
void print_inorder(); //
void inorder(tree_node*); //
void print_preorder(); //
void preorder(tree_node*); //
void print_postorder(); //
void postorder(tree_node*); //
void insert(char); //
void remove(char); //
void find(char); //
}; //
//
// Smaller elements go left //
// larger elements go right //
void BinarySearchTree::insert(char data) //
{ //
tree_node* t = new tree_node; //
tree_node* parent; //
t->data = data; //
t->left = NULL; //
t->right = NULL; //
parent = NULL; //
//
// is this a new tree? //
if(isEmpty()) //
{ //
root = t; //
} //
else
{
//Note: ALL insertions are as leaf nodes
tree_node* curr;
curr = root;
// Find the Node's parent
while(curr)
{
parent = curr;
if(t->data > curr->data)
{
curr = curr->right;
}
else
{
curr = curr->left;
}
}
if(t->data < parent->data)
{
parent->left = t;
}
else
{
parent->right = t;
}
}
}
void BinarySearchTree::find(char dAta)
{
//Locate the element
bool found = false;
if(isEmpty())
{
cout<<" This Tree is empty! "<<endl;
return;
}
tree_node* curr;
tree_node* parent;
curr = root;
while(curr != NULL)
{
if(curr->data == dAta)
{
found = true;
break;
}
else
{
parent = curr;
if(dAta > curr->data)
{
curr = curr->right;
}
else
{
curr = curr->left;
}
}
}//while
if(!found)
{
cout<<" Data not found! "<<endl;
return;
}
else
{
cout<<curr->data<<endl;
}
}
void BinarySearchTree::remove(char dAta)
{
//Locate the element
bool found = false;
if(isEmpty())
{
cout<<" This Tree is empty! "<<endl;
return;
}
tree_node* curr;
tree_node* parent;
curr = root;
while(curr != NULL)
{
if(curr->data == dAta)
{
found = true;
break;
}
else
{
parent = curr;
if(dAta > curr->data)
{
curr = curr->right;
}
else
{
curr = curr->left;
}
}
}//while
if(!found)
{
cout<<" Data not found! "<<endl;
return;
}
// 3 cases :
// 1. We're removing a leaf node
// 2. We're removing a node with a single child
// 3. we're removing a node with 2 children
// Node with single child
if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL && curr->right == NULL))
{
if(curr->left == NULL && curr->right != NULL)
{
if(parent->left == curr)
{
parent->left = curr->right;
delete curr;
}
else
{
parent->right = curr->right;
delete curr;
}
}
else // left child present, no right child
{
if(parent->left == curr)
{
parent->left = curr->left;
delete curr;
}
else
{
parent->right = curr->left;
delete curr;
}
}
return;
}
//We're looking at a leaf node
if( curr->left == NULL && curr->right == NULL)
{
if(parent->left == curr)
{
parent->left = NULL;
}
else
{
parent->right = NULL;
}
delete curr;
return;
}
//Node with 2 children
// replace node with smallest value in right subtree
if (curr->left != NULL && curr->right != NULL)
{
tree_node* chkr;
chkr = curr->right;
if((chkr->left == NULL) && (chkr->right == NULL))
{
curr = chkr;
delete chkr;
curr->right = NULL;
}
else // right child has children
{
//if the node's right child has a left child
// Move all the way down left to locate smallest element
if((curr->right)->left != NULL)
{
tree_node* lcurr;
tree_node* lcurrp;
lcurrp = curr->right;
lcurr = (curr->right)->left;
while(lcurr->left != NULL)
{
lcurrp = lcurr;
lcurr = lcurr->left;
}
curr->data = lcurr->data;
delete lcurr;
lcurrp->left = NULL;
}
else
{
tree_node* tmp;
tmp = curr->right;
curr->data = tmp->data;
curr->right = tmp->right;
delete tmp;
}
}
return;
}
}
void BinarySearchTree::print_inorder()
{
inorder(root);
}
void BinarySearchTree::inorder(tree_node* p)
{
if(p != NULL)
{
if(p->left)
{
inorder(p->left);
cout<<" "<<p->data<<" ";
}
if(p->right)
{
inorder(p->right);
}
}
else
{
return;
}
}
void BinarySearchTree::print_preorder()
{
preorder(root);
}
void BinarySearchTree::preorder(tree_node* p)
{
if(p != NULL)
{
cout<<" "<<p->data<<" ";
if(p->left)
{
preorder(p->left);
}
if(p->right)
{
preorder(p->right);
}
}
else
{
return;
}
}
void BinarySearchTree::print_postorder()
{
postorder(root);
}
void BinarySearchTree::postorder(tree_node* p)
{
if(p != NULL)
{
if(p->left)
{
postorder(p->left);
}
if(p->right)
{
postorder(p->right);
}
cout<<" "<<p->data<<" ";
}
else
{
return;
}
}
int main() //
{ //
BinarySearchTree b; //
int choice,tmp1; //
char dataFileName[50]; //
char temp; //
fstream Infile; //
//
while(1) //
{ //
cout<<endl<<endl; //
cout<<" DNJ--Assignment Four "<<endl; //
cout<<" ----------------------------- "<<endl; //
cout<<" 1. Insertion From File "<<endl; //
cout<<" 2. Insertion From Keyboard "<<endl; //
cout<<" 3. Find "<<endl; //
cout<<" 4. Delete "<<endl; //
cout<<" 5. Print In-Order "<<endl; //
cout<<" 6. Print Pre-Order "<<endl; //
cout<<" 7. Print Post-Order "<<endl; //
cout<<" 8. Exit "<<endl; //
cout<<" Enter your choice : "; //
cin>>choice; //
//
switch(choice) //
{ //
case 1 : //
system("clear"); //
cout<<" Inserting Data From File : "; //
cout<<endl<<endl; //
cout<<" Enter the name of the datafile : "; //
cout<<endl; //
cin>>dataFileName; //
Infile.open(dataFileName,ios::in); //
if(!Infile) //
{ //
cerr<<"Error opening file!"<<endl; //
} //
else //
{ //
Infile>>temp; //
while(!Infile.eof()) //
{ //
b.insert(temp); //
Infile>>temp; //
}
cout<<"Load Successful!"<<endl;
}
//
break; //
//
//
case 2 : //
system("clear"); //
cout<<" Inserting Data From Keyboard : "; //
cout<<endl<<endl; //
cout<<" Enter the data : "; //
cout<<endl; //
cin>>temp; //
b.insert(temp);
//
break; //
//
case 3 : //
system("clear"); //
cout<<endl; //
cout<<" Find Data "<<endl; //
cout<<" -------------------"<<endl; //
b.find(temp);
//
break; //
//
case 4 : //
system("clear"); //
cout<<endl; //
cout<<" Delete Data "<<endl; //
cout<<" --------------------"<<endl; //
cin>>temp; //
b.remove(temp);
//
break; //
//
case 5 : //
system("clear"); //
cout<<" Printing - In-Order : "; //
b.print_inorder();
//
break; //
//
case 6 : //
system("clear"); //
cout<<" Printing - Pre-Order :"; //
b.print_preorder();
//
break; //
//
case 7 : //
system("clear"); //
cout<<" Printing - Post-Order :"; //
b.print_postorder();
//
break; //
//
case 8 : //
//
return 0; //
//
} //
} //
} //
/*******************************************************************************************************/