要回答题目给出的问题，首先需要将 tree->list-1 和 tree->list-2 的代码敲下来（当然还有书本 106 页的树结构代码）：
tree->list-1 ：
;;; 63-tree-list-1.scm
(load "p106-tree.scm")
(define (tree->list-1 tree)
(if (null? tree)
'()
(append (tree->list-1 (left-branch tree))
(cons (entry tree)
(tree->list-1 (right-branch tree))))))
tree->list-2 ：
;;; 63-tree-list-2.scm
(load "p106-tree.scm")
(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 '()))
书本 106 页，树的构造和选择函数：
;;; p106-tree.scm
(define (make-tree entry left right)
(list entry left right))
(define (entry tree)
(car tree))
(define (left-branch tree)
(cadr tree))
(define (right-branch tree)
(caddr tree))
现在，定义出书本 106 页图 2-16 的几棵树(从左到右分别为 a 、 b 和 c)：
1 ]=> (load "p106-tree.scm")
;Loading "p106-tree.scm"... done
;Value: right-brach
1 ]=> (define a (make-tree 7
(make-tree 3
(make-tree 1 '() '())
(make-tree 5 '() '()))
(make-tree 9
'()
(make-tree 11 '() '()))))
;Value: a
1 ]=> (define b (make-tree 3
(make-tree 1 '() '())
(make-tree 7
(make-tree 5 '() '())
(make-tree 9
'()
(make-tree 11 '() '())))))
;Value: b
1 ]=> (define c (make-tree 5
(make-tree 3
(make-tree 1 '() '())
'())
(make-tree 9
(make-tree 7 '() '())
(make-tree 11 '() '()))))
;Value: c
并对它们执行 tree->list-1 和 tree->list-2 ：
1 ]=> (load "63-tree-list-1.scm")
;Loading "63-tree-list-1.scm"...
; Loading "p106-tree.scm"... done
;... done
;Value: tree->list-1
1 ]=> (load "63-tree-list-2.scm")
;Loading "63-tree-list-2.scm"...
; Loading "p106-tree.scm"... done
;... done
;Value: tree->list-2
1 ]=> (tree->list-1 a) ; a
;Value 11: (1 3 5 7 9 11)
1 ]=> (tree->list-2 a)
;Value 12: (1 3 5 7 9 11)
1 ]=> (tree->list-1 b) ; b
;Value 13: (1 3 5 7 9 11)
1 ]=> (tree->list-2 b)
;Value 14: (1 3 5 7 9 11)
1 ]=> (tree->list-1 c) ; c
;Value 15: (1 3 5 7 9 11)
1 ]=> (tree->list-2 c)
;Value 16: (1 3 5 7 9 11)
从前面的测试部分可以看出，对于同一棵树， tree->list-1 和 tree->list-2 都生成同一个列表。
对于不同形状但是包含的元素相同的多棵树， tree->list-1 和 tree->list-2 也都生成同一个列表。
要了解两个函数的执行效率，最好的办法就是展开两个函数对同一一棵树的执行过程。
对于 tree->list-1 ，如果给定树 a ，那么计算过程的展开如下：
(tree->list-1 a)
(tree->list-1 (list 7
(list 3
(list 1 '() '())
(list 5 '() '()))
(list 9
'()
(list 11 '() '()))))
(append (tree->list-1 (list 3
(list 1 '() '())
(list 5 '() '())))
(cons 7
(tree->list-1 (list 9
'()
(list 11 '() '())))))
(append (append (tree->list-1 (list 1 '() '()))
(cons 3
(tree->list-1 (list 5 '() '()))))
(cons 7
(tree->list-1 (list 9
'()
(list 11 '() '())))))
(append (append (append (tree->list-1 '())
(cons 1
(tree->list-1 '())))
(cons 3
(tree->list-1 (list 5 '() '()))))
(cons 7
(tree->list-1 (list 9
'()
(list 11 '() '())))))
(append (append (append '()
(cons 1 '()))
(cons 3
(tree->list-1 (list 5 '() '()))))
(cons 7
(tree->list-1 (list 9
'()
(list 11 '() '())))))
(append (append (append '()
(cons 1 '()))
(cons 3
(append (tree->list-1 '())
(cons 5
(tree->list-1 '())))))
(cons 7
(tree->list-1 (list 9
'()
(list 11 '() '())))))
(append (append (append '()
(cons 1 '()))
(cons 3
(append '()
(cons 5 '()))))
(cons 7
(tree->list-1 (list 9
'()
(list 11 '() '())))))
(append (append (append '()
(cons 1 '()))
(cons 3
(append '()
(cons 5 '()))))
(cons 7
(append (tree->list-1 '())
(cons 9
(tree->list-1 (list 11 '() '()))))))
(append (append (append '()
(cons 1 '()))
(cons 3
(append '()
(cons 5 '()))))
(cons 7
(append '()
(cons 9
(append (tree->list-1 '())
(cons 11
(tree->list-1 '())))))))
(append (append (append '()
(cons 1 '()))
(cons 3
(append '()
(cons 5 '()))))
(cons 7
(append '()
(cons 9
(append '()
(cons 11 '()))))))
(append (append (append '() '(1))
(cons 3
(append '() '(5))))
(cons 7
(append '()
(cons 9 (append '() '(11))))))
...
(append '(1 3 5)
'(7 9 11))
'(1 3 5 7 9 11)
从展开过程来看，对于节点数为 6 的树， tree->list-1 需要伸展 6 次，使用 6 次 append ， 以及 6 次 cons ，可以看出，对于大小为 \(n\) 的树， append 和 cons 的调用次数正比于 \(n\) 。
因为 cons 的复杂度为 \(\Theta(1)\) ，比 append 的 \(\Theta(n)\) 要低，所以 tree->list-1 的复杂度可以通过统计 append 调用的次数来计算：对于树中每个节点，需要调用一次 append ，因此对于节点数为 \(n\) 的树来说， tree->list-1 的复杂度为 \(\Theta(n^2)\) 。
另一方面，对于 tree->list-2 ，同样给定树 a 作为输入，有以下展开序列：
(tree->list-2 a)
(tree->list-2 (list 7
(list 3
(list 1 '() '())
(list 5 '() '()))
(list 9
'()
(list 11 '() '()))))
(copy-to-list (list 7
(list 3
(list 1 '() '())
(list 5 '() '()))
(list 9
'()
(list 11 '() '())))
'())
(copy-to-list (list 3
(list 1 '() '())
(list 5 '() '()))
(cons 7
(copy-to-list (list 9
'()
(list 11 '() '()))
'())))
(copy-to-list (list 3
(list 1 '() '())
(list 5 '() '()))
(cons 7
(copy-to-list '()
(cons 9
(copy-to-list (list 11 '() '())
'())))))
(copy-to-list (list 3
(list 1 '() '())
(list 5 '() '()))
(cons 7
(copy-to-list '()
(cons 9
(copy-to-list '()
(cons 11
(copy-to-list '() '())))))))
(copy-to-list (list 1 '() '())
(cons 3
(copy-to-list (list 5 '() '())
(cons 7
(copy-to-list '()
(cons 9
(copy-to-list '()
(cons 11
(copy-to-list '() '())))))))))
(copy-to-list '()
(cons 1
(copy-to-list '()
(cons 3
(copy-to-list (list 5 '() '())
(cons 7
(copy-to-list '()
(cons 9
(copy-to-list '()
(cons 11
(copy-to-list '() '())))))))))))
...
(cons 1 (cons 3 (cons 7 (cons 9 (cons 11 '())))))
'(1 3 7 9 11)
从展开过程来看，对于节点数为 6 的树来说， tree->list-2 展开 6 次，调用 6 次 copy-to-list ，调用 6 次 cons ，可以看出，对于节点数为 \(n\) 的树， tree->list-2 调用 cons 和 copy-to-list 的次数等同于 \(n\) 。
tree->list-2 的复杂度可以通过统计 cons 的调用次数来统计：每次展开需要调用一次 cons ，而 cons 的复杂度为 \(\Theta(1)\) ，因此对于节点数为 \(n\) 的树来说， tree->list-2 的复杂度为 \(\Theta(n)\) 。
通过对比，可以发现，虽然 tree->list-1 和 tree->list-2 对于同样的树生成的列表一样，但是 tree->list-2 的复杂度比 tree->list-1 更低。