Write a C++ program to implement Binary Search Tree operations using Linked Lists

By | January 8, 2017

C++ program to implement BST operations using Linked Lists

#include<stdlib.h>
#include<iostream>

using namespace std;

struct node
{
  int info;
  struct node *left;
  struct node *right;
};
typedef struct node tree ;
tree *root=NULL;
class BIN
{
  int num;
  tree *p,*prev,*temp;
  public:
  void insert();
  void inorder(tree *);
  void postorder(tree *);
  void preorder(tree *);
  void display();
};
void BIN:: insert()
{
  p=new(tree);
  cout<<"\n Enter  number:";
  cin>>num;
  p->info=num;
  p->left=p->right=NULL;
  if(root==NULL)
  {
    root=p;
    return;
  }
  temp=root;
  while(temp!=NULL)
  {
    if(num>=temp->info)
    {
      prev=temp;
      temp=temp->right;
    }
    else
    {
      prev=temp;
      temp=temp->left;
    }
  }
  if(num>=prev->info)
    prev->right=p;
  else
    prev->left=p;
}
void BIN::preorder(tree *temp)
{
  if(temp!=NULL)
  {
    cout<<" "<<temp->info;
    preorder(temp->left);
    preorder(temp->right);
  }
}
void BIN:: inorder(tree *temp)
{
  if(temp!=NULL)
  {
    inorder(temp->left);
    cout<<" "<<temp->info;
    inorder(temp->right);
  }
}
void  BIN::postorder(tree *temp)
{
  if(temp!=NULL)
  {
    postorder(temp->left);
    postorder(temp->right);
    cout<<" "<<temp->info;
  }
}
void BIN:: display()
{
  if(root==NULL)
  {
    cout<<"\n ***EMPTY TREE**** \n";
    return;
  }
  cout<<"\n\n THE PREORDER DISPLAY IS:   ";
  preorder(root);
  cout<<"\n\n THE INORDER DISPLAY IS:   ";
  inorder(root);
  cout<<"\n\n THE POSTORDER DISPLAY IS:   ";
  postorder(root);
}
int main()
{
  BIN o;
  int ch=1;
  int count=0;
  while(ch)
  {
    cout<<"\n***********MENU***********";
    cout<<"\n1:INSERT-IN-TREE\n2:DISPLAY\n3.QUIT\n";
    cout<<"\nEnter your choice:\n";
    cin>>ch;
    switch(ch)
    {
      case 1:
         count++;
         o.insert();
         break;
      case 2:
      cout<<"\n\n THE NUMBER OF NODES IN THE BST is "<< count;
      o.display();
      break;
      case 3:exit(0);
    }
  }
  return 0;
}

 

OUTPUT ::

 

***********MENU***********
1:INSERT-IN-TREE
2:DISPLAY
3.QUIT

Enter your choice:
1

 Enter  number:1

***********MENU***********
1:INSERT-IN-TREE
2:DISPLAY
3.QUIT

Enter your choice:
1

 Enter  number:2

***********MENU***********
1:INSERT-IN-TREE
2:DISPLAY
3.QUIT

Enter your choice:
1

 Enter  number:3

***********MENU***********
1:INSERT-IN-TREE
2:DISPLAY
3.QUIT

Enter your choice:
1

 Enter  number:4

***********MENU***********
1:INSERT-IN-TREE
2:DISPLAY
3.QUIT

Enter your choice:
2


 THE NUMBER OF NODES IN THE BST is 4

 THE PREORDER DISPLAY IS:    1 2 3 4

 THE INORDER DISPLAY IS:    1 2 3 4

 THE POSTORDER DISPLAY IS:    4 3 2 1
***********MENU***********
1:INSERT-IN-TREE
2:DISPLAY
3.QUIT

Enter your choice:
 3

 

Leave a Reply