Go to your University || Python Lab || DSA Lab || AI & Machine Learning Lab || Linux Lab || OOPs Lab || DBMS Lab || JAVA Lab ||| Free Online Tutorials ||| 
companies for Campus Placement || Logical Reasoning || Quantitative Aptitude || General English || Technical-MCQ and Interview Questions || HR Interview Questions

1 Answer

0 like 0 dislike
by (150 points)
/*This program is of creation of AVL Tree for char type data 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<<(char)(ptr->data)<<" ";

   indisplay(ptr->right);

}

void predisplay(struct node *ptr)

{

   if(ptr==NULL)

      return;

   cout<<(char)(ptr->data)<<" ";

   predisplay(ptr->left);

   predisplay(ptr->right);

}

void postdisplay(struct node *ptr)

{

   if(ptr==NULL)

      return;

   postdisplay(ptr->left);

   postdisplay(ptr->right);

   cout<<(char)(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;

}

void main()

{

   int choice;

   char ch='j';

   char 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 ; after last element):";

   while(a!=';')

   {

    cin>>a;

    if(a!=';')

    root=create(root,(int)(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,(int)(a));

   break;

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

      break;

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

     cin>>a;

     if(search(root,int(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,(int)(a));

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

     break;

case 9:

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

     break;

case 10:

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

     break;

case 11:exit(0);

       break;

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

   }

   }while(ch=='j');

}

//ans:- In order : C G I M N O P T U

Online Courses & Fee

  1. AI, ML & Deep Learning - INR 3000/- (80% OFF)
  2. Web development using python (Django) - INR 2000/- (80% OFF)

FREE Online Certification Courses or Tutorials

  1. Python Programming
  2. Machine Learning Using Python
  3. Linux/Unix
  4. Data Structures and Algorithms(DSA)
  5. Database Management System(DBMS)
  6. Object Oriented Programming(OOPs) using C++
  7. Java Programming
  8. C Programming

[[ CALL - 07976731765 ]]

Details

Study Resources

  Realize your learning potential with courses starting at ₹ 420
 Placements:   List of companies | Logical Reasoning Questions | Quantitative Aptitude Questions | General English Questions | Technical-MCQ and Interview Questions
 Online Free Training:  MACHINE LEARNINGPython Programming | Database Management System(DBMS) | Object Oriented Programming(OOPs) using C++ | Data Structures and Algorithms(DSA) | Java Programming | Linux/Unix | C Programming
Exams: List of Exams After Graduation | List of Engineering Entrance Examinations (UG/PG) | JEE Main | JEE Advanced | GATE | IES | ISROList of PSUs
 Download Previous Year Papers For:  GATE | IES | RAJASTHAN TECHNICAL UNIVERSITY (RTU-Kota)RPSC Technical Exams | ISRO
 Goeduhub
About Us | Contact Us   Social::   |  | 
...