C++ Program to Implement a Binary Search Tree using Linked Lists

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


/*
* 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 noden";
cin>>root->data;
root->r=NULL;
root->l=NULL;
}
else
{
p = root;
cout<<"enter value of noden";
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 leftn";
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 rightn";
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 inordern";
inorder(root);
cout<<"printing traversal in preordern";
preorder(root);
cout<<"printing traversal in postordern";
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
Post a Comment