We can easily write a procedure
pair-tree-sum to give us the sum
of a binary tree of integers, whose interior nodes are pairs and
whose leaves are the integers.
[ blah blah blah... rewrite some of the following, simplifying to only handle trees, not proper lists. ]
Our notion of a "pair tree" is a binary tree of pairs. Here
we're doing something a little strange, because in general we're
improper lists. We'll regard the
of a pair as the "left child" and "right child" fields of
a tree node. A proper list wouldn't be a pair tree, because it
the last pair in the list would point to the empty list object,
not a number.
(Later, I'll show a record facility that allows us to build "tree node" records that are not pairs. That's nicer, because it doesn't confuse pairs' roles in improper lists with their roles in trees. For now, we'll stick with pairs, because the point of this example is recursion, not the details of records.)
Just as we did for proper lists, we start by characterizing this data structure recursively. We'll consider any subtree of a pair-tree to be a pair-tree. This includes the leaves, e.g., the numbers in a tree of numbers. (This is analogous to the way we considered the empty list to be a kind of list in the recursive characterization of lists.)
A pair tree is either
Our recursive summing procedure will have to deal with these two cases:
The first case is the base case for the recursion. The sum of a leaf is the numeric of that leaf.
The second case is the recursive case, where we have a subtree to sum.
Scheme>(define (pair-tree-sum pair-tree) (cond ((number? pair-tree) pair-tree) (else (+ (pair-tree-sum (car pair-tree)) (pair-tree-sum (cdr pair-tree))))))
Try this out, and make sure you understand why it works.
Scheme>(pair-tree-sum 1) 1 Scheme>(pair-tree-sum '(1 . 2)) 3 Scheme>(pair-tree-sum '((40 . 30) . (20 . 10))) 100
Notice how simple
pair-tree-sum is, and how it depends
on getting the base case for the recursion right. If we hadn't
considered the leaves to be pair-trees in their own right,
it would have gotten much uglier. For example, if we'd "bottomed
out" at pairs whose left and right children weren't both pairs,
we'd have had more cases to deal with--cases where one child
is a leaf but the other's not.
newline expressions at the beginning of
pair-tree-sum, as we did for
list-sum, and try it out
again. Be sure you understand the output in terms of the recursive