Hi,
My program is supposed to implement a binary tree with an insert, remove, copy, pre-order, post-order and in-order functions.
Problem is that my code compiles but doesn't work correctly. When I try to insert more than one node/child node the program crashes/freezes. Could someone help me out.
Thanks.
header file: brownt7.h
#ifndef _BROWNT7_H
#define _BROWNT7_H
#include <iostream>
typedef signed int ElementF10;
struct BSTNode;
typedef BSTNode *BSTPtr;
struct BSTNode
{
ElementF10 element;//holds the value to be added
BSTPtr left;
BSTPtr right;
};
//defining class with name QueueF10
class BSTF10 {
public:
BSTF10( );
BSTF10( const BSTF10 & );
~BSTF10( );
void insertBSTNode(const ElementF10);
void removeBSTNode(const ElementF10);
BSTPtr searchBST( const ElementF10 ) const;
void preOrderBST( ) const;
void inOrderBST( ) const;
void postOrderBST( ) const;
private:
BSTPtr rootBST;
void initializeBST( BSTPtr & );
bool isEmptyBST( const BSTPtr ) const;
void copyBST( const BSTPtr );
void destroyBST( BSTPtr & );
void insertBSTNode( const ElementF10, BSTPtr & );
void removeBSTNode( const ElementF10, BSTPtr & );
void deleteBSTNode( const ElementF10, BSTPtr & );
void findMinBSTNode( BSTPtr &, BSTPtr & );
BSTPtr searchBST( const ElementF10, const BSTPtr ) const;
void preOrderBST( const BSTPtr ) const;
void inOrderBST( const BSTPtr ) const;
void postOrderBST( const BSTPtr ) const;
};
#endif
Implementation file: brownt7.cpp
#include "brownt7.h"
#include <iostream>
#include <iomanip>
#include <cstdlib>
using namespace std;
typedef bool BoolF10;
BSTF10 queue;
int menu()
{
system("clear");
cout << "__________________________________________________________________________\n";
cout << "What do you want to do?\n";
cout << "__________________________________________________________________________\n";
cout << " 1. Insert a new element\n";
cout << " 2. Remove an element\n";
cout << " 3. Display the BST tree from top to bottom\n";
cout << " 4. Display the BST tree in ascending order\n";
cout << " 5. Display the BST tree from bottom to top\n";
cout << " 6. Copy the BST tree from one to another\n";
cout << " 7. Exit\n";
cout << "__________________________________________________________________________\n";
cout << " \n\nYour choice: ";
int option;
cin >> option;
while (option < 1 || option > 7)
{
cout << "\a\nYou entered an invalid choice. \nEnter a number from 1 to 6.\n";
cin >> option;
}
return option;
}
BSTF10::BSTF10()//: queueArray(NULL), QUEUE_CAPACITY(5)//constructor
{
initializeBST(rootBST);
}
BSTF10::BSTF10( const BSTF10 & old )//copy constructor
{
BSTF10 current;
current.copyBST(rootBST);
}
void BSTF10::insertBSTNode(const ElementF10 num)
{
insertBSTNode(num, rootBST);
}
void BSTF10::insertBSTNode(const ElementF10 number, BSTPtr &holdNode)
{
if (isEmptyBST(holdNode)){
BSTPtr node = new(nothrow) BSTNode;
if(node != NULL)
{
node->element = number;
holdNode = node;
}
}
else if (number < holdNode->element)
insertBSTNode(number, holdNode->left);
else
insertBSTNode(number, holdNode->right);
}
BSTPtr BSTF10::searchBST(const ElementF10 holdNum) const
{
searchBST(holdNum, rootBST);
}
BSTPtr BSTF10::searchBST(const ElementF10 theNumber, BSTPtr holdTree) const
{
BSTPtr node = rootBST;
if(isEmptyBST(holdTree)){
return holdTree;
}
BSTNode *nodePtr = rootBST;
while (nodePtr)
{
if (nodePtr->element == theNumber)
return holdTree;
else if (theNumber < nodePtr->element)
nodePtr = nodePtr->left;
else
nodePtr = nodePtr->right;
}
return holdTree;
}
void BSTF10::removeBSTNode(const ElementF10 number)
{
BSTNode *nnode;
nnode = new BSTNode;
removeBSTNode(number, nnode);
}
void BSTF10::removeBSTNode(const ElementF10 hNum, BSTPtr &hNode)
{
if(isEmptyBST(hNode)){
cout << endl << "The Binary Tree is empty" << endl;
cout << "Press enter to continue" << endl;
cin.get();
}
else
{
if (hNode->element == hNum)
deleteBSTNode(hNum, hNode);
else if (hNum < hNode->element)
hNode = hNode->left;
else
hNode = hNode->right;
}
}
void BSTF10::preOrderBST() const
{
BSTNode *nNode;
nNode = new BSTNode;
cout << endl << "START" << endl;
preOrderBST(nNode);
cout << "FINISH" << endl;
}
void BSTF10::preOrderBST( const BSTPtr holdPtr ) const
{
if(holdPtr != NULL)
{
cout << holdPtr->element << " -> ";
if(holdPtr->left)
preOrderBST(holdPtr->left);
if(holdPtr->right)
preOrderBST(holdPtr->right);
}
}
void BSTF10::inOrderBST() const
{
inOrderBST(rootBST);
}
void BSTF10::inOrderBST( const BSTPtr holdPtr ) const
{
if (holdPtr)
{
inOrderBST(holdPtr->left);
cout << holdPtr->element << endl;
inOrderBST(holdPtr->right);
}
}
void BSTF10::postOrderBST() const
{
postOrderBST(rootBST);
}
void BSTF10::postOrderBST( const BSTPtr holdPtr ) const
{
if (holdPtr)
{
postOrderBST(holdPtr->left);
postOrderBST(holdPtr->right);
cout << holdPtr->element << endl;
}
}
void BSTF10::initializeBST( BSTPtr &holdBSTPTR )
{
holdBSTPTR = NULL;
}
bool BSTF10::isEmptyBST( const BSTPtr holdPTR) const
{
if(rootBST == NULL)
return true;
else
return false;
}
void BSTF10::copyBST( const BSTPtr copy)
{
if (isEmptyBST(copy))
{
return;
}
else
{
BSTF10 second;
second.copyBST(copy->left);
second.copyBST(copy->right);
}
}
void BSTF10::destroyBST( BSTPtr &nodePtr )
{
if (nodePtr)
{
if (nodePtr->left)
destroyBST(nodePtr->left);
if (nodePtr->right)
destroyBST(nodePtr->right);
delete nodePtr;
}
}
void BSTF10::deleteBSTNode( const ElementF10 holdsVal, BSTPtr &holdsNd )
{
BSTNode *tempNodePtr;
if (isEmptyBST(holdsNd)){
cout << "This node in the Binary tree is empty.\n";
cout << "Press enter to continue" << endl;
cin.ignore();
cin.get();
}
else if (holdsNd->right == NULL)
{
tempNodePtr = holdsNd;
holdsNd = holdsNd->left;
delete tempNodePtr;
}
else if (holdsNd->left == NULL)
{
findMinBSTNode(holdsNd->right, tempNodePtr);
tempNodePtr->element = holdsNd->element;
holdsNd = holdsNd->right;
delete tempNodePtr;
}
else
{
tempNodePtr = holdsNd->right;
while (tempNodePtr->left)
tempNodePtr = tempNodePtr->left;
tempNodePtr->left = holdsNd->left;
tempNodePtr = holdsNd;
holdsNd = holdsNd->right;
delete tempNodePtr;
}
}
void BSTF10::findMinBSTNode( BSTPtr &holdNode, BSTPtr &holdTNode )
{
if(holdNode->left == NULL){
holdTNode = rootBST;
holdNode = holdNode->right;
}
else
holdNode = holdNode->left;
}
BSTF10::~BSTF10()//destructor
{
destroyBST(rootBST);
}
Also,
I already asked for help on another thread, but no one answered there because I attached the cpp files... I'd appreciate it if the other thread is deleted. Thanks.