Exercise 2.64: The following procedure
list->tree converts an ordered list to a balanced binary tree. The
helper procedure partial-tree takes as arguments an integer n and
list of at least n elements and constructs a balanced tree containing the
first n elements of the list. The result returned by partial-tree
is a pair (formed with cons) whose car is the constructed tree
and whose cdr is the list of elements not included in the tree.
(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))))))))
Write a short paragraph explaining as clearly as you can how
partial-tree works. Draw the tree produced by list->tree for
the list (1 3 5 7 9 11).
What is the order of growth in the number of steps required by
list->tree to convert a list of n elements?
练习 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))))))))
用简短的段落尽可能清楚地解释 partial-tree 的工作原理。画出 list->tree 对表 (1 3 5 7 9 11) 产生的树。
list->tree 将含 n 个元素的表转换为树所需步骤数的增长阶是多少？
(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))))))))