swolll 32 Light Poster

This is seg faulting whenever I try to remove anything. I've been trying to fix it for hours, to no avail.

Any ideas?

#ifndef BST_H_
#define BST_H_

#include <stdexcept>
#include <iostream>
#include "btnode.h"

using namespace std;

/*
	A class to represent a templated binary search tree.
*/
template <typename T>
class BST
{
	private:
	
		//pointer to the root node in the tree
		BTNode<T>* root;
		
	public:
		
		//default constructor to make an empty tree
		BST();
		
		/*
			You have to document these 4 functions
		*/
		void insert(T value);
		bool search(const T& value) const;
		bool search(BTNode<T>* node, const T& value) const;
		void printInOrder() const;
		void remove(const T& value);
		
		//function to print out a visual representation
		//of the tree (not just print the tree's values 
		//on a single line)
		void print() const;
		
	private:
		
		//recursive helper function for "print()"
		void print(BTNode<T>* node,int depth) const;
};

/*
	Default constructor to make an empty tree
*/
template <typename T>
BST<T>::BST()
{
	root = NULL;
}

template <typename T>
void BST<T>::insert(T value)
{
	BTNode<T>* newNode = new BTNode<T>(value);
	cout << newNode->data;
	if(root == NULL)
	{
		root = newNode;
		return;
	}
	BTNode<T>* current = root;
	while(true)
	{
		if(current->left == NULL && current->right == NULL)
			break;
		if(current->right != NULL && current->left != NULL)
		{
			if(newNode->data > current->data) 
				current = current->right;
			else if(newNode->data < current->data)
				current = current->left;
		}
		else if(current->right != NULL && current->left == NULL)
		{
			if(newNode->data < current->data) 
				break;
			else if(newNode->data > current->data)
				current = current->right;
		}
		else if(current->right == NULL && current->left != NULL)
		{
			if(newNode->data > current->data) 
				break;
			else if(newNode->data < current->data)
				current = current->left;
		}
	}
	
	if(current->data > newNode->data)
	{	
		current->left = newNode;
		cout << current->data << "DATA" << endl;
		cout << &current << "ADDY" << endl;
		cout << &current->left << "L ADDY" << endl;
		cout << &current->right << "R ADDY" << endl;
	}
	else
	{
		current->right = newNode;
		cout << current->data << "DATA" << endl;
		cout << &current << "ADDY" << endl;
		cout << &current->left << "L ADDY" << endl;
		cout << &current->right << "R ADDY" << endl;
	}
	return;
}
  
//public helper function
template <typename T>
bool BST<T>::search(const T& value) const
{
	return(search(root,value)); //start at the root
}

//recursive function
template <typename T>
bool BST<T>::search(BTNode<T>* node, const T& value) const 
{
	if(node == NULL || node->data == value)
		return(node != NULL); //found or couldn't find value
	else if(value < node->data)
		return search(node->left,value); //search left subtree
	else
		return search(node->right,value); //search right subtree
}

template <typename T>
void BST<T>::printInOrder() const
{
	//print out the value's in the tree in order
	//
	//You may need to use this function as a helper
	//and create a second recursive function
	//(see "print()" for an example)
}

template <typename T>
void BST<T>::remove(const T& value)
{
    if(root == NULL)
    {
        cout << "Tree is empty. No removal. "<<endl;
        return;
    }
	if(!search(value))
	{
		cout << "Value is not in the tree. No removal." << endl;
		return;
	}
    BTNode<T>* current = root;
    BTNode<T>* parent;

	cout << root->data << " ROOT" << endl;
	cout << current->data << "CURRENT BEFORE" << endl;
	
    while(current != NULL)
    {
		// Assume root is not deleted.
		if(value > current->data)
		{
			parent = current; 
			current = current->right;
		}
		else if(value < current->data)
		{
			parent = current; 
			current = current->left;			
		}
		else;
	}
	cout << "OUTTTT" << endl;
/*
  // 3 cases :
    //We're looking at a leaf node

    if(current->left == NULL && current->right == NULL)				// It's a leaf
    {
		if(parent == current)
			delete parent;
        else if(parent->left == current)
        {
			parent->left = NULL;
			delete current;
		}
        else 
        {
			parent->right = NULL;
			delete current;
		}
		cout << "The value " << value << " was removed." << endl;
        return;
    }
	
	// Node with single child
    if((current->left == NULL && current->right != NULL) || (current->left != NULL && current->right == NULL))
    {
        if(current->left == NULL && current->right != NULL)
        {
            if(parent->left == current)
            {
                parent->left = current->right;
				cout << "The value " << value << " was removed." << endl;
                delete current;
            }
            else
            {
                parent->right = current->right;
				cout << "The value " << value << " was removed." << endl;
                delete current;
            }
        }
        else // left child present, no right child
        {
            if(parent->left == current)
            {
                parent->left = current->left;
				cout << "The value " << value << " was removed." << endl;
                delete current;
            }
            else
            {
                parent->right = current->left;
				cout << "The value " << value << " was removed." << endl;
                delete current;
            }
        }
        return;
    }

    //Node with 2 children - Replace node with smallest value in right subtree.
    if (current->left != NULL && current->right != NULL)
    {
        BTNode<T>* check;
        check = current->right;
        if((check->left == NULL) && (check->right == NULL))
        {
            current = check;
            delete check;
            current->right = NULL;
			cout << "The value " << value << " was removed." << endl;
        }
        else // right child has children
        {
            //if the node's right child has a left child; Move all the way down left to locate smallest element
            if((current->right)->left != NULL)
            {
                BTNode<T>* leftCurrent;
                BTNode<T>* leftParent;
                leftParent = current->right;
                leftCurrent = (current->right)->left;
                while(leftCurrent->left != NULL)
                {
                    leftParent = leftCurrent;
                    leftCurrent = leftCurrent->left;
                }
                current->data = leftCurrent->data;
                delete leftCurrent;
                leftParent->left = NULL;
				cout << "The value " << value << " was removed." << endl;
            }
            else
            {
                BTNode<T>* temp;
                temp = current->right;
                current->data = temp->data;
                current->right = temp->right;
                delete temp;
				cout << "The value " << value << " was removed." << endl;
            }
        }
        return;
    }*/
}

/*
	Print out the values in the tree and their
	relationships visually.  Sample output:
	
	                    22
                18
        15
10
                9
        5
                3
                        1
*/
template <typename T>
void BST<T>::print() const
{
	print(root,0);
}

template <typename T>
void BST<T>::print(BTNode<T>* node,int depth) const
{
	if(node == NULL)
	{
		std::cout << std::endl;
		return;
	}
	
	print(node->right,depth+1);
	for(int i=0; i < depth; i++)
	{
		std::cout << "\t";
	}
	std::cout << node->data << std::endl;
	print(node->left,depth+1);
}

#endif
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.