Friday, December 2, 2011

Binary Search Tree using C++

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
int flag=0;
int l=0,r=0;

typedef struct node  {
    struct node *left;
    int val;
    struct node *right;
}tree;

tree *root,*t,*temp,*max;

tree *insert(tree *t,int k) {

   if(flag==0) {
      root=new tree;
      root->val=k;
      root->left=NULL;
      root->right=NULL;
      flag=1;
   }
   else {
       if(t==NULL) {
         t=new tree;
         t->val=k;
         t->left=NULL;
         t->right=NULL;
       }
       else if(k==t->val)
              cout<<"Already present..\n";
       else if(k>t->val)
              t->right=insert(t->right,k);
       else
              t->left=insert(t->left,k);
   }
   return t;
}


void inorder(tree *t) {
      if(t->left!=NULL)
         inorder(t->left);
      cout<<t->val<<" ";
      if(t->right!=NULL)
         inorder(t->right);
}

void preorder(tree *t) {
     cout<<t->val<<" ";
     if(t->left!=NULL)
          preorder(t->left);
     if(t->right!=NULL)
          preorder(t->right);
}

void postorder(tree *t) {
     if(t->left!=NULL)
        postorder(t->left);
     if(t->right!=NULL)
        postorder(t->right);
     cout<<t->val<<" ";
}

int height(tree *t)  {
  if(t->left!=NULL) {
       l++;
       height(t->left);
  }
  if(t->right!=NULL) {
       r++;
       height(t->right);
  }
  return (l>r?l:r)
}

void mirror(tree *t) {
     if(t==NULL)
         return;
     mirror(t->left);
     mirror(t->right);
     temp=t->left;
     t->left=t->right;
     t->right=temp;
}

void findmax(tree *t) {
  /*for normal binary trees*/
  if(t) {
     if(t->val > max->val)
        max=t;
     findmax(t->left);
     findmax(t->right);
  }
}

void main() {
   clrscr();
   int k=0;
   do {
       cout<<"Enter value:";
       cin>>k;
       if(k)
          t=insert(root,k);
   }while(k!=0);

   cout<<"Preorder:";
   preorder(root);
   cout<<"\nInorder:";
   inorder(root);
   cout<<"\nPostorder:";
   postorder(root);
   cout<<"\nHeight:"<<height(root);
   cout<<"\nBalance factor : "<<(abs(l-r));
   mirror(root);
   cout<<"\nMirror tree:";
   inorder(root);
   max=root;
   findmax(root);
   cout<<"\nMax value : "<<max->val;
   getch();
}

No comments:

Post a Comment