the delete must be by copying the data and then deleting if their are 2 nodes from that one root.
CODE IS AT VERY END FOR THAT. CALLED REMOVE.
Thanks.
main
#include <iostream>
#include "my_bst.h"
using namespace std;
int main()
{
my_bst<int,int> ab;
ab.insert(4,1);
ab.insert(2,2);
ab.insert(6,3);
ab.insert(1,4);
ab.insert(3,5);
ab.insert(5,6);
ab.insert(7,7);
cout<<"preorder print:\n";
ab.preorder_print();
cout<<endl;
cout<<"inorder print:\n";
ab.inorder_print();
cout<<endl;
cout<<"postorder print:\n";
ab.postorder_print();
cout<<endl;
cout<<"key doesn't exist in tree?\n";
ab.search(200);
cout<<"key was found in tree?\n";
ab.search(2);
ab.remove(2);
return 0;
}BST node
#ifndef MY_BST_NODE_H
#define MY_BST_NODE_H
#include <iostream>
using namespace std;
template<class KT,class DT>
class my_bst_node
{
public:
my_bst_node();
my_bst_node(KT tag, DT info, my_bst_node* l=0, my_bst_node* r=0);
KT key;
DT data;
my_bst_node* left;
my_bst_node* right;
};
template<class KT, class DT>
my_bst_node<KT,DT>::my_bst_node()
{
left=right=0;
}
template<class KT, class DT>
my_bst_node<KT,DT>::my_bst_node(KT tag, DT info, my_bst_node* l, my_bst_node* r)
{
key=tag;
data=info;
left=l;
right=r;
}
#endifmy bst
#ifndef MY_BST_H
#define MY_BST_H
#include <iostream>
#include "my_bst_node.h"
using namespace std;
template<class KT,class DT>
class my_bst
{
public:
//default constructor
my_bst();
//inserts a new node into binary tree
void insert(KT searchkey, const DT &newDataItem);
//search for the key and if found return true
void search(KT searchkey);
//prints out tree based on visiting the root node, then the left subtree and last the right subtree
void preorder_print();
//prints out tree based on visiting the left subtree, then the root node, and last the right subtree
void inorder_print();
//prints out tree based on visiting the left subtree, then the right subtree, and last the root node
void postorder_print();
//remove data item
void remove(KT searchkey);
//returns height of BST
int height();
//check if tree is balanced
bool balanced() const;
//
void show_bst_structure() const;
private:
my_bst_node<KT,DT>* root;
//helper function of insert
void insert(my_bst_node<KT,DT>*& newnode ,my_bst_node<KT,DT>*& nodepointer);
//helper function of search
void search(my_bst_node<KT,DT>*& d, const KT& searchkey);
//helper function of preorder print
void preorder_print(my_bst_node<KT,DT>*& f);
//helper function of inorder print
void inorder_print(my_bst_node<KT,DT>*& g);
//helper function of postorder print
void postorder_print(my_bst_node<KT,DT>*& n);
//helper function of remove
void remov(my_bst_node<KT,DT>*& n, KT deletekey);
//function to delete the node
void deletenode(my_bst_node<KT,DT>* g);
//function to find the maximum value
my_bst_node<KT,DT>* findmax(my_bst_node<KT,DT>*& h);
//helper function of get height
int height(my_bst_node<KT,DT>* p);
};
template <class KT, class DT>
my_bst<KT,DT>::my_bst()
{
root=NULL;
}
template <class KT, class DT>
void my_bst<KT,DT>::insert(KT searchkey, const DT& newDataItem)
{
my_bst_node<KT,DT>* temp=new my_bst_node<KT,DT>(searchkey, newDataItem);
insert(temp, root);
}
template <class KT, class DT>
void my_bst<KT,DT>::insert(my_bst_node<KT,DT>*& newnode ,my_bst_node<KT,DT>*& nodepointer)
{
//if empty tree
if(nodepointer==NULL)
{
nodepointer=newnode;
}
//key less than root nodes
else if((newnode->key)<=(nodepointer->key))
{
insert(newnode,nodepointer->left);
}
//key greater than root nodes
else
{
insert(newnode,nodepointer->right);
}
}
template <class KT, class DT>
void my_bst<KT,DT>::search(KT searchkey)
{
my_bst_node<KT,DT>* temp=root;
search(temp,searchkey);
}
template <class KT, class DT>
void my_bst<KT,DT>::search(my_bst_node<KT,DT>*&d ,const KT& searchkey)
{
//if empty tree
if(d==NULL)
{
cout<<"false\n";
}
//keys match
else if(searchkey==d->key)
{
cout<<"true\n";
}
//if the search key is less than root nodes search key
else if(searchkey<d->key)
{
search(d->left,searchkey);
}
//if the search key is greater than root nodes search key
else
{
search(d->right,searchkey);
}
}
template <class KT, class DT>
void my_bst<KT,DT>::preorder_print()
{
my_bst_node<KT,DT>* temp;
temp=root;
preorder_print(temp);
}
template <class KT, class DT>
void my_bst<KT,DT>::preorder_print(my_bst_node<KT,DT>*& f)
{
if(f!=NULL)
{
cout<<f->data<<endl;
preorder_print(f->left);
preorder_print(f->right);
}
}
template <class KT, class DT>
void my_bst<KT,DT>::inorder_print()
{
my_bst_node<KT,DT>* temp;
temp=root;
inorder_print(temp);
}
template <class KT, class DT>
void my_bst<KT,DT>::inorder_print(my_bst_node<KT,DT>*& g)
{
if(g!=NULL)
{
inorder_print(g->left);
cout<<g->data<<endl;
inorder_print(g->right);
}
}
template <class KT, class DT>
void my_bst<KT,DT>::postorder_print()
{
my_bst_node<KT,DT>* temp=root;
postorder_print(temp);
}
template <class KT, class DT>
void my_bst<KT,DT>::postorder_print(my_bst_node<KT,DT>*& n)
{
if(n!=NULL)
{
postorder_print(n->left);
postorder_print(n->right);
cout<<n->data<<endl;
}
}
template <class KT, class DT>
void my_bst<KT,DT>::remove(KT searchkey)
{
my_bst_node<KT,DT>* temp5=root;
remov(temp5,searchkey);
}
template <class KT, class DT>
void my_bst<KT,DT>::remov(my_bst_node<KT,DT>*& n, KT deletekey)
{
if(deletekey<n->key)
{
remov(n->left,deletekey);
}
else if(deletekey>n->key)
{
remov(n->right,deletekey);
}
else if(deletekey==n->key)
{
deletenode(n);
}
}
template <class KT, class DT>
void my_bst<KT,DT>::deletenode(my_bst_node<KT,DT>* g)
{
my_bst_node<KT,DT>* temp1;
if((g->left!=NULL)&&(g->right!=NULL))
{
temp1=findmax(g->left);
delete g;
}
else
{
delete g;
}
}
template <class KT, class DT>
my_bst_node<KT,DT>* my_bst<KT,DT>::findmax(my_bst_node<KT,DT>*& h)
{
//empty tree
if(h==NULL)
{
return NULL;
}
//found max
if(h->right==NULL)
{
return h;
}
//recursive call to right subtree since right contains max value
else
{
findmax(h->right);
}
}
/*template <class KT, class DT>
int my_bst<KT,DT>::height()
{
my_bst_node<KT,DT>* temp=root;
return height(temp);
}
template <class KT, class DT>
int my_bst<KT,DT>::height(my_bst_node<KT,DT>* p)
{
//empty tree
if(p==NULL)
{
return 0;
}
//
else
{
if(height(p->left)>height(p->right))
{
return height(p->left+1);
}
else
{
return height(p->right+1);
}
}
}
*/
#endif