Java Reference
In-Depth Information
Programming Projects
1.
Implement a yes/no guessing game called 20 Questions using a binary tree. At the beginning of each round of the
game, the human player thinks of an object. The computer tries to guess the object by asking a series of no more
than 20 yes-or-no questions. Eventually the computer guesses what the object is. If this guess is correct, the computer
wins; if not, the human player wins.
The computer keeps track of a binary tree with nodes representing questions and answers. A “question” node contains
a left “yes” subtree and a right “no” subtree. An “answer” node is a leaf. This tree can be traversed to ask the human
player questions until it reaches a leaf node, at which point the computer asks whether that answer is the correct one.
Initially the computer is not very intelligent, but it grows more intelligent with each game. If the computer's answer
guess is incorrect, the player must give it a new question to help it in future games. This is similar to the game found
at the web site
http://animalgame.com/.
You should write methods to construct a tree, play a game, and save/load the
tree's state from a file.
2.
Write a program that encodes and decodes Morse code files using a binary tree. Morse code is a system that encodes
the 26 English letters and 10 numeric digits into sequences of dots, dashes, and spaces. Your tree can store the
encodings of each letter and number, going left for a dot and right for a dash. When your program reads a sequence
of Morse code characters, it should traverse the tree in the appropriate direction for each character and output the
letter or number it reaches at the end of each sequence.
3.
Write a program that performs Huffman encoding and compression using a binary tree. Huffman coding is an algorithm
devised by David A. Huffman of MIT in 1952 for compressing text data to make a file occupy a smaller number of
bytes. The idea of Huffman coding is to abandon the rigid 8-bits-per-character requirement of ASCII encoding and
use different-length binary encodings for different characters. The advantage of doing this is that if a character occurs
frequently in the file, such as the letter e, it could be given a shorter encoding (fewer bits), making the file smaller.
Your program should contain methods to read an input text file, count its characters, and use these counts to build a
Huffman tree for the characters by frequency. Use this Huffman tree to output an encoded and compressed version of
the file. Also write a method to read and decompress this file later. You may want to use helper classes for reading
and writing a file one bit at a time. You can find classes called
BitInputStream
and
BitOutputStream
at our
web site,
http://buildingjavaprograms.com.
4.
The actual
Set
interface in the
java.util
package has several methods that are beyond those implemented by our
search tree in this chapter. Write a version of
SearchTree<E>
that adds some or all of these methods. The methods
to add are the following (some headers are slightly modified; see the Java API Specification for descriptions of each
method):
•
public void addAll(SearchTree<E> tree)
•
public void clear()
•
public boolean containsAll(SearchTree<E> tree)
•
public boolean equals(Object o)
•
public boolean isEmpty()
•
public boolean remove(Object o)
•
public void removeAll(SearchTree<E> tree)
•
public void retainAll(SearchTree<E> tree)
•
public Object[] toArray()
Search WWH ::
Custom Search