Code:
#include iostream
#include cstdlib
#include cstring
#include fstream
using namespace std;
/*
* Node Declaration
*/
struct node
{
int count, level;
string key;
node *right;
node *left;
node *parent;
node *root;
}*root;
/*
* Class Declaration
*/
class AATree
{
public:
int lookup(string &);
void skew(node *);
bool split(node *);
void rebal(node *);
node *insert(node *,node *);
void print(node *);
int countnode(node *);
AATree()
{
root = NULL;
}
};
/*
* Main: Contains Menu
*/
int main()
{
AATree at;
int ch;
string x;
ifstream fin ("test.txt");
while (1)
{
cout<<"\n---------------------"<
cout<<"\nOperations on AA Tree"<
cout<<"\n---------------------"<
cout<<"1.Insert String into the Tree"<
cout<<"2.Print Tree Data"<
cout<<"3.Total Tree Nodes"<
cout<<"4.Exit"<
cout<<"Enter Your Choice: ";
cin>>ch;
switch (ch)
{
case 1:
if (fin.is_open())
{
while (fin>>x)
{
at.lookup(x);
}
fin.close();
}
break;
case 2:
cout<<"Elemets of AA Tree"<
at.print(root);
break;
case 3:
cout<<"Total number of nodes"<
cout<
break;
case 4:
cout<<"Exiting"<
exit(1);
break;
default:
cout<<"Wrong Choice"<
}
}
return 0;
}
/*
* Insert String into the Tree
*/
int AATree::lookup(string &key)
{
node *temp = new node;
temp->key = key;
temp->level = 1;
temp->count = 0;
temp->left = NULL;
temp->right = NULL;
temp->parent = NULL;
temp = insert(root, temp);
return temp->count;
}
/*
* Skew Tree
*/
void AATree::skew(node *temp)
{
node *ptr = temp->left;
if (temp->parent->left == temp)
temp->parent->left = ptr;
else
temp->parent->right = ptr;
ptr->parent = temp->parent;
temp->parent = ptr;
temp->left = ptr->right;
if (temp->left != NULL)
temp->left->parent = temp;
ptr->right = temp;
temp->level = (temp->left ? temp->left->level + 1 : 1);
}
/*
* Splitting of AA Tree
*/
bool AATree::split(node *temp)
{
node* ptr = temp->right;
if (ptr && ptr->right && (ptr->right->level == temp->level))
{
if (temp->parent->left == temp)
temp->parent->left = ptr;
else
temp->parent->right = ptr;
ptr->parent = temp->parent;
temp->parent = ptr;
temp->right = ptr->left;
if (temp->right != NULL)
temp->right->parent = temp;
ptr->left = temp;
ptr->level = temp->level + 1;
return true;
}
return false;
}
/*
* Rebalancing of AA Tree
*/
void AATree::rebal(node* temp)
{
temp->left = NULL;
temp->right = NULL;
temp->level = 1;
for (temp = temp->parent; temp != root; temp = temp->parent)
{
if (temp->level != (temp->left ? temp->left->level + 1 : 1 ))
{
skew(temp);
if (temp->right == NULL)
temp = temp->parent;
else if (temp->level != temp->right->level)
temp = temp->parent;
}
if (temp->parent != root)
{
if (split(temp->parent) == false)
break;
}
}
}
/*
* Insert Function to insert string into the tree
*/
node* AATree::insert(node* temp, node* ins)
{
if (root == NULL)
{
ins->count = 1;
ins->parent = NULL;
ins->left = NULL;
ins->right = NULL;
root = ins;
return root;
}
if (ins->key < temp->key)
{
if (temp->left)
return insert(temp->left, ins);
temp->left = ins;
ins->parent = temp;
ins->count = 1;
rebal(ins);
return ins;
}
if (ins->key > temp->key)
{
if (temp->right)
return insert(temp->right, ins);
temp->right = ins;
ins->parent = temp;
ins->count = 1;
rebal(ins);
return ins;
}
temp->count++;
delete ins;
return temp;
}
/*
* Display Tree Elements
*/
void AATree::print(node* temp)
{
if (!temp)
return;
print(temp->left);
cout <<"Value: "<
cout<<" Level: "<
print(temp->right);
}
/*
* Count number of nodes in AA Tree
*/
int AATree::countnode(node* temp)
{
if (!temp)
return 0;
int count = 1;
count = count + countnode(temp->left);
count = count + countnode(temp->right);
return count;
}
Output:
$ g++ aatrees.cpp
$ a.out
test.txt
"1 2 3 4 5 11 22 33 44 55 101 202 303 404 505 1111 2222 3333 4444 5555"
---------------------
Operations on AA Tree
---------------------
1.Insert String into the Tree
2.Print Tree Data
3.Total Tree Nodes
4.Exit
Enter Your Choice: 1
---------------------
Operations on AA Tree
---------------------
1.Insert String into the Tree
2.Print Tree Data
3.Total Tree Nodes
4.Exit
Enter Your Choice: 2
Elemets of AA Tree
Value: 1 Count:1 Level: 1
Value: 101 Count:1 Level: 1
Value: 11 Count:1 Level: 2
Value: 1111 Count:1 Level: 1
Value: 2 Count:1 Level: 3
Value: 202 Count:1 Level: 1
Value: 22 Count:1 Level: 2
Value: 2222 Count:1 Level: 1
Value: 3 Count:1 Level: 4
Value: 303 Count:1 Level: 1
Value: 33 Count:1 Level: 2
Value: 3333 Count:1 Level: 1
Value: 4 Count:1 Level: 3
Value: 404 Count:1 Level: 1
Value: 44 Count:1 Level: 2
Value: 4444 Count:1 Level: 1
Value: 5 Count:1 Level: 3
Value: 505 Count:1 Level: 1
Value: 55 Count:1 Level: 2
Value: 5555 Count:1 Level: 1
---------------------
Operations on AA Tree
---------------------
1.Insert String into the Tree
2.Print Tree Data
3.Total Tree Nodes
4.Exit
Enter Your Choice: 3
Total number of nodes
20
---------------------
Operations on AA Tree
---------------------
1.Insert String into the Tree
2.Print Tree Data
3.Total Tree Nodes
4.Exit
Enter Your Choice: 4
Exiting
------------------
(program exited with code: 1)
Press return to continue
More C++ Programs:
