[text] code

Viewer

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. struct node{
  6.     int data;
  7.     node* left;
  8.     node* right;
  9. };
  10.  
  11. class bst{
  12.      public:
  13.     node* root;
  14.  
  15.     bst(){
  16.         root=NULL;
  17.     }
  18.     node* getroot(){
  19.             return this->root;
  20.     }
  21.     void insert(int key){
  22.         node* nn=new node;
  23.         nn->data=key;
  24.         nn->right=NULL;
  25.         nn->left=NULL;
  26.         if(root==NULL){
  27.             root=nn;
  28.         }
  29.         else{
  30.             node* t=root;
  31.             node* p=NULL;
  32.             while(t!=NULL){
  33.                 p=t;
  34.                 if(t->data<key){
  35.                     t=t->right;
  36.                 }
  37.                 else if(t->data>key){
  38.                     t=t->left;
  39.                 }
  40.             }
  41.                 if(p->data>key){
  42.                     p->left=nn;}
  43.                     else{
  44.                         p->right=nn;
  45.                     }
  46.                 }
  47.             }
  48.  
  49.  
  50.  
  51.     void inorder(node* t) {
  52.         if(t!=NULL){
  53.         inorder(t->left);
  54.         cout<<t->data<<"->";
  55.         inorder(t->right);
  56.         }
  57.     }
  58.     void postorder(node* t) {
  59.            if(t!=NULL){
  60.            postorder(t->left);
  61.  
  62.            postorder(t->right);
  63.            cout<<t->data<<"->";
  64.            }
  65.        }
  66.     void preorder(node* t) {
  67.               if(t!=NULL){
  68.             cout<<t->data<<"->";
  69.               preorder(t->left);
  70.  
  71.               preorder(t->right);
  72.  
  73.               }
  74.           }
  75.     void deleted(int key){
  76.              node* parent = NULL;
  77.              node* t = root;
  78.  
  79.                 while(t!=NULL && t->data != key){
  80.                     parent = t;
  81.                     if(key<t->data)
  82.                         t = t->left;
  83.                     else if(key> t->data)
  84.                         t = t->right;
  85.                 }
  86.                 if(t==NULL){
  87.                     cout<<"Data Not found"<<endl;
  88.                     return;
  89.                 }
  90.  
  91.                 if(t->left == NULL && t->right == NULL ){
  92.                     if(parent!=NULL){
  93.                         if(parent->left == t)
  94.                             parent->left = NULL;
  95.                         else if(parent->right == t)
  96.                             parent->right = NULL;
  97.                     }
  98.                     else{
  99.                         root = NULL;
  100.                     }
  101.                 }
  102.                 else if(t->left == NULL && t->right != NULL ){
  103.                     if(parent!=NULL){
  104.                             if(parent->left == t)
  105.                                 parent->left = t->right;
  106.                             else if(parent->right == t)
  107.                                 parent->right = t->right;
  108.                     }
  109.                     else{
  110.                         root = t->right;
  111.                     }
  112.                 }
  113.                 else if(t->left != NULL && t->right == NULL ){
  114.                     if(parent!=NULL){
  115.                         if(parent->left == t)
  116.                             parent->left = t->left;
  117.                         else if(parent->right == t)
  118.                             parent->right = t->left;
  119.                     }
  120.                     else{
  121.                         root = t->left;
  122.                     }
  123.                 }
  124.                 else if(t->left != NULL && t->right != NULL ){
  125.                     node* successor = t->right;
  126.                     while(successor->left !=NULL)
  127.                             successor = successor->left;
  128.                     int val = successor->data;
  129.                     deleted(successor->data);
  130.  
  131.                     t->data = val;
  132.                 }
  133.             }
  134. };
  135.  
  136. int main()
  137. {
  138.     bst b;
  139.     b.insert(6);
  140.     b.insert(7);
  141.     b.insert(8);
  142.     b.insert(9);
  143.     b.insert(10);
  144.  
  145.  
  146.    // b.inorder(b.getroot());
  147.     //cout<<"\n";
  148.     b.deleted(10);
  149.     b.postorder(b.getroot());
  150.     cout<<"\n";
  151.     b.deleted(8);
  152.     b.postorder(b.getroot());
  153.     //cout<<"\n";
  154.   //  b.preorder(b.getroot());
  155.     return 0;
  156. }
  157.  

Editor

You can edit this paste and save as new:


File Description
  • code
  • Paste Code
  • 07 Dec-2022
  • 3.57 Kb
You can Share it: