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

a) 这两个过程对所有的树都产生同样的结果吗？如果不是，它们产生出的结果有什么不同？它们对图2-16中的那些树产生什么样的表？

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

a) 先做个实验吧。

先把 tree 的选择函数定义写一下：

(define entry car)
(define left-branch cadr)
(define right-branch caddr)

再把 tree 的构造函数定义写一下：

(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->list-2：

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

从实验结果看，它们对图2-16中的那些树都产生相同的结果。看上去的确是等价的。

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