Exercise 2.63 · 习题

Exercise 2.63: Each of the following two
procedures converts a binary tree to a list.

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

Do the two procedures produce the same result for every tree? If not, how do
the results differ? What lists do the two procedures produce for the trees in
Figure 2.16?

Do the two procedures have the same order of growth in the number of steps

required to convert a balanced tree with n elements to a list? If not,

which one grows more slowly?

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

这两个过程对每棵树产生的结果是否相同？若不同，结果有何区别？对图 2.16 中的各棵树，两个过程分别产生什么表？

将含 n 个元素的平衡树转换为表时，这两个过程所需步骤数的增长阶是否相同？若不同，哪个增长更慢？