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.

• `BinaryTree(rootValue)` returns a binary tree with the given root value and no children.
• `setRootValue(rootValue)` sets the root value.
• `getRootValue()` returns the root value.
• `setLeftChild(binaryTree)` sets the left child to the given binary tree. You do not need to check that `binaryTree` is a true `BinaryTree`, but you may if you like.
• `getLeftChild()` returns the left child.
• `setRightChild(binaryTree)` sets the right child to the given binary tree.
• `getRightChild()` returns the right child.
• `__str__()` is a special Python method that returns a string representation of the binary tree, as described below.
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')
mytree.setRightChild(BinaryTree('righty'))
mytree.getRightChild().setLeftChild(BinaryTree('rightylefty'))```
...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.

• `Tree(rootValue)` returns a tree with the given root value and no children.
• `setRootValue(rootValue)` sets the root value.
• `getRootValue()` returns the root value.
• `numChildren()` returns the number of children.
• `appendChild(tree)` appends a `Tree` as a child. Again, you do not need to check that `tree` is a `Tree`, but you may if you like.
• `insertChild(index, tree)` inserts the given tree at the given index, similarly to how one inserts an object into a list in Python.
• `popChild(index=None)` removes the child at the given index and returns it, similarly to how one pops an object from a Python list. The `index=None` syntax specifies that the user may omit the `index` argument, in which case it is assumed to have a value of `None`. This is how Python's list `pop()` behaves.
• `__setitem__(index, tree)` is a special Python method that sets the child at the given index to the given tree.
• `__getitem__(index)` is a special Python method that returns the child at the given index.
• `__str__()` is that special Python method that returns a string representation. See details below.
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)
mytree.appendChild(Tree('oney'))
print str(mytree)
mytree.appendChild(Tree('twoy'))
print str(mytree)
mytree[0].appendChild(Tree('oneyoney'))
print str(mytree)
mytree[0].appendChild(Tree('oneytwoy'))
print str(mytree)
mytree[0][0].appendChild(Tree('oneyoneyoney'))
print str(mytree)
mytree.popChild(0)
print str(mytree)```
...produces this output:
```[rooty]
[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:

• `setFirstChild(tree)` sets the first child to the given tree.
• `getFirstChild()` returns the first child.
• `setNextSibling(tree)` sets the next sibling to the given tree.
• `getNextSibling()` returns the next sibling.
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:

• `BinaryTree` is correct (3 points) and clear/well-commented (1 point).
• `parse()` and `evaluate()` are correct (3 points) and clear/well-commented (1 point).
• `Tree` based on a list is correct (3 points) and clear/well-commented (1 point).
• `Tree` based on a binary tree is correct (3 points) and clear/well-commented (1 point).