In c++ how do you 1. Declare a class WordNode to store a word and its frequency.
ID: 3771862 • Letter: I
Question
In c++ how do you
1. Declare a class WordNode to store a word and its frequency. You need store the words in a binary tree, so this class will have two pointers to the left and right WordNode. Then, implement a constructor for class WordNode with four parameters for its fields. The default value for the frequency is 1 and those of the left and right pointers are NULL. The prototype is:
Then, declare a class WordTree to represent binary search trees for words. This class should have a WordNode* pointer for the root of the tree.
2. Implement a member function of class WordTree to insert a word into the corresponding binary search tree sorted by words. Its prototype is:
3. Implement a member function class WordTree to insert a word into the corresponding binary sorted (descendingly) by frequencies and then (increasingly) by words. Its prototype is:
4. Implement a member function of class WordTree to traverse this tree to build another binary search tree (sorted by frequencies). Its prototype is:
void copyTo(WordTree &tree)
This function copies words and their frequencies from the current tree to the binary search tree referred by 'tree'. It traverses all nodes of the current tree in the pre-order mode and insert its word and frequency into 'tree' using its 'insert' function
5. Implement a member function of class WordTree to read the words in an input file one-by-one and insert them into the tree. Its prototype is:
6. Implement a member function of class WordTree to write the words and frequencies to an output file in desending order. The prototype is:
To write the frequencies by descending order, you need to traverse the tree using the in-order mode.
7. Implement your main function with the following steps:
8. Report the size and height of 'treeWord' and 'treeFreq'.
Explanation / Answer
#include <iostream>
#include<cctype>
#include <stdlib.h>
#include <conio.h>
#include <string>
using namespace std;
struct WordNode
{
string element;
WordNode *left;
WordNode *right;
int height;
};
typedef struct WordNode *Node_pointer;
class bstree
{
public:
void insert(string,Node_pointer &);
void del(string, Node_pointer &);
bool find(string,Node_pointer &);
void isEmpty(Node_pointer &);
void copyTo(Node_pointer &,Node_pointer &);
Node_pointer nodecopyTo(Node_pointer &);
void printSorted(Node_pointer);
int bsheight(Node_pointer);
Node_pointer srl(Node_pointer &);
Node_pointer drl(Node_pointer &);
Node_pointer srr(Node_pointer &);
Node_pointer drr(Node_pointer &);
int nonodes(Node_pointer);
int deletemin(Node_pointer &);
};
void bstree::insert(string x,Node_pointer &p)
{
if (p == NULL)
{
p = new node;
p->element = x;
p->left=NULL;
p->right = NULL;
p->height=0;
if (p==NULL)
{
cout<<"Out of Space "<<endl;
}
}
else
{
if (x<p->element)
{
insert(x,p->left);
if ((bsheight(p->left) - bsheight(p->right))==2)
{
if (x < p->left->element)
{
p=srl(p);
}
else
{
p = drl(p);
}
}
}
else if (x>p->element)
{
insert(x,p->right);
if ((bsheight(p->right) - bsheight(p->left))==2)
{
if (x > p->right->element)
{
p=srr(p);
}
else
{
p = drr(p);
}
}
}
else
{
cout<<"Element Exists "<<endl;
}
}
string m,n,d;
m=bsheight(p->left);
n=bsheight(p->right);
d=max(m,n);
p->height = d + 1;
}
bool bstree::find(string x,Node_pointer &p)
{
if (p==NULL)
{
return false;
}
else
{
if (x < p->element)
{
find(x,p->left);
}
else
{
if (x>p->element)
{
find(x,p->right);
}
else
{
return true;
}
}
}
}
void bstree::copyTo(Node_pointer &p,Node_pointer &p1)
{
isEmpty(p1);
p1 = nodecopyTo(p);
}
void bstree::isEmpty(Node_pointer &p)
{
Node_pointer d;
if (p != NULL)
{
isEmpty(p->left);
isEmpty(p->right);
d=p;
free(d);
p=NULL;
}
}
Node_pointer bstree::nodecopyTo(Node_pointer &p)
{
Node_pointer temp;
if (p==NULL)
{
return p;
}
else
{
temp = new node;
temp->element = p->element;
temp->left = nodecopyTo(p->left);
temp->right = nodecopyTo(p->right);
return temp;
}
}
void bstree::del(string x,Node_pointer &p)
{
Node_pointer d;
if (p==NULL)
{
cout<<"Sorry! element not found "<<endl;
}
else if ( x < p->element)
{
del(x,p->left);
}
else if (x > p->element)
{
del(x,p->right);
}
else if ((p->left == NULL) && (p->right == NULL))
{
d=p;
free(d);
p=NULL;
cout<<"Element deleted successfully "<<endl;
}
else if (p->left == NULL)
{
d=p;
free(d);
p=p->right;
cout<<"Element deleted successfully "<<endl;
}
else if (p->right == NULL)
{
d=p;
p=p->left;
free(d);
cout<<"Element deleted successfully "<<endl;
}
else
{
p->element = deletemin(p->right);
}
}
int bstree::deletemin(Node_pointer &p)
{
int c;
cout<<"inside deltemin "<<endl;
if (p->left == NULL)
{
c=p->element;
p=p->right;
return c;
}
else
{
c=deletemin(p->left);
return c;
}
}
void bstree::printSorted(Node_pointer p)
{
if (p!=NULL)
{
printSorted(p->left);
cout<<p->element<<" ";
printSorted(p->right);
}
}
Node_pointer bstree:: srl(Node_pointer &p1)
{
Node_pointer p2;
p2 = p1->left;
p1->left = p2->right;
p2->right = p1;
p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
p2->height = max(bsheight(p2->left),p1->height) + 1;
return p2;
}
Node_pointer bstree:: srr(Node_pointer &p1)
{
Node_pointer p2;
p2 = p1->right;
p1->right = p2->left;
p2->left = p1;
p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
p2->height = max(p1->height,bsheight(p2->right)) + 1;
return p2;
}
Node_pointer bstree:: drl(Node_pointer &p1)
{
p1->left=srr(p1->left);
return srl(p1);
}
Node_pointer bstree::drr(Node_pointer &p1)
{
p1->right = srl(p1->right);
return srr(p1);
}
int bstree::nonodes(Node_pointer p)
{
int count=0;
if (p!=NULL)
{
nonodes(p->left);
nonodes(p->right);
count++;
}
return count;
}
int main()
{
Node_pointer root,root1,min,max;//,flag;
string a,findele,delele;
int choice;
char ch='y';
bstree bst;
root = NULL;
root1=NULL;
do
{
cout<<"Enter 1 to insert a new node"<<endl;
cout<<"Enter 2 to search a value"<<endl;
cout<<"Enter 3 to delete a value"<<endl;
cout<<"Enter 4 to display printSorted"<<endl;
cout<<"Enter 5 to display the height of the tree"<<endl;
cout<<"Enter 0 to exit"<<endl;
cout<<" Enter the choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<" ADDING NEW NODE"<<endl;
cout<<" ::::::::::::: "<<endl;
cout<<"Enter a new value: ";
cin>>a;
bst.insert(a,root);
cout<<" The new value have been added to your tree successfully "<<endl;
break;
case 2:
cout<<" Enter WordNode to search: ";
cin>>findele;
if (root != NULL)
{
bst.find(findele,root);
}
break;
case 3:
cout<<" Enter WordNode to delete: ";
cin>>delele;
bst.del(delele,root);
bst.printSorted(root);
cout<<endl;
break;
case 4:
cout<<" IN-ORDER TRAVERSAL"<<endl;
bst.printSorted(root);
cout<<endl;
break;
case 5:
cout<<" HEIGHT "<<endl;
cout<<"The height of the tree is: " <<bst.bsheight(root)<<endl;
break;
case 0:
cout<<" Thank your for using AVL tree program "<<endl;
break;
default:
cout<<"Sorry! wrong input "<<endl;
break;
}
system("pause");
}
while(choice != 0);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.