C++ program to print all the elements of AVL tree














































C++ program to print all the elements of AVL tree



#include <iostream>
using namespace std;
struct node
{
int value;
struct node *right;
struct node *left;
int height;
};
class avl
{
public:int height(struct node *y)
{
if(y==NULL)
{
return 0;
}else
{
return y->height;
}
}
int max(int a,int b)
{
if(a>b)
{
return a;
}
return b;
}
struct node *newnode(int data)
{
node *temp=new node();
temp->value=data;
temp->left=temp->right=NULL;
temp->height=1;
return temp;
}
struct node *leftrotate(struct node *y)
{
struct node *x=y->right;
struct node *t2=x->left;
x->left=y;
y->right=t2;
y->height=max(height(y->right),height(y->left))+1;
    x->height=max(height(x->right),height(x->left))+1;
return x;
}
struct node *rightrotate(struct node *x)
{
struct node *y=x->left;
struct node *t2=y->right;
y->right=x;
x->left=t2;
x->height=max(height(x->right),height(x->left))+1;
y->height=max(height(y->right),height(y->left))+1;
return y;
}
int balancefactor(struct node *root)
  {
   if(root==NULL)
  {
   return 0;
  }
   else
   {
    return (height(root->left)-height(root->right));
   }
  }
    struct node* insert(struct node *root,int value)
  {
    if(root==NULL)
    {
     return (newnode(value));
    }
    if(value<root->value)
    {
      root->left=insert(root->left,value);
    }
    else if(value>root->value)
    {
    root->right=insert(root->right,value);
    }
    else
    {
    return root;
    }
  root->height=1+max(height(root->left),height(root->right));
    int balance=balancefactor(root);
    if(balance>1 && value<root->left->value)
    {
     return rightrotate(root);
    }
    if(balance>1 && value>root->left->value)
    {
    root->left=leftrotate(root->left);
     return rightrotate(root);
    }
    if(balance<-1 && value>root->right->value)
    {
     return leftrotate(root);
    }
    if(balance<-1 && value<root->right->value)
    {
    root->right=rightrotate(root->right);
     return leftrotate(root);
    }
    return root;
  }
    void preorder(struct node *root)
  {
   if(root!=NULL)
   {
   cout<<root->value<<" ";
   preorder(root->left);
   preorder(root->right);
   }
  }
  void inorder(struct node *root) 
{ if (root!=NULL) 
{
    inorder(root->left); 
    cout << root->value<< " "; 
    inorder(root->right); 
}
}
void postorder(struct node *root) 
{ 
    if (root!=NULL) 
   { postorder(root->left); 
    postorder(root->right); 
    cout <<root->value<< " "; 
  } 
}
};
int main()
{
   struct node *root=NULL;
     avl T;
    root=T.insert(root,100);
    root=T.insert(root,250);
root=T.insert(root,370);
root=T.insert(root,400);
root=T.insert(root,520);
root=T.insert(root,260);
cout<<"preorder"<<endl;
T.preorder(root);
cout<<endl;
cout<<"inorder"<<endl;
T.inorder(root);
cout<<endl;
cout<<"postorder"<<endl;
T.postorder(root);
return 0;
}
output:
preorder
370 250 100 260 400 520 
inorder
100 250 260 370 400 520 
postorder
100 260 250 520 400 370 

More Articles of Paras Verma:

Name Views Likes
C++ program to calculate (x^n)%1000000007.where 1<=x<=100000 420 19
C++ program to print all the elements of AVL tree 2741 13
C++ program to find an element into AVL tree 2592 12

Comments