C++ Program to Implement Binary Search Tree

«
»
This C++ Program demonstrates operations on Binary Search Tree

Here is source code of the C++ Program to demonstrate Binary Tree. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  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 *, node *);
  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.         case 2:
  68.             if (root == NULL)
  69.             {
  70.                 cout<<"Tree is empty, nothing to delete"<<endl;
  71.                 continue;
  72.             }
  73.             cout<<"Enter the number to be deleted : ";
  74.             cin>>num;
  75.             bst.del(num);
  76.             break;
  77.         case 3:
  78.             cout<<"Inorder Traversal of BST:"<<endl;
  79.             bst.inorder(root);
  80.             cout<<endl;
  81.             break;
  82. 	case 4:
  83.             cout<<"Preorder Traversal of BST:"<<endl;
  84.             bst.preorder(root);
  85.             cout<<endl;
  86.             break;
  87.         case 5:
  88.             cout<<"Postorder Traversal of BST:"<<endl;
  89.             bst.postorder(root);
  90.             cout<<endl;
  91.             break;
  92.         case 6:
  93.             cout<<"Display BST:"<<endl;
  94.             bst.display(root,1);
  95.             cout<<endl;
  96.             break;
  97.         case 7:
  98.             exit(1);
  99.         default:
  100.             cout<<"Wrong choice"<<endl;
  101.         }
  102.     }
  103. }
  104.  
  105. /*
  106.  * Find Element in the Tree
  107.  */
  108. void BST::find(int item, node **par, node **loc)
  109. {
  110.     node *ptr, *ptrsave;
  111.     if (root == NULL)
  112.     {
  113.         *loc = NULL;
  114.         *par = NULL;
  115.         return;
  116.     }
  117.     if (item == root->info)
  118.     {
  119.         *loc = root;
  120.         *par = NULL;
  121.         return;
  122.     }
  123.     if (item < root->info)
  124.         ptr = root->left;
  125.     else
  126.         ptr = root->right;
  127.     ptrsave = root;
  128.     while (ptr != NULL)
  129.     {
  130.         if (item == ptr->info)
  131.         {
  132.             *loc = ptr;
  133.             *par = ptrsave;
  134.             return;
  135.         }
  136.         ptrsave = ptr;
  137.         if (item < ptr->info)
  138.             ptr = ptr->left;
  139. 	else
  140. 	    ptr = ptr->right;
  141.     }
  142.     *loc = NULL;
  143.     *par = ptrsave;
  144. }
  145.  
  146. /*
  147.  * Inserting Element into the Tree
  148.  */
  149. void BST::insert(node *tree, node *newnode)
  150. {
  151.     if (root == NULL)
  152.     {
  153.         root = new node;
  154.         root->info = newnode->info;
  155.         root->left = NULL;
  156.         root->right = NULL;
  157.         cout<<"Root Node is Added"<<endl;
  158.         return;
  159.     }
  160.     if (tree->info == newnode->info)
  161.     {
  162.         cout<<"Element already in the tree"<<endl;
  163.         return;
  164.     }
  165.     if (tree->info > newnode->info)
  166.     {
  167.         if (tree->left != NULL)
  168.         {
  169.             insert(tree->left, newnode);	
  170. 	}
  171. 	else
  172. 	{
  173.             tree->left = newnode;
  174.             (tree->left)->left = NULL;
  175.             (tree->left)->right = NULL;
  176.             cout<<"Node Added To Left"<<endl;
  177.             return;
  178.         }
  179.     }
  180.     else
  181.     {
  182.         if (tree->right != NULL)
  183.         {
  184.             insert(tree->right, newnode);
  185.         }
  186.         else
  187.         {
  188.             tree->right = newnode;
  189.             (tree->right)->left = NULL;
  190.             (tree->right)->right = NULL;
  191.             cout<<"Node Added To Right"<<endl;
  192.             return;
  193.         }	
  194.     }
  195. }
  196.  
  197. /*
  198.  * Delete Element from the tree
  199.  */
  200. void BST::del(int item)
  201. {
  202.     node *parent, *location;
  203.     if (root == NULL)
  204.     {
  205.         cout<<"Tree empty"<<endl;
  206.         return;
  207.     }
  208.     find(item, &parent, &location);
  209.     if (location == NULL)
  210.     {
  211.         cout<<"Item not present in tree"<<endl;
  212.         return;
  213.     }
  214.     if (location->left == NULL && location->right == NULL)
  215.         case_a(parent, location);
  216.     if (location->left != NULL && location->right == NULL)
  217.         case_b(parent, location);
  218.     if (location->left == NULL && location->right != NULL)
  219.         case_b(parent, location);
  220.     if (location->left != NULL && location->right != NULL)
  221.         case_c(parent, location);
  222.     free(location);
  223. }
  224.  
  225. /*
  226.  * Case A
  227.  */
  228. void BST::case_a(node *par, node *loc )
  229. {
  230.     if (par == NULL)
  231.     {
  232.         root = NULL;
  233.     }
  234.     else
  235.     {
  236.         if (loc == par->left)
  237.             par->left = NULL;
  238.         else
  239.             par->right = NULL;
  240.     }
  241. }
  242.  
  243. /*
  244.  * Case B
  245.  */
  246. void BST::case_b(node *par, node *loc)
  247. {
  248.     node *child;
  249.     if (loc->left != NULL)
  250.         child = loc->left;
  251.     else
  252.         child = loc->right;
  253.     if (par == NULL)
  254.     {
  255.         root = child;
  256.     }
  257.     else
  258.     {
  259.         if (loc == par->left)
  260.             par->left = child;
  261.         else
  262.             par->right = child;
  263.     }
  264. }
  265.  
  266. /*
  267.  * Case C
  268.  */
  269. void BST::case_c(node *par, node *loc)
  270. {
  271.     node *ptr, *ptrsave, *suc, *parsuc;
  272.     ptrsave = loc;
  273.     ptr = loc->right;
  274.     while (ptr->left != NULL)
  275.     {
  276.         ptrsave = ptr;
  277.         ptr = ptr->left;
  278.     }
  279.     suc = ptr;
  280.     parsuc = ptrsave;
  281.     if (suc->left == NULL && suc->right == NULL)
  282.         case_a(parsuc, suc);
  283.     else
  284.         case_b(parsuc, suc);
  285.     if (par == NULL)
  286.     {
  287.         root = suc;
  288.     }
  289.     else
  290.     {
  291.         if (loc == par->left)
  292.             par->left = suc;
  293.         else
  294.             par->right = suc;
  295.     }
  296.     suc->left = loc->left;
  297.     suc->right = loc->right;
  298. }
  299.  
  300. /*
  301.  * Pre Order Traversal
  302.  */
  303. void BST::preorder(node *ptr)
  304. {
  305.     if (root == NULL)
  306.     {
  307.         cout<<"Tree is empty"<<endl;
  308.         return;
  309.     }
  310.     if (ptr != NULL)
  311.     {
  312.         cout<<ptr->info<<"  ";
  313.         preorder(ptr->left);
  314.         preorder(ptr->right);
  315.     }
  316. }
  317. /*
  318.  * In Order Traversal
  319.  */
  320. void BST::inorder(node *ptr)
  321. {
  322.     if (root == NULL)
  323.     {
  324.         cout<<"Tree is empty"<<endl;
  325.         return;
  326.     }
  327.     if (ptr != NULL)
  328.     {
  329.         inorder(ptr->left);
  330.         cout<<ptr->info<<"  ";
  331.         inorder(ptr->right);
  332.     }
  333. }
  334.  
  335. /*
  336.  * Postorder Traversal
  337.  */
  338. void BST::postorder(node *ptr)
  339. {
  340.     if (root == NULL)
  341.     {
  342.         cout<<"Tree is empty"<<endl;
  343.         return;
  344.     }
  345.     if (ptr != NULL)
  346.     {
  347.         postorder(ptr->left);
  348.         postorder(ptr->right);
  349.         cout<<ptr->info<<"  ";
  350.     }
  351. }
  352.  
  353. /*
  354.  * Display Tree Structure
  355.  */
  356. void BST::display(node *ptr, int level)
  357. {
  358.     int i;
  359.     if (ptr != NULL)
  360.     {
  361.         display(ptr->right, level+1);
  362.         cout<<endl;
  363.         if (ptr == root)
  364.             cout<<"Root->:  ";
  365.         else
  366.         {
  367.             for (i = 0;i < level;i++)
  368.                 cout<<"       ";
  369. 	}
  370.         cout<<ptr->info;
  371.         display(ptr->left, level+1);
  372.     }
  373. }

