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.
/*
* C++ Program to Perform Inorder Recursive Traversal of a Given Binary Tree
*/
# include <iostream>
# include <cstdlib>
using namespace std;
/*
* Node Declaration
*/
struct node
{
int info;
struct node *left;
struct node *right;
}*root;
/*
* Class Declaration
*/
class BST
{
public:
void insert(node *, node *);
void inorder(node *);
void display(node *, int);
BST()
{
root = NULL;
}
};
/*
* Main Contains Menu
*/
int main()
{
int choice, num;
BST bst;
node *temp;
while (1)
{
cout<<"-----------------"<<endl;
cout<<"Operations on BST"<<endl;
cout<<"-----------------"<<endl;
cout<<"1.Insert Element "<<endl;
cout<<"2.Inorder Traversal"<<endl;
cout<<"3.Display"<<endl;
cout<<"4.Quit"<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
temp = new node;
cout<<"Enter the number to be inserted : ";
cin>>temp->info;
bst.insert(root, temp);
break;
case 2:
cout<<"Inorder Traversal of BST:"<<endl;
bst.inorder(root);
cout<<endl;
break;
case 3:
cout<<"Display BST:"<<endl;
bst.display(root,1);
cout<<endl;
break;
case 4:
exit(1);
default:
cout<<"Wrong choice"<<endl;
}
}
}
/*
* Inserting Element into the Tree
*/
void BST::insert(node *tree, node *newnode)
{
if (root == NULL)
{
root = new node;
root->info = newnode->info;
root->left = NULL;
root->right = NULL;
cout<<"Root Node is Added"<<endl;
return;
}
if (tree->info == newnode->info)
{
cout<<"Element already in the tree"<<endl;
return;
}
if (tree->info > newnode->info)
{
if (tree->left != NULL)
{
insert(tree->left, newnode);
}
else
{
tree->left = newnode;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
cout<<"Node Added To Left"<<endl;
return;
}
}
else
{
if (tree->right != NULL)
{
insert(tree->right, newnode);
}
else
{
tree->right = newnode;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
cout<<"Node Added To Right"<<endl;
return;
}
}
}
/*
* In Order Traversal
*/
void BST::inorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
inorder(ptr->left);
cout<<ptr->info<<" ";
inorder(ptr->right);
}
}
/*
* Display Tree Structure
*/
void BST::display(node *ptr, int level)
{
int i;
if (ptr != NULL)
{
display(ptr->right, level+1);
cout<<endl;
if (ptr == root)
cout<<"Root->: ";
else
{
for (i = 0;i < level;i++)
cout<<" ";
}
cout<<ptr->info;
display(ptr->left, level+1);
}
}
$ 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
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.
Next Steps:
- Get Free Certificate of Merit in C++ Programming
- Participate in C++ Programming Certification Contest
- Become a Top Ranker in C++ Programming
- Take C++ Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Related Posts:
- Buy C++ Books
- Apply for Computer Science Internship
- Apply for Information Technology Internship
- Practice Programming MCQs
- Apply for C++ Internship