I have written the code for the binary Search tree, but now I am working on figu
ID: 3620554 • Letter: I
Question
I have written the code for the binary Search tree, but now I am working on figuring out how to put in these driver functions:Write a driver function which creates and fills a BSTree_* of C++ strings by reading from an input file word-by-word.
Convert all alphabetic characters to lower-case before insertion. If a string has all alphabetic characters but it ends in '.' (a period) or ',' (a comma), remove the last character using the string function erase() before inserting it. Other than this exception, simply SKIP strings which contain punctuation or numbers.
I know I can use the isalpha/isupper/tolower functions, but I am not sure how to use them...Here is the code I have for my binary search tree so far...I need to figure out how to insert the driver functions into it.
#include <iostream>
#include <fstream>
#include <string>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <math.h>
#include <time.h>
using namespace std;
template <typename Comparable>
class binaryNode{
public:
Comparable element;
binaryNode *left;
binaryNode *right;
binaryNode ( const Comparable & theElement, binaryNode *lt, binaryNode *rt) : element(theElement), left(lt), right (rt) {}
};
template <typename Comparable>
class binarySearchTree{
struct binaryNode{
public:
Comparable element;
binaryNode *left;
binaryNode *right;
binaryNode ( const Comparable & theElement, binaryNode *lt, binaryNode *rt) : element(theElement), left(lt), right (rt) {}
};
public:
binarySearchTree(){root = NULL; treeDepth = 0;}
binarySearchTree(const binarySearchTree & rhs);
~binarySearchTree(){
makeEmpty();
}
void makeEmpty(){
if (root != NULL)
makeEmpty( root);
}
void makeEmpty (binaryNode * & t){
if (t != NULL){
makeEmpty( t -> left);
makeEmpty( t -> right);
delete t;
}
t = NULL;
}
int height(){
return height(root);
}
int height (binaryNode *t){
if (t == NULL)
return -1;
else
return 1 + max (height ( t -> left) , height ( t -> right));
}
binaryNode * findMin (binaryNode *t) const{
if (t == NULL)
return NULL;
if(t -> left == NULL)
return t;
return findMin(t -> left);
}
binaryNode *findMax (binaryNode *t) const{
if (t != NULL)
while ( t -> right != NULL)
t = t -> right;
return t;
}
bool contains ( const Comparable & x, binaryNode *t) const{
if (t == NULL)
return false;
else if ( x < t -> element )
return contains (x, t-> left);
else if ( t -> elements < x )
return contains ( x, t -> right);
else
return true;
}
bool isEmpty() const;
void printTree(binaryNode *aNode){
if ( aNode != NULL ) {
printTree( aNode->left );
cout << aNode->element << " ";
printTree( aNode->right );
}
}
void printTree(){
printTree(root);
}
void insert (const Comparable &x) {
insert (x, root);
}
void remove(const Comparable &x){
remove(x, root);
}
void remove (const Comparable & x, binaryNode * & t){
if (t == NULL)
return;
if (x < t -> element)
remove (x, t -> left);
else if (t -> element < x)
remove (x, t -> right);
else if( t -> left != NULL && t -> right != NULL){
t -> element = findMin(t -> right) -> element;
remove (t -> element, t -> right);
}
else{
binaryNode *oldNode = t;
t = ( t -> left != NULL) ? t -> left : t -> right;
delete oldNode;
}
height();
// treeDepth = height();
}
const binarySearchTree & operator = (const binarySearchTree & rhs);
binaryNode *getRoot(){
return root;
}
private:
void insert(const Comparable & x, binaryNode * & t) const{
if( t == NULL)
t = new binaryNode(x, NULL, NULL);
else if (x < t -> element)
insert(x, t-> left);
else if (t -> element < x)
insert(x, t-> right);
else
;
}
binaryNode *root;
int treeDepth;
};
int main(int argc, char **argv)
{
binarySearchTree<int>aTree;
aTree.insert(6);
aTree.insert(5);
aTree.insert(4);
aTree.remove(4);
aTree.remove(6);
aTree.printTree();
return 0;
}
Explanation / Answer
#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
#include<cstdlib>
#define MAX_SIZE 1000//maximum length of inputted line
struct BSTNode{
char *word;//pointer to the word that is being stored
int count;//variable used to count the number of times the word encounter
struct BSTNode *left;//points to the left subtree
struct BSTNode *right;//points to the right subtree
};
void print(struct BSTNode *);//function to print the tree
int isNonword(char *p);//function to determine if it is a word or not
struct BSTNode *allocate(char *word){//create a node
struct BSTNode *newNode= new BSTNode;//pointer to new node
newNode->word= word;
newNode->count=1;
newNode->left=NULL;
newNode->right=NULL;
return(newNode);
}
struct BSTNode *insert(struct BSTNode *root1,
char *word)
{//insert a word into
int compare;
//binary tree, variable used to get the result from strcmp
if(root1==NULL){
return(allocate(word));
}
if((compare= strcmp(word,root1->word))==0)
{
//if it is equal to zero it means
root1->count++;//the two words are equal
}
else if(compare>0)
{
//if it is less than zero then the word pointed to by
root1->right=insert(root1->right,word);
//word is greater than to the word
}//pointed to by root1
else{
//if it is less than zero then
root1->left=insert(root1->left,word);
//then the word pointed to by
}//word is less than to the word pointed
//to by root1
return (root1);//return the pointer to the root
//of the tree
}//end of the function
int main()
{
//main program
char line[MAX_SIZE];//variable for inputted line
char word[MAX_SIZE];//variable for word
int lines=0;//variable for current line number
char *p;//variable for current line position
char *w;//variable that is used for loading a line
struct BSTNode *root;//the root of the tree
ifstream inWordFile("words.txt",ios::in);
//opens a file to read
if(!inWordFile)
{
cerr<<"File could not be opened,"<<endl;
exit(1);
}
while(inWordFile>>(fgets(line, 100, stdin)))
{
//read the file a line
lines++;//at a time
p=line;
while(*p)
{//loops until the end of the line
while(*p && (isNonword(p)!=1))//omit leading
p++; //non-word
w= word;
//stop at word, then put it into word[]
while(isNonword(p)==0)
*w++= *p++;
*w= '';
if(word[0])//inserting it into the tree
root= insert(root, word);
}
}
print(root);//print the word
system("puse");
return 0;//indicate that program exited cleanly
}//end of main program
void print(struct BSTNode *root1)
{
//struct BSTNode *root1 is the root of the tree
if(root1==NULL)
//if there is no treee it means nothing to print
return;
print(root1->left);//prints the left subtree
cout<<" "<<root1->count<<" "<<root1->word<<endl;
print(root1->right);//prints the right subtree
}//end of print funtion
int isNonword(char *p)
{
//checks if it is a character or functuation mark
if((*p=='.')||(*p==','))
return 1;
//returns 1 if it is a functuation mark
else if((*p=='!')||(*p=='?'))
return 1;
else
return 0;//else return 0 if character/letter
}//end of isNonword function