CS61A Lab 9: Recursive Data - Trees and Sets (Solutions)

Week 9, 2011




General Trees (with infinite children)

Trees are a way we have of representing a hierarchy of information. A family tree is a good example of something with a tree structure. You have a matriarch and a patriarch followed by all the descendants. Alternately, we may want to organize a series of information geographically. At the very top, we have the world, but below that we have countries, then states, then cities. We can also decompose arithmetic operations into something much the same way.

The name 'tree' comes from the branching structure of the pictures, like real trees in nature except that they are drawn with the root at the top and the leaves at the bottom.

Terminology

	node 		-	a point in the tree. In these pictures, each node includes a datum (value at each node)
	root 		- 	the node at the top. Every tree has one root node
	children	- 	the nodes directly beneath it.
	leaf 		- 	a node that has no children. 

Representation

We are going to create our own tree structure called Trees (note the capital T!). This is only one implementation of a tree structure in which every tree has at least one node, every node has a datum (values at internal nodes), and nodes can have any number of children. Here are the constructor and selectors:


	make_tree(datum, children)
	datum(node)
	children(node)

The selector children should return a list of trees. There is a name for a list of trees: a forest!

It is very important to remember that Tree and Forest are two different data types! A forest is just a list, although its elements are required to be trees, and so we can manipulate forests using the standard procedures for sequences (slicing, popping, appending, concatenating, etc.). A tree is not a sequence, and should be manipulated only with the tree constructor and selectors. DATA ABSTRACTION!

A leaf node is one with no children: leaf(node) will return true if the children of the node is the empty list.

The implementation of this ADT can be found in the following file: ~cs61a/lib/tree-op.py

Question 1:

The following exercise is about Trees. To use the Tree ADT with constructors make_tree and selectors datum and children.

In your terminal:

	cp ~cs61a/lib/tree_ops.py .

Open the python interpreter:

	from tree_ops import *

Take a moment to study the implementation of Trees. Look at the constructors, selectors, and printing functions. Do not worry about understanding the OOP implementation, just study the selectors and constructors. At the bottom, we give you some premade trees that you can work with for each section.

Now, after loading the file, the variable kennedy contains the following Tree:

Use the correct series of selectors to return the value 'Caroline' from the tree. Remember that a forest is a LIST of trees.

datum(children(children(kennedy)[0])[1])

Mutual Recursion (Your TA will take a moment to explain this)

Mutual Recursion occurs when you have a function that will deal with Trees, as well as a function that will deal with Forests. Both functions call each other to solve whatever problem is at hand.

def square_tree(tree):
    return make_tree(square(datum(tree)), square_forest(children(tree)))

def square_forest(forest):
    if forest == []:
   	   return []
    else:
   	   return [square_tree(forest[0])] + square_forest(forest[1:])

The variable t is defined in tree_ops.py and is a Tree of integers that you can use to test your functions. Try out the following to see how it works!

>>> print_tree(t)
_______________
>>> st = square_tree(t)
>>> print_tree(st)
_______________

Exercise: Draw your interpretation of this tree on a piece of paper

Question 2:

Define the function tree_map which takes a function and a Tree as an argument and returns the equivalent Tree with the function applied to each node’s value. (Hint! This should be a similar but more general form of square tree)

def tree_map(func, t):
    return make_tree(func(datum(tree)), square_forest(func, children(tree)))

def forest_map(func, forest):
    if forest == []:
        return []
    else:
        return [square_tree(func, forest[0])] + square_forest(func, forest[1:])
>>> print_tree(t)
____________
>>> st = tree_map(square, t)
>>> print_tree(st)
____________

Question 3:

Define the function max_of_tree which takes in a Tree as an argument and returns the max of all of the values of each node in the Tree.

def max_of_tree(tree):
       return max(datum(tree), max_of_forest(children(tree)))

def max_of_forest(forest):
       if forest == []:
           return 0

   else:
           return max(max_of_tree(forest[0]), max_of_forest(forest[1:]))
>>> print_tree(t)
____________
>>> max_of_tree(t)
____________



Binary Trees (with 0, 1 or 2 children)

Representation

Every tree has at least one node, every node has a datum (values at internal nodes), and nodes can have 0 or 2 children. Here are the constructor and selectors: make_bin_tree(datum, children)

	b_datum(node)
	b_left_branch(node)
	b_right_branch(node)

Once Again, take a moment to study the representation of binary trees we have given you. Do no worry about the OOP representation, only about the constructors, selectors, and printing functions. We have given you a binary tree to work with in the variable b_t.

Question 4:

Define the function sum_of_bin_tree which takes a binary Tree as an argument and returns the sum of all of the values of each node in the binary Tree.

def sum_of_bin_tree(b_t):
   if b_leaf(b_t):
       return b_datum(b_t)
   else:
       return b_datum(b_t) + sum_of_bin_tree(b_left_branch(b_t)) +      sum_of_bin_tree(b_right_branch(b_t))
>>> b_t
____________
>>> sum_of_bin_tree(b_t)
____________

Question 5:

Define the function count_leaves which takes in a Tree as an argument and returns the number of leaves in that tree.

>>> b_t
____________
>>> count_leaves(b_t)
____________

def count_leaves(b_t):
   if b_t is None:
       return 0
   elif b_leaf(b_t):
       return 1
   else:
       return count_leaves(b_left_branch(b_t)) + count_leaves(b_right_branch(b_t))


Sets

A set is an unordered collection of distinct objects that supports membership testing, union, intersection, and adjunction.

Construction

>>> s = {3, 2, 1, 4, 4}
>>> s
{1, 2, 3, 4}

Adjunction

>>> s.add(5)
>>> s
{1, 2, 3, 4, 5}

Operations

>>> 3 in s
True
>>> 7 not in s
True
>>> len(s)
4
>>> s.union({1, 5})
{1, 2, 3, 4, 5}
>>> s.intersection({6, 5, 4, 3})
{3, 4}

For more detail on Sets you can go to the following link: PythonSets

Question 6:

Implement the union function for sets. Union takes in two sets, and returns a new set with elements from the first set, and all other elements that have not already have been seen in the second set.

>>> r = {0, 6, 6}
>>> s = {1, 2, 3, 4}
>>> t = union(s, {1, 6})
{1, 2, 3, 4, 6}
>>> union(r, t)
{0, 1, 2, 3, 4, 6}
def union(s1, s2):
   t = s1
   for elem in s2:
       t.add(elem)
   return t