Advertisement
wa12rior

bst

May 28th, 2022
425
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  * C++ Program To Implement BST
  3.  */
  4. # include <iostream>
  5. # include <cstdlib>
  6. using namespace std;
  7. /*
  8.  * Node Declaration
  9.  */
  10. struct node
  11. {
  12.     int info;
  13.     struct node *left;
  14.     struct node *right;
  15. }*root;
  16.  
  17. /*
  18.  * Class Declaration
  19.  */
  20. class BST
  21. {
  22.     public:
  23.         void find(int, node **, node **);    
  24.         void insert(node *tree, node *newnode);
  25.         void del(int);
  26.         void case_a(node *,node *);
  27.         void case_b(node *,node *);
  28.         void case_c(node *,node *);
  29.         void preorder(node *);
  30.         void inorder(node *);
  31.         void postorder(node *);
  32.         void display(node *, int);
  33.         BST()
  34.         {
  35.             root = NULL;
  36.         }
  37. };
  38. /*
  39.  * Main Contains Menu
  40.  */
  41. int main()
  42. {
  43.     int choice, num;
  44.     BST bst;
  45.     node *temp;
  46.     while (1)
  47.     {
  48.         cout<<"-----------------"<<endl;
  49.         cout<<"Operations on BST"<<endl;
  50.         cout<<"-----------------"<<endl;
  51.         cout<<"1.Insert Element "<<endl;
  52.         cout<<"2.Delete Element "<<endl;
  53.         cout<<"3.Inorder Traversal"<<endl;
  54.         cout<<"4.Preorder Traversal"<<endl;
  55.         cout<<"5.Postorder Traversal"<<endl;
  56.         cout<<"6.Display"<<endl;
  57.         cout<<"7.Quit"<<endl;
  58.         cout<<"Enter your choice : ";
  59.         cin>>choice;
  60.         switch(choice)
  61.         {
  62.         case 1:
  63.             temp = new node;
  64.             cout<<"Enter the number to be inserted : ";
  65.             cin>>temp->info;
  66.             bst.insert(root, temp);
  67.             break;
  68.         case 2:
  69.             if (root == NULL)
  70.             {
  71.                 cout<<"Tree is empty, nothing to delete"<<endl;
  72.                 continue;
  73.             }
  74.             in:cout<<"Enter the number to be deleted : ";
  75.             cin>>num;
  76.             bst.del(num);
  77.             break;
  78.         case 3:
  79.             cout<<"Inorder Traversal of BST:"<<endl;
  80.             bst.inorder(root);
  81.             cout<<endl;
  82.             break;
  83.     case 4:
  84.             cout<<"Preorder Traversal of BST:"<<endl;
  85.             bst.preorder(root);
  86.             cout<<endl;
  87.             break;
  88.         case 5:
  89.             cout<<"Postorder Traversal of BST:"<<endl;
  90.             bst.postorder(root);
  91.             cout<<endl;
  92.             break;
  93.         case 6:
  94.             cout<<"Display BST:"<<endl;
  95.             bst.display(root,1);
  96.             cout<<endl;
  97.             break;
  98.         case 7:
  99.             exit(1);
  100.         default:
  101.             cout<<"Wrong choice"<<endl;
  102.         }
  103.     }
  104. }
  105.  
  106. /*
  107.  * Find Element in the Tree
  108.  */
  109. void BST::find(int item, node **par, node **loc)
  110. {
  111.     node *ptr, *ptrsave;
  112.     if (root == NULL)
  113.     {
  114.         *loc = NULL;
  115.         *par = NULL;
  116.         return;
  117.     }
  118.     if (item == root->info)
  119.     {
  120.         *loc = root;
  121.         *par = NULL;
  122.         return;
  123.     }
  124.     if (item < root->info)
  125.         ptr = root->left;
  126.     else
  127.         ptr = root->right;
  128.     ptrsave = root;
  129.     while (ptr != NULL)
  130.     {
  131.         if (item == ptr->info)
  132.         {
  133.             *loc = ptr;
  134.             *par = ptrsave;
  135.             return;
  136.         }
  137.         ptrsave = ptr;
  138.         if (item < ptr->info)
  139.             ptr = ptr->left;
  140.     else
  141.         ptr = ptr->right;
  142.     }
  143.     *loc = NULL;
  144.     *par = ptrsave;
  145. }
  146.  
  147. /*
  148.  * Inserting Element into the Tree
  149.  */
  150. void BST::insert(node *tree, node *newnode)
  151. {
  152.     if (root == NULL)
  153.     {
  154.         root = new node;
  155.         root->info = newnode->info;
  156.         root->left = NULL;
  157.         root->right = NULL;
  158.         cout<<"Root Node is Added"<<endl;
  159.         return;
  160.     }
  161.     if (tree->info == newnode->info)
  162.     {
  163.         cout<<"Element already in the tree"<<endl;
  164.         return;
  165.     }
  166.     if (tree->info > newnode->info)
  167.     {
  168.         if (tree->left != NULL)
  169.         {
  170.             insert(tree->left, newnode);   
  171.     }
  172.     else
  173.     {
  174.             tree->left = newnode;
  175.             (tree->left)->left = NULL;
  176.             (tree->left)->right = NULL;
  177.             cout<<"Node Added To Left"<<endl;
  178.             return;
  179.         }
  180.     }
  181.     else
  182.     {
  183.         if (tree->right != NULL)
  184.         {
  185.             insert(tree->right, newnode);
  186.         }
  187.         else
  188.         {
  189.             tree->right = newnode;
  190.             (tree->right)->left = NULL;
  191.             (tree->right)->right = NULL;
  192.             cout<<"Node Added To Right"<<endl;
  193.             return;
  194.         }  
  195.     }
  196. }
  197.  
  198. /*
  199.  * Delete Element from the tree
  200.  */
  201. void BST::del(int item)
  202. {
  203.     node *parent, *location;
  204.     if (root == NULL)
  205.     {
  206.         cout<<"Tree empty"<<endl;
  207.         return;
  208.     }
  209.     find(item, &parent, &location);
  210.     if (location == NULL)
  211.     {
  212.         cout<<"Item not present in tree"<<endl;
  213.         return;
  214.     }
  215.     if (location->left == NULL && location->right == NULL)
  216.         case_a(parent, location);
  217.     if (location->left != NULL && location->right == NULL)
  218.         case_b(parent, location);
  219.     if (location->left == NULL && location->right != NULL)
  220.         case_b(parent, location);
  221.     if (location->left != NULL && location->right != NULL)
  222.         case_c(parent, location);
  223.     free(location);
  224. }
  225.  
  226. /*
  227.  * Case A
  228.  */
  229. void BST::case_a(node *par, node *loc )
  230. {
  231.     if (par == NULL)
  232.     {
  233.         root = NULL;
  234.     }
  235.     else
  236.     {
  237.         if (loc == par->left)
  238.             par->left = NULL;
  239.         else
  240.             par->right = NULL;
  241.     }
  242. }
  243.  
  244. /*
  245.  * Case B
  246.  */
  247. void BST::case_b(node *par, node *loc)
  248. {
  249.     node *child;
  250.     if (loc->left != NULL)
  251.         child = loc->left;
  252.     else
  253.         child = loc->right;
  254.     if (par == NULL)
  255.     {
  256.         root = child;
  257.     }
  258.     else
  259.     {
  260.         if (loc == par->left)
  261.             par->left = child;
  262.         else
  263.             par->right = child;
  264.     }
  265. }
  266.  
  267. /*
  268.  * Case C
  269.  */
  270. void BST::case_c(node *par, node *loc)
  271. {
  272.     node *ptr, *ptrsave, *suc, *parsuc;
  273.     ptrsave = loc;
  274.     ptr = loc->right;
  275.     while (ptr->left != NULL)
  276.     {
  277.         ptrsave = ptr;
  278.         ptr = ptr->left;
  279.     }
  280.     suc = ptr;
  281.     parsuc = ptrsave;
  282.     if (suc->left == NULL && suc->right == NULL)
  283.         case_a(parsuc, suc);
  284.     else
  285.         case_b(parsuc, suc);
  286.     if (par == NULL)
  287.     {
  288.         root = suc;
  289.     }
  290.     else
  291.     {
  292.         if (loc == par->left)
  293.             par->left = suc;
  294.         else
  295.             par->right = suc;
  296.     }
  297.     suc->left = loc->left;
  298.     suc->right = loc->right;
  299. }
  300.  
  301. /*
  302.  * Pre Order Traversal
  303.  */
  304. void BST::preorder(node *ptr)
  305. {
  306.     if (root == NULL)
  307.     {
  308.         cout<<"Tree is empty"<<endl;
  309.         return;
  310.     }
  311.     if (ptr != NULL)
  312.     {
  313.         cout<<ptr->info<<"  ";
  314.         preorder(ptr->left);
  315.         preorder(ptr->right);
  316.     }
  317. }
  318. /*
  319.  * In Order Traversal
  320.  */
  321. void BST::inorder(node *ptr)
  322. {
  323.     if (root == NULL)
  324.     {
  325.         cout<<"Tree is empty"<<endl;
  326.         return;
  327.     }
  328.     if (ptr != NULL)
  329.     {
  330.         inorder(ptr->left);
  331.         cout<<ptr->info<<"  ";
  332.         inorder(ptr->right);
  333.     }
  334. }
  335.  
  336. /*
  337.  * Postorder Traversal
  338.  */
  339. void BST::postorder(node *ptr)
  340. {
  341.     if (root == NULL)
  342.     {
  343.         cout<<"Tree is empty"<<endl;
  344.         return;
  345.     }
  346.     if (ptr != NULL)
  347.     {
  348.         postorder(ptr->left);
  349.         postorder(ptr->right);
  350.         cout<<ptr->info<<"  ";
  351.     }
  352. }
  353.  
  354. /*
  355.  * Display Tree Structure
  356.  */
  357. void BST::display(node *ptr, int level)
  358. {
  359.     int i;
  360.     if (ptr != NULL)
  361.     {
  362.         display(ptr->right, level+1);
  363.         cout<<endl;
  364.         if (ptr == root)
  365.             cout<<"Root->:  ";
  366.         else
  367.         {
  368.             for (i = 0;i < level;i++)
  369.                 cout<<"       ";
  370.     }
  371.         cout<<ptr->info;
  372.         display(ptr->left, level+1);
  373.     }
  374. }
Advertisement
RAW Paste Data Copied
Advertisement