C++ program to delete a tree














































C++ program to delete a tree



#include<iostream>
using namespace std;
class node
{
 string word;
 string meaning;
 node *left;
 node *right;
 friend class tree;
 friend class queue;// friend class queue;
};

class tree
{
  node *root;
 public:
     tree()
    {
     root=NULL;
    }
    //create
    void bst_create_nr();
    void bfs();
        //deleting
        void bst_delete(node *);
        void dt();
        void display_ino_btree(node *);  //in display     (left,root,right)
        void indisp();

};



class queue
{
  int f,r;
  node *d[20];
  public:
     queue();
     void insert(node *);
     node* qdelete();
     int isempty();
};

queue::queue()
{
 f=r=-1;
}

void queue::insert(node *temp)
{
 r++;
 d[r]=temp;
}

node* queue::qdelete()
{
 f++;
 return(d[f]);
}

int queue::isempty()
{
 if(f==r)
  return 0;
 else
  return 1;
}

void tree::bst_create_nr()
{
  node *temp,*curr;
  int flag=0;
  char ch;
  do
  {
    if(root==NULL)
    {
     root=new node();
     cout<<"\nEnter the root keyword & meaning:\n";
     cin>>root->word;
     cin.ignore();
     getline(cin,root->meaning);
     root->left=root->right=NULL;
    }
    else
    {
     temp=root;
     curr=new node();
     curr->left=curr->right=NULL;
     cout<<"\nEnter the keyword & meaning:\n";
     cin>>curr->word;
     cin.ignore();
     getline(cin,curr->meaning);
     while(flag==0)
     {
        if(curr->word<temp->word)
        {
      if(temp->left==NULL)
      {
       flag=1;temp->left=curr;
      }
      else
      {temp=temp->left;}
        }
    else if(curr->word>temp->word)
    {
      if(temp->right==NULL)
      {
       flag=1;temp->right=curr;
      }
      else
      {temp=temp->right;}
        }
    else
    {
     cout<<"\n Duplicate not allow in BST";
     flag=1;
    }
    }//inside while
   }//else
    cout<<"\nDo you want to Add more elements to Binary tree (y/n): ";
    cin>>ch;
 flag=0;
 }while(ch=='y');
}




void tree::bst_delete(node *root)
{
  int flag=0;
  string key;
  cout<<"Enter the key to delete: ";
  cin>>key;
  node *curr,*temp,*temp1,*temp2,*s,*p; //p=parent
  p=NULL;
  //as root is modified in b/w so using curr to traverse
  curr=root;
  while(curr!=NULL)
  {
  if(key==curr->word)
  {  
        if(curr==root)
        {      
          if(curr->left==NULL && curr->right==NULL)
          {
           delete (curr);
          }
          else if(curr->left!=NULL && curr->right==NULL)
          {
           root=curr->left;
           curr->left=curr->right=NULL;
           delete (curr);
          }
          else if(curr->left==NULL && curr->right!=NULL)
          {
            root=curr->right;
            curr->left=curr->right=NULL;
            delete (curr);
          }
          else if(curr->left!=NULL && curr->right!=NULL)
          {
           temp=curr->left;
           root=curr->right;
           s=root;
           while(s->left!=NULL)
           {s=s->left;}
           s->left=temp;
           curr->left=curr->right=NULL;
           delete (curr);
          }    
        }//if end
        else
        {      
          if(curr->left==NULL && curr->right==NULL)
          {
           if(curr==p->left)
            p->left=NULL;
           else
            p->right=NULL;     
           delete (curr);
          }
          else if(curr->left!=NULL && curr->right==NULL)
          {
           if(curr==p->left)
            p->left=curr->left;
           else
            p->right=curr->left;
           curr->left=curr->right=NULL;
           delete (curr);
          }
          else if(curr->left==NULL && curr->right!=NULL)
          {
           if(curr==p->left)
            p->left=curr->right;
           else
            p->right=curr->right;
           curr->left=curr->right=NULL;
            delete (curr);
          }
          else if(curr->left!=NULL && curr->right!=NULL)
          {
           temp1=curr->right;
           temp2=curr->left;
           s=temp1;
           if(curr==root->left)
            p->left=temp1;
           else
            p->right=temp1;
           while(s->left!=NULL)
           {s=s->left;}
           s->left=temp2;
           curr->left=curr->right=NULL;
           delete (curr);
          }
        }
   flag=1;     
   cout<<"\nKey deleted!!";
   break;
   }
   else if(key<curr->word)
   {
     p=curr;      
     curr=curr->left;
   }
   else if(key>curr->word)
   {  
     p=curr;    
     curr=curr->right;
   } 
  }
  if(flag==0)
   cout<<"\nKey not found";
}

void tree::dt()
{
  bst_delete(root);
}

void tree::display_ino_btree(node *root) //in order
{
 if(root!=NULL)
 {
  display_ino_btree(root->left);
  cout<<root->word<<" => "<<root->meaning<<"\n";
  display_ino_btree(root->right);
 }
}

void tree::indisp()
{
 display_ino_btree(root);
 cout<<endl;
}

void bst_disp(tree T)
{
      
  cout<<"\nInordered BST is   : \n\n";
  T.indisp();
  cout<<"\n\n============================================================\n";
}

int main()
{
 tree T,T2;
 int ch,h;
 string key;
 node *croot;
 while(ch!=10)
 {
  
  cout<<"\n1. Create BST using Non-Recursive Method";
  cout<<"\n2. Delete from BST";
  cout<<"\n3. Create BST using Non-Recursive Method";
  cout<<"\n4.Exit";
  cout<<"\n\nChoice:";
  cin>>ch;
  switch(ch)
  {
   case 1:T.bst_create_nr();                           //bst_disp() is a "outside function" not a funtion of tree or node
        
      break;
   case 2: T.dt();
          bst_disp(T);
          break; 
   case 3:bst_disp(T);
          break;
   case 4:break;
   default:cout<<"\nPls Enter the correct choice";
  }
 }
 return 0;
}


More Articles of Divyanjali Soni:

Name Views Likes
C++ program to delete a tree 228 0

Comments