Code:
#include iostream
#include cstdio
#include sstream
#include algorithm
#define pow2(n) (1 << (n))
using namespace std;
/*
* Node Declaration
*/
struct avl_node
{
int data;
struct avl_node *left;
struct avl_node *right;
}*root;
/*
* Class Declaration
*/
class avlTree
{
public:
int height(avl_node *);
int diff(avl_node *);
avl_node *rr_rotation(avl_node *);
avl_node *ll_rotation(avl_node *);
avl_node *lr_rotation(avl_node *);
avl_node *rl_rotation(avl_node *);
avl_node* balance(avl_node *);
avl_node* insert(avl_node *, int );
void display(avl_node *, int);
void inorder(avl_node *);
void preorder(avl_node *);
void postorder(avl_node *);
avlTree()
{
root = NULL;
}
};
/*
* Main Contains Menu
*/
int main()
{
int choice, item;
avlTree avl;
while (1)
{
cout<<"\n---------------------"<
cout<<"AVL Tree Implementation"<
cout<<"\n---------------------"<
cout<<"1.Insert Element into the tree"<
cout<<"2.Display Balanced AVL Tree"<
cout<<"3.InOrder traversal"<
cout<<"4.PreOrder traversal"<
cout<<"5.PostOrder traversal"<
cout<<"6.Exit"<
cout<<"Enter your Choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter value to be inserted: ";
cin>>item;
root = avl.insert(root, item);
break;
case 2:
if (root == NULL)
{
cout<<"Tree is Empty"<
continue;
}
cout<<"Balanced AVL Tree:"<
avl.display(root, 1);
break;
case 3:
cout<<"Inorder Traversal:"<
avl.inorder(root);
cout<
break;
case 4:
cout<<"Preorder Traversal:"<
avl.preorder(root);
cout<
break;
case 5:
cout<<"Postorder Traversal:"<
avl.postorder(root);
cout<
break;
case 6:
exit(1);
break;
default:
cout<<"Wrong Choice"<
}
}
return 0;
}
/*
* Height of AVL Tree
*/
int avlTree::height(avl_node *temp)
{
int h = 0;
if (temp != NULL)
{
int l_height = height (temp->left);
int r_height = height (temp->right);
int max_height = max (l_height, r_height);
h = max_height + 1;
}
return h;
}
/*
* Height Difference
*/
int avlTree::diff(avl_node *temp)
{
int l_height = height (temp->left);
int r_height = height (temp->right);
int b_factor= l_height - r_height;
return b_factor;
}
/*
* Right- Right Rotation
*/
avl_node *avlTree::rr_rotation(avl_node *parent)
{
avl_node *temp;
temp = parent->right;
parent->right = temp->left;
temp->left = parent;
return temp;
}
/*
* Left- Left Rotation
*/
avl_node *avlTree::ll_rotation(avl_node *parent)
{
avl_node *temp;
temp = parent->left;
parent->left = temp->right;
temp->right = parent;
return temp;
}
/*
* Left - Right Rotation
*/
avl_node *avlTree::lr_rotation(avl_node *parent)
{
avl_node *temp;
temp = parent->left;
parent->left = rr_rotation (temp);
return ll_rotation (parent);
}
/*
* Right- Left Rotation
*/
avl_node *avlTree::rl_rotation(avl_node *parent)
{
avl_node *temp;
temp = parent->right;
parent->right = ll_rotation (temp);
return rr_rotation (parent);
}
/*
* Balancing AVL Tree
*/
avl_node *avlTree::balance(avl_node *temp)
{
int bal_factor = diff (temp);
if (bal_factor > 1)
{
if (diff (temp->left) > 0)
temp = ll_rotation (temp);
else
temp = lr_rotation (temp);
}
else if (bal_factor < -1)
{
if (diff (temp->right) > 0)
temp = rl_rotation (temp);
else
temp = rr_rotation (temp);
}
return temp;
}
/*
* Insert Element into the tree
*/
avl_node *avlTree::insert(avl_node *root, int value)
{
if (root == NULL)
{
root = new avl_node;
root->data = value;
root->left = NULL;
root->right = NULL;
return root;
}
else if (value < root->data)
{
root->left = insert(root->left, value);
root = balance (root);
}
else if (value >= root->data)
{
root->right = insert(root->right, value);
root = balance (root);
}
return root;
}
/*
* Display AVL Tree
*/
void avlTree::display(avl_node *ptr, int level)
{
int i;
if (ptr!=NULL)
{
display(ptr->right, level + 1);
printf("\n");
if (ptr == root)
cout<<"Root -> ";
for (i = 0; i < level && ptr != root; i++)
cout<<" ";
cout<
display(ptr->left, level + 1);
}
}
/*
* Inorder Traversal of AVL Tree
*/
void avlTree::inorder(avl_node *tree)
{
if (tree == NULL)
return;
inorder (tree->left);
cout<
inorder (tree->right);
}
/*
* Preorder Traversal of AVL Tree
*/
void avlTree::preorder(avl_node *tree)
{
if (tree == NULL)
return;
cout<
preorder (tree->left);
preorder (tree->right);
}
/*
* Postorder Traversal of AVL Tree
*/
void avlTree::postorder(avl_node *tree)
{
if (tree == NULL)
return;
postorder ( tree ->left );
postorder ( tree ->right );
cout<
}
Output:
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 2
Tree is Empty
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 8
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 2
Balanced AVL Tree:
Root -> 8
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 5
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 2
Balanced AVL Tree:
Root -> 8
5
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 4
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 2
Balanced AVL Tree:
8
Root -> 5
4
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 11
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 2
Balanced AVL Tree:
11
8
Root -> 5
4
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 15
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 2
Balanced AVL Tree:
15
11
8
Root -> 5
4
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 3
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 2
Balanced AVL Tree:
15
11
8
Root -> 5
4
3
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 6
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 2
Balanced AVL Tree:
15
11
8
6
Root -> 5
4
3
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 2
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 2
Balanced AVL Tree:
15
11
8
6
Root -> 5
4
3
2
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 4
Preorder Traversal:
5 3 2 4 11 8 6 15
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 5
Postorder Traversal:
2 4 3 6 8 15 11 5
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 3
Inorder Traversal:
2 3 4 5 6 8 11 15
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 2
Balanced AVL Tree:
15
11
8
6
Root -> 5
4
3
2
---------------------
AVL Tree Implementation
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 6
------------------
(program exited with code: 1)
Press return to continue
More C++ Programs:
