This C++ program, displays the traversal of a binary search tree in inorder,postorder and preorder mode using linked lists. A linked list is an ordered set of data elements, each containing a link to its successor.
Here is the source code of the C++ program which takes the value of root node and consecutively all other nodes as input and generates a binary search tree on the basis of the values of these nodes(all distinct). This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is also shown below.
/*
* C++ Program to Implement a Binary Search Tree using Linked Lists
*/
#include <iostream>
using namespace std;
#include <conio.h>
struct tree
{
tree *l, *r;
int data;
}*root = NULL, *p = NULL, *np = NULL, *q;
void create()
{
int value,c = 0;
while (c < 7)
{
if (root == NULL)
{
root = new tree;
cout<<"enter value of root node\n";
cin>>root->data;
root->r=NULL;
root->l=NULL;
}
else
{
p = root;
cout<<"enter value of node\n";
cin>>value;
while(true)
{
if (value < p->data)
{
if (p->l == NULL)
{
p->l = new tree;
p = p->l;
p->data = value;
p->l = NULL;
p->r = NULL;
cout<<"value entered in left\n";
break;
}
else if (p->l != NULL)
{
p = p->l;
}
}
else if (value > p->data)
{
if (p->r == NULL)
{
p->r = new tree;
p = p->r;
p->data = value;
p->l = NULL;
p->r = NULL;
cout<<"value entered in right\n";
break;
}
else if (p->r != NULL)
{
p = p->r;
}
}
}
}
c++;
}
}
void inorder(tree *p)
{
if (p != NULL)
{
inorder(p->l);
cout<<p->data<<endl;
inorder(p->r);
}
}
void preorder(tree *p)
{
if (p != NULL)
{
cout<<p->data<<endl;
preorder(p->l);
preorder(p->r);
}
}
void postorder(tree *p)
{
if (p != NULL)
{
postorder(p->l);
postorder(p->r);
cout<<p->data<<endl;
}
}
int main()
{
create();
cout<<"printing traversal in inorder\n";
inorder(root);
cout<<"printing traversal in preorder\n";
preorder(root);
cout<<"printing traversal in postorder\n";
postorder(root);
getch();
}
Output enter value of root node 7 enter value of node 8 value entered in right enter value of node 4 value entered in left enter value of node 6 value entered in right enter value of node 3 value entered in left enter value of node 5 value entered in left enter value of node 2 value entered in left printing traversal in inorder 2 3 4 5 6 7 8 printing traversal in preorder 7 4 3 2 6 5 8 printing traversal in postorder 2 3 5 6 4 8 7
Sanfoundry Global Education & Learning Series – 1000 C++ Programs.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.
Next Steps:
- Get Free Certificate of Merit in Data Structure I
- Participate in Data Structure I Certification Contest
- Become a Top Ranker in Data Structure I
- Take Data Structure I 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:
- Practice Computer Science MCQs
- Apply for Data Structure Internship
- Buy Programming Books
- Apply for Information Technology Internship
- Practice Programming MCQs