Question & Answer: 1. In a C++ class definition for an abstract data type WordTree of strings, store the words and the counts of the…..

1. In a C++ class definition for an abstract data type WordTree of strings, store the words and the counts of the words in a single binary search tree. Each word occurring in the text can only be stored once in the tree. Implement each member function in the class below. The WordTree class may have only one member variable, root, and it must be private. provide an appropriate copy constructor, destructor and assignment operator for the WordTree class as well.

 #include <iostream>
        #include <string>
        using namespace std;
        
        typedef string ItemType;
        
        struct WordNode {
            ItemType m_data;
            WordNode *m_left;
            WordNode *m_right;
            // You may add additional data members and member functions in WordNode
        };
        
        class WordTree {
            
        private:
            WordNode *root;
            
        public:
        
              // default constructor            
            WordTree() : root(nullptr) { };
    
              // copy constructor
            WordTree(const WordTree& rhs);
    
              // assignment operator
            const WordTree& operator=(const WordTree& rhs);  

              // Inserts val at the front of the list    
            void add(ItemType v);

              // Returns the number of distince words / nodes   
            int distinctWords() const;
    
              // Returns the total number of words inserted, including duplicate
              // values    
            int totalWords() const;
    
              // Prints the LinkedList 
            friend ostream& operator<<(ostream &out, const WordTree& rhs);

              // Destroys all the dynamically allocated memory
              // in the tree.
            ~WordTree();
        };

The add function enables a client to insert elements into the WordTree. If an element has already been added, repeated calls to add will not add a new WordNode. Instead the count of the occurrences of that word will increase.

The key and the number of occurrences of the key are printed. The output should be sorted according to the key.

2. implement overloading the output operator in a class as a non member friend function.

When comparing items, just use the == or != operators provided for the string type by the library. These do case-sensitive comparisons. In other words, the The THE will count as different words.

3. write a main routine and the WordTree member functions.

Expert Answer

 

Given below is the implementation for WordTree. I presume the file is named WordTree.h and have implemented all th functions needed in the same file. Here are the 2 files needed. Output shown at the end. Please don’t forget to rate the answer if it helped. Thank you.

WordTree.h

#include <iostream>
#include <string>
using namespace std;

typedef string ItemType;

struct WordNode {
ItemType m_data;
WordNode *m_left;
WordNode *m_right;
// You may add additional data members and member functions in WordNode
int m_count; // to store the count of the word

WordNode(ItemType data)
{
m_data = data;
m_left = m_right = nullptr;
m_count = 1;//when a node is created , it means its appearing atleast once
}

WordNode(const WordNode &n)
{
m_data = n.m_data;
m_count = n.m_count;
if(n.m_left != nullptr)
m_left = new WordNode(*n.m_left);
else
m_left = nullptr;
if(n.m_right != nullptr)
m_right = new WordNode(*n.m_right);
else
m_right = nullptr;
}

int distinctWords()
{
int count = 1;
if(m_left != nullptr)
count += m_left->distinctWords();
if(m_right != nullptr)
count += m_right->distinctWords();
return count;
}

int totalWords()
{
int count = m_count;
if(m_left != nullptr)
count += m_left->totalWords();
if(m_right != nullptr)
count += m_right->totalWords();
return count;
}

friend ostream& operator << (ostream &out, const WordNode &n);

};

class WordTree {

private:
WordNode *root;
void deleteTree(WordNode *w); //recursively delete tree nodes in post order traversal
public:

// default constructor
WordTree() : root(nullptr) { };

// copy constructor
WordTree(const WordTree& rhs);

// assignment operator
const WordTree& operator=(const WordTree& rhs);

// Inserts val at the front of the list
void add(ItemType v);

// Returns the number of distince words / nodes
int distinctWords() const;

// Returns the total number of words inserted, including duplicate
// values
int totalWords() const;

// Prints the LinkedList
friend ostream& operator<<(ostream &out, const WordTree& rhs);

// Destroys all the dynamically allocated memory
// in the tree.
~WordTree();
};

WordTree::WordTree(const WordTree& rhs)
{
*this = rhs;
}

// assignment operator
const WordTree& WordTree::operator=(const WordTree& rhs)
{
if(rhs.root == nullptr)
root = nullptr;
else
root = new WordNode(*rhs.root);
return *this;
}

// Inserts val at the front of the list
void WordTree::add(ItemType v)
{

if(root == nullptr)
root = new WordNode(v);
else
{
WordNode *curr = root;
while(curr != nullptr)
{
if(curr->m_data == v) //already word in tree, increase count
{
curr->m_count++;
return;
}
else if(v < curr->m_data)
{
if(curr->m_left == nullptr)
{
curr ->m_left = new WordNode(v);
return;
}
else
curr = curr->m_left;
}
else
{

if(curr->m_right == nullptr)
{
curr ->m_right = new WordNode(v);
return;
}
else
curr = curr->m_right;
}
}
}
}
// Returns the number of distince words / nodes
int WordTree::distinctWords() const
{
if(root == nullptr)
return 0;
else
return root->distinctWords();
}

// Returns the total number of words inserted, including duplicate
// values
int WordTree::totalWords() const
{
if(root == nullptr)
return 0;
else
return root->totalWords();

}

// Prints the LinkedList
ostream& operator<<(ostream &out, const WordTree& rhs)
{
if(rhs.root != nullptr)
out << *rhs.root;
return out;

}

// Destroys all the dynamically allocated memory
// in the tree.
WordTree::~WordTree()
{
deleteTree(root);
}

void WordTree::deleteTree(WordNode *w)
{
if(w == nullptr) return;
deleteTree(w->m_left);
deleteTree(w->m_right);
delete w;
}

ostream& operator << (ostream &out, const WordNode &n)
{
if(n.m_left != nullptr)
out << *n.m_left;
out << n.m_data << “[” << n.m_count << “]” << endl;

if(n.m_right != nullptr)
out << *n.m_right;

return out;
}

WordTreeMain.cpp

//program to demostrate WordTree . The program loads each word from the specified input file into
//the WordTree and then prints number of total words and distint words and also lists the contents
// of the tree.
#include <iostream>
#include <fstream>
#include “WordTree.h”
using namespace std;
int main()
{
string filename;
cout << “Enter a filename containing some text: ” ;
getline(cin, filename);

ifstream ifs(filename.c_str());
if(!ifs.is_open())
{
cout << “Could not open input file ” << filename << “.” << endl;
return 1;
}

string word;
WordTree tree;
while(ifs >> word)
tree.add(word);

ifs.close();

cout << “The contents of tree are : ” << endl;
cout << tree << endl;

cout << “Total number of words = ” << tree.totalWords() << endl;
cout << “Distinct words = ” << tree.distinctWords() << endl;
return 0;
}

Input File: sample.txt

Once upon a time there lived a little boy in a village
All the people in the village loved the boy

Output

Enter a filename containing some text: sample.txt
The contents of tree are :
All[1]
Once[1]
a[3]
boy[2]
in[2]
little[1]
lived[1]
loved[1]
people[1]
the[3]
there[1]
time[1]
upon[1]
village[2]

Total number of words = 21
Distinct words = 14

Still stressed from student homework?
Get quality assistance from academic writers!