i am trying to make a Binary Search tree and my program is crashing when i try to insert names from a file into the tree and i cant figure out y. my load file function works if i just read in the names of the file then print them but if i try to put them into the tree it crashes. i dont see anything wrong with my insert function in my BST class
Key Class
Code:
#include <iostream>
#include <queue>
#include <fstream>
#include <string>
#include <conio.h>
using namespace std;
// structs/Classes
/*********************************************************************/
struct Key {
char* data; // string
Key();
Key(char* data) { this->data = new char[strlen(data)];
strcpy(this->data,data);}
~Key() {delete data;};
Key(Key& key);
void print();
Key& operator= (Key& key);
bool operator== (Key& key) { return 0 == strcmp(this->data,key.data);} // is this == to that key
bool operator< (Key& key) { return -1 == strcmp(this->data,key.data);}// is this < that key
bool operator> (Key& key) { return 1 == strcmp(this->data,key.data);} // is this > that key
};
Key::Key()
{
data = NULL;
}
Key::Key(Key& key)
{
data = key.data;
}
Key& Key::operator= (Key& key)
{
data = key.data;
return *this;
}
void Key::print()
{
cout << data << endl;
}
/************************************************** *******************/
BST tree class
Code:
class BST_Node {
private:
Key key; // key holds the data
BST_Node* left; // ptr to left subtree
BST_Node* right; // ptr to right subtree
public:
// Managers
BST_Node();
BST_Node(Key key); // Construct given key-data
BST_Node(BST_Node& node); // Copy Constructor
~BST_Node(); // Destruct node
// Operators
BST_Node& operator= (BST_Node& node); // Assignment
// Accessors
Key getKey() {return key;}; // get Key Data
BST_Node* getLeft() {return left;}; // get root of left subtree
BST_Node* getRight() {return right;}; // get root of right subtree
void setLeft(BST_Node* node);
void setRight(BST_Node* node);
};
BST_Node::BST_Node()
{
key.data = NULL;
left = NULL;
right = NULL;
}
BST_Node::BST_Node(Key key)
{
cout << "enter key" << endl;
cin >> key.data;
}
BST_Node::BST_Node(BST_Node& node)
{
right = node.right;
left = node.left;
//key = node.key;
}
BST_Node::~BST_Node()
{
delete left;
delete right;
}
BST_Node& BST_Node::operator= (BST_Node& node)
{
right = node.right;
left = node.left;
//key = node.key;
return *this;
}
void BST_Node::setLeft(BST_Node* node)
{
this->left = node;
}
void BST_Node::setRight(BST_Node* node)
{
this->right = node;
}
/************************************************** *******************/
BST Class
Code:
class BST {
private:
BST_Node* root; // root of tree
int size; // number of elements in tree
string inFileName,
outFileName,
name;
// Mutators - called by public methods
bool insert(BST_Node* subRoot, Key key); // insert to subtree (recursive)
void preOrder(BST_Node* subRoot); // preOrder-Traversal of tree (recursive)
void inOrder(BST_Node* subRoot); // inOrder-Traversal of tree (recursive)
void postOrder(BST_Node* subRoot); // postOrder-Traversal of tree (recursive)
public:
// Managers
BST(); // Construct Empty Tree
BST(BST& bst); // Copy Constructor
~BST(); // Destruct tree
// Operators
BST& operator= (BST& bst); // Assignment
// Accessors
int getSize() {return size;}; // returns number of elements in tree
bool empty(); // is tree empty?
bool full(); // is memory available?
void preOrder(); // preOrder-Traversal of tree (recursive)
void inOrder(); // inOrder-Traversal of tree (recursive)
void postOrder(); // postOrder-Traversal of tree (recursive)
bool findKey(); // take input from user-keyboard
bool findKey(Key key);
void breadthFirst(); // breadth-First-Traversal of tree
bool findKey(Key key, /*BST_Node* parent,*/ BST_Node* foundNode); // given key-data, find node
void loadFile();
void saveFile();
// Mutators
bool insert(); // take input from user-keyboard
bool insert(Key key); // insert key-data into tree
bool delNode(); // take input from user-keyboard
bool delNode(Key key); // delete node containing key-data from tree
ifstream inFile;
ofstream outFile;
};
BST::BST()
{
size = 0;
root = NULL;
}
BST::BST(BST& bst)
{
root = bst.root;
size = bst.size;
}
BST& BST::operator= (BST& bst)
{
root = bst.root;
size = bst.size;
return *this;
}
BST::~BST()
{
delete root->getLeft();
delete root->getRight();
}
bool BST::insert()
{
Key key;
cout << "Enter a key" << endl;
cin >> key.data;
return insert(key);
}
bool BST::insert(BST_Node* subRoot, Key key)
{
BST_Node* node = new BST_Node(key);
if(subRoot == NULL)
{
subRoot = node;
return true;
}
if(key == subRoot->getKey())
{
return false;
delete node;
}
if(key < subRoot->getKey())
{
if(subRoot->getLeft() == NULL)
{
root->setLeft(new BST_Node(key));
return true;
}
else
{
return insert(subRoot->getRight(), key.data);
}
return true;
}
return false;
}
bool BST::empty()
{
return root == NULL;
}
bool BST::full()
{
BST_Node* bstnode = new BST_Node;
if(!bstnode)
{
return true;
}
else
{
delete bstnode;
return false;
}
}
bool BST::insert(Key key)
{
return insert(root, key);
}
bool BST::findKey()
{
Key key;
cout << "What would you like to find" << endl;
cin >> key.data;
return findKey(key);
}
bool BST::findKey(Key key)
{
if(root == NULL)
return false;
return findKey(key, /*root,*/ root);
}
bool BST::findKey(Key key, /*BST_Node* parent,*/ BST_Node* foundNode)
{
if(foundNode == NULL)
return false;
else if(key.data == foundNode->getKey().data)
return true;
else if(key.data < foundNode->getKey().data)
{
return findKey(key, foundNode->getLeft());
}
else if(key.data > foundNode->getKey().data)
{
return findKey(key, foundNode->getRight());
}
else
return false;
}
void BST::inOrder()
{
inOrder(root);
}
void BST::inOrder(BST_Node* subRoot)
{
if(subRoot == NULL)
return;
inOrder(subRoot->getLeft());
subRoot->getKey().print();
inOrder(subRoot->getRight());
}
void BST::preOrder()
{
preOrder(root);
}
void BST::preOrder(BST_Node* subRoot)
{
//base case
if(subRoot == NULL)
return;
//process
subRoot->getKey().print();
//go left
preOrder(subRoot->getLeft());
//go right
preOrder(subRoot->getRight());
}
void BST::postOrder()
{
postOrder(root);
}
void BST::postOrder(BST_Node* subRoot)
{
if (root == NULL)
return;
postOrder(subRoot->getLeft());
postOrder(subRoot->getRight());
subRoot->getKey().print();
}
void BST::breadthFirst()
{
queue <BST_Node*>q;
if (root == NULL)
return;
q.push(root);
while (!q.empty())
{
if(root->getLeft() != NULL)
q.push(root->getLeft());
if(root->getRight() != NULL)
q.push(root->getRight());
q.front()->getKey().print();
q.pop();
}
}
bool BST::delNode()
{
Key key;
cout << "What do you want to delete?" << endl;
cin >> key.data;
return delNode(key);
}
bool BST::delNode(Key key)
{
BST_Node* node = root;
if(findKey(key,root))
{
if(root == NULL)
return false;
if(root->getLeft() == NULL)
{
root = root->getRight();
delete node;
return false;
}
else if(root->getRight() == NULL)
{
root = root->getLeft();
delete node;
return false;
}
else
{
node = root->getLeft();
while(node->getRight() != NULL)
node = node->getRight();
return true;
}
root->getKey() = node->getKey();
delNode(key);
/* else if(key < root->getKey().data)
root = root->getLeft();
if(key == root->getKey())
{
delete key.data;
return true;
}
else if(root->getLeft() == NULL)
{
p = root->getRight();
free(root);
return false;
}
else if(root->getRight() == NULL)
{
p = root->getLeft();
free(root);
return false;
}
else
{
node = root->getRight();
p = root->getRight();
while (p->getLeft())
{
p = p->getLeft();
}
p->setLeft(root->getLeft());
free(root);
return true;
}
if(root->getKey() < key)
{
root->getLeft() = delete key.data;
return true;
}
else
{
root->setRight();
return true;
}*/
}
else
return false;
}
void BST::loadFile()
{
Key key;
cout << "Enter the the file location" << endl;
cin >> inFileName;
inFile.open(inFileName.c_str());
if (!inFile.is_open()) //test for file
{
cerr << "Cannot open file: " << inFileName << endl;
getche();
}
while(!inFile.eof()) //loop through untill end of file
{
inFile >> name;
/*if(key.data == NULL)
return;
else
insert(key);*/
cout << name << endl;
}// end obtain info
inFile.close();//close infile
}
void BST::saveFile()
{
Key key;
cout << "Enter where you want to save the file" << endl;
cin >> outFileName;
outFile.open(outFileName.c_str());
if(!outFile.is_open())
{
cerr << "Cannot open file: " << outFileName << endl;
getche();
}
else
{
outFile << key.data << endl;
}
outFile.close();//close outfile
}
/************************************************** *******************/
Code:
int menu();
void main () {
BST bst;
switch(menu())
{
case 1:
bst.inOrder();
break;
case 2:
bst.preOrder();
break;
case 3:
bst.postOrder();
break;
case 4:
bst.breadthFirst();
break;
case 5:
bst.loadFile();
break;
case 6:
bst.saveFile();
break;
case 7:
bst.insert();
break;
case 8:
//bst.delNode();
break;
case 9:
bst.findKey();
break;
case 10:
break;
default:
break;
}
}
int menu()
{
int choice;
cout << "________________BST________________\n" << endl;
cout << "1) Print In-Order Traversal\n"
<< "2) Print Pre-Order Traversal\n"
<< "3) Print Post-Order Traversal\n"
<< "4) Print Breadth-First Traversal\n"
<< "5) Load BST from file\n"
<< "6) Save BST to file\n"
<< "7) Add to tree\n"
<< "8) Delete from tree\n"
<< "9) Find a value in tree\n"
<< "10) Quit Program" << endl;
cout << "Enter your choice" << endl;
cin >> choice;
return choice;
}