0

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;
};
3
Contributors
2
Replies
3
Views
9 Years
Discussion Span
Last Post by Sci@phy
0

Assuming that print forward is to print the data in ascending order all you have to do is inorder traversal
which should be something like this

void inorder(tree_ptr)
{
  if  ( tree_ptr -> left )
     inorder( tree_ptr->left);
//  print the value stored in this node
  if (   tree_ptr -> right )
     inorder( tree_ptr->right);
}

And reverse print is the opposite of the above algorithm. go right then left. Google inorder traversal for explanation.

And inserting a node in the tree is not that simple as you have wrote. google it

0

Also, when working with classes that allocate memory dynamically, you HAVE to write destructor that will free all allocated memory!

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.