I need some help with this binary search tree. I am having a problem printing out the tree. I don't quite understand how to do it. I know that I need to use recursive call to traverse to the end of the tree but the way the header file is written I can not find any examples any where on the net like the header file. (Header file provided by instructor can not be changed) The instructions say when a 'p' is read in from the file the printforward function is to print out to the terminal the continents of the tree in order.
Can someone please help me?
Also did I set up the insert function correctly?
Here is what I have written so far plus the header and test driver.
#ifndef BSTREE_H
#define BSTREE_H
#include <cstddef>
#include <new>
#include <string>
using namespace std;
class FullBSTree // Exception class
{
};
class EmptyBSTree // Exception class
{
};
class NotFoundBSTree // Exception class
{
};
typedef char SomeType; // Set SomeType as a char
struct BSTreeNode // Node of BSTree
{
SomeType data; // Data stored in node
BSTreeNode* leftPtr; // Pointer to left subtree
BSTreeNode* rightPtr; // Pointer to right subtree
};
class BSTree // BSTree Abstract Data Type
{
private:
BSTreeNode* rootPtr; // Pointer to root of BSTree
public:
BSTree(); // Default constructor
~BSTree(); // Destructor
void InsertItem(SomeType item); // Inserts item into BSTree
void DeleteItem(SomeType item); // Deletes item from BSTree if present
void MakeEmpty(); // Deallocates all BSTree nodes and sets root to NULL
int Size() const; // Returns total number of data values stored
bool IsFull() const; // Returns true if BSTree full, false otherwise
bool IsEmpty() const; // Returns true if BSTree empty, false otherwise
string ForwardPrint() const; // Returns tree items concatenated in order for printing
string ReversePrint() const; // Returns tree items concatenated in reverse order for printing
};
#endif#include "bstree.h"
#include <new>
#include <cstddef>
#include <iostream>
#include <string>
BSTree::BSTree() // Default constructor
{
rootPtr = NULL;
}
BSTree::~BSTree() // Destructor
{
}
void BSTree::InsertItem(SomeType item) // Inserts item into BSTree
{
BSTreeNode* tempPtr, * leftPtr, * rightPtr;
if (rootPtr == NULL)
{
tempPtr = new BSTreeNode;
tempPtr->data = item;
tempPtr->leftPtr = NULL;
tempPtr->rightPtr = NULL;
rootPtr = tempPtr;
}
else if (item < rootPtr->data)
{
tempPtr = new BSTreeNode;
tempPtr->data = item;
leftPtr = tempPtr;
}
else
{
tempPtr = new BSTreeNode;
tempPtr->data = item;
rightPtr = tempPtr;
}
cout << item;
}
void BSTree::DeleteItem(SomeType item) // Deletes item from BSTree if present
{
if (rootPtr == NULL)
throw FullBSTree();
if (item == rootPtr->data)
{
cout << rootPtr->data;
delete rootPtr;
}
}
void BSTree::MakeEmpty() // Deallocates all BSTree nodes and sets root to NULL
{
}
int BSTree::Size() const // Returns total number of data values stored
{
BSTreeNode* tempPtr;
int numberOfNodes = 0;
if(rootPtr == NULL)
return 0;
}
bool BSTree::IsFull() const // Returns true if BSTree full, false otherwise
{
BSTreeNode* fullPtr;
try
{
fullPtr = new BSTreeNode;
delete fullPtr;
return false;
}
catch ( bad_alloc )
{
return true;
}
}
bool BSTree::IsEmpty() const // Returns true if BSTree empty, false otherwise
{
return (rootPtr == NULL);
}
/***************************************************
here is the problem function
***************************************************/
string BSTree::ForwardPrint() const // Returns tree items concatenated in order for printing
{
string inputs;
if ( rootPtr != NULL )
{ // (Otherwise, there's nothing to print.)
// Print the root item.
while (rootPtr->leftPtr != NULL)
{
inputs = rootPtr->leftPtr->data;
ForwardPrint();
return inputs;
}
// Print items in left subtree.
ForwardPrint(); // Print items in right subtree.
}
}
string BSTree::ReversePrint() const // Returns tree items concatenated in reverse order for printing
{
}#include <iostream>
#include <fstream>
#include <string>
#include "bstree.h"
using namespace std;
int main(int argc, char * const argv[])
{
BSTree tree;
char command, letter;
ifstream inputs;
if (argc != 2)
{
cout << "Usage: \n program07 <inputfile>\n";
return 1;
}
inputs.open(argv[1]);
if (!inputs)
{
cout << "Error - unable to open input file";
return 1;
}
inputs >> command;
while(!inputs.eof())
{
switch (command)
{
case 'c':
{
cout << "Constructor()" << endl;
break;
}
case '+':
{
inputs >> letter;
cout <<"+";
tree.InsertItem(letter);
cout << "\n";
break;
}
case '-':
{
try
{
inputs >> letter;
cout << "DeleteItem('" << letter << "')";
tree.DeleteItem(letter);
cout <<"- " << letter << "\n";;
break;
}
catch(FullBSTree)
{
cout << " -- '" << letter << "' not found" << endl;
}
}
case 'p':
{
cout << tree.ForwardPrint();
cout <<"p\n";
break;
}
case 'r':
{
tree.ReversePrint();
cout <<"r\n";
break;
}
case 's':
{
cout << tree.Size() << " ";
cout <<"s\n";
break;
}
case 'm':
{
tree.MakeEmpty();
cout <<"m\n";
break;
}
case 'd':
{
tree.~BSTree();
cout <<"d\n";
break;
}
default:
{
cout << "Command not recognized" << endl;
}
}
inputs >> command;
}
//cout << command;
system("pause");
return 1;
};
