1 ;; The first three lines of this file were inserted by DrScheme. They record metadata
2 ;; about the language level of this file in a form that our tools can easily process.
3 #reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname |29.1|) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp")))))
4 ;Exercise 29.1.1.   A number tree is either a number or a pair of number trees. Develop the function sum-tree, which determines the sum of the numbers in a tree. How should we measure the size of a tree? What is its abstract running time?    Solution
5 ;
6 ;Exercise 29.1.2.   Hand-evaluate (maxi2 (list 0 1 2 3)) in a manner similar to our evaluation of (maxi (list 0 1 2 3)). What is the abstract running time of maxi2?    Solution
7 ;
8 ;A number tree (nt) is either
9 ;1. a number or
10 ;2. (make-tree nt1 nt2)
11 ;where nt1 and nt2 are number trees.
12 
13 (define-struct tree (left right))
14 
15 ;sum-tree : nt -> number
16 ;Sums all the numbers in a number tree.
17 (define (sum-tree ant)
18   (cond
19     [(number? ant) ant]
20     [else (+ (sum-tree (tree-left ant))
21              (sum-tree (tree-right ant)))]))
22 
23 (define tree1 (make-tree (make-tree (make-tree 4 9)
24                                     (make-tree 2 7))
25                          (make-tree 5 -3)))
26 
27 (sum-tree tree1)
28 
29 The size of a tree can be measured either by the number of nested trees it contains or by the length of the most nested tree. (if so, then the running time is on the order of N) I prefer the first since its definition allows easier calculation of the abstract running time.  Or it could be considered the number of numbers (on the order of N?).
30 
31 (+ (sum-tree (tree-left ant))
32    (sum-tree (tree-right ant)))
33 
34 (+ (+ (sum-tree (tree-left ant))
35       (sum-tree (tree-right ant)))
36    (sum-tree (tree-right ant)))