Question
I need help in C++ implementing binary search tree. I have the .h file for the binary search tree class. I have 4 classic texts,
I need help in C++ implementing binary search tree. I have the .h file for the binary search tree class. I have 4 classic texts, and 2 different dictionaries.
Classic Texts:
Alice In Wonderland.txt
A Tale of Two Cities.txt
Pride And Prejudice.txt
War and Peace.txt
2 different dictionaries:
Dictionary.txt
Dictionary-brit.txt
The data structures from the standard template library can not be used.The main program should open the text file, read in the words, remove the punctuation and change all the characters to be lower case, and then insert them into your data structure. The provided dictionaries are all lower case without punctuation. Once the structures are built, the program should write an output file with the following format: The title of the first classic text Number of words not appearing in the first dictionary, followed by the words Number of words not appearing in the second dictionary, followed by the words The total number of words in the text, followed by the unique words (Note: this will be the same as the Sum of the frequencies, and the number of nodes in your binary search tree for the classic text) The number of words in the requested word range and the frequency of each of those words:
The title of the first classic text
Number of words not appearing in the first dictionary, followed by the words
Number of words not appearing in the second dictionary, followed by the words
The total number of words in the text, followed by the unique words (Note: this will be the same as the Sum of the frequencies, and the number of nodes in your binary search tree for the classic text) .
The number of words in the requested word range and the frequency of each of those words.
Their frequencies in a specified lexical range (called RangeQuery) for each text (for example, all the words between raft and reflex might be : rag, rage, rails, rearranged, and reels).
Here is the pseudo code for the RangeQuery:
Algorithm RangeQuery(key1, key2, v):
Input: Search keys, key1 and key2 and a node v of a binary search tree T
Output: The elements stored in the subtree of T rooted at v whose keys are in the range [key1,key2]
if T.isExternal(v) then return 0
if key1 <= key(v) <= key2 then print RangeQuery(key1, key2, T.leftChild(v))
printData(v);
print RangeQuery(key1, key2, T.rightChild(v))
else if key(v) < key1 then print RangeQuery(key1, key2, T.rightChild(v))
else if key2 < key(v) then print RangeQuery(key1, key2, T.leftChild(v)) end RangeQuery
I have to make 4 text files, one for each of the classic texts.
Here is an example of an output for all the words between raft and reflex in the War And Peace Text:
War And Peace
0
2 : Michaela, gumshoed
10,431 total words
2,010 unique words
8
rag : 1
rage : 3
rails : 4
rearranged : 2
reels : 1
Here is my Code:
// bst.h
#ifndef bst_h #define bst_h
#ifndef NULL #define NULL 0x00 #endif
#include
class BSTNode { private: std::string data; int frequency; BSTNode *left; BSTNode *right; public: BSTNode(std::string d) { data = d; frequency = 1; left = NULL; right = NULL; } ~BSTNode() {}
friend class BSTree; };
class BSTree { private: BSTNode *root;
void destroy(BSTNode*); BSTNode* find(BSTNode*, std::string);
void increment_frequency(BSTNode *ptr); void insert(BSTNode**, std::string); void print_list(BSTNode*, int*); void print_range(std::string, std::string, BSTNode*);
public: BSTree(); ~BSTree(); void insert(std::string); void print_list(int n);
void print_tree(int n); void print_range(std::string, std::string); // output all the strings in the tree lexically between the parameters };
#endif
--------------------------------------------------------------------
// bst.cpp
//#include "bst.h" //#include
//BSTree::BSTree() { // root = NULL; //}
destructor: // call destroy on the root of the tree
destroy(BSTNode* p) // **recursively** destroy the tree pointed to by p (what traversal?)
find(BSTNode* node, std::string word) // **recursively** search for word starting at node // return a pointer to the target node -OR- // the pointer where the target node should be
increment_frequency(BSTNode* ptr) // increment the frequency at the node ptr
insert( BSTNode* *p, std::string word) // if the pointer p is pointing to null then // create a new node at p // otherwise, _insert_ word to the left or right subtree // (**recursively**)
insert(std::string word) // insert word to the root of the tree by first _finding_ the // place to insert. If word is already in the tree, _increment_ // its frequency, otherwise _insert_ the word
print_list( BSTNode* p, int *n) // if p is not null, // if we have more to print // recursively print the left tree // cout the data : frequency and decrement the count (n) // print the right tree. (what traversal?)
print_list(int n) // call print_list on the root
print_tree(int n) // call print_list on the root
print_range( std::string k1, std::string k2, BSTNode* p) // use pseudocode Range Query
print_range( std::string k1, std::string k2) // call print_range on the root of this tree
--------------------------------------------------------------
#include
int main(int argc, const char * argv[]) { // declare the data structures here // BSTree myTree;
// Here is the code I started .. // std::ifstream infile(argv[1]); // std::string line; // std::string word; // while(std::getline(infile, line)) // { // std::istringstream iss(line); // while(iss >> word) // { // word.erase(std::remove_if (word.begin(), word.end(), ispunct), word.end()); // std::transform(word.begin(), word.end(), word.begin(), ::tolower); // // at this point word contains a punctuation free lower case word // from the text (HINT: do something with it) // // } // } return 0; }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started