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 << ¤t << "ADDY" << endl;
cout << ¤t->left << "L ADDY" << endl;
cout << ¤t->right << "R ADDY" << endl;
}
else
{
current->right = newNode;
cout << current->data << "DATA" << endl;
cout << ¤t << "ADDY" << endl;
cout << ¤t->left << "L ADDY" << endl;
cout << ¤t->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