1 665c255d 2023-08-04 jrmu (define (entry tree) (car tree))
2 665c255d 2023-08-04 jrmu (define (left-branch tree) (cadr tree))
3 665c255d 2023-08-04 jrmu (define (right-branch tree) (caddr tree))
4 665c255d 2023-08-04 jrmu (define (make-tree entry left right)
5 665c255d 2023-08-04 jrmu (list entry left right))
7 665c255d 2023-08-04 jrmu (define (element-of-set? x set)
8 665c255d 2023-08-04 jrmu (cond ((null? set) #f)
9 665c255d 2023-08-04 jrmu ((= x (entry set)) #t)
10 665c255d 2023-08-04 jrmu ((< x (entry set))
11 665c255d 2023-08-04 jrmu (element-of-set? x (left-branch set)))
12 665c255d 2023-08-04 jrmu ((> x (entry set))
13 665c255d 2023-08-04 jrmu (element-of-set? x (right-branch set)))))
15 665c255d 2023-08-04 jrmu (define (adjoin-set x set)
16 665c255d 2023-08-04 jrmu (cond ((null? set) (make-tree x '() '()))
17 665c255d 2023-08-04 jrmu ((= x (entry set)) set)
18 665c255d 2023-08-04 jrmu ((< x (entry set))
19 665c255d 2023-08-04 jrmu (make-tree (entry set)
20 665c255d 2023-08-04 jrmu (adjoin-set x (left-branch set))
21 665c255d 2023-08-04 jrmu (right-branch set)))
22 665c255d 2023-08-04 jrmu ((> x (entry set))
23 665c255d 2023-08-04 jrmu (make-tree (entry set)
24 665c255d 2023-08-04 jrmu (left-branch set)
25 665c255d 2023-08-04 jrmu (adjoin-set x (right-branch set))))))
26 665c255d 2023-08-04 jrmu (define (tree->list-1 tree)
27 665c255d 2023-08-04 jrmu (if (null? tree)
29 665c255d 2023-08-04 jrmu (append (tree->list-1 (left-branch tree))
30 665c255d 2023-08-04 jrmu (cons (entry tree)
31 665c255d 2023-08-04 jrmu (tree->list-1 (right-branch tree))))))
32 665c255d 2023-08-04 jrmu (define (tree->list-2 tree)
33 665c255d 2023-08-04 jrmu (define (copy-to-list tree result-list)
34 665c255d 2023-08-04 jrmu (if (null? tree)
36 665c255d 2023-08-04 jrmu (copy-to-list (left-branch tree)
37 665c255d 2023-08-04 jrmu (cons (entry tree)
38 665c255d 2023-08-04 jrmu (copy-to-list (right-branch tree)
39 665c255d 2023-08-04 jrmu result-list)))))
40 665c255d 2023-08-04 jrmu (copy-to-list tree '()))
42 665c255d 2023-08-04 jrmu ;; a. Do the two procedures produce the same result for every tree? If not, how do the results differ? What lists do the two procedures produce for the trees in figure 2.16?
44 665c255d 2023-08-04 jrmu ;; Yes, they produce the same result for every tree. They both produce '(1, 3, 5, 7, 9, 11)
46 665c255d 2023-08-04 jrmu ;; b. Do the two procedures have the same order of growth in the number of steps required to convert a balanced tree with n elements to a list? If not, which one grows more slowly?
48 665c255d 2023-08-04 jrmu ;; No, the second procedure is faster. Each procedure makes around n calls to itself (slightly more calls since there are 2 extra per tree with empty leaves). However, the first procedure uses append whereas the second one uses cons. Append has order of growth of (length list1), so I'm guessing the overall order of growth for tree->list-1 is n^2? whereas it is n? for tree->list-2.
