A text concordance is an alphabetical listing of all the distinct words in a document.

The basic storage structure for a concordance is an array of Binary Search Trees, one tree for

words starting with A, one for words starting with B, etc.

1. You will write a c++ program that reads a text file and constructs the concordance that

contains the distinct words in the file and, for each word, the line number of the first

occurrence, and how many there are in the file then allows the user to search the

concordance for a particular word, and to print out a list of all the distinct words in the

concordance.

2. Words that are upper case (or have uppercase letters in them) are treated the same as the

word written with all lowercase letters.

3. Words in the list will NOT have ANY non-alphabetic characters at the beginning or end

of the word

o i.e. the word hello!! and the word ---Hello will both be saved as the word hello

4.The program will ask the user to input the file name at run-time

5.The program will ask the user for words to search for until the user indicates they are

done

6. After searching for words, the program will display a list of the distinct words in

alphabetical order, the line number of their first occurrence, and how many there are in

the file

I also attach the code that has to be used. Please use template and struct. Try to solve the question with my code . May be or not ,you need to change a little of my code. use My code when solve. Please do not use cctype, set, map, algorithm, vector,sstype,sstring related header file and code.

Simply use string, fstream.. to complete thus c++ code. I already attached code for this program. Please use this code to complete the whole program. For function implimentation or in main.cpp, use that kind of code for which only need string,fstream header file. Do not use sstype,cctype, map,vector, algorithm, set type of header file.

also, the output will be count the each word in every line and it will show the first line and total ocuurance of each word.

Also, it will ignore all other characters other than alphabet. exampel; 2023th, it will ignore the number but will count the letter t and h.

please write complete programm. do as easy for beginners

it will show the every single alphabet not the word. if possible provide output too

#include

#ifndef BINARY_SEARCH_TREE

#define BINARY_SEARCH_TREE

template

class BST

{

public:

/***** Function Members *****/

BST();

/*------------------------------------------------------------------------

Construct a BST object.

Precondition: None.

Postcondition: An empty BST has been constructed.

-----------------------------------------------------------------------*/

bool empty() const;

/*------------------------------------------------------------------------

Check if BST is empty.

Precondition: None.

Postcondition: Returns true if BST is empty and false otherwise.

-----------------------------------------------------------------------*/

bool search(const DataType & item) const;

/*------------------------------------------------------------------------

Search the BST for item.

Precondition: None.

Postcondition: Returns true if item found, and false otherwise.

-----------------------------------------------------------------------*/

void insert(const DataType & item);

/*------------------------------------------------------------------------

Insert item into BST.

Precondition: None.

Postcondition: BST has been modified with item inserted at proper

position to maintain BST property.

------------------------------------------------------------------------*/

void remove(const DataType & item);

/*------------------------------------------------------------------------

Remove item from BST.

Precondition: None.

Postcondition: BST has been modified with item removed (if present);

BST property is maintained.

Note: remove uses auxiliary function search2() to locate the node

containing item and its parent.

------------------------------------------------------------------------*/

void inorder(ostream & out) const;

/*------------------------------------------------------------------------

Inorder traversal of BST.

Precondition: ostream out is open.

Postcondition: BST has been inorder traversed and values in nodes

have been output to out.

Note: inorder uses private auxiliary function inorderAux().

------------------------------------------------------------------------*/

private:

/***** Node class *****/

class BinNode

{

public:

DataType data;

BinNode * left;

BinNode * right;

// BinNode constructors

// Default -- data part is default DataType value; both links are null.

BinNode()

: left(0), right(0)

{}

// Explicit Value -- data part contains item; both links are null.

BinNode(DataType item)

: data(item), left(0), right(0)

{}

};// end of class BinNode declaration

typedef BinNode * BinNodePointer;

/***** Private Function Members *****/

void search2(const DataType & item, bool & found,

BinNodePointer & locptr, BinNodePointer & parent) const;

/*------------------------------------------------------------------------

Locate a node containing item and its parent.

Precondition: None.

Postcondition: locptr points to node containing item or is null if

not found, and parent points to its parent.#include

------------------------------------------------------------------------*/

void inorderAux(ostream & out,

BinNodePointer subtreePtr) const;

/*------------------------------------------------------------------------

Inorder traversal auxiliary function.

Precondition: ostream out is open; subtreePtr points to a subtree

of this BST.

Postcondition: Subtree with root pointed to by subtreePtr has been

output to out.

------------------------------------------------------------------------*/

/***** Data Members *****/

BinNodePointer myRoot;

}; // end of class template declaration

