Introduction to Data Structures CS106 Spring
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:
Create a class BinaryTree to represent binary trees
in Python, in the file BinaryTree.py.
Your class should provide binary tree
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.
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:
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
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).