C++ Program to Perform Inorder Recursive Traversal of a Given Binary Tree

«
»
This C++ program, using recursion, performs recursive Inorder traversal of a Given Binary Tree.

Here is the source code of the C++ program to perform Inorder Traversal. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Perform Inorder Recursive Traversal of a Given Binary Tree
  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 insert(node *, node *);
  24.         void inorder(node *);
  25.         void display(node *, int);
  26.         BST()
  27.         {
  28.             root = NULL;
  29.         }
  30. };
  31. /*
  32.  * Main Contains Menu
  33.  */
  34. int main()
  35. {
  36.     int choice, num;
  37.     BST bst;
  38.     node *temp;
  39.     while (1)
  40.     {
  41.         cout<<"-----------------"<<endl;
  42.         cout<<"Operations on BST"<<endl;
  43.         cout<<"-----------------"<<endl;
  44.         cout<<"1.Insert Element "<<endl;
  45.         cout<<"2.Inorder Traversal"<<endl;
  46.         cout<<"3.Display"<<endl;
  47.         cout<<"4.Quit"<<endl;
  48.         cout<<"Enter your choice : ";
  49.         cin>>choice;
  50.         switch(choice)
  51.         {
  52.         case 1:
  53.             temp = new node;
  54.             cout<<"Enter the number to be inserted : ";
  55.             cin>>temp->info;
  56.             bst.insert(root, temp);
  57.             break;
  58.         case 2:
  59.             cout<<"Inorder Traversal of BST:"<<endl;
  60.             bst.inorder(root);
  61.             cout<<endl;
  62.             break;
  63.         case 3:
  64.             cout<<"Display BST:"<<endl;
  65.             bst.display(root,1);
  66.             cout<<endl;
  67.             break;
  68.         case 4:
  69.             exit(1);
  70.         default:
  71.             cout<<"Wrong choice"<<endl;
  72.         }
  73.     }
  74. }
  75.  
  76.  
  77. /*
  78.  * Inserting Element into the Tree
  79.  */
  80. void BST::insert(node *tree, node *newnode)
  81. {
  82.     if (root == NULL)
  83.     {
  84.         root = new node;
  85.         root->info = newnode->info;
  86.         root->left = NULL;
  87.         root->right = NULL;
  88.         cout<<"Root Node is Added"<<endl;
  89.         return;
  90.     }
  91.     if (tree->info == newnode->info)
  92.     {
  93.         cout<<"Element already in the tree"<<endl;
  94.         return;
  95.     }
  96.     if (tree->info > newnode->info)
  97.     {
  98.         if (tree->left != NULL)
  99.         {
  100.             insert(tree->left, newnode);
  101.         }
  102.         else
  103.         {
  104.             tree->left = newnode;
  105.             (tree->left)->left = NULL;
  106.             (tree->left)->right = NULL;
  107.             cout<<"Node Added To Left"<<endl;
  108.             return;
  109.         }
  110.     }
  111.     else
  112.     {
  113.         if (tree->right != NULL)
  114.         {
  115.             insert(tree->right, newnode);
  116.         }
  117.         else
  118.         {
  119.             tree->right = newnode;
  120.             (tree->right)->left = NULL;
  121.             (tree->right)->right = NULL;
  122.             cout<<"Node Added To Right"<<endl;
  123.             return;
  124.         }
  125.     }
  126. }
  127.  
  128. /*
  129.  * In Order Traversal
  130.  */
  131. void BST::inorder(node *ptr)
  132. {
  133.     if (root == NULL)
  134.     {
  135.         cout<<"Tree is empty"<<endl;
  136.         return;
  137.     }
  138.     if (ptr != NULL)
  139.     {
  140.         inorder(ptr->left);
  141.         cout<<ptr->info<<"  ";
  142.         inorder(ptr->right);
  143.     }
  144. }
  145.  
  146.  
  147. /*
  148.  * Display Tree Structure
  149.  */
  150. void BST::display(node *ptr, int level)
  151. {
  152.     int i;
  153.     if (ptr != NULL)
  154.     {
  155.         display(ptr->right, level+1);
  156.         cout<<endl;
  157.         if (ptr == root)
  158.             cout<<"Root->:  ";
  159.         else
  160.         {
  161.             for (i = 0;i < level;i++)
  162.                 cout<<"       ";
  163. 	}
  164.         cout<<ptr->info;
  165.         display(ptr->left, level+1);
  166.     }
  167. }

advertisement
$ g++ inorder.cpp
$ a.out
 
-----------------
Operations on BST
-----------------
1.Insert Element
2.Inorder Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 7
Root Node is Added
-----------------
Operations on BST
-----------------
1.Insert Element
2.Inorder Traversal
3.Display
4.Quit
Enter your choice : 3
Display BST:
 
Root->:  7
-----------------
Operations on BST
-----------------
1.Insert Element
2.Inorder Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 3
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element
2.Inorder Traversal
3.Display
4.Quit
Enter your choice : 3
Display BST:
 
Root->:  7
              3
-----------------
Operations on BST
-----------------
1.Insert Element
2.Inorder Traversal
3.Display
4.Quit
Enter your choice : 2
Inorder Traversal of BST:
3  7
-----------------
Operations on BST
-----------------
1.Insert Element
2.Inorder Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 9
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element
2.Inorder Traversal
3.Display
4.Quit
Enter your choice : 3
Display BST:
 
              9
Root->:  7
              3
-----------------
Operations on BST
-----------------
1.Insert Element
2.Inorder Traversal
3.Display
4.Quit
Enter your choice : 2
Inorder Traversal of BST:
3  7  9
-----------------
Operations on BST
-----------------
1.Insert Element
2.Inorder Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 2
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element
2.Inorder Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 1
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element
2.Inorder Traversal
3.Display
4.Quit
Enter your choice : 3
Display BST:
 
              9
Root->:  7
              3
                     2
                            1
-----------------
Operations on BST
-----------------
1.Insert Element
2.Inorder Traversal
3.Display
4.Quit
Enter your choice : 2
Inorder Traversal of BST:
1  2  3  7  9
-----------------
Operations on BST
-----------------
1.Insert Element
2.Inorder Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 8
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element
2.Inorder Traversal
3.Display
4.Quit
Enter your choice : 3
Display BST:
 
              9
                     8
Root->:  7
              3
                     2
                            1
-----------------
Operations on BST
-----------------
1.Insert Element
2.Inorder Traversal
3.Display
4.Quit
Enter your choice : 2
Inorder Traversal of BST:
1  2  3  7  8  9
-----------------
Operations on BST
-----------------
1.Insert Element
2.Inorder Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 11
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element
2.Inorder Traversal
3.Display
4.Quit
Enter your choice : 3
Display BST:
 
                     11
              9
                     8
Root->:  7
              3
                     2
                            1
-----------------
Operations on BST
-----------------
1.Insert Element
2.Inorder Traversal
3.Display
4.Quit
Enter your choice : 2
Inorder Traversal of BST:
1  2  3  7  8  9  11
-----------------
Operations on BST
-----------------
1.Insert Element
2.Inorder Traversal
3.Display
4.Quit
Enter your choice : 4

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

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

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