Hello. I have spent some time working on my BST tree and have finally gotten it to work. I was wondering if some people could take a look at my code and perhaps offer some criticism.
I would really appreciate it. Thank you.
Code:
//======================
// BST.h
//======================
struct node
{
int element;
node * left;
node * right;
};
// My BST class
class BST
{
public:
BST();
~BST();
void insert();
void remove();
void display();
private:
node * root;
int num_in_tree;
void insert(int, node *&);
int remove(int, node *&);
node * inorderSuccessor(node *&);
int children(node *);
void display(node *);
void destroy(node *&);
};
//=============
// BST.cpp
//=============
#include <iostream>
#include "BST.h"
using namespace std;
BST::BST()
{
root = NULL;
num_in_tree = 0;
}
BST::~BST()
{
destroy(root);
}
//================================================
// INPUT: none
// OUTPUT: none
// gets input from user and calls recursive insert
//================================================
void BST::insert()
{
int key;
cout << "Enter a number to insert:\n";
cin >> key;
cin.get();
insert(key, root);
}
//================================================
// INPUT: none
// OUTPUT: none
// gets input from user and calls recursive remove
//================================================
void BST::remove()
{
int key;
cout << "Enter a number to remove\n";
cin >> key;
cin.get();
if(remove(key, root) == 1)
cout << "Number not found.\n";
}
//============================================
// INPUT: none
// OUTPUT: none
// wrapper function for display
//============================================
void BST::display()
{
display(root);
}
//============================================
// INPUT: pointer to a node
// OUTPUT: none
// recursively inserts a new node into the BST
//============================================
void BST::insert(int newElement, node *& troot)
{
if(!troot)
{
troot = new node;
troot->element = newElement;
troot->left = NULL;
troot->right = NULL;
++num_in_tree;
}
else if(newElement < troot->element)
{
insert(newElement, troot->left);
}
else
{
insert(newElement, troot->right);
}
}
//================================================
// INPUT: pointer to a node
// OUTPUT: 1 if element to be deleted is not found
// 0 if element is successfully deleted
//================================================
int BST::remove(int oldElement, node *& troot)
{
if(!troot)
{
return 1; //error code
}
else if(oldElement < troot->element)
{
remove(oldElement, troot->left);
}
else if(oldElement > troot->element)
{
remove(oldElement, troot->right);
}
else if(children(troot) == 2)
{
troot->element = inorderSuccessor(troot->right)->element;
remove(troot->element, troot->right);
}
else
{
if(troot->left)
{
troot->element = troot->left->element;
remove(troot->element, troot->left);
}
else if(troot->right)
{
troot->element = troot->right->element;
remove(troot->element, troot->right);
}
else
{
node * oldNode = troot;
troot = NULL;
delete oldNode;
return 0;
--num_in_tree;
}
}
}
//=========================================
// INPUT: pointer to a node
// OUTPUT: pointer to the inorder successor
// of the input node
//=========================================
node * BST::inorderSuccessor(node *& troot)
{
if(!troot->left)
{
return troot;
}
else
{
inorderSuccessor(troot->left);
}
}
//==================================
// INPUT: pointer to a node
// OUTPUT: 0 if node has no children
// 1 if node has 1 child
// 2 if node has 2 children
//==================================
int BST::children(node * troot)
{
if(troot->left && troot->right)
{
return 2;
}
else if(troot->left || troot->right)
{
return 1;
}
else
{
return 0;
}
}
//=========================================
// INPUT: pointer to a node
// OUTPUT: contents of tree in sorted order
// recursively prints contents of the BST
//=========================================
void BST::display(node * troot)
{
if(troot)
{
display(troot->left);
cout << troot->element << endl;
display(troot->right);
}
}
//================================
// INPUT: pointer to a node
// OUTPUT: none
// recursively deletes the BST
//================================
void BST::destroy(node *& troot)
{
if(troot)
{
destroy(troot->left);
destroy(troot->right);
delete troot;
}
troot = NULL;
}