Purchase Solution

C++ Binary Tree Sorting of text words

Not what you're looking for?

Ask Custom Question

As different authors tend to use different vocabularies and to use common words with differing frequencies. Given an essay or other text, it is interesting to find what distinct words are used and how many times each is used.

I'm trying to produce a driver program and the information-retrieval package using ordinary binary search trees.

I really want to complete this program using the outline I'm presenting you here:
1) Create the data structure (binary search tree).

2) Ask the user for the name of a text file and open it to read.

3) Read the file, split it apart into individual words, and insert the words into the data structure. With each word will be kept a frequency count (how many times the word appears in the input), and when duplicate words are encountered, the frequency count will be increased. The same word will not be inserted twice in the tree.

4) Print the number of comparisons done and the CPU time used in part 3. (By CPU time, I mean the amount of time for which the CPU was used for processing the comparisons (reading the file, splitting & inserting words)).

5) That I can, If I wish, print out all the words in the data structure, in alphabetical
order, with their frequency counts.

6) Put everything in parts 2-5 into a do . . . while loop that will run as many
times as the user wishes. Thus the user can build the data structure with
more than one file if desired. By reading the same file twice, the user can
compare time for retrieval with the time for the original insertion. (Let me clarify here, because parts 2 to 5 will be in a "do while" loop, then I can compare time for retrieval with the time for the original insertion).

Some additional specifications I was trying to implement to the program:
* I want the input to the driver will to be a file. The program will be executed with several different files; the name of the file to be used should be requested from the user while the program is running.

* A word is defined as a sequence of letters, together with apostrophes (') and hyphens (-), provided that the apostrophe or hyphen is both immediately preceded and followed by a letter. Uppercase and lowercase letters should be regarded as the same (by translating all letters into either uppercase or lowercase, as you prefer). A word is to be truncated to its first 20 characters (that is, only 20 characters are to be stored in the data structure) but words longer than 20 characters may appear in the text. Non-alphabetic characters (such as digits, blanks, punctuation marks, control characters) may appear in the text file. The appearance of any of these terminates a word, and the next word begins only when a letter appears.

* The program should not allow to be changed at all when I change implementation of data structures later.

Final specifications for the functions to I want implemented first with binary
search trees:
void update(const String &word,
Search_tree< Record > &structure, int &num_comps);

postcondition: If word was not already present in structure, then word has been inserted into structure and its frequency count is 1. If word was already present in structure, then its frequency count has been increased by 1. The variable parameter num_comps is set to the number of comparisons of words done.

void print(const Search_tree< Record > &structure);

postcondition: All words in structure are printed at the terminal in alphabetical order together with their frequency counts.

Purchase this Solution

Solution Summary

A Binary Tree is used to sort words read from a text. A text is provided in a file and is parsed by the program by certain rules and inserted into a binary tree. Binary tree is then used to display sorted results.

Solution Preview

Attached is the complete C++ project in Visual Studio 2010. If you are not using VS, you can take the following source files to your development system:


You will also find executable in the release folder which you can test. There are two .txt files I used for sample text input files.


Note. The Binary Tree implementation is limited to only the ...

Purchase this Solution

Free BrainMass Quizzes
Basic Networking Questions

This quiz consists of some basic networking questions.

Inserting and deleting in a linked list

This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.

Word 2010: Table of Contents

Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.

Basic UNIX commands

Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.

Basic Computer Terms

We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.