Laboratory: Trees

Write a procedure, (number-tree-largest tree), that finds the largest value in a number tree. Follow the pattern for recursion over a tree.

> (number-tree-largest (cons (cons 1 (cons 4 5)) (cons 2 3)))
5
> (number-tree-largest (cons (cons -1 (cons -100 (cons -5 -4))) 
                             (cons (cons -3 -2) -3)))
-1

As you may recall from the reading, we have defined color trees as follows.

Using this recursive definition, write a procedure, (color-tree? val) that returns true (#t) if val is a color tree and false (#f) otherwise.

Write a procedure, (count-colors ctree), that counts how many colors appear in a tree.

> (count-colors "blue")
1
> (count-colors (cons "red" "blue"))
2
> (count-colors (cons "red" (cons "white" "blue")))
3
> (count-colors (cons (cons 'aardvark "red") (cons "white" "blue")))
3

Let's explore pair structures more generally. As you've noted, trees are built from cons cells (a.k.a. pairs). Sometimes it is useful to find out how many cons cells are in a tree or other pair structure.

a. Define and test a procedure named cons-cell-count that takes any Scheme value and determines how many boxes would appear in its box-and-pointer diagram. (The data structure that is represented by such a box, or the region of a computer's memory in which such a structure is stored is called a cons cell. Every time the cons procedure is used, explicitly or implicitly, in the construction of a Scheme value, a new cons cell is allocated, to store information about the car and the cdr. Thus cons-cell-count also tallies the number of times cons was invoked during the construction of its argument.)

For example, the structure in the following box-and-pointer diagram contains seven cons-cells, so when you apply cons-cell-count to that structure, it should return 7. On the other hand, the string "sample" contains no cons-cells, so the value of (cons-cell-count "sample") is 0.

In answering this question, you should consider whether each value, in turn, is a pair using the pair? predicate.

b. Use cons-cell-count to find out how many cons cells are needed to construct the list

See the notes at the end of the lab if you have trouble creating that list.

c. Draw a box-and-pointer diagram of this list to check the answer.

Recall the render-color-tree! procedure from the reading.

;;; Procedure:
;;;   render-color-tree!
;;; Parameters:
;;;   ctree, a tree of colors
;;;   image, an image 
;;;   left, an integer
;;;   top, an integer
;;;   width, an integer
;;;   height, an integer
;;; Purpose:
;;;   Render the tree into the portion of the image bounded at
;;;   the left by left, at the top by top, and with the specified
;;;   width and height.
;;; Produces:
;;;   [Nothing; Called for the side effect.]
;;; Preconditions:
;;;   ctree is a color tree (a pair structure that contains only colors)
;;;   image is a valid image identifier
;;;   0 <= left < (image-width image)
;;;   0 <= top < (image-height image)
;;;   width > 0
;;;   height > 0 
;;;   left+width < (image-width image)
;;;   top+height < (image-height image)
;;; Postconditions:
;;;   The tree has now been rendered.
(define render-color-tree!
  (lambda (ctree image left top width height)
    (cond
      [(pair? ctree)
       (render-color-tree! (car ctree) image 
                                       left top 
                                       (/ width 2) height)
       (render-color-tree! (cdr ctree) image
                                       (+ left (/ width 2)) top
                                       (/ width 2) height)]
      [else
       (image-select-rectangle! image REPLACE
                                left top width height)
       (context-set-fgcolor! ctree)
       (image-fill-selection! image)
       (context-update-displays!)
       (image-select-nothing! image)])))

a. Add render-color-tree! to your definitions pane.

b. Create a new 200x200 image named canvas.

c. What effect do you expect the following instruction to have?

> (render-color-tree! "blue" canvas 0 0 200 200)

d. Check your answer experimentally.

e. What effect do you expect the following instruction to have?

> (render-color-tree! (cons "black" "red") canvas 0 0 200 200)

f. Check your answer experimentally.

g. What effect do you expect the following instruction to have?

> (render-color-tree! (cons (cons "green" "yellow") "orange") canvas 0 0 200 200)

h. Check your answer experimentally.

i. What effect do you expect the following instruction to have?

> (render-color-tree! (cons "red" (cons (cons "blue" "purple") "black")) canvas 0 0 200 200)

j. Check your answer experimentally.

k. Create and render your own interesting color tree.

a. What preconditions should render-color-tree! have?

b. Use the color-tree? predicate from an earlier exercise to rewrite render-color-tree! so that it reports an appropriate error if its preconditions are not met. Use husk-and-kernel style, checking the preconditions in the husk.

c. In your implementation from (b), the tree is traversed twice: Once in color-tree? to check that the tree is valid, and once in the kernel to do the work of rendering the tree. Some programmers see this as inefficient. Write another version of render-color-tree! that does not use color-tree? to verify preconditions. Instead, the kernel should verify as it goes along that each leaf is a color. That is, the kernel should issue an error message if it finds any tree value that is neither a pair nor a color.

One potentially interesting way to experiment with color trees is to have a procedure build those trees. How? We might provide the procedure with an intended size of the tree.

a. Using this technique, write a procedure, (random-bw-tree size), that randomly builds a black and white tree of the appropriate size.

b. Using this technique, write a procedure, (random-color-tree size colors), that builds a random color tree of the desired size, randomly selecting the color from the list colors.

Create a new version of render-color-tree! that has an extra parameter, vsplit?, a Boolean value. If the Boolean is true, when render-color-tree! should split the area vertically (as it currently does). If the Boolean is false, render-color-tree! should split the area horizontally. In both cases, the recursive calls should negate that Boolean value so that the splits alternate between vertical and horizontal.

For the tree (cons "red" (cons "blue" "white")), we would expect something like the following.

+--------+--------+
|        |        |
|        |  blue  |
+  red   +--------+
|        |        |
|        |  white |
+--------+--------+

As you may recall, a tree is either (a) a non-pair value or (b) the cons of two trees. In the reading, you saw a procedure that counted the number of values in a tree. In this lab, you wrote a procedure that counted the number of cons cells (pairs) in a tree. What is the relationship between the numbers returned by those two procedures?

a. Write a procedure, (color-tree-contains? ctree color), that determines whether color appears anywhere in ctree. (We may have written a similar procedure during the class discussion. If so, you can start with that procedure.)

b. Rewrite the procedure to determine if a color nearby to color appears somewhere in ctree. (You might say that two colors are nearby if their red, green, and blue components all differ by less than sixteen.)

c. Write (tree-contains tree value), a generalized version of color-tree-contains that works with a heterogeneous tree (that is, a tree that contains multiple kinds of values).

If, for some reason, you are having trouble creating the list

(0 (1 (2 (3 (4)))))

try

(list 0 (list 1 (list 2 (list 3 (list 4)))))

Return to the problem.