0

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.

#endif

And 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

2
Contributors
1
Reply
2
Views
6 Years
Discussion Span
Last Post by VernonDozier
1

I suggest approaching the problem in the following organized manner. You want to see where it first breaks. Thus if the error shows up in, say the Search routine, that may not mean the Search routine is incorrect. It may mean that the Insertion routine is incorrect. Presumably you have tested this with some data, so you must have a driver program that has a main. You haven't posted that program. What type is the data? I normally test with integers first. They are a constant size (normally 4 bytes) and I can see them in a debugger and I can display them.

I would take a small set (i.e. {1,2,3,4,5}) and make a driver program to insert and search for them. You again need to find out exactly where your program breaks and under what circumstances:

  1. Insertion of the first element (root node).
  2. Insertion of the second element (child node).
  3. Insertion at a certain depth.
  4. Insertion in a certain order, but runs fine in other orders.
  5. Inserts fine, but cannot search.
  6. Works for some data types, but not others.
  7. Dozens of other scenarios.

You'll have driver program that you'll be changing to get it to fail at different times and nail things down. Does it work fine if and only if you insert the items in an ordered list? Only if you have a fairly balanced tree? Etc. Etc.

You should also consider the possibility of writing a non-templated Binary Search Tree and getting it to work for some data type, then when that works, expand to a template.

We can't run your code without a main function, so you should include a driver program with main, tell us where the failure is, stuff like that (you mentioned seg faults, but without seeing the data that you are using and the driver program, it's hard to visualize).

Votes + Comments
Perfect.
This question has already been answered. 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.