Serendip

Web Studio

問題2.63a

tree->list-1、tree->list-2 のどちらの手続きでも同じ結果となる。

(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 '()))

(define tree1
  (make-tree 7
             (make-tree 3
                        (make-tree 1 '() '())
                        (make-tree 5 '() '()))
             (make-tree 9
                        '()
                        (make-tree 11 '() '()))))
tree1
gosh> (7 (3 (1 () ()) (5 () ())) (9 () (11 () ())))
(tree->list-1 tree1)
gosh> (1 3 5 7 9 11)
(tree->list-2 tree1)
gosh> (1 3 5 7 9 11)

(define tree2
  (make-tree 3
             (make-tree 1 '() '())
             (make-tree 7
                        (make-tree 5 '() '())
                        (make-tree 9
                                   '()
                                   (make-tree 11 '() '())))))
tree2
gosh> (3 (1 () ()) (7 (5 () ()) (9 () (11 () ()))))
(tree->list-1 tree2)
gosh> (1 3 5 7 9 11)
(tree->list-2 tree2)
gosh> (1 3 5 7 9 11)

(define tree3
  (make-tree 5
             (make-tree 3
                        (make-tree 1 '() '())
                        '())
             (make-tree 9
                        (make-tree 7 '() '())
                        (make-tree 11 '() '()))))
tree3
gosh> (5 (3 (1 () ()) ()) (9 (7 () ()) (11 () ())))
(tree->list-1 tree3)
gosh> (1 3 5 7 9 11)
(tree->list-2 tree3)
gosh> (1 3 5 7 9 11)

問題2.63b

tree->list-1 は再帰的プロセス、tree->list-2 は反復的プロセスを使っている。
tree->list-1 の方が append の分だけステップ数はわずかに増える。
n が大きくなればなるほどステップ数の差が開いていくので tree->list-2 の方がより遅くステップ数が増加する。

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る