2008 October 13 / jjddaavviiss@@ccaarrlleettoonn..eedduu

Introduction To Trees

Carleton College CS 201, Prof. Joshua R. Davis

In this assignment you will implement a binary tree, a tree using a list, and a tree using a binary tree. You will also use the binary tree datastructure to parse and evaluate simple algebraic expressions.

0. Implement BinaryTree

Here is the ADT spec we will use for BinaryTree. By the way, it is slightly different from the one we discussed in class (the only difference is that the constructor takes a value now) and quite different from the one in the book.

The string representation should begin with "[", then give the string representation of the root value, then a comma and a space, then a string representation of the left child tree (or "[]" if there is no left child), then the comma and a space, then the string representation of the right child tree (or "[]" if there is no right child), and finally "]". For example, if we construct a tree using this sequence of commands...
mytree = BinaryTree('rooty')
...then at the end the string representation should be
[rooty, [], [righty, [rightylefty, [], []], []]]
Notice that this looks like a nest of Python lists. That's no accident; a nest of lists is one of our favorite ways to describe trees (more on that another time).

For this part of the assignment, implement the entire BinaryTree class, including __str__(), in a file binarytree.py.

1. Write Functions To Parse And Evaluate Algebraic Expressions

Our book describes a notion of fully-parenthesized arithmetic expressions, and describes how to scan, parse, and evaluate them. In this part of the assignment we do much the same thing, but with some important changes. First, we allow our expressions to involve not just numbers but also variables with names such as 'x', 'y', etc. Second, we clearly distinguish among the scanning, parsing, and evaluating processes (whereas the book combines them somewhat).

Let's briefly review the main ideas and jargon using an example. Suppose that we begin with a fully-parenthesized expression stored in a string:

mystring = '( ( 3 + x ) * 15 )'
Using the Python string method split(), we can easily scan this string into a list of tokens. Try it yourself.
mytokens = mystring.split()
Keep in mind that each token is a string. That is, the "15" is a string, not a number. It will not turn into a number until we do the evaluation step, later.

Once you have scanned the string into a list of tokens, you feed the list of tokens to the parse() function (which you will write). This function outputs a parse tree — that is, a binary tree in which the tokens are the values of the various tree nodes. Continuing our example, the parse tree's string representation is

[*, [+, [3, [], []], [x, [], []]], [15, [], []]]
(Draw this tree out yourself, to understand why it is correct.) Again, keep in mind that the tokens stored in the parse tree are all strings; "15" is still a string, not a number. This is a key difference between our approach and the book's.

Finally, you feed the tree to an evaluate() function (which you will write) to turn it into a numeric value. When you do this, you must specify the numeric value of each variable occurring in the original expression. For simplicity, let us assume that there is only one variable in any given expression — e.g. 'x' or 'y', but not both. So your evaluate() function should take in a parse tree, a variable name, and a value to plug in for that variable; it should return the overall numerical value of the expression. Continuing our example, suppose that the parse tree above is stored in mytree; then

evaluate(mytree, 'x', 2)
should return 75, since ( ( 3 + 2 ) * 15 ) = 75.

For this part of the assignment, write your parse() and evaluate() functions in a file called algebra.py.

2. Implement Tree Using A List

In class and in this assignment, our general Tree ADT is specified by the following method list. Notice that it is somewhat different from our book's.

The string representation of a Tree behaves a little differently from that of a BinaryTree due to the variable number of children. Namely, we do not insert commas and "[]" to indicate the place of a missing child; instead, we just list the children that are there. For example, the code...
mytree = Tree('rooty')
print str(mytree)
print str(mytree)
print str(mytree)
print str(mytree)
print str(mytree)
print str(mytree)
print str(mytree)
...produces this output:
[rooty, [oney]]
[rooty, [oney], [twoy]]
[rooty, [oney, [oneyoney]], [twoy]]
[rooty, [oney, [oneyoney], [oneytwoy]], [twoy]]
[rooty, [oney, [oneyoney, [oneyoneyoney]], [oneytwoy]], [twoy]]
[rooty, [twoy]]

For this part of the assignment, implement the Tree class, including the three special methods, in a file treeusinglist.py. Follow the implementation idea we discussed in class, where each tree node stores (1) its value and (2) a Python list of children. (Note: This is different from the idea that a tree is simply a "nest of lists", with the 0th item in the list being the root value, and the other items being children. As we discussed it, that produced a different ADT, so it is not what I'm talking about in this assignment. Nevertheless, our string representation does give the impression that the tree is a nest of lists, because that is a standard way to write down trees, no matter what the exact ADT is.)

3. Implement Tree As A Binary Tree

In class we've discussed a "first child, next sibling" trick that lets you implement an arbitrary tree using a binary tree. In this part of the assignment, you will implement the Tree ADT described in the preceding section as a subclass of BinaryTree, as follows.

In the file treeusingbinarytree.py, declare Tree as a subclass of BinaryTree. Implement these four methods using BinaryTree's methods:

Then, in this same file, implement the full Tree ADT using only these four methods. If you do it the way I expect, then you should not need to override __init__(), setRootValue(), or getRootValue().

4. Submit Your Work Electronically

By Wednesday at 11:59 PM, submit your four files (binarytree.py, algebra.py, treeusinglist.py, and treeusingbinarytree.py) electronically, either using hsp or by putting it on COURSES manually. Your work will be graded based on these criteria: