**C++ only no c codes please!! ** Procedural code if possible **I will be using
ID: 3691267 • Letter: #
Question
**C++ only no c codes please!!
** Procedural code if possible
**I will be using Visual Studio
** Please add comments to functions if possible and please include header file info if used!!
Develop a C++ program that will recursively alphabetize a set of strings in a user-specified file using the tree sort algorithm explained in the lectures whilemaintaining a balanced binary tree at all times.The instructor will test your program with an input file containing:
Max Hank Jet Frisky Chata Richard Nan Sam Thomas Karen Gerri Ingrid Alan Dana
When done print out the contents of the tree in inorder in a tabular format similar to the following:
Explanation / Answer
Code:
#include<iostream>
#include<cstdio>
#include<sstream>
#include<algorithm>
#include<string>
#define pow2(n) (1 << (n))
using namespace std;
struct node
{
string data;
struct node *lft;
struct node *rght;
}*root;
class avl
{
public:
int theight(node *);
int dif(node *);
node *rr_rot(node *);
node *ll_rot(node *);
node *lr_rot(node *);
node *rl_rot(node *);
node* bal(node *);
node* insrt(node *, string );
void display(node *, int);
void inor(node *);
avl()
{
root = NULL;
}
};
int main()
{
int ch;
string item;
avl avl;
while (1)
{
cout<<"1.Insert Element "<<endl;
cout<<"2.Display AVL Tree"<<endl;
cout<<"3.InOrder traversal"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Enter choice: ";
cin>>ch;
switch(ch)
{
case 1:
cout<<"Enter value : ";
cin>>item;
root = avl.insrt(root, item);
break;
case 2:
if (root == NULL)
{
cout<<"Empty Tree"<<endl;
continue;
}
cout<<"AVL Tree:"<<endl;
avl.display(root, 1);
break;
case 3:
cout<<"Inorder Traversal:"<<endl;
avl.inor(root);
cout<<endl;
break;
case 4:
exit(1);
break;
default:
cout<<"Wrong Choice"<<endl;
}
}
return 0;
}
/* Height of AVL Tree*/
int avl::theight(node *temp1)
{
int h = 0;
if (temp1 != NULL)
{
int l_height = theight (temp1->lft);
int r_height = theight (temp1->rght);
int max_height = max (l_height, r_height);
h = max_height + 1;
}
return h;
}
/* Finding balance factor of node */
int avl::dif(node *temp1)
{
int l_height = theight (temp1->lft);
int r_height = theight (temp1->rght);
int balfact= l_height - r_height;
return balfact;
}
/* Right- Right Rotation of AVL Tree*/
node *avl::rr_rot(node *tparent)
{
node *temp1;
temp1 = tparent->rght;
tparent->rght = temp1->lft;
temp1->lft = tparent;
return temp1;
}
/*Left- Left Rotation of AVL Tree*/
node *avl::ll_rot(node *tparent)
{
node *temp1;
temp1 = tparent->lft;
tparent->lft = temp1->rght;
temp1->rght = tparent;
return temp1;
}
/* Left - Right Rotation of AVL Tree */
node *avl::lr_rot(node *tparent)
{
node *temp1;
temp1 = tparent->lft;
tparent->lft = rr_rot (temp1);
return ll_rot (tparent);
}
/*Right- Left Rotation of AVL Tree*/
node *avl::rl_rot(node *tparent)
{
node *temp1;
temp1 = tparent->rght;
tparent->rght = ll_rot (temp1);
return rr_rot (tparent);
}
/*AVL Tree Balancing*/
node *avl::bal(node *temp1)
{
int bal_factor = dif (temp1);
if (bal_factor > 1)
{
if (dif (temp1->lft) > 0)
temp1 = ll_rot (temp1);
else
temp1 = lr_rot (temp1);
}
else if (bal_factor < -1)
{
if (dif (temp1->rght) > 0)
temp1 = rl_rot (temp1);
else
temp1 = rr_rot (temp1);
}
return temp1;
}
/*Insertion of values*/
node *avl::insrt(node *root, string value)
{
if (root == NULL)
{
root = new node;
root->data = value;
root->lft = NULL;
root->rght = NULL;
return root;
}
else if (value < root->data)
{
root->lft = insrt(root->lft, value);
root = bal (root);
}
else if (value >= root->data)
{
root->rght = insrt(root->rght, value);
root = bal (root);
}
return root;
}
/* Display of the AVL Tree*/
void avl::display(node *ptr, int level)
{
int i;
if (ptr!=NULL)
{
display(ptr->rght, level + 1);
printf(" ");
if (ptr == root)
cout<<"Root -> ";
for (i = 0; i < level && ptr != root; i++)
cout<<" ";
cout<<ptr->data;
display(ptr->lft, level + 1);
}
}
/*Inorder Traversal of the AVL Tree*/
void avl::inor(node *tre)
{
if (tre == NULL)
return;
inor (tre->lft);
cout<<tre->data<<" "<<theight(tre)<<endl;
inor (tre->rght);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.