I need help in C++ implementing binary search tree. I have the .h file for the b

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, 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 <string>

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 <iostream>

//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 <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <algorithm>
#include <ctime>
// add any other needed include files..

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;
}

Explanation / Answer

#include<stdlib.h>

#include<string.h>

#include<fstream>

#include<iostream>

#define CNT 5

using namespace std;

struct node

{

string data;

node *Left_link;

node *Right_link;

};

node* insert_node(node *temp,node *newnode);

struct node *root=NULL;

class Bintree

{

public:

bool add(string str);

public:

void Display();

void DrawTree(struct node *root, int space);

};

bool Bintree::add(string x)

{

node *temp=root;

node *newnode;

newnode=new node;

newnode->Left_link=NULL;

newnode->Right_link=NULL;

newnode->data=x;

root=insert_node(temp,newnode);

}

node* insert_node(node *temp,node *newnode)

{

if(temp==NULL)

{

temp=newnode;

}

else if(temp->data < newnode->data)

{

insert_node(temp->Right_link,newnode);

if(temp->Right_link==NULL)

temp->Right_link=newnode;

}

else

{

insert_node(temp->Left_link,newnode);

if(temp->Left_link==NULL)

temp->Left_link=newnode;

}

return temp;

}

void inorderdisplay(node *t = root)

{

if(root==NULL)

{

printf(" Its Empty Tree ");

}

else if(t!=NULL)

{

inorderdisplay(t->Left_link);

cout<<t->data<<"-->";

inorderdisplay(t->Right_link);

}

}

node* TreeSearch(node *root, string key)

{

node *temp;

temp = root;

while (temp != NULL)

{

if(temp->data==key)

{

cout<<" The Element "<<temp->data<<"is Present"<<endl;

return temp;

}

if(temp->data > key)

temp = temp->Left_link;

else

temp = temp->Right_link;

}

return NULL;

}

void printSideways(node *root, int space)

{

if (root == NULL)

return;

space += CNT;

printSideways(root->Right_link, space);

cout<<endl;

for(int i=CNT;i<space;i++)

cout<<" ";

cout<<root->data;

printSideways(root->Left_link, space);

}

int main()

{

Bintree obj;

string datavalue;

ifstream infile;

infile.open("words.txt");//reading Words from the File

for(int i=0;i<8;i++)

{

infile>>datavalue;

obj.add(datavalue);

}

int option;

cout<<" -------------------------"<<endl;

cout<<" Implementation of Binary tree"<<endl;

while(true)

{

cout<<" ** MENU **"<<endl;

cout<<" 11.Insert the Data"<<endl;

cout<<" 12.Display"<<endl;

cout<<" 13.Search"<<endl;

cout<<" 14.printSideways"<<endl;

cout<<" 15.exit"<<endl;

cout<<" Please Select any Choice"<<endl;

cin>>option;

switch(option)

{

case 1:

cout<<" Please Enter the New Node"<<endl;

cin>>datavalue;

obj.add(datavalue);

break;

case 2:

cout<<" Inorder Display"<<endl;

inorderdisplay();

break;

case 3:

cout<<" Enter the Word to Search:"<<endl;

cin>>datavalue;

TreeSearch(root,datavalue);

break;

case 4:

printSideways(root,4);

break;

case 5:

exit(0);

default:

cout<<" Invalid Option"<<endl;

}

}

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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