Homework 4 — Programming Language Paradigms

Objective

Develop mastery of object-oriented polymorphism.

Due Date

Beginning of class session 11.

Tasks

1. In Eclipse, check out the project PythonEtude, from your SVN repository. All your work for this assignment should be done within that project. Put your code in the given binary_tree.py file.

2. To help you develop this mastery, on this assignment you may use conditional statements only where specifically indicated. All other control must be done using polymorphic method dispatch or iterators. You may not use break or continue within loops.

   If you write a loop that iterates over a built-in Python list object, you may not mutate that list object within the loop. Per the Python Tutorial, Section 4.2, “It is not safe to modify the sequence being iterated over in the loop.” However, you may (and probably should) create your own iterable datatype that can safely be mutated during iteration. Such a custom datatype isn’t necessary for preorder(), inorder(), and postorder() below, but I suspect it is for levelorder().

   You’ll get a zero on this assignment if you don’t follow these restrictions!

3. Develop a module that defines classes representing binary trees. Your module must satisfy the following:
   1. Include iterator methods for the four standard tree traversals. You should use generators in your implementation where possible. Your iterators should be such that if t is a binary tree object, then the following loops would perform the appropriate traversals:

      • for a in t.preorder():
            print(a)
        

      • for b in t.inorder():
            print(b)
        

      • for c in t.postorder():
            print(c)
        

      • for d in t.levelorder():
            print(d)
        

      Hints:

      • You will likely want to create a helper class, EmptyIterator, that implements an empty iterator. So, for example, the following loop would print nothing:

            for e in EmptyIterator():
                print("Hi!")
        

      • In Python 3, you can’t mutate built-in lists or collections.deques while iterating over them, but you can make your own iterable queue class. (Perhaps you might want a deque field in instances of your class?)

   2. Include a top-level factory function, build_tree(preord, inord), that takes two strings representing a pre-order and in-order traversal of a tree. Based on these strings, your function should return an object representing a binary tree with one character stored in each node. Valid inputs will not have repeated characters. If the pair of strings do not represent a valid tree, your function should raise an appropriate exception. You may use conditional statements in your implementation of this function.

      Below are some valid function calls for your testing, though you should come up with some simpler ones on your own:

      • empty tree: build_tree('', '')
      • one-node tree: build_tree('A', 'A')
      • three-node tree full: build_tree('ABC', 'BAC')
      • three-node tree (left,right): build_tree('ABC', 'BCA')
      • WA5, #5: build_tree('THEQUICKLAZYFOX', 'QIUCEHLAZKFYTXO')
      • seven-node tree (full): build_tree('AQUICHE', 'UQIAHCE')
      • 15-node tree (full): build_tree('UNCOPYRIGHTABLE', 'OCPNRYIUTHAGLBE')
      • 12-node tree (lots of lefts and rights): build_tree('AMBIDEXTROUS', 'MIDBEARTUOXS')
      • 12-node tree (left, left, right, right, ...): build_tree('FLOWCHARTING', 'OWARNGITHCLF')
      • 10-node tree (no right-children for nodes at odd depth): build_tree('LUMBERJACK', 'EBMRULCAKJ')
   3. Write appropriate docstrings and other comments. (Don’t go overboard. Good choices of names will obviate the need for many comments.)
   4. Include appropriate tests for all the code you’ve written. The tests can be in whatever format seems best—doctests, test functions, etc.

Turn-in Instructions

Turn in your work by committing it to your SVN repository.