# 2.63

## 练习 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 '())
)


## b) 将n个结点的平衡树变换为表时，这两个过程所需的步数具有同样量级的增长速度吗？如果不一样，哪个过程增长得慢一些？

a) 先做个实验吧。

(define entry car)


(define (make-tree entry left right)
(list entry left right)
)

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

(define tree-2
(make-tree 3
(make-tree 1 '() '())
(make-tree 7
(make-tree 5 '() '())
(make-tree 9
'()
(make-tree 11 '() '())
)
)
)
)

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

tree-1

tree-2

tree-3


(tree->list-1 tree-1)

(tree->list-2 tree-1)

(tree->list-1 tree-2)

(tree->list-2 tree-2)

(tree->list-1 tree-3)

(tree->list-2 tree-3)


b) 看起来它们的步数也是一样的，但是 tree->list-2 的空间复杂度更低。