Write a C++ program that will the binary search tree implementation of a diction

Question

Write a C++ program that will the binary search tree implementation of a dictionary to find Word co-occurrence (appearing together in sequence or simultaneously). This is a phenomenon that counts the frequency of pairs of words. Your code should insert as a pair any two words and keep track of their frequency.

For example, if your input file contains the following sentence

a penny saved is a penny earned

the following will happen

add : <a, penny> frequency 1

add <penny, saved> frequency 1

add<saved, is> frequency 1

add <is, a> frequency 1

<a, penny> in tree only add frequency – becomes 2

Add<penny, earned> frequency 1

Etc.

Your program should:

·       read text from an input file.

·       Calculate statistics and display results including the pair and its frequency.

Explanation / Answer

Please find the code below .

// reading a text file
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

string GetTextFromFile();
string GetfileWord();

struct node
{
string key;
int count;
struct node *left, *right;
};
struct node *root = NULL;
// A utility function to create a new BST node
struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
temp->count = 1;
return temp;
}

// A utility function to do inorder traversal of BST
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("%s(%d) ", root->key, root->count);
inorder(root->right);
}
}

/* A utility function to insert a new node with given key in BST */
struct node* insert(struct node* node, string key)
{
/* If the tree is empty, return a new node */
if (node == NULL)
return newNode(key);

// If key already exists in BST, icnrement count and return
if (key == node->key)
{
(node->count)++;
return node;
}

/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);

/* return the (unchanged) node pointer */
return node;
}
/* Given a non-empty binary search tree, return the node with
minimum key value found in that tree. Note that the entire
tree does not need to be searched. */
struct node * minValueNode(struct node* node)
{
struct node* current = node;

/* loop down to find the leftmost leaf */
while (current->left != NULL)
current = current->left;

return current;
}

string GetfileWord()
{
std::string fileName = "example.txt";
std::string line;
std::fstream file;
int cnt=0;
std::string pairsWord="";
file.open(fileName.c_str());

if(!file.good())
{
std::cout << "Problem with file!" << std::endl;
return "";
}
while(!file.eof())
{
getline(file, line);

if(line.empty())
continue;

std::istringstream iss(line);

for(std::string word; iss >> word;)
{
if(cnt==0)
{
pairsWord= word;
cnt++;
}
else
{
pairsWord= "'"+pairsWord+","+word+"'";
cnt=0;

root = insert(root, pairsWord);

}

}

}
return "";
}
int main ()
{

GetfileWord();
printf("Inorder traversal of the given tree ");
inorder(root);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.