#include <iostream>
using namespace std;
#define SUCCESS 0
#define FAILURE -1
#define DUPLICATE 1
#define SPACE 10
class TreeNode
{
public:
int data;
TreeNode* left;
TreeNode* right;
TreeNode()
{
data = 0;
left = right = NULL;
}
TreeNode( int data )
{
this->data = data;
left = right = NULL;
}
};
class BST
{
public:
TreeNode* root;
BST()
{
root = NULL;
}
bool isEmpty(void)
{
if( root == NULL )
return true;
else
return false;
}
int insertNode( TreeNode* &new_node )
{
if( root == NULL )
{
root = new_node;
cout << "Value Inserted!" << endl;
return SUCCESS;
}
else
{
TreeNode* temp = root;
while( temp != NULL )
{
if( new_node->data == temp->data )
{
cout << "Value already exists!" << endl;
delete new_node;
return DUPLICATE;
}
else if( new_node->data < temp->data && temp->left == NULL)
{
cout << "Value Inserted to the left!" << endl;
temp->left = new_node;
return SUCCESS;
}
else if( new_node->data < temp->data )
temp = temp->left;
else if( new_node->data > temp->data && temp->right == NULL)
{
cout << "Value Inserted to the right!" << endl;
temp->right = new_node;
return SUCCESS;
}
else if( new_node->data > temp->data )
temp = temp->right;
}
}
return FAILURE;
}
TreeNode* insertNodeRecursive( TreeNode* &r, TreeNode* &new_node )
{
if( r == NULL )
{
cout << "Node inserted!" << endl;
r = new_node;
return r;
}
else {
if( new_node->data < r->data )
r->left = insertNodeRecursive( r->left, new_node );
else if( new_node->data > r->data )
r->right = insertNodeRecursive( r->right, new_node );
else
return r;
}
return r;
}
void printPreorder( TreeNode* r )
{
if( r == NULL )
return;
cout << r->data << " ";
printPreorder( r->left );
printPreorder( r->right );
}
void printInorder( TreeNode* r )
{
if( r == NULL )
return;
printInorder( r->left );
cout << r->data << " ";
printInorder( r->right );
}
void printPostorder( TreeNode* r )
{
if( r == NULL )
return;
printPostorder( r->left );
printPostorder( r->right );
cout << r->data << " ";
}
int height( TreeNode* root )
{
if( root == NULL )
return -1;
int lheight = height( root->left );
int rheight = height( root->right );
if( lheight > rheight )
return lheight+1;
else
return rheight+1;
}
void printLevelOrder( TreeNode* root )
{
int h = height( root );
for( int level=0; level<=h; level++ )
{
printGivenLevel( root, level );
}
}
void printGivenLevel( TreeNode* root, int level )
{
if( root == NULL )
return;
if( level == 0 )
{
cout << root->data << " ";
return;
}
printGivenLevel( root->left, level-1 );
printGivenLevel( root->right,level-1 );
}
void print2D(TreeNode * r, int space)
{
if (r == NULL) // Base case 1
return;
space += SPACE; // Increase distance between levels 2
print2D(r->right, space); // Process right child first 3
cout << endl;
for (int i = SPACE; i < space; i++) // 5
cout << " "; // 5.1
cout << r->data << "\n"; // 6
print2D(r->left, space); // Process left child 7
}
bool searchIterative( TreeNode *root, int data )
{
if(root == NULL)
return false;
else
{
while( root != NULL )
{
if( root->data == data )
return true;
else if( data < root->data )
root = root->left;
else if( data > root->data )
root = root->right;
}
return false;
}
}
TreeNode* searchRecursive(TreeNode* &root, int data )
{
if( root == NULL || data == root->data)
return root;
else if( data < root->data )
return searchRecursive( root->left, data );
else
return searchRecursive( root->right, data );
}
TreeNode* findMin( TreeNode* &r )
{
TreeNode* temp = r;
while( temp->left != NULL )
temp = temp->left;
cout << "Mini: " << temp->data << endl;
return temp;
}
TreeNode* deleteNode( TreeNode* &r, int data )
{
if( r == NULL )
return r;
else if( data < r->data )
r->left = deleteNode( r->left, data );
else if( data > r->data )
r->right = deleteNode( r->right, data );
else
{
if( r->left == NULL ) // left NULL
{
TreeNode* temp = r->right;
delete r;
return temp;
}
else if( r->right == NULL ) // right NULL
{
TreeNode* temp = r->left;
delete r;
return temp;
}
else // both child present
{
TreeNode* temp = findMin( r->right );
r->data = temp->data;
r->right = deleteNode( r->right, temp->data );
}
}
return r;
}
};
class AVL : public BST
{
public:
int getBalanceFactor( TreeNode* n )
{
if( n == NULL )
return -1;
return (height(n->left) - height(n->right));
}
TreeNode* rightRotate( TreeNode* &y )
{
TreeNode* x = y->left;
TreeNode* T2 = x->right;
x->right = y;
y->left = T2;
return x;
}
TreeNode* leftRotate( TreeNode* &x )
{
TreeNode* y = x->right;
TreeNode* T2 = y->left;
y->left = x;
x->right = T2;
return y;
}
TreeNode* insertAVL(TreeNode* &r, TreeNode* new_node)
{
if (r == NULL)
{
r = new_node;
cout << "Value inserted successfully" << endl;
return r;
}
if (new_node->data < r->data)
{
r->left = insertAVL(r->left, new_node);
} else if (new_node->data > r->data)
{
r->right = insertAVL(r->right, new_node);
} else
{
cout << "No duplicate values allowed!" << endl;
return r;
}
int bf = getBalanceFactor(r);
if (bf > 1 && new_node->data < r->left->data)
return rightRotate(r);
if (bf < -1 && new_node->data > r->right->data)
return leftRotate(r);
if (bf > 1 && new_node->data > r->left->data) {
r -> left = leftRotate(r -> left);
return rightRotate(r);
}
if (bf < -1 && new_node->data < r->right->data) {
r -> right = rightRotate(r -> right);
return leftRotate(r);
}
return r;
}
TreeNode* deleteAVL( TreeNode* &r, int data )
{
if( r == NULL )
return r;
else if( data < r->data )
r->left = deleteAVL( r->left, data );
else if( data > r->data )
r->right = deleteAVL( r->right, data );
else
{
if( r->left == NULL ) // left NULL
{
TreeNode* temp = r->right;
delete r;
return temp;
}
else if( r->right == NULL ) // right NULL
{
TreeNode* temp = r->left;
delete r;
return temp;
}
else // both child present
{
TreeNode* temp = findMin( r->right );
r->data = temp->data;
r->right = deleteAVL( r->right, temp->data );
}
}
int bf = getBalanceFactor( r );
if (bf == 2 && getBalanceFactor(r->left) >= 0)
return rightRotate(r);
else if (bf == 2 && getBalanceFactor(r->left) == -1)
{
r->left = leftRotate(r->left);
return rightRotate(r);
}
else if (bf == -2 && getBalanceFactor(r->right) <= -0)
return leftRotate(r);
else if (bf == -2 && getBalanceFactor(r->right) == 1) {
r->right = rightRotate(r->right);
return leftRotate(r);
}
return r;
}
};
int main()
{
AVL test;
int option;
do
{
cout << "\nWhat operation do you want to perform? " << endl;
cout << "0. Exit Program" << endl;
cout << "1. Insert Node" << endl;
cout << "2. Search Node" << endl;
cout << "3. Delete Node" << endl;
cout << "4. Print BST Values" << endl;
cout << "5. Clear Screen" << endl;
cin >> option;
if (option == 0)
{
// Option 0: Exit Program
}
else if(option == 1)
{
// Option 1: Insert Node
int data;
cout << "Enter a data: ";
cin >> data;
TreeNode* new_node = new TreeNode(data);
test.root = test.insertAVL( test.root, new_node );
}
else if (option == 2)
{
// Option 2: Search Node
int data;
cout << "Enter data to search: ";
cin >> data;
TreeNode* result = test.searchRecursive( test.root, data );
if( result == NULL)
cout << "Data not found" << endl;
else
cout << "Data present" << endl;
}
else if (option == 3)
{
// Option 3: Delete Node
int data;
cout << "Enter data to delete: ";
cin >> data;
test.root = test.deleteAVL( test.root, data );
}
else if (option == 4)
{
// Option 4: Print BST Values
cout << "Preorder: " << endl;
test.printPreorder(test.root);
cout << endl << endl;
cout << "Inorder: " << endl;
test.printInorder(test.root);
cout << endl << endl;
cout << "Postorder: " << endl;
test.printPostorder(test.root);
cout << endl << endl;
cout << "Level Order: " << endl;
test.printLevelOrder(test.root);
cout << endl << endl;
cout << "Print 2D: " << endl;
test.print2D( test.root, 5 );
cout << endl << endl;
}
else if (option == 5)
{
// Option 5: Clear Screen
system("clear");
}
else
{
// Default: Enter proper option
cout << "Enter proper option!\n" << endl;
}
} while( option != 0 );
}