advertisement
$ g++ bst.cpp
$ a.out
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 8
Root Node is Added
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
Root->:  8
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 9
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
              9
Root->:  8
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 5
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
              9
Root->:  8
              5
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 11
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
                     11
              9
Root->:  8
              5
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 3 
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 7
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
                     11
              9
Root->:  8
                     7
              5
                     3
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 10
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
                     11
                            10
              9
Root->:  8
                     7
              5
                     3
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 2
Enter the number to be deleted : 10
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
                     11
              9
Root->:  8
                     7
              5
                     3
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 3
Inorder Traversal of BST:
3  5  7  8  9  11  
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 4
Preorder Traversal of BST:
8  5  3  7  9  11  
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 5
Postorder Traversal of BST:
3  7  5  11  9  8  
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 2
Enter the number to be deleted : 8
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
              11
Root->:  9
                     7
              5
                     3
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 10
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
              11
                     10
Root->:  9
                     7
              5
                     3
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 15
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
                     15
              11
                     10
Root->:  9
                     7
              5
                     3
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 4
Preorder Traversal of BST:
9  5  3  7  11  10  15  
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 5
Postorder Traversal of BST:
3  7  5  10  15  11  9  
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
                     15
              11
                     10
Root->:  9
                     7
              5
                     3
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 7
 
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn