SICP 問題 2.62（二進木のフラット化）

問題

下の二つの手続はそれぞれ二進木をリストに変換する。

(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. 二つの手続は全ての木に対して同じ結果を生じるか。そうでなければ、結果はどう違うか。二つの手続は図2.16のような木からどういうリストを生じるか。

b. n 個の要素の釣り合っている木をリストに変換するのに必要なステップ数の増加の程度は、二つの手続で同じか。違うならどちらがより遅く増加するか

解答

a.

tree->list-1 は左側のtree、entryの値、右側のtree の順序でガンガン展開していく方法を素直に実装した感じ。
tree->list-2 は・・・う〜ん、反復的な実装がされてるけど、やってることは実質同じ。
ちなみに 図2.16のデータを作るとこんな感じ。

(define list1 '(7 (3 (1 () ()) (5 () ())) (9 () (11 () ()))))
(define list2 '(3 (1 () ()) (7 (5 () ()) (9 () (11 () ())))))
(define list3 '(5 (3 (1 () ()) ()) (9 (7 () ()) (11 () ()))))

で、こいつらを元にして実験してみると・・・

gosh> (tree->list-1 list1)

(1 3 5 7 9 11)

gosh> (tree->list-2 list1)

(1 3 5 7 9 11)

gosh> (tree->list-1 list2)

(1 3 5 7 9 11)

gosh> (tree->list-2 list2)

(1 3 5 7 9 11)

gosh> (tree->list-1 list3)

(1 3 5 7 9 11)

gosh> (tree->list-2 list3)

(1 3 5 7 9 11)

gosh> 

b.

n 個の要素の釣り合っている木をリストに変換するのに必要なステップ数の増加の程度は、二つの手続で同じか。違うならどちらが寄り遅く増加するか

tree->list-1 は append 使ってるからな〜。tree->list-2 に比べると大きいんじゃない？
すんません、よく分かってないっす。。