Ok so i have 2 programs due in 2 hours
I have everything working, or so i believe except throwing exceptions. I have no idea how to go about this and can not find anything useful. My teacher is long gone to bed lol so im in trouble
Anyone who could enlighten me on this would be a savior thank you. I understand what they need to do. Throwing and catching per-say. im just not sure on the actual code.
Here is the main program he provided. I realize this is long but I'm just flabbergausted on what to do
Code:
/* To compile this program, do the following
aCC olab10BSTreeMain.cpp BSTree.cpp
To execute with test data file
a.out < /nfshome/csal/public_html/spring.10/2170/olab10sp10.dat
uses exceptions
As always let me know if there are syntax errors in program
*/
#include <iostream>
#include "BSTree.h"
using namespace std;
int main()
{
BSTree MyTree; // A binary search tree used in examples
// See what happens when an empty tree is printed
cout << "An empty tree:" << MyTree << "*" << endl;
cout << "Count: " << MyTree.Count() << endl;
try
{
cout << "First String: " << MyTree.First() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
try
{
cout << "Last String: " << MyTree.Last() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
cin >> MyTree; // read's into
cout << "Tree after first read: " << MyTree << endl;;
cout << "Count: " << MyTree.Count() << endl;
try
{
cout << "First String: " << MyTree.First() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
try
{
cout << "Last String: " << MyTree.Last() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
MyTree.Insert("into"); // insert new root
cout << "Tree after insert: " << MyTree << endl;;
cin >> MyTree; // read's insert
cout << "Tree after second read: " << MyTree << endl; // This does inorder traversal
cout << "Count: " << MyTree.Count() << endl;
try
{
cout << "First String: " << MyTree.First() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
try
{
cout << "Last String: " << MyTree.Last() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
cin >> MyTree; // read's into
cin >> MyTree; // read's link
cin >> MyTree; // read's list
cout << "Tree after read: " << MyTree << endl; // This does inorder traversal
cout << "Count: " << MyTree.Count() << endl;
try
{
cout << "First String: " << MyTree.First() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
try
{
cout << "Last String: " << MyTree.Last() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
cin >> MyTree; // read one string into the tree
cout << "Tree after read: " << MyTree << endl; // This does inorder traversal
cout << "Count: " << MyTree.Count() << endl;
try
{
cout << "First String: " << MyTree.First() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
try
{
cout << "Last String: " << MyTree.Last() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
cin >> MyTree; // read's next
cin >> MyTree; // read's last
cout << "Tree after read: " << MyTree << endl; // This does inorder traversal
cout << "Count: " << MyTree.Count() << endl;
try
{
cout << "First String: " << MyTree.First() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
try
{
cout << "Last String: " << MyTree.Last() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
cout << "Inorder traversal: " << endl;
MyTree.InOrderTraversal();
cout << endl;
cout << "Preorder traversal: " << endl;
MyTree.PreOrderTraversal();
cout << endl;
cout << "Postorder traversal: " << endl;
MyTree.PostOrderTraversal();
cout << endl;
cin >> MyTree; // read's link
cin >> MyTree; // read's insurance
cout << "Tree after read: " << MyTree << endl; // This does inorder traversal
cout << "Count: " << MyTree.Count() << endl;
try
{
cout << "First String: " << MyTree.First() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
try
{
cout << "Last String: " << MyTree.Last() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
cout << "Inorder traversal: " << endl;
MyTree.InOrderTraversal();
cout << endl;
cout << "Preorder traversal: " << endl;
MyTree.PreOrderTraversal();
cout << endl;
cout << "Postorder traversal: " << endl;
MyTree.PostOrderTraversal();
cout << endl;
cin >> MyTree; // read's help
cin >> MyTree; // read's insert
cout << "Tree after read: " << MyTree << endl; // This does inorder traversal
cout << "Count: " << MyTree.Count() << endl;
try
{
cout << "First String: " << MyTree.First() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
try
{
cout << "Last String: " << MyTree.Last() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
cout << "Inorder traversal: " << endl;
MyTree.InOrderTraversal();
cout << endl;
cout << "Preorder traversal: " << endl;
MyTree.PreOrderTraversal();
cout << endl;
cout << "Postorder traversal: " << endl;
MyTree.PostOrderTraversal();
cout << endl;
cout << "Count: " << MyTree.Count() << endl;
try
{
cout << "First String: " << MyTree.First() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
try
{
cout << "Last String: " << MyTree.Last() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
cout << "Inorder traversal: " << endl;
MyTree.InOrderTraversal();
cout << endl;
cout << "Preorder traversal: " << endl;
MyTree.PreOrderTraversal();
cout << endl;
cout << "Postorder traversal: " << endl;
MyTree.PostOrderTraversal();
cout << endl;
cin >> MyTree; // read's justice
cout << "Tree after read: " << MyTree << endl; // This does inorder traversal
cout << "Count: " << MyTree.Count() << endl;
try
{
cout << "First String: " << MyTree.First() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
try
{
cout << "Last String: " << MyTree.Last() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
cout << "Inorder traversal: " << endl;
MyTree.InOrderTraversal();
cout << endl;
cout << "Preorder traversal: " << endl;
MyTree.PreOrderTraversal();
cout << endl;
cout << "Postorder traversal: " << endl;
MyTree.PostOrderTraversal();
cout << endl;
cin >> MyTree; // read's just
cout << "Tree after read: " << MyTree << endl; // This does inorder traversal
cout << "Count: " << MyTree.Count() << endl;
try
{
cout << "First String: " << MyTree.First() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
try
{
cout << "Last String: " << MyTree.Last() << endl;
}
catch (NonExistent myexception)
{
cerr << "There are data itemd in the tree" << endl;
}
cout << "Inorder traversal: " << endl;
MyTree.InOrderTraversal();
cout << endl;
cout << "Preorder traversal: " << endl;
MyTree.PreOrderTraversal();
cout << endl;
cout << "Postorder traversal: " << endl;
MyTree.PostOrderTraversal();
cout << endl;
// test copy constructor
BSTree CopyTree(MyTree);
cout << "Copy Tree: " << CopyTree << endl;;
cout << "end of main"<<endl;
return 0;
}
and here is the code im working on
Code:
#include <string>
using namespace std;
// THIS IS WHERE IM HAVING TROUBLE
class myexception
{
public:
void NonExistent();
};
struct node
{
string data;
node *left;
node *right;
};
class BSTree
{
public:
//Define deconstructor
~BSTree();
void DestroyTree();
void Insert(string);
void Delete(string);
void InOrderTraversal();
void PreOrderTraversal();
void PostOrderTraversal();
int Count();
string First();
string Last();
private:
void DestroyTree(node *current);
void InOrderTraversal(node *current);
void PreOrderTraversal(node *current);
void PostOrderTraversal(node *current);
int Count(node *current);
string First(node *current);
string Last(node *current);
node *root;
};
void myexception::NonExistent()
{
cerr << "Error";
}
BSTree::~BSTree()
{
DestroyTree();
}
void BSTree::DestroyTree()
{
DestroyTree(root);
}
void BSTree::DestroyTree(node *current)
{
if (current != NULL)
{
DestroyTree(current->left);
DestroyTree(current->right);
delete current;
}
}
void BSTree::Insert(string data)
{
node *current = new node;
node *parent = new node;
current = root;
parent = NULL;
while (current != NULL)
{
parent = current;
if (data < current->data)
{
current = current->left;
}
else
{
current = current->right;
}
}
if (parent == NULL)
{
root->data = data;
}
else if (data < parent->data)
{
parent->left->data = data;
}
else
{
parent->right->data = data;
}
}
//In order public and private functions
void BSTree::InOrderTraversal()
{
if (root == NULL)
{
return;
}
else
{
InOrderTraversal(root);
}
}
void InOrderTraversal(node *current)
{
if (current == NULL)
{
return;
}
else
{
InOrderTraversal(current->left);
cout << current->data;
InOrderTraversal(current->right);
}
}
//Post order public and private functions
void BSTree::PostOrderTraversal()
{
if (root == NULL)
{
return;
}
else
{
PostOrderTraversal(root);
}
}
void PostOrderTraversal(node *current)
{
if (current == NULL)
{
return;
}
else
{
PostOrderTraversal(current->left);
PostOrderTraversal(current->right);
cout << current->data;
}
}
//Pre order public and private functions
void BSTree::PreOrderTraversal()
{
if (root == NULL)
{
return;
}
else
{
PreOrderTraversal(root);
}
}
void PreOrderTraversal(node *current)
{
if (current == NULL)
{
return;
}
else
{
cout << current->data;
PreOrderTraversal(current->left);
PreOrderTraversal(current->right);
}
}
//Count functions
int BSTree::Count()
{
if (root == NULL)
{
return 0;
}
else
{
Count(root);
}
}
int Count(node *current)
{
if (current == NULL)
{
return 0;
}
else
{
int count = 1;
count += Count(current->left);
count += Count(current->right);
return count;
}
}
//Print first functions
string BSTree::First()
{
if (root == NULL)
{
return 0;
//throw NonExistent();
}
else
{
First(root);
}
}
//Print second functions
string First(node *current)
{
if (current->left == NULL)
{
cout << current->left->data;
}
else
{
First(current->left);
}
}
string BSTree::Last()
{
if (root = NULL)
{
return 0;
//throw NonExistent();
}
else
{
Last(root);
}
}
string Last(node *current)
{
if (current->right == NULL)
{
cout << current->right->data;
}
else
{
First(current->right);
}
}
void BSTree::Delete(string data)
{
bool found = false;
if (root == NULL)
{
//exception
}
node *current = new node;
node *parent = new node;
current = root;
while(current)
{
if(current->data == data)
{
found = true;
break;
}
else
{
parent = current;
if(current->data ==data)
{
current = current->right;
}
else
{
current = current->left;
}
}
}
if(!found)
{
//exception
}
// 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((current->left == NULL && current->right != NULL) || (current->left != NULL && current->right == NULL))
{
if(current->left == NULL && current->right != NULL)
{
if(parent->left == current)
{
parent->left = current->right;
delete current;
}
else
{
parent->right = current->right;
delete current;
}
}
else // left child present, no right child
{
if(parent->left == current)
{
parent->left = current->left;
delete current;
}
else
{
parent->right = current->left;
delete current;
}
}
return;
}
//We're looking at a leaf node
if( current->left == NULL && current->right == NULL)
{
if(parent->left == current)
{
parent->left = NULL;
}
else
{
parent->right = NULL;
}
delete current;
return;
}
//Node with 2 children
// replace node with smallest value in right subtree
if (current->left != NULL && current->right != NULL)
{
node *chkr = new node;
chkr = current->right;
if((chkr->left == NULL) && (chkr->right == NULL))
{
current = chkr;
delete chkr;
current->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((current->right)->left != NULL)
{
node *lcurr = new node;
node *lcurrp = new node;
lcurrp = current->right;
lcurr = (current->right)->left;
while(lcurr->left != NULL)
{
lcurrp = lcurr;
lcurr = lcurr->left;
}
current->data = lcurr->data;
delete lcurr;
lcurrp->left = NULL;
}
else
{
node *tmp = new node;
tmp = current->right;
current->data = tmp->data;
current->right = tmp->right;
delete tmp;
}
}
return;
}
}