# weima learns to program

my attempt to do the exercises in sicp.

## Tuesday, July 22, 2008

### sicp exercise 2.63

;; Exercise 2.63.  Each of the following two procedures converts a binary tree to a list.

;; (define (tree->list-1 tree)
;;   (if (null? tree)
;;       NULL
;;       (append (tree->list-1 (left-branch tree))
;;               (cons (entry tree)
;;                     (tree->list-1 (right-branch tree))))))

;; (define (tree->list-2 tree)
;;   (define (copy-to-list tree result-list)
;;     (if (null? tree)
;;         result-list
;;         (copy-to-list (left-branch tree)
;;                       (cons (entry tree)
;;                             (copy-to-list (right-branch tree)
;;                                           result-list)))))
;;   (copy-to-list tree NULL))

;; 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?

;; 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?

;; a.
;;

(define NULL (list))
(define (entry tree) (car tree))
(define (make-tree item left-tree right-tree) (list item left-tree right-tree))

(define (tree->list-1 tree)
(if (null? tree)
NULL
(append (tree->list-1 (left-branch tree))
(cons (entry tree)
(tree->list-1 (right-branch tree))))))

(define (tree->list-2 tree)
(define (copy-to-list tree result-list)
(if (null? tree)
result-list
(copy-to-list (left-branch tree)
(cons (entry tree)
(copy-to-list (right-branch tree)
result-list)))))
(copy-to-list tree NULL))

(define tree1 (list 7 (list 3 (list 1 NULL NULL) (list 5 NULL NULL)) (list 9 NULL (list 11 NULL NULL))))
(define tree2 (list 3 (list 1 NULL NULL) (list 7 (list 5 NULL NULL) (list 9 NULL (list 11 NULL NULL)))))
(define tree3 (make-tree 5
(make-tree 3
(make-tree 1 NULL NULL)
NULL)
(make-tree 9
(make-tree 7 NULL NULL)
(make-tree 11 NULL NULL))))

(display tree1) (newline)
(display tree2) (newline)
(display tree3) (newline)

(display (tree->list-1 tree1)) (newline)
(display (tree->list-1 tree2)) (newline)
(display (tree->list-1 tree3)) (newline)
(display (tree->list-2 tree1)) (newline)
(display (tree->list-2 tree2)) (newline)
(display (tree->list-2 tree3)) (newline)

;; b.

;; the procedure tree->list-2 is faster that the tree->list-1