Trees

Two metaphors trees

There is two metaphors to describe tree.

1. Recursive description (wooden trees):

A tree has a root label and a list of branches
Each branch is a tree
A tree with zero branches is called a leaf
A tree starts the root

2. Relative Description (family trees):

Each location in a tree is called a node
Each node has a label that can be any value
One node can be the parent/children of another
The top node is the root node

Implementing the Tree Abstraction

def tree(label, branches =[]):
    for branch in branches:
        assert is_tree(branch)
    return[label] + list(branches)

def label(tree):
    return tree[0]

def branches(tree):
    return tree[1:]

def leaves(tree):
    if is_leaf(tree):
        return [label(tree)]
    else:
        return sum([leaves(b) for b in branches(tree)])

def is_tree(tree):
    if type(tree) != list or len(tree) < 1:
     return False
    for branch in branches(tree):
        if not is_tree(branch):
            return False
    return True

def is_leaf(tree):
    return not branches(tree)


def count_leaves(t):
    if is_leaf(t):
        return 1
    else:
        branch_counts = [count_leaves(b) for b in branches(t)]
        return sum(branch_counts)

def increment_leaves(t):
    if is_leaf(t):
        return tree(label(t) + 1)
    else:
        return tree(label(t), [increment_leaves(b) for b in branches(t)])

def increment(t):
    return tree(label(t) + 1, [increment(b) for b in branches(t)])

def print_sums(t, path_sum):
    path_sums = path_sum + label(t)
    if is_leaf(t):
        print(path_sum)
    else:
        for branch in branches(t):
            path_sums(branch, path_sums)


def count_paths(t, total):
    if label(t) == total:
        return 1

    else:
        return 0

    return found + sum([count_paths(b, total - label(t)) for b in branches(t)])

>>> tree(1)
[1]
>>> tree(1, [2, 3])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "C:\Users\CS61A\tree\tree.py", line 3, in tree
    assert is_tree(branch)
AssertionError
>>> tree(1, [tree(2), tree(3)])
[1, [2], [3]]
>>> t = tree(1, [tree(2), tree(3)])
>>> tree(4, [t])
[4, [1, [2], [3]]]

# complex tree
>>> t1 = tree(3, [tree(4), tree(5), tree(6)])
>>> t2 = tree(7, [tree(8), tree(9)])
>>> tree(1, [tree(2), t1, t2])
[1, [2], [3, [4], [5], [6]], [7, [8], [9]]]

Due to abstraction, you cannot be input the number directory into the list.

Tree Processing

fibonatti tree

def fib_tree(n):
  if n == 0 or n == 1:
    return tree(n)
  else:
    left, right = fib_tree(n - 2), fib_tree(n - 1)
    return tree(label(left) + label(right), [left, right])

>>> fib_tree(4)
[3, [1, [0], [1]], [2, [1], [1, [0], [1]]]]
>>> fifth = fib_tree(5)
>>> fifth
[5, [2, [1], [1, [0], [1]]], [3, [1, [0], [1]], [2, [1], [1, [0], [1]]]]]
>>> label(branches(fifth)[0])
2
>>> count_leaves(fifth)
8


def height(t):
    """Return the height of a tree.

    >>> t = tree(3, [tree(5, [tree(1)]), tree(2)])
    >>> height(t)
    2
    >>> t = tree(3, [tree(1), tree(2, [tree(5, [tree(6)]), tree(1)])])
    >>> height(t)
    3
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t):
        return 0

    return max([height(b) + 1 for b in branches(t)])

    if is_leaf(t):
        return label(t)

    return max([label(t) + max_path_sum(b) for b in branches(t)])


def find_path(t, x):
    """
    >>> t = tree(2, [tree(7, [tree(3), tree(6, [tree(5), tree(11)])] ), tree(15)])
    >>> find_path(t, 5)
    [2, 7, 6, 5]
    >>> find_path(t, 10)  # returns None
    """
    if x == label(t):
        return [x]
    for b in branches(t):
        path = find_path(b, x)
        if path:
            return [label(t)] + path

Tree Algorithm