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---------------------" << endl;
cout << "AVL Tree Implementation" << endl;
cout << "\n---------------------" << endl;
cout << "1.Insert Element into the tree" << endl;
cout << "2.Display Balanced AVL Tree" << endl;
cout << "3.InOrder traversal" << endl;
cout << "4.PreOrder traversal" << endl;
cout << "5.PostOrder traversal" << endl;
cout << "6.Exit" << endl;
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" << endl;
continue;
}
cout << "Balanced AVL Tree:" << endl;
avl.display(root, 1);
break;
case 3:
cout << "Inorder Traversal:" << endl;
avl.inorder(root);
cout << endl;
break;
case 4:
cout << "Preorder Traversal:" << endl;
avl.preorder(root);
cout << endl;
break;
case 5:
cout << "Postorder Traversal:" << endl;
avl.postorder(root);
cout << endl;
break;
case 6:
exit(1);
break;
default:
cout << "Wrong Choice" << endl;
}
}
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;
cout<<"Right-Right Rotation";
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;
cout<<"Left-Left Rotation";
return temp;
}
/*
* Left - Right Rotation
*/
avl_node *avlTree::lr_rotation(avl_node *parent)
{
avl_node *temp;
temp = parent->left;
parent->left = rr_rotation(temp);
cout<<"Left-Right Rotation";
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);
cout<<"Right-Left Rotation";
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 << ptr->data;
display(ptr->left, level + 1);
}
}
/*
* Inorder Traversal of AVL Tree
*/
void avlTree::inorder(avl_node *tree)
{
if (tree == NULL)
return;
inorder(tree->left);
cout << tree->data << " ";
inorder(tree->right);
}
/*
* Preorder Traversal of AVL Tree
*/
void avlTree::preorder(avl_node *tree)
{
if (tree == NULL)
return;
cout << tree->data << " ";
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 << tree->data << " ";
}
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: 1
Enter value to be inserted: 23
---------------------
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:
23
---------------------
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: 45
---------------------
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:
45
Root -> 23
---------------------
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:
23 45
---------------------
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:
23 45
---------------------
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:
45 23
---------------------
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: 37
Left-Left RotationRight-Left RotationRight-Right Rotation
---------------------
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:
------------------
(program exited with code: 0)
Press return to continue
More C++ Programs:
