2.64

练习 2.64 下面过程list->tree将一个有序表变换为一棵平衡二叉树。其中的辅助函数partial-tree以整数n和一个至少包含n个元素的表为参数，构造出一棵包含这个表的前n个元素的平衡树。由partial-tree返回的结果是一个序对（用cons构造），其car是构造出的树，其cdr是没有包含在树中那些元素的表。

(define (list->tree elements)
    (car 
        (partial-tree 
            elements 
            (length elements)
        )
    )
)

(define (partial-tree elts n)
    (if (= n 0)
        (cons '() elts)
        (let 
            (
                (left-size 
                    (quotient (- n 1) 2)
                )
            )
            (let ((left-result (partial-tree elts left-size)))
                (let 
                    (
                        (left-tree (car left-result))
                        (non-left-elts (cdr left-result))
                        (right-size (- n (+ left-size 1)))
                    )

                    (let 
                        (
                            (this-entry (car non-left-elts))
                            (right-result 
                                (partial-tree 
                                    (cdr non-left-elts) 
                                    right-size
                                )
                            )
                        )

                        (let 
                            (
                                (right-tree (car right-result))
                                (remaining-elts
                                    (cdr right-result)
                                )
                            )

                            (cons 
                                (make-tree this-entry left-tree right-tree)
                                remaining-elts
                            )
                        )
                    )
                )
            )
        )
    )
)

a) 请简要地并尽可能清楚地解释为什么partial-tree能完成工作。请画出将list->tree用于表(1 3 5 7 9 11)产生的树。

b) 过程list->tree转换n个元素的表所需的步数以什么量级增长？

a) 先做个实验吧。

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

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

(define (quotient n m) 
    (floor (/ n m))
)

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

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

(list->tree (list 1 3 5 7 9 11))

真的可以！

完成的过程真是妙不可言！首先，使用 quotient 计算出左子树的最大大小，然后用总长度减掉左子树的最大大小再减1，得到右子树的最大大小。因此左子树和右子树的大小是差不多的（平衡的）。被减掉的那个1，就成为了树根。

首先从所有的元素里挑出左子树的最大大小那么多元素，构建左子树。然后从没有被放进左子树的元素中构建右子树。最后，将树根、左子树、右子树组合成一棵树。于是完成了工作（剩下的没有被放进树中的元素（如果有的话），和树一起组合成序对返回）。

b) 假设 partial-tree 所需的步数是以 f(n) 的量级增长。那么对于给定的 n，又会分别调用两次 partial-tree，即 f(n) = f(n/2) + f(n/2) = 2 * f(n/2)。

当 n = 1 时，左子树大小为0，右子树大小为0，只有树根，只需要一步，即 f(1) = 1。

所以，partial-tree 所需的步数是以 $f(n) = 2 * log^{n}_{2}$ 的量级增长的。