Removing in Bineary Tree

Removing In Bineary Tree All 3 cases: 
1st case having no child (leaf node)
2nd case having one child (non leaf node)
3rd case having two childs :)
==========================================

#include<iostream.h>
#include<conio.h>
class treenode{
public:
int info;
treenode *left,*right;
treenode()
{ this->info=NULL;
  this->left=NULL;
  this->right=NULL;
}
treenode(int info)
{ this->info=info;
  this->left=NULL;
  this->right=NULL;
}
void setinfo(int info)
{ this->info=info; }
int getinfo()
{ return info; }
void setleft(treenode *left)
{  this->left=left; }
void setright(treenode *right)
{   this->right=right; }
treenode *getleft()
{ return left; }
treenode *getright()
{  return right; }

void insert(treenode *root,int info)
{
treenode *node=new treenode(info);
treenode *p,*q;
p=q=root;
while(info!=p->getinfo() && q!=NULL)
{
p=q;
if(info<p->getinfo())
{ q=p->getleft(); }
else
{  q=p->getright(); }
}
if(info==p->getinfo())
{ cout<<" \n Attempt to insert duplicate "<<info<<endl;
delete node;
}
else if(info<p->getinfo())
{ p->setleft(node); }
else
{p->setright(node); }
}

void preorder(treenode *root)
{
if(root!=NULL)
{ cout<<"\t"<<root->getinfo();
preorder(root->getleft());
preorder(root->getright());
}}
void postorder(treenode *root)
{
if(root!=NULL)
{
postorder(root->getleft());
postorder(root->getright());
cout<<"\t"<<root->getinfo();
}}
void inorder(treenode *root)
{
if(root!=NULL)
{
inorder(root->getleft());
cout<<"\t"<<root->getinfo();
inorder(root->getright());
}}

treenode *remove(treenode *tree,int info)
{
treenode *t;
int cmp=info-tree->getinfo();
if(cmp<0){
t=remove(tree->getleft(),info);
tree->setleft(t);
}
else if(cmp>0){
t=remove(tree->getright(),info);
tree->setright(t);
}
else if(tree->getleft()!=NULL && tree->getright()!=NULL)
{
treenode *minnode;
minnode=findmin(tree->getright());
tree->setinfo(minnode->getinfo());
t=remove(tree->getright(),minnode->getinfo());
tree->setright(t);
}
else
{ treenode *nodetodelete=tree;
  if(tree->getleft()==NULL)
  tree=tree->getright();
  else if(tree->getright()==NULL)
  tree=tree->getright();
  else{
  tree=NULL;
  delete nodetodelete;}
}
return tree;
}
treenode *findmin(treenode *tree)
{ if(tree==NULL)
 return NULL;
 if(tree->getleft()==NULL)
 return tree;
 return findmin(tree->getleft());
}

};
void main()
{
clrscr();
int x[]={14,15,4,8,7,3,5,2,1,9,6,-1};
treenode *root=new treenode();
root->setinfo(x[0]);
for(int i=1;x[i]>0;i++)
{ root->insert(root,x[i]);}
cout<<"\n\nDispaly ::Pre Order\n\n";
root->preorder(root);
cout<<"\n\n Display ::In Order\n\n";
root->inorder(root);
cout<<"\n\n Display ::Post Order\n\n";
root->postorder(root);
getch();
clrscr();
root->preorder(root);
cout<<"\n\n Removing leaf node     :: 1st case\n\n ";
root->remove(root,x[10]);
root->preorder(root);
cout<<"\n\n Removing Non leaf node :: 2nd case\n\n";
root->remove(root,x[6]);
root->preorder(root);
cout<<"\n\n Removing parent node [having two child] ::case 3\n\n";
root->remove(root,x[2]);
root->preorder(root);
getch();
}

Share this

Programming Seeker