Introduction to Data Structures CS106 Spring 2012

Lab 5: Abstraction and Uses of Binary Trees

Check out the twenty_questions project for Lab 5. This contains the DocTest infrastructure but nothing else useful — you will need to enter the classes and algorithms for this project from scratch. There are two major parts to this lab:

1. Create a class BinaryTree to represent binary trees in Python, in the file BinaryTree.py.

   • Your class should provide binary tree constructors, accessor operations to retrieve the value at the root and the left and right subtrees, and appropriate equality testing (__eq__, for ==) and abstraction functions (__repr__).
   • Create a test suite for your BinaryTree class, at the top of BinaryTree.py.
   • You may represent the binary trees with the “list of lists” representation from 6.4.1 or the “nodes and references” representation from 6.4.2 (or some other representation if you can come up with one). You are welcome to copy as much as you like from the textbook, but you must cite it appropriately if you do so.
   • You must provide axioms for all of your tree operations, so you should make sure that you have “pure-functional” versions of the fundamental constructors and the accessors. You may optionally include mutator operations as well if you like, but make sure to provide axioms for them (and tests in your test suite) if you do.

2. In the file game.py, create a program to play the “20 questions” game for animals, along the lines discussed in lecture (your program must take the “guess the secret thing” role rather than the role of coming up with something and answering questions). You should use the BinaryTree class to represent the questions (as the values of the non-leaf nodes) and possible results (the values of the leaf nodes). You should do this in two steps:

   1. Start by writing a version that has a pre-built tree with at least six leaves (this will be a variable in the game procedure) and asks the questions from the tree until it arrives at a leaf, and then ask whether or not it has identified the mystery animal. If it does not know the animal, it can just print something like “rats — I didn't get it”. Since this is game is almost entirely composed of user interface operations, you don't need to have a test suite, but you can cut and paste the output of various test runs into a comment at the top, as documentation for the user.
   2. Enhance your program (and, if necessary, your BinaryTree class, along with its axioms and test suite) so that the can be played repeatedly, with the program adding new animals to the tree when it fails to guess correctly. When told that it has not identified the mystery animal, your program should ask what it was and then ask for a question to distinguish it from its final guess. It should use this information to adjust the tree accordingly for the next game (you do not need to keep the tree balanced). At the completion of a series of games, you should print the modified tree. (If you like, you can cut and paste the new tree back into the program so that it will be enhanced permanently, for the next round — in fact, you are invited to think about how to automate this).

As always, add a README.txt file and a README-DESIGN.txt file. Then use Team->Commit to hand in your work as well as Blackboard (and, of course, you can also use commit to make backups also at each significant milestone, e.g., at the end of each bullet item above).