計算機プログラムの構造と解釈 第二版 P92 問題2.63

問題はaとbの二つ。

aは実際、写経して実行してみると分かる。
普通にリストに変換される。

bの議論は
再帰をもちいるか反復を用いるかの違い議論みたいなもんだと思う。
と思ったけど、結局左から順に処理してるだけなのでどちらもθ(n)っぽい。
これの読書会の時話に出たんだけど、appendは重いということなので
やっぱりbの方が遅く増加する。

実装

#!/usr/local/bin/gosh
;; -*- coding: utf-8 -*-

(use ggc.debug.trace)
(use math.mt-random)


(define nil '())

(define (entry tree) (car tree))

(define (left-branch tree) (cadr tree))

(define (right-branch tree) (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)) #t) 
        ((< x (entry set))
         (element-of-set? x (left-branch set)))
        ((> x (entry set))
         (element-of-set? x (right-branch set)))))


(define (adjoin-set x set)
  (cond ((null? set) (make-tree x nil nil))
        ((= x (entry set)) set)
        ((< x (entry set))
         (make-tree (entry set)
                    (adjoin-set x (left-branch set))
                    (right-branch set)))
        ((> x (entry set))
         (make-tree (entry set)
                    (left-branch set)
                    (adjoin-set x (right-branch set))))))

;;P91 図2.16の木を表したもの左からtree1、tree2、tree3
(define tree1 (make-tree 7 
                         (make-tree 3 
                                    (make-tree 1 nil nil)
                                    (make-tree 5 nil nil))
                         (make-tree 9
                                    nil
                                    (make-tree 11 nil nil))))

(define tree2 (make-tree 3
                         (make-tree 1 nil nil)
                         (make-tree 7
                                    (make-tree 5 nil nil)
                                    (make-tree 9
                                               nil
                                               (make-tree 11 nil nil)))))

(define tree3 (make-tree 5
                         (make-tree 3
                                    (make-tree 1 nil nil)
                                    nil)
                         (make-tree 9
                                    (make-tree 7 nil nil)
                                    (make-tree 11 nil nil))))

;;P92図2.17の木を表した物を、tree4とする。
(define tree4 (make-tree 1
                         nil
                         (make-tree 2
                                    nil
                                    (make-tree 3
                                               nil
                                               (make-tree 4
                                                          nil
                                                          (make-tree 5
                                                                     nil
                                                                     (make-tree 6
                                                                                nil
                                                                                (make-tree 7 nil nil))))))))

;;問題2.63
(define (tree->list-1 tree)
  (if (null? tree) nil
    (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 nil))

;; main
(define (main args)

  (display "tree1:" )
  (display tree1)
  (newline)

  (display "tree2:" )
  (display tree2)
  (newline)

  (display "tree3:" )
  (display tree3)
  (newline)

  (display "tree4:" )
  (display tree4)
  (newline)


  (display "(tree->list-1 tree1): ")
  (display (tree->list-1 tree1))
  (newline)

  (display "(tree->list-1 tree2): ")
  (display (tree->list-1 tree2))
  (newline)

  (display "(tree->list-1 tree3): ")
  (display (tree->list-1 tree3))
  (newline)

  (display "(tree->list-1 tree4): ")
  (display (tree->list-1 tree4))
  (newline)

  (display "(tree->list-2 tree1): ")
  (display (tree->list-2 tree1))
  (newline)

  (display "(tree->list-2 tree2): ")
  (display (tree->list-2 tree2))
  (newline)

  (display "(tree->list-2 tree3): ")
  (display (tree->list-2 tree3))
  (newline)

  (display "(tree->list-2 tree4): ")
  (display (tree->list-2 tree4))
  (newline)


  0)

実行

tree1:(7 (3 (1 () ()) (5 () ())) (9 () (11 () ())))
tree2:(3 (1 () ()) (7 (5 () ()) (9 () (11 () ()))))
tree3:(5 (3 (1 () ()) ()) (9 (7 () ()) (11 () ())))
tree4:(1 () (2 () (3 () (4 () (5 () (6 () (7 () ())))))))
(tree->list-1 tree1): (1 3 5 7 9 11)
(tree->list-1 tree2): (1 3 5 7 9 11)
(tree->list-1 tree3): (1 3 5 7 9 11)
(tree->list-1 tree4): (1 2 3 4 5 6 7)
(tree->list-2 tree1): (1 3 5 7 9 11)
(tree->list-2 tree2): (1 3 5 7 9 11)
(tree->list-2 tree3): (1 3 5 7 9 11)
(tree->list-2 tree4): (1 2 3 4 5 6 7)

よくできているなぁ。