# CS 1410 Assignment #10: Binary Search Tree solution

\$30.00

Original Work ?

## Description

You should submit your solution on Canvas as a cpp file named as
This assignment has the same problem of word counting as Assignment 1. Please read its
problem description for the detailed requirements of input and output.
In Assignment 1, you used arrays for storing words and their frequencies. As you have
observed, that implementation is inflexible because you can store only a limited number of
words (not to exceed the array size). In addition, adding a new word is inefficient, as you need
to shift other words in the arrays in order to insert the new one.
In this assignment, binary search trees will be used. You will use a binary search tree T for
counting words. That is, when you read a word from the input file, you will find the node
containing that word in the tree. If that node exists, you increase its frequency. If not, you
create a new node for the word (with initial frequency of 1) and insert it into the tree.
After reading all the words, you will use another binary search tree F to sort the frequencies.
You will visit each node of T and insert the corresponding word and frequency into F based on
frequencies. Because different words might have the same frequency, when inserting, you
compare the frequencies first. If they are equal, you will compare the words.
Task 1 (5 points). 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:
WordNode(int word, int freq = 1, WordNode *left = NULL, WordNode *right = NULL)
Then, declare a class WordTree to represent binary search trees for words. This class has a
WordNode* pointer for the root of the tree.
Task 2 (5 points). Implement a member function of class WordTree to insert a word into the
corresponding binary search tree sorted by words. Its prototype is:
void insert(int word)
Task 3 (5 points). 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:
void insert(string word, int freq)
Task 4 (10 points). 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 implemented in Task 3.
Task 5 (5 points). 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:
Task 6 (5 points). Implement a member function of class WordTree to write the words and
frequencies to an output file in desending order. The prototype is:
void save(string filename)
To write the frequencies by descending order, you need to traverse the tree using the
in­ordermode.