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;
}

#endif

my 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

Edited 7 Years Ago by lotrsimp12345: n/a

line #224:
U are getting the max node in the temp variable. But u have not put it in the particular location. No links assigned. !!!!!!!!!

* Instead of deleting the cur node, copy the maxnode data into cur node and delete the max node.

There may somemore error I dint checked all your code.

This question has already been answered. Start a new discussion instead.