spider68

bst implementation

Jul 24th, 2021
835
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. using namespace std;
  3. class tree{
  4.     public:
  5.     int data;
  6.     tree*left;
  7.     tree*right;
  8.     tree(int n){
  9.         data=n;
  10.         left=right=NULL;
  11.     }
  12. };
  13.  
  14. tree*insert(tree*root,int n){
  15.     if(!root)return new tree(n);
  16.     if(root->data==n)return root;
  17.     if(n < root->data)root->left=insert(root->left,n);
  18.     else root->right=insert(root->right,n);
  19. }
  20.  
  21. tree*deletenode(tree*root,int n){
  22.     if(!root)return root;
  23.     if(root->data==n){
  24.         if(root->left==NULL)return root->right;
  25.         else if(root->right==NULL)return root->left;
  26.         else{
  27.             tree*tmp=root->right;
  28.             while(tmp->left){
  29.                 tmp=tmp->left;
  30.             }
  31.             tmp->left=root->left;
  32.             root=root->right;
  33.             return root;
  34.         }
  35.     }
  36.     else if(root->data>n){
  37.         root->left=deletenode(root->left,n);
  38.     }
  39.     else{
  40.         root->right=deletenode(root->right,n);
  41.     }
  42.     return root;
  43. }
  44.  
  45.  
  46. void preorder(tree*root){
  47.     if(!root)return;
  48.     cout<<root->data<<" ";
  49.     preorder(root->left);
  50.     preorder(root->right);
  51. }
  52. void inorder(tree*root){
  53.     if(!root)return;
  54.     inorder(root->left);
  55.     cout<<root->data<<" ";
  56.     inorder(root->right);
  57. }
  58. void postorder(tree*root){
  59.     if(!root)return;
  60.     postorder(root->left);
  61.     postorder(root->right);
  62.     cout<<root->data<<" ";
  63. }
  64. int main(){
  65.     tree*root=NULL;
  66.     root=insert(root,2);
  67.     root=insert(root,5);
  68.     root=insert(root,2);
  69.     root=insert(root,4);
  70.     root=insert(root,9);
  71.     root=insert(root,3);
  72.     root=insert(root,1);
  73.     preorder(root);
  74.     cout<<endl;
  75.     inorder(root);
  76.     cout<<endl;
  77.     postorder(root);
  78.     cout<<endl;
  79.     root=deletenode(root,5);
  80.     preorder(root);
  81.     cout<<endl;
  82.     inorder(root);
  83.     cout<<endl;
  84.     postorder(root);
  85. }
RAW Paste Data