Hey I'm new here so forgive me if I do something wrong. Just let me know and I'll try to fix it. Basically I'm trying to write a binary search tree without using recursion. (Difficult I know, but if you can show me how to do it without changing the function calls then I'd appreciate it.) Anyways, I'm having two problems. 1) In my delete function, if I delete the rootPtr, I get a segmentation fault because rootPtr isn't pointing to anything now. If you could tell me how to reassign it I'd appreciate it. My other problem is with the other 3 functions, Size() (Counts number of nodes in the tree), TotalLevels() (Counts how many levels are in the tree), and Level() (finds what level a node is on) because I don't know how to write those codes without recursion, or using recursion that doesn't have arguments in the function call. This is a project so I cannot change the function prototypes. Any help would be greatly appreciated.
Header file
#ifndef BSTREE_H
#define BSTREE_H
#include <cstddef>
#include <new>
#include <string>
using namespace std;
class FullBSTree // Exception class models full BSTree condition
{
/* No code here */
};
class EmptyBSTree // Exception class models empty BSTree condition
{
/* No code here */
};
class NotFoundBSTree // Exception class models not found in BSTree condition
{
/* No code here */
};
class FoundInBSTree // Exception class models found in BSTree condition
{
/* No code here */
};
template <typename SomeType>
struct BSTreeNode // Node of BSTree
{
SomeType data; // Data stored in node
BSTreeNode<SomeType>* leftPtr; // Pointer to left subtree
BSTreeNode<SomeType>* rightPtr; // Pointer to right subtree
};
template <typename SomeType>
class BSTree // BSTree Abstract Data Type
{
private:
BSTreeNode<SomeType>* rootPtr; // Pointer to root of BSTree
public:
/************** Start of Functions You Must Implement ****************/
BSTree();
// BSTree()
// Default constructor initializes root pointer to NULL
~BSTree();
// ~BSTree()
// Destructor deallocates all tree nodes
void InsertItem(SomeType item);
// InsertItem()
// Inserts item into BSTree; if tree already full, throws FullBSTree exception
// If item is already in BSTree, throw FoundInBSTree exception
void DeleteItem(SomeType& item);
// DeleteItem()
// Deletes item from BSTree if item is present AND returns object via reference parameter
// If tree is empty, throw the EmptyBSTree exception
// If tree is not empty and item is NOT present, throw NotFoundBSTree
void MakeEmpty();
// MakeEmpty()
// Deallocates all BSTree nodes and sets root pointer to NULL
int Size() const;
// Size()
// Returns total number of data values stored in tree
bool IsFull() const;
// IsFull()
// Returns true if BSTree is full; returns false otherwise
bool IsEmpty() const;
// IsEmpty()
// Returns true if BSTree is empty; returns false otherwise
SomeType Min() const;
// Min()
// Returns minimum value in tree; throws EmptyBSTree if tree is empty
SomeType Max() const;
// Max()
// Returns maximum value in tree; throws EmptyBSTree if tree is empty
int TotalLevels() const;
// TotalLevels()
// Returns the maximum level value for current tree contents
// Levels are numbered 0, 1, ..., N-1. This function returns N
// Throws EmptyBSTree if empty
int Level(SomeType item) const;
// Level()
// Returns the level within the BSTree at which the value item is found
// If tree is empty, throws EmptyBSTree
// If tree is not empty and item is not found, throws NotFoundBSTree
/************** End of Functions You Must Implement ****************/
void Print() const; // DO NOT WRITE THIS FUNCTION
// Print()
// Prints binary search tree contents in inorder, preorder, and postorder forms
// NOTE: THIS CODE HAS BEEN INCLUDED AT THE END OF main.cpp
};
#include "bstree.cpp" // Note: Template classes cannot be compiled on their own
// since the data type argument is found in the client code.
#endifAnd the implementation file
#include <iostream>
using namespace std;
#include "bstree.h"
template <typename SomeType>
BSTree<SomeType>::BSTree()
{
rootPtr=NULL;
}
template <typename SomeType>
BSTree<SomeType>::~BSTree()
{
MakeEmpty();
}
template <typename SomeType>
void BSTree<SomeType>::MakeEmpty()
{
if(rootPtr)
{
if (rootPtr->leftPtr)
delete rootPtr->leftPtr;
if (rootPtr->rightPtr)
delete rootPtr->rightPtr;
rootPtr=NULL;
}
}
template <typename SomeType>
bool BSTree<SomeType>::IsEmpty() const
{
return(rootPtr==NULL);
}
template <typename SomeType>
bool BSTree<SomeType>::IsFull() const
{
BSTreeNode<SomeType>* isfull;
try
{
isfull=new BSTreeNode<SomeType>;
delete isfull;
return false;
}
catch(bad_alloc)
{
return true;
}
}
template <typename SomeType>
void BSTree<SomeType>::InsertItem(SomeType item)
{
if(IsFull())
throw FullBSTree();
bool found=false;
BSTreeNode<SomeType>* Ptr=new BSTreeNode<SomeType>;
BSTreeNode<SomeType>* currentPtr;
BSTreeNode<SomeType>* parentPtr;
currentPtr=rootPtr;
Ptr->data=item;
Ptr->leftPtr=NULL;
Ptr->rightPtr=NULL;
parentPtr=NULL;
if(IsEmpty())
rootPtr=Ptr;
else
{
currentPtr=rootPtr;
while(currentPtr)
{
parentPtr=currentPtr;
if(Ptr->data>currentPtr->data)
currentPtr=currentPtr->rightPtr;
else
currentPtr=currentPtr->leftPtr;
}
if(Ptr->data<parentPtr->data)
parentPtr->leftPtr=Ptr;
else if(Ptr->data>parentPtr->data)
parentPtr->rightPtr=Ptr;
else
throw FoundInBSTree();
}
}
template <typename SomeType>
void BSTree<SomeType>::DeleteItem(SomeType& item) //Issue Function
{
if(IsEmpty())
throw EmptyBSTree();
BSTreeNode<SomeType>* parentPtr;
BSTreeNode<SomeType>* tempPtr;
tempPtr=rootPtr;
while(tempPtr!=NULL) //Checking to see where the item is to delete.
{
if(item<tempPtr->data)
{
parentPtr=tempPtr;
tempPtr=tempPtr->leftPtr;
}
else if(item>tempPtr->data)
{
parentPtr=tempPtr;
tempPtr=tempPtr->rightPtr;
}
else //Found the value so breaks loop.
break;
}
if(tempPtr==NULL) //If temp is NULL then it didn't find the value.
throw NotFoundBSTree();
else if(parentPtr==NULL)//If parentPtr==NULL then it's the rootPtr
{
if(rootPtr->leftPtr!=NULL)//Go down to the biggest value in the left subtree
{
parentPtr=tempPtr;
tempPtr=tempPtr->leftPtr;
while(tempPtr!=NULL)
{
parentPtr=tempPtr;
tempPtr=tempPtr->rightPtr;
}
rootPtr=parentPtr;
delete parentPtr;
}
else if((rootPtr->leftPtr==NULL)&&(rootPtr->rightPtr!=NULL))//If no left subtree get the smallest value from right subtree
{
parentPtr=tempPtr;
tempPtr=tempPtr->rightPtr;
while(tempPtr!=NULL)
{
parentPtr=tempPtr;
tempPtr=tempPtr->leftPtr;
}
rootPtr=parentPtr;
delete parentPtr;
}
else//If no children just delete rootPtr by setting it to NULL
delete parentPtr;
rootPtr==NULL;
}
else
{
if(tempPtr->leftPtr==NULL&&tempPtr->rightPtr==NULL) //Just a node with no children.
{
if(parentPtr==tempPtr)
delete parentPtr;
else if(parentPtr->leftPtr==tempPtr)
{
parentPtr->leftPtr=NULL;
delete tempPtr;
}
else
{
parentPtr->rightPtr=NULL;
delete tempPtr;
}
}
if(tempPtr->leftPtr==NULL&&tempPtr->rightPtr!=NULL) //Node with only a right child.
{
if(parentPtr->leftPtr==tempPtr)
{
parentPtr->leftPtr=tempPtr->rightPtr;
delete tempPtr;
}
else
{
parentPtr->rightPtr=tempPtr->rightPtr;
delete tempPtr;
}
}
if(tempPtr->leftPtr!=NULL&&tempPtr->rightPtr==NULL) //Node with only a left child.
{
if(parentPtr->leftPtr==tempPtr)
{
parentPtr->leftPtr=tempPtr->leftPtr;
delete tempPtr;
}
else
{
parentPtr->rightPtr=tempPtr->leftPtr;
delete tempPtr;
}
}
if(tempPtr->leftPtr!=NULL&&tempPtr->rightPtr!=NULL) //Node that has 2 children.
{
BSTreeNode<SomeType>* checkPtr;
checkPtr=tempPtr->rightPtr;
if((checkPtr->leftPtr==NULL)&&(checkPtr->rightPtr==NULL))
{
tempPtr=checkPtr;
delete checkPtr;
tempPtr->rightPtr=NULL;
}
else
{
if((tempPtr->rightPtr)->leftPtr!=NULL)
{
BSTreeNode<SomeType>* lefttemp;
BSTreeNode<SomeType>* leftparent;
leftparent=tempPtr->rightPtr;
lefttemp=(tempPtr->rightPtr)->leftPtr;
while(lefttemp->leftPtr!=NULL)
{
leftparent=lefttemp;
lefttemp=lefttemp->leftPtr;
}
tempPtr->data=lefttemp->data;
delete lefttemp;
leftparent->leftPtr=NULL;
}
else
{
BSTreeNode<SomeType>* newtemp;
newtemp=tempPtr->rightPtr;
tempPtr->data=newtemp->data;
tempPtr->rightPtr=newtemp->rightPtr;
delete newtemp;
}
}
}
}
}
template <typename SomeType>
int BSTree<SomeType>::Size() const
{
if(rootPtr==NULL)
return 0;
else
return Size(rootPtr->leftPtr)+Size(rootPtr->rightPtr);
}
template <typename SomeType>
SomeType BSTree<SomeType>::Min() const
{
BSTreeNode<SomeType>* tempPtr;
tempPtr=rootPtr;
while(tempPtr->leftPtr!=NULL)
{
tempPtr=tempPtr->leftPtr;
}
return tempPtr->data;
}
template <typename SomeType>
SomeType BSTree<SomeType>::Max() const
{
BSTreeNode<SomeType>* tempPtr;
tempPtr=rootPtr;
while(tempPtr->rightPtr!=NULL)
{
tempPtr=tempPtr->rightPtr;
}
return tempPtr->data;
}
template <typename SomeType>
int BSTree<SomeType>::TotalLevels() const
{
/*** Save this function for LAST!! ***/
}
template <typename SomeType>
int BSTree<SomeType>::Level(SomeType item) const
{
}Thanks again