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.

  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).