- In C Template Class T Class Freqtable Template Class T Class Node Public Node Const T Val Node Left No 1 (37.17 KiB) Viewed 36 times
class FreqTable;
template <class T>
class Node
{
public:
Node(const T& val, Node* left, Node* right);
T get_val() const { return val; }
int get_freq() const { return freq; }
Node* get_left() const { return left; }
Node* get_right() const { return right; }
private:
T val;
int freq;
Node* left;
Node* right;
friend class FreqTable<T>;
};
template <class T>
Node<T>::Node(const T& val, Node* left, Node*
right)
{
this->val = val;
this->freq = 1;
this->left = left;
this->right = right;
}
#include "queue_dll.h"
#include "node.h"
#include <string>
#include <iostream>
using namespace std;
template <class T>
class FreqTable
{
public:
// Given functions.
FreqTable();
FreqTable(const FreqTable& other);
~FreqTable() { clear(); }
Node<T>* get_root() const { return root;
}
bool is_empty() const { return root == nullptr;
}
int freq_of(const T& val) const;
bool remove(const T& val);
void clear();
DLList<T> values() const;
FreqTable& operator=(const FreqTable&
other);
// Required Functions.
void insert(const T& val);
T top() const;
int freq_of(char c) const;
void trim(int min_freq);
private:
Node<T> *root;
void copy_from(Node<T>* node);
void values(DLList<T>& result,
Node<T>* node) const;
void remove_1(Node<T>* ptr, Node<T>*
prev);
void remove_2(Node<T>* node);
void clear(Node<T>* node);
};
// ------- REQUIRED FUNCTIONS --------- //
template <class T>
void FreqTable<T>::insert(const T& val)
{
}
template <class T>
T FreqTable<T>::top() const
{
}
template <class T>
void FreqTable<T>::trim(int min_freq)
{
}
template <>
int FreqTable<string>::freq_of(char c) const
{
return 0;
}
// ------------------------------------------ //
template <class T>
FreqTable<T>::FreqTable()
{
root = nullptr;
}
template <class T>
void FreqTable<T>::copy_from(Node<T>* node)
{
if (node == nullptr)
return;
insert(node->val);
copy_from(node->left);
copy_from(node->right);
}
template <class T>
FreqTable<T>::FreqTable(const FreqTable<T>&
other)
{
root = nullptr;
copy_from(other.root);
}
template <class T>
int FreqTable<T>::freq_of(const T& val) const
{
Node<T>* node = root;
while(node != nullptr) {
if (val == node->val) return
node->freq;
if (val < node->val)
node = node->left;
else
node = node->right;
}
return 0;
}
template <class T>
DLList<T> FreqTable<T>::values() const
{
DLList<T> result;
values(result, root);
return result;
}
template <class T>
void FreqTable<T>::values(DLList<T>& result,
Node<T>* node) const
{
if (node == nullptr)
return;
values(result, node->left);
result.add_to_tail(node->val);
values(result, node->right);
}
template <class T>
bool FreqTable<T>::remove(const T& val)
{
Node<T>* node = root;
Node<T>* prev = nullptr;
while (node != nullptr) {
if (node->val == val)
break;
prev = node;
if (val < node->val)
node =
node->left;
else
node =
node->right;
}
if (node == nullptr)
return false;
if (node->freq > 1)
node->freq--;
else if (node->left == nullptr || node->right
== nullptr)
remove_1(node, prev);
else
remove_2(node);
return true;
}
template <class T>
void FreqTable<T>::remove_1(Node<T>* ptr,
Node<T>* prev)
{
if (ptr == root) {
if (root->left != nullptr)
root =
root->left;
else
root =
root->right;
}
else if (ptr == prev->left) {
if (ptr->right != nullptr)
prev->left =
ptr->right;
else
prev->left =
ptr->left;
}
else {
if (ptr->right != nullptr)
prev->right =
ptr->right;
else
prev->right =
ptr->left;
}
delete ptr;
}
template <class T>
void FreqTable<T>::remove_2(Node<T>* node)
{
Node<T>* rep = node->left;
Node<T>* prev = node;
while (rep->right != nullptr) {
prev = rep;
rep = rep->right;
}
node->val = rep->val;
node->freq = rep->freq;
remove_1(rep, prev);
}
template <class T>
void FreqTable<T>::clear()
{
clear(root);
root = nullptr;
}
template <class T>
void FreqTable<T>::clear(Node<T>* node)
{
if (node == nullptr)
return;
clear(node->left);
clear(node->right);
delete node;
}
template <class T>
FreqTable<T>& FreqTable<T>::operator=(const
FreqTable<T>& other)
{
if (this == &other)
return *this;
clear();
copy_from(other.root);
return *this;
}
template <class T>
void print(ostream& out, Node<T>* node) {
if (node == nullptr)
return;
print(out, node->get_left());
out << node->get_val() << ": "
<< node->get_freq() << endl;
print(out, node->get_right());
}
template <class T>
ostream& operator<<(ostream& out, const
FreqTable<T>& table) {
print(out, table.get_root());
return out;
}
Overview The FreqTable class is a binary search tree that stores in each node a value and a count for how many times this value was inserted into the tree. You are given in this Things you are given Class Node in node.h. Each node has a value, a frequency, and pointers to the left and right child nodes. Note that the constructor initializes the freq data member to 1. Class FreqTable: This is similar to the bst.h implementation with the following main differences: Function int freq_of(const T& val) const returns the frequency of val. This function replaces function contains in class BST. Function bool remove(const T& val) decrements the frequency of val. If the frequency is 1, the node is deleted. The stream insertion operator (<<) is overloaded to allow for printing the frequency table. Many functions were removed. Things you are required to do Implement the following functions: void insert(const T& val) Inserts val into the tree. This function must run in 0(\text{height})0(height) in the worst case. T top() const Returns the value that has the highest frequency. This function must run in 0(1)0(1). If the tree is empty, throw a string exception. Note. Add a comment to this function describing what changes you made in class FrequencyTable outside this function (if any). void trim(int min_freq) Removes from the tree every node whose frequency is less than or equal to the given minimum frequency.
This function must perform 0(n)0(n) data compares, in the worst case, where nn is the number of nodes in the tree. Data compares are compares that involve values stored in the tree. Comparisons between pointers are not considered data compares. HINT. Which traversal is the most suitable for this function? int freq_of(char ch) Returns the sum of the frequencies of the strings in the tree starting with the given character. This function must run in 0(\text{height} + k)0(height+k), where kk is Notes: You are allowed to add new data members to class FreqTable but not to class Node. You are allowed to add new private functions, but not new public functions. - All of your implementation must be provided in freq.h.