Binary Search Tree Implementation
- by Gabe
I've searched the forum, and tried to implement the code in the threads I found. But I've been working on this real simple program since about 10am, and can't solve the seg. faults for the life of me.
Any ideas on what I'm doing wrong would be greatly appreciated.
BST.h (All the implementation problems should be in here.)
#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 = new BTNode<T>(NULL);
current = root;
current->data = root->data;
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;
else
current->right = newNode;
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;
BTNode<T>* parent;
current = root;
parent->left = NULL;
parent->right = NULL;
cout << root->left << "LEFT " << root->right << "RIGHT " << endl;
cout << root->data << " ROOT" << endl;
cout << current->data << "CURRENT BEFORE" << endl;
while(current != NULL)
{
cout << "INTkhkjhbljkhblkjhlk " << endl;
if(current->data == value)
break;
else if(value > current->data)
{
parent = current;
current = current->right;
}
else
{
parent = current;
current = current->left;
}
}
cout << current->data << "CURRENT AFTER" << endl;
// 3 cases :
//We're looking at a leaf node
if(current->left == NULL && current->right == NULL) // It's a leaf
{
if(parent->left == current)
parent->left = NULL;
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
main.cpp
#include "bst.h"
#include <iostream>
using namespace std;
int main()
{
BST<int> tree;
cout << endl << "LAB #13 - BINARY SEARCH TREE PROGRAM" << endl;
cout << "----------------------------------------------------------" << endl;
// Insert.
cout << endl << "INSERT TESTS" << endl; // No duplicates allowed.
tree.insert(0);
tree.insert(5);
tree.insert(15);
tree.insert(25);
tree.insert(20);
// Search.
cout << endl << "SEARCH TESTS" << endl;
int x = 0;
int y = 1;
if(tree.search(x))
cout << "The value " << x << " is on the tree." << endl;
else
cout << "The value " << x << " is NOT on the tree." << endl;
if(tree.search(y))
cout << "The value " << y << " is on the tree." << endl;
else
cout << "The value " << y << " is NOT on the tree." << endl;
// Removal.
cout << endl << "REMOVAL TESTS" << endl;
tree.remove(0);
tree.remove(1);
tree.remove(20);
// Print.
cout << endl << "PRINTED DIAGRAM OF BINARY SEARCH TREE" << endl;
cout << "----------------------------------------------------------" << endl;
tree.print();
cout << endl << "Program terminated. Goodbye." << endl << endl;
}
BTNode.h
#ifndef BTNODE_H_
#define BTNODE_H_
#include <iostream>
/*
A class to represent a node in a
binary search tree.
*/
template <typename T>
class BTNode
{
public:
//constructor
BTNode(T d);
//the node's data value
T data;
//pointer to the node's left child
BTNode<T>* left;
//pointer to the node's right child
BTNode<T>* right;
};
/*
Simple constructor. Sets the data
value of the BTNode to "d" and defaults its
left and right child pointers to NULL.
*/
template <typename T>
BTNode<T>::BTNode(T d)
: left(NULL), right(NULL)
{
data = d;
}
#endif
Thanks.
