Mutable Trees

We define a tree to be a recursive data abstraction that has a label (the value stored in the root of the tree) and branches (a list of trees directly underneath the root).

Previously we implemented trees by using a functional data abstraction, with the tree constructor function and the label and branches selector functions. Now we implement trees by creating the Tree class. Here is part of the class included in the lab.

class Tree:
    """
    >>> t = Tree(3, [Tree(2, [Tree(5)]), Tree(4)])
    >>> t.label
    3
    >>> t.branches[0].label
    2
    >>> t.branches[1].is_leaf()
    True
    """
    def __init__(self, label, branches=[]):
        for b in branches:
            assert isinstance(b, Tree)
        self.label = label
        self.branches = list(branches)

    def is_leaf(self):
        return not self.branches

Even though this is a new implementation, everything we know about the functional tree data abstraction remains true. That means that solving problems involving trees as objects uses the same techniques that we developed when first studying the functional tree data abstraction (e.g. we can still use recursion on the branches!). The main difference, aside from syntax, is that tree objects are mutable.

Here is a summary of the differences between the tree data abstraction implemented as a functional abstraction vs. implemented as class:

-Tree constructor and selector functionsTree class
Constructing a treeTo construct a tree given a label and a list of branches, we call tree(label, branches)To construct a tree object given a label and a list of branches, we call Tree(label, branches) (which calls the Tree.__init__ method).
Label and branchesTo get the label or branches of a tree t, we call label(t) or branches(t) respectivelyTo get the label or branches of a tree t, we access the instance attributes t.label or t.branches respectively.
MutabilityThe functional tree data abstraction is immutable because we cannot assign values to call expressionsThe label and branches attributes of a Tree instance can be reassigned, mutating the tree.
Checking if a tree is a leafTo check whether a tree t is a leaf, we call the convenience function is_leaf(t)To check whether a tree t is a leaf, we call the bound method t.is_leaf(). This method can only be called on Tree objects.

Implementing trees as a class gives us another advantage: we can specify how we want them to be output by the interpreter by implementing the __repr__ and __str__ methods.

Here is the __repr__ method:

def __repr__(self):
    if self.branches:
        branch_str = ', ' + repr(self.branches)
    else:
        branch_str = ''
    return 'Tree({0}{1})'.format(self.label, branch_str)

With this implementation of __repr__, a Tree instance is displayed as the exact constructor call that created it:

>>> t = Tree(4, [Tree(3), Tree(5, [Tree(6)]), Tree(7)])
>>> t
Tree(4, [Tree(3), Tree(5, [Tree(6)]), Tree(7)])
>>> t.branches
[Tree(3), Tree(5, [Tree(6)]), Tree(7)]
>>> t.branches[0]
Tree(3)
>>> t.branches[1]
Tree(5, [Tree(6)])

Here is the __str__ method. You do not need to understand how this function is implemented.

def __str__(self):
    def print_tree(t, indent=0):
        tree_str = '  ' * indent + str(t.label) + "\n"
        for b in t.branches:
            tree_str += print_tree(b, indent + 1)
        return tree_str
    return print_tree(self).rstrip()

With this implementation of __str__, we can pretty-print a Tree to see both its contents and structure:

>>> t = Tree(4, [Tree(3), Tree(5, [Tree(6)]), Tree(7)])
>>> print(t)
4
  3
  5
    6
  7
>>> print(t.branches[0])
3
>>> print(t.branches[1])
5
  6

(Optional) Side notes: In real-world programs, the oop-style Tree is actually used much more often than the functional-style tree. What may surprise you is that Python is actually not the best programming language suitable for functional programming. Python is among the mainstream programming languages that support a mix-style programming paradigm.