//--- Definition of constructor

template

inline BST::BST()

: myRoot(0)

{}

//--- Definition of empty()

template

inline bool BST::empty() const

{ return myRoot == 0; }

//--- Definition of search()

template

bool BST::search(const DataType & item) const

{

BST::BinNodePointer locptr = myRoot;

bool found = false;

while (!found && locptr != 0)

{

if (item < locptr->data) // descend left

locptr = locptr->left;

else if (locptr->data < item) // descend right

locptr = locptr->right;

else // item found

found = true;

}

return found;

}

//--- Definition of insert()

template

inline void BST::insert(const DataType & item)

{

BST::BinNodePointer

locptr = myRoot, // search pointer

parent = 0; // pointer to parent of current node

bool found = false; // indicates if item already in BST

while (!found && locptr != 0)

{

parent = locptr;

if (item < locptr->data) // descend left

locptr = locptr->left;

else if (locptr->data < item) // descend right

locptr = locptr->right;

else // item found

found = true;

}

if (!found)

{ // construct node containing item

locptr = new BST::BinNode(item);

if (parent == 0) // empty tree

myRoot = locptr;

else if (item < parent->data ) // insert to left of parent

parent->left = locptr;

else // insert to right of parent

parent->right = locptr;

}

else

cout << "Item already in the tree ";

}

//--- Definition of remove()

template

void BST::remove(const DataType & item)

{

bool found; // signals if item is found

BST::BinNodePointer

x, // points to node to be deleted

parent; // " " parent of x and xSucc

search2(item, found, x, parent);

if (!found)

{

cout << "Item not in the BST ";

return;

}

//else

if (x->left != 0 && x->right != 0)

{ // node has 2 children

// Find x's inorder successor and its parent

BST::BinNodePointer xSucc = x->right;

parent = x;

while (xSucc->left != 0) // descend left

{

parent = xSucc;

xSucc = xSucc->left;

}

// Move contents of xSucc to x and change x

// to point to successor, which will be removed.

x->data = xSucc->data;

x = xSucc;

} // end if node has 2 children

// Now proceed with case where node has 0 or 1 child

BST::BinNodePointer

subtree = x->left; // pointer to a subtree of x

if (subtree == 0)

subtree = x->right;

if (parent == 0) // root being removed

myRoot = subtree;

else if (parent->left == x) // left child of parent

parent->left = subtree;

else // right child of parent

parent->right = subtree;

delete x;

}

//--- Definition of inorder()

template

inline void BST::inorder(ostream & out) const

{

inorderAux(out, myRoot);

}

//--- Definition of search2()

template

void BST::search2(const DataType & item, bool & found,

BinNodePointer & locptr,

BinNodePointer & parent) const

{

locptr = myRoot;

parent = 0;

found = false;

while (!found && locptr != 0)

{

if (item < locptr->data) // descend left

{

parent = locptr;

locptr = locptr->left;

}

else if (locptr->data < item) // descend right

{

parent = locptr;

locptr = locptr->right;

}

else // item found

found = true;

}

}

//--- Definition of inorderAux()

template

void BST::inorderAux(ostream & out,

BinNodePointer subtreeRoot) const

{

if (subtreeRoot != 0)

{

inorderAux(out, subtreeRoot->left); // L operation

out << subtreeRoot->data << " "; // V operation

inorderAux(out, subtreeRoot->right); // R operation

}

}

#endif