Gadgets 4 Students Career Guide Free Tutorials  Go to Your University  Placement Preparation 
0 like 2 dislike
2.3k views

1 Answer

0 like 0 dislike
by (150 points)
/*This program is of creation of AVL Tree which includes following features:-

1.Create

2.In order

3.Pre order

4.Post order

5.Insert

6.Height of tree

7.Search element

8.Delete element

9.Find minimum

10.Find maximum

#this code is written in turboc++

*/

#include<iostream.h>

#include<conio.h>

#include<alloc.h>

#include<process.h>

struct node

{

  int data;

  struct node* right,*left;

}*root=NULL;

int height(struct node *ptr )

{

     int l,r,h;

     if(ptr==NULL)

return -1;

     else

     {

       l=height(ptr->left);

       r=height(ptr->right);

       h= l>r?l+1:r+1;

     }

     return h;

}

int balance(struct node *ptr)

{

  int l,r,b;

  if(ptr==NULL)

    return 0;

  else

  {

    l=height(ptr->left);

    r=height(ptr->right);

    b=l-r;

  }

  return b;

}

struct node* llrotate(struct node *ptr)

{

   struct node *temp;

   temp=ptr->left;

   ptr->left=temp->right;

   temp->right=ptr;

   return temp;

}

struct node* rrrotate(struct node *ptr)

{

   struct node *temp;

   temp=ptr->right;

   ptr->right=temp->left;

   temp->left=ptr;

   return temp;

}

struct node* lrrotate(struct node *ptr)

{

  struct node *temp;

  temp=ptr->left->right;

  ptr->left->right=temp->left;

  temp->left=ptr->left;

  ptr->left=temp->right;

  temp->right=ptr;

  return temp;

}

struct node* rlrotate(struct node *ptr)

{

  struct node *temp;

  temp=ptr->right->left;

  ptr->right->left=temp->right;

  temp->right=ptr->right;

  ptr->right=temp->left;

  temp->left=ptr;

  return temp;

}

struct node* create(struct node *ptr,int a)

{

    if(ptr==NULL)

    {

struct node *nn;

nn=(struct node*)malloc(sizeof(struct node));

nn->data=a;

nn->right=NULL;

nn->left=NULL;

ptr=nn;

    }

    else

    {

      if((ptr->data)>a)

      {

ptr->left=create(ptr->left,a);

if(balance(ptr)==2)

{

   if(a<ptr->left->data)

   {

     ptr=llrotate(ptr);

   }

   else

   {

     ptr=lrrotate(ptr);

   }

}

      }

      else if(ptr->data==a)

cout<<"element already exist!\n";

      else

      {

ptr->right=create(ptr->right,a);

if(balance(ptr)==-2)

{

   if(a>ptr->right->data)

   {

     ptr=rrrotate(ptr);

   }

   else

   {

     ptr=rlrotate(ptr);

   }

}

      }

    }

    return ptr;

}

struct node* findmin(struct node *ptr)

{

  if(ptr->left)

    return findmin(ptr->left);

  else

    return ptr;

}

struct node* findmax(struct node *ptr)

{

  if(ptr->right)

    return findmax(ptr->right);

  else

    return ptr;

}

struct node* del(struct node *ptr,int a)

{

    if(ptr==NULL)

    {

cout<<"Element not present!!"<<endl;

    }

    else

