Review Questions

1. Draw the tree that would be formed by inserting the words in this question into a binary search tree. Use lowercase letters.

2. Show all three traversals of this tree.

3. Show the tree from Question 1 after removing draw, by, and letters in that order.

4. Answer Question 1, but store the words in a heap instead of a binary search tree.

5. Given the following frequency table, construct a Huffman code tree. Show the initial priority queue and all changes in its state as the tree is constructed.

Programming Projects

1. Assume that a class Expressi onTree has a data field that is a BinaryTree. Write an instance method to evaluate an expression stored in a binary tree whose nodes contain

Review Questions

1. Show where the following keys would be placed in a hash table of size 5 using open addressing: 1000, 1002, 1007, 1003. Where would these keys be after rehashing to a table of size 11?

2. Answer Question 1 for a hash table that uses chaining.

3. Write a toString method for class Hashtabl eOpen. This method should display each table element that is not null and is not deleted.

4. Class Hashtabl eChain uses the class Li nkedlis t, which is implemented as a double-linked list. Write the put method using a single linked list to hold elements that hash to the sane index.

5. Write the get method for the class in Question 4.

6. Write the reffove method for the class in Question 4.

7. Write inner class Ent rySet for the class in Question 4 (see Listing. 7.11).

Programming Projects

1. Complete all methods of class HuffmanTree and test them out using a document file and a Java source file on your computer. You can download class Bi tSt ring from the Web site for this textbook.

2. the a HashNap to store the frequency counts for all the words in a large text document. When vnn arc done ilicrdav the contents of this Hachlian Nm create a we view of the

Programming Projects

I. Assume that a class ExpressionTree has a data field that is a BinaryTree. Write an instance method to evaluate an expression stored in a binary tree whose nodes contain either integer values (stored in Integer objects) or operators (stored in Character objects). Your method should implement the following algorithm.

Algorithm to Evaluate an Expression Tree

1. if the root node is an Integer object

2. Return the integer value.

3. else if the root node is a Character object

4. Let leftVal be the value obtained by recursively applying this algorithm to the left subtree.

5. Let rightVal be the value obtained by recursively applying this algorithm to the right subtree.

6. Return the value obtained by applying the operator in the root node to leftVal and rightVal.

Use method readBi naryTree to read the expression tree.

2. Write an application to test the HuffnanTree class. Your application will need to read a text file and build a frequency table for the characters occurring in that file. Once that table is built, create a Huffman code tree and then a string consisting of '0' and '1' digit characters that represents the code string for that file. Read that string back in and re-create the contents of the original file.

3. Solve Programming Project 4 in Chapter 4, 'Queues," using the class Priori tyQueue.

4. Build a generic Huffmaniree.cT> class such that the symbol type T is specified when the tree
is created. Test this class by using it to encode the words in your favorite nursery rhyme.

5. Write clone, size, and height methods for the BinaryTree class.

Programming Projects

1. Complete all methods of class HuffmanTree and test them out using a document file and a Java source file on your computer. You can download class Bi tStri ng from the Web site for this textbook.

2. Use a FleshMap to store the frequency counts for all the words in a large text doctunent. When you are done, display the contents of this HashMap. Next, create a set view of the Map and store its contents in an array. Then sort the array based on key value and display it. Finally, sort the array in decreasing order by frequency and display it.

3. Solve Project 2 using a TreeMap. You can display the words in key sequence without performing a sort.

4. Modify Project 2 to save the line numbers for every occurrence of a word as well as the count.

5. (Based on an example in Brian W. Kernighan and Rob Pike, The Practice of Programming, Addison-Wesley, 1999) We want to generate "random text" in the style of another author. Your first task is to collect a group of prefix strings of two words that occur in a text file and associate them with a list of suffix strings using a Map. For example, the text for Charles Dickens' A Christmas Carol contains the four phrases:

Marley was dead: to begin with. Marley was as dead as a door-nail. Marley was as dead as a door-nail. Marley was dead.

The prefix string "Marley was" would be associated with the ArrayList containing the four suffix strings "dead: ", "as", "as", "dead. ''. You must go through the text and examine each successive pair of two-word strings to see whether that pair is already in the map as a key. If so, add the next word to the ArrayLi st that is the value for that prefix string. For example, in examining the first two sentences shown, you would first add to the entry ("Harley was", ArrayLi st "dead :"). Next you would add the entry ("was dead", ArrayList "as"). Next you would add the entry ("dead as", ArrayList "al, and so on.