Showing posts with label CPP. Show all posts
Showing posts with label CPP. Show all posts

Tuesday, 24 February 2015

Implement of Binary Search Tree(BST) and its Operations in CPP

Here a CPP code to make a BST and perform its all operations.


#include <iostream.h>
class btree
{
 private :
  struct node
  {
   node *left ;
   char data ;
   node *right ;
  } *root ;
  char *arr ;
  int *lc ;
  int *rc ;
 public :
  btree ( char *a, int *l, int *r, int size ) ;
  void insert ( int index ) ;
  static node* buildtree ( char *a, int *l, int *r, int index ) ;
  void display( ) ;
  static void inorder ( node *sr ) ;
  ~btree( ) ;
  static void del ( node *sr ) ;
} ;
btree :: btree ( char *a, int *l, int *r, int size )
{
 root = NULL ;
 arr = new char[size] ;
 lc = new int[size] ;
 rc = new int[size] ;
 for ( int i = 0 ; i < size ; i++ )
 {
  * ( arr + i ) = * ( a + i ) ;
  * ( lc + i ) = * ( l + i ) ;
  * ( rc + i ) = * ( r + i ) ;
 }
}
void btree :: insert ( int index )
{
 root = buildtree ( arr, lc, rc, index ) ;
}
node* btree :: buildtree ( char *a, int *l, int *r, int index )
{
 node *temp = NULL ;
 if ( index != -1 )
 {
  temp = new node ;
  temp -> left = buildtree ( a, l, r, * ( l + index ) ) ;
  temp -> data = * ( a + index ) ;
  temp -> right = buildtree ( a, l, r, * ( r + index ) ) ;
 }
 return temp ;
}
void btree :: display( )
{
 inorder ( root ) ;
}
void btree :: inorder ( node *sr )
{
 if ( sr != NULL )
 {
  inorder ( sr -> left ) ;
  cout << sr -> data << "\t" ;
  inorder ( sr -> right ) ;
 }
}
btree :: ~btree( )
{
 delete arr ;
 delete lc ;
 delete rc ;
 del ( root ) ;
}
void btree :: del ( node *sr )
{
 if ( sr != NULL )
 {
  del ( sr -> left ) ;
  del ( sr -> right ) ;
 }
 delete sr ;
}
void main( )
{
 char a[ ] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0', 'H' } ;
 int  l[ ] = {  1,   3,   5,   -1,   9,  -1,  -1,   -1,   -1,  -1 } ;
 int  r[ ] = {  2,   4,   6,   -1,  -1,  -1,  -1,   -1,   -1,  -1 } ;
 int sz = sizeof ( a ) ;
 btree bt ( a, l, r, sz ) ;
 bt.insert( 0 ) ;
 cout << "\nIn-order Traversal: " << endl ;
 bt.display( ) ;
}

C++ program for creation and traversal of a Binary Tree

A Simple CPP program for creation a binary tree and understand traversal of that tree.


#include<iostream.h>
#include<conio.h>
#include<process.h>
struct tree_node
{
 tree_node *left;
 tree_node *right;
 int data;
} ;
class bst
{
 tree_node *root;
 public:
 bst()
 {
  root=NULL;
 }
 int isempty() 
 {
  return(root==NULL);
 }
 void insert(int item);
 void inordertrav();
 void inorder(tree_node *);
 void postordertrav();
 void postorder(tree_node *);
 void preordertrav();
 void preorder(tree_node *);
};
void bst::insert(int item)
{
 tree_node *p=new tree_node;
 tree_node *parent;
 p->data=item;
 p->left=NULL;
 p->right=NULL;
 parent=NULL;
 if(isempty())
  root=p;
 else
 {
  tree_node *ptr;
  ptr=root;
  while(ptr!=NULL)
  {
   parent=ptr;
   if(item>ptr->data)  
    ptr=ptr->right;
   else
    ptr=ptr->left;
  } 
  if(item<parent->data)
   parent->left=p;
  else
   parent->right=p;
 }
}
void bst::inordertrav()
{
 inorder(root);
}
void bst::inorder(tree_node *ptr)
{
 if(ptr!=NULL)
 {
  inorder(ptr->left);
  cout<<"  "<<ptr->data<<"     ";
  inorder(ptr->right);
 }
}
void bst::postordertrav()
{
 postorder(root);
}
void bst::postorder(tree_node *ptr)
{
 if(ptr!=NULL)
 {
  postorder(ptr->left);
  postorder(ptr->right);
  cout<<"  "<<ptr->data<<"     ";
 }
}
void bst::preordertrav()
{
 preorder(root);
}
void bst::preorder(tree_node *ptr)
{
 if(ptr!=NULL)
 {
  cout<<"  "<<ptr->data<<"     ";
  preorder(ptr->left);
  preorder(ptr->right);
 }
}
void main()
{
 bst b;
 b.insert(52);
 b.insert(25);
 b.insert(50);
 b.insert(15);
 b.insert(40);
 b.insert(45);
 b.insert(20); cout<<"inorder"<<endl;
 b.inordertrav();
 cout<<endl<<"postorder"<<endl;
 b.postordertrav();
 cout<<endl<<"preorder"<<endl;
 b.preordertrav();
 getch();
}