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.

  1. /*
  2. * C++ Program to Implement a Binary Search Tree using Linked Lists
  3.  */
  4. #include <iostream>
  5. using namespace std;
  6. #include <conio.h>
  7. struct tree
  8. {
  9.     tree *l, *r;
  10.     int data;
  11. }*root = NULL, *p = NULL, *np = NULL, *q;
  12.  
  13. void create()
  14. {
  15.     int value,c = 0;   
  16.     while (c < 7)
  17.     {
  18.         if (root == NULL)
  19.         {
  20.             root = new tree;
  21.             cout<<"enter value of root node\n";
  22.             cin>>root->data;
  23.             root->r=NULL;
  24.             root->l=NULL;
  25.         }
  26.         else
  27.         {
  28.             p = root;
  29.             cout<<"enter value of node\n";
  30.             cin>>value;
  31.             while(true)
  32.             {
  33.                 if (value < p->data)
  34.                 {
  35.                     if (p->l == NULL)
  36.                     {
  37.                         p->l = new tree;
  38.                         p = p->l;
  39.                         p->data = value;
  40.                         p->l = NULL;
  41.                         p->r = NULL;
  42.                         cout<<"value entered in left\n";
  43.                         break;
  44.                     }
  45.                     else if (p->l != NULL)
  46.                     {
  47.                         p = p->l;
  48.                     }
  49.                 }
  50.                 else if (value > p->data)
  51.                 {
  52.                     if (p->r == NULL)
  53.                     {
  54.                         p->r = new tree;
  55.                         p = p->r;
  56.                         p->data = value;
  57.                         p->l = NULL;
  58.                         p->r = NULL;
  59.                         cout<<"value entered in right\n";
  60. 		        break;
  61. 		    }
  62.                     else if (p->r != NULL)
  63.                     {
  64.                         p = p->r;
  65.                     }
  66.                  }
  67.              }
  68.         }
  69.         c++;
  70.     }
  71. }
  72. void inorder(tree *p)
  73. {
  74.     if (p != NULL)
  75.     {
  76.         inorder(p->l);
  77.         cout<<p->data<<endl;
  78.         inorder(p->r);
  79.     }
  80. }
  81. void preorder(tree *p)
  82. {
  83.     if (p != NULL)
  84.     {
  85.         cout<<p->data<<endl;
  86.         preorder(p->l);
  87.         preorder(p->r);
  88.     }
  89. }
  90. void postorder(tree *p)
  91. {
  92.     if (p != NULL)
  93.     {
  94.         postorder(p->l);
  95.         postorder(p->r);
  96.         cout<<p->data<<endl;
  97.     }
  98. }
  99. int main()
  100. {
  101.     create();
  102.     cout<<"printing traversal in inorder\n";
  103.     inorder(root);
  104.     cout<<"printing traversal in preorder\n";
  105.     preorder(root);
  106.     cout<<"printing traversal in postorder\n";
  107.     postorder(root);
  108.     getch();
  109. }

advertisement
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.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). 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!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.