I have to implement the lexicon class to represent text vocabularies in the form of binary search trees. The class should support the following functions, which I must implement:
<pre>classlexicon {
public:
lexicon()
~lexicon();
void insert(const string &s);
int lookup(const string &s) const;
int depth(const string &s) const;
void replace(const string &s1, const string &s2);
friend ostream &operator<< (ostream &out, const lexicon &l);
};
The insert (s) method will insert the word s into the tree.
The lookup method (s) will look for the word s in the tree and return the occurrence frequency. The result will be 0 (zero) if the word does not exist in the tree.
The depth (s) method will search for the word s in the tree, as will lookup. If it does not exist, it will return −1. But if it exists, it will return the depth at which the node containing it in the tree is located, ie the length of the path from the root to this node. We assume that the root of the tree is at a depth of 0 (zero).
The replace method (s1, s2) will replace all occurrences of the word s1 with an equal number of occurrences of the word s2. If s1 does not exist in the tree, then nothing will happen. If there is also the number of occurrences is k> 0, then s1 will be deleted and the word s2 will be searched. If it does not exist, it will be entered with a frequency of k. But if there is, then the frequency of its occurrence will be informed accordingly (it will increase by k).
When deleting a word from the dictionary (done indirectly by the replace method), if a node with two non-empty children is deleted, then the deleted node is replaced by the one containing the immediately smaller word. If a node that has a non-empty child is deleted, then it is replaced by its child.
Dictionaries should be printed in alphabetical order, with the words followed by their frequency.
An example is:
<pre>int main() {
lexicon l;
l.insert("the");
l.insert("boy");
l.insert("and");
l.insert("the");
l.insert("wolf");
cout << "The word 'the' is found " << l.lookup("the") << " time(s)" << endl;
cout << "The word 'and' is found at depth " << l.depth("and") << endl;
cout << l;
l.replace("and", "dummy");
cout << "After replacement: \n";
cout << l;
cout << "Now the word 'and' is found at depth " << l.depth("dummy") << endl;
l.replace("boy", "dummy");
cout << "After replacement: \n";
cout << l;
cout << "Now the word 'and' is found at depth " << l.depth("dummy") << endl;
l.replace("the", "dummy");
cout << "After replacement: \n";
cout << l;
cout << "Now the word 'and' is found at depth " << l.depth("dummy") << endl;
l.replace("wolf", "dummy");
cout << "After replacement: \n";
cout << l;
cout << "Now the word 'and' is found at depth " << l.depth("dummy") << endl;
return 0;
}
This must print:
and 1
boy 1
the 2
wolf 1
and is now found 1 time(s) at depth 2
boy is now found 1 time(s) at depth 1
the is now found 2 time(s) at depth 0
wolf is now found 1 time(s) at depth 1
dummy is now found 0 time(s) at depth -1
wolf is now found 1 time(s) at depth 1
dummy is now found 1 time(s) at depth 2
wolf is now found 1 time(s) at depth 1
dummy is now found 2 time(s) at depth 1
wolf is now found 1 time(s) at depth 1
dummy is now found 4 time(s) at depth 0
wolf is now found 0 time(s) at depth -1
dummy 5
but my code prints:
and 1
boy 1
the 2
wolf 1
and is now found 1 time(s) at depth 2
boy is now found 1 time(s) at depth 1
the is now found 2 time(s) at depth 0
wolf is now found 1 time(s) at depth 1
dummy is now found 0 time(s) at depth -1
wolf is now found 1 time(s) at depth 1
dummy is now found 1 time(s) at depth 2
wolf is now found 1 time(s) at depth 1
dummy is now found 2 time(s) at depth 1
wolf is now found 1 time(s) at depth 1
dummy is now found 6 time(s) at depth 0
wolf is now found 0 time(s) at depth -1
dummy 4
dummy 7.
What I have tried:
<pre>#include <iostream>
#include <queue>
using namespace std;
struct node {
int freq;
string word;
node *left, *right;
node(const string &new_word) {
freq = 1;
this->word = new_word;
left = right = nullptr;
}
};
node* search(node* tree, const string &key) {
if(tree == nullptr) {
return tree;
}
if(tree->word == key) {
return tree;
}
else if(tree->word < key) {
return search(tree->right, key);
}
else {
return search(tree->left, key);
}
}
class lexicon {
public:
node *root;
void Insert(const string &w, node* tree) {
if(w == tree->word) {
tree->freq++;
return;
}
if(w < tree->word) {
if(tree->left == nullptr) {
tree->left = new node(w);
}
else {
this->Insert(w, tree->left);
}
}
else {
if(tree->right == nullptr) {
tree->right = new node(w);
}
else {
this->Insert(w, tree->right);
}
}
}
int Look_up(const string &w, node* tree) const{
if(tree == nullptr) {
return 0;
}
else if(w == tree->word) {
return tree->freq;
}
else if(w < tree->word) {
return this->Look_up(w, tree->left);
}
else {
return this->Look_up(w, tree->right);
}
}
int Depth(const string &w, node* tree, int &deep) const{
if(tree == nullptr) {
return -1;
}
if(tree->word == w) {
return deep;
}
else if(w > tree->word) {
deep++;
return Depth(w, tree->right, deep);
}
else {
deep++;
return Depth(w, tree->left, deep);
}
}
void Replace(const string &s1, const string &s2, node*& tree) {
if(tree == nullptr) {
return;
}
else if(s1 == tree->word && tree != root) {
node* to_s2 = search(root, s2);
if(to_s2 == nullptr) {
this->insert(s2);
node* new_to_s2 = search(root, s2);
new_to_s2->freq += tree->freq-1;
}
else {
to_s2->freq += tree->freq;
}
if(tree->left == nullptr && tree->right == nullptr) {
tree = nullptr;
}
else if(tree->left != nullptr && tree->right == nullptr) {
tree = move(tree->left);
}
else if(tree->left == nullptr && tree->right != nullptr) {
tree = move(tree->right);
}
else {
node* minNode = this->FindMin(tree->left);
tree->word = minNode->word;
tree->freq = minNode->freq;
this->Replace(minNode->word, s2, minNode);
}
}
else if(s1 < tree->word) {
this->Replace(s1, s2, tree->left);
}
else if(s1 > tree->word) {
this->Replace(s1, s2, tree->right);
}
else if(s1 == root->word) {
node* to_s2 = search(root, s2);
if(to_s2 == nullptr) {
this->insert(s2);
node* new_to_s2 = search(root, s2);
new_to_s2->freq += tree->freq-1;
}
else {
to_s2->freq += tree->freq;
}
if(root->left == nullptr && root->right == nullptr) {
root = nullptr;
}
else if(root->left != nullptr && root->right == nullptr) {
root = move(root->left);
}
else if(root->left == nullptr && root->right != nullptr) {
root = move(root->right);
}
else {
node* minNode = this->FindMin(root->left);
root->word = minNode->word;
this->Replace(minNode->word, s2, minNode);
}
}
}
node* FindMin(node* &tree) {
if(tree == nullptr) {
return 0;
}
else if(tree->right == nullptr) {
return tree;
}
else {
return this->FindMin(tree->right);
}
}
void inorder(node* tree) const{
if(tree == nullptr) {
return;
}
if(tree != nullptr) {
inorder(tree->left);
cout << tree->word << " " << tree->freq << endl;
inorder(tree->right);
}
}
lexicon() {
root = nullptr;
}
~lexicon() {
node* t;
node* p = root->right;
for(t=root; t!=nullptr; t = t->left) {
node* temp = t;
delete temp;
}
for(t=p; t!=nullptr; t = t->right) {
node* temp = t;
delete temp;
}
delete p;
}
void insert(const string &s) {
if(root == nullptr) {
this->root = new node(s);
}
else {
this->Insert(s, this->root);
}
}
int lookup(const string &s) const {
return Look_up(s, this->root);
}
int depth(const string &s) const {
int deep=0;
return Depth(s, this->root, deep);
}
void replace(const string &s1, const string &s2) {
this->Replace(s1, s2, this->root);
}
friend ostream & operator << (ostream &out, const lexicon &l) {
l.inorder(l.root);
return out;
}
};