SICP 2.63

木は苦手だが、そんなこと言ってちゃいかん。

(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

どちらも、次の処理を再帰的に繰り返す構造になっている。よって、生成する結果は同じ。

1. 左の枝をシリアライズ
2. 右の枝をシリアライズ
3. 2の結果にentryをcons
4. 1の結果に3の結果を連結

b

ステップ数の増加の程度ねぇ。木が大きくなると遅くなるのはどっちか?という質問か。
ステップ数はどちらも部分木の数と一致するはず。だからステップ数の増加の速さは同じ。
じゃなかった。appendのステップ数はリストの長さに比例するから、tree->list-1の方が増加の速さは大きくなるんだ。