問題2.63

SICP超久しぶり。
思えば学部2-3年のころに一生懸命やっていたな。
ranobaの開発に移ってから、ずっとほったらかしにしていた。
やっぱり難しい。あまり成長してないのか。。。。
なんにしろ、いい加減に終わらせないとね。ぱっぱと飛ばしてこう。

(define (entry tree) (car tree))

(define (left-branch tree)
  (if (> (length tree) 1)
      (cadr tree)
      '()))

(define (right-branch tree)
  (if (> (length tree) 2)
      (caddr tree)
      '())

(define (make-tree entry left right)
  (list entry left right))

(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((= x (entry set)) true)
        ((< x (entry set))
         (element-of-set? x (left-branch set)))
        ((> x (entry set))
         (element-of-set? x (right-branch set)))))

(define (tree->list-1 tree)
  (if (null? tree)
      '()
      (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 '()))


;; a
;; 同じである

;; b
;; 1は再帰的手続きであり、appendを使っているのでステップ数の増加の程度ははO(n^2)である。
;; 2も再帰的手続きであるcopy-to-listが入れ子になっているので、反復的手続きではない)が、ステップ数の増加の程度はO(n)である。
;; 多分。