    {

      if((ptr->data)>a)

      {

ptr->left=del(ptr->left,a);

if(balance(ptr)==-2)

{

   if(ptr->right->right)

   {

     ptr=rrrotate(ptr);

   }

   else

   {

     ptr=rlrotate(ptr);

   }

}

      }

      else if(ptr->data==a)

      {

struct node *temp;

if(ptr->left&&ptr->right)

{

   temp=findmin(ptr->right);

   ptr->data=temp->data;

   ptr->right=del(ptr->right,ptr->data);

}

else

{

   if(ptr->left)

   {

     temp=findmax(ptr->left);

     ptr->data=temp->data;

     ptr->left=del(ptr->left,ptr->data);

   }

   else if(ptr->right)

   {

     temp=findmin(ptr->right);

     ptr->data=temp->data;

     ptr->right=del(ptr->right,ptr->data);

   }

   else

   {

     temp=ptr;

     ptr=NULL;

     free(temp);

   }

}

      }

      else

      {

ptr->right=del(ptr->right,a);

if(balance(ptr)==2)

{

   if(ptr->left->left)

   {

     ptr=llrotate(ptr);

   }

   else

   {

     ptr=lrrotate(ptr);

   }

}

      }

    }

    return ptr;

}

void indisplay(struct node *ptr)

{

   if(ptr==NULL)

      return;

   indisplay(ptr->left);

   cout<<ptr->data<<" ";

   indisplay(ptr->right);

}

void predisplay(struct node *ptr)

{

   if(ptr==NULL)

      return;

   cout<<ptr->data<<" ";

   predisplay(ptr->left);

   predisplay(ptr->right);

}

void postdisplay(struct node *ptr)

{

   if(ptr==NULL)

      return;

   postdisplay(ptr->left);

   postdisplay(ptr->right);

   cout<<ptr->data<<" ";

}

struct node* search(struct node *ptr,int a)

{

    if(ptr==NULL)

      return ptr;

    else if(ptr->data>a)

      return search(ptr->left,a);

    else if(ptr->data<a)

      return search(ptr->right,a);

    return ptr;

}

//ans:- In order : 5 10 12 15 17 19 20 25

void main()

{

   int choice;

   char ch='j';

   int a;

   clrscr();

   cout<<"1.Create\t2.In order\t3.Pre order\t4.Post order\t5.Insert\t6.Height of tree\t7.Search element\t8.Delete element\t9.Find minimum\t10.Find maximum\t11.Exit"<<endl;

   do{

   cout<<"Choose a operation which you want to perform:";

   cin>>choice;

   switch(choice)

   {

case 1:

   cout<<"Enter elements(enter -1 after last element):";

   while(a!=-1)

   {

    cin>>a;

    if(a!=-1)

    root=create(root,a);

   }

   break;

case 2:

   indisplay(root);

   cout<<"\n";

   break;

case 3:

   predisplay(root);

   cout<<"\n";

   break;

case 4:

   postdisplay(root);

   cout<<"\n";

   break;

        case 5:

           cout<<"Enter element which you want to insert:";

           cin>>a;

           root=create(root,a);

           break;

case 6:cout<<"Height of tree = "<<height(root)<<endl;

      break;

case 7:cout<<"Enter element:";

     cin>>a;

     if(search(root,a))

cout<<"Element found"<<endl;

     else

cout<<"Element not found!!"<<endl;

     break;

case 8:

     cout<<"Enter element which you want to delete:";

     cin>>a;

     root=del(root,a);

     cout<<"Deletion successful!!\n";

     break;

case 9:

     cout<<"minimum = "<<(findmin(root)->data)<<"\n";

     break;

case 10:

     cout<<"maximum = "<<(findmax(root)->data)<<"\n";

     break;

case 11:exit(0);

       break;

default:cout<<"Wrong entry\n";

   }

   }while(ch=='j');

}

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.

Best Data Science Courses on Datacamp
Best Data Science Courses on Coursera
Best Data Science Courses on Udemy
Best Data Science Courses on Pluralsight
Best Data Science Courses & Microdegrees on Udacity
Best Artificial Intelligence[AI] Courses on Coursera
Best Machine Learning[ML] Courses on Coursera
Best Python Programming Courses on Coursera
Best Artificial Intelligence[AI] Courses on Udemy
Best Python Programming Courses on Udemy

 Important Lists:

Important Lists, Exams & Cutoffs Exams after Graduation PSUs

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy || Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 

 

Free Online Directory
...