Implement a unique-keyed BST in C++. (It would be easier in Java, and still easier in Racket or Python, but I want you to do explicit memory management. Deal with it.) Use strings as the keys, and integers as the values. Each of your functions should report not only the right answer, but how long it took to run in milliseconds. (You can do this by printing a message, or by returning a tuple of values.)
Shaffer gives you much of this in Java. You may want to download the C++ edition of his textbook to get the corresponding C++ code as a starting point; you'll still need to write test cases, and add some more functions.
Required operations:
treesort function that takes in a list
of strings, sorts it using a BST, and returns the sorted list.
Dr. Siegfried's traditional project for this course: a "concordance" program that takes in a bunch of text, breaks it into words, and produces an alphabetized list of words, with the number of times each word appears in the text. A "word" is defined, for purposes of this problem, as a sequence of one or more letters: you can throw away spaces, punctuation, numbers, newlines, etc.
For example, applying the program to the preceding paragraph should produce an answer like
1 A 1 Dr 1 Siegfried 3 a 1 alphabetized 1 an 1 and 1 appears 1 as 1 away 1 breaks 1 bunch 1 can 1 count 1 course 1 defined 1 each 1 etc 2 for 2 in 1 into 1 is 1 it 1 letters 1 list 1 newlines 1 number 1 numbers 5 of 1 problem 1 produces 1 program 1 project 1 punctuation 1 purposes 1 reads 1 s 1 sequence 1 spaces 2 text 1 that 2 the 2 this 1 throw 1 times 1 traditional 1 with 3 word 2 words 1 you(I don't really care about output formatting, as long as I can see the information and it's alphabetized.)
I actually did the above in two lines with Unix shell filters, but since this is a data structures course, I want you to write it using the BST implementation from above.
Your methods should report not only the right answer, but also how long it took to execute the method, in milliseconds. I'll try it on some large samples of text, and will expect your method to run reasonably fast.