乐正

Actions speak louder than words.

Sicp-ex2-64

问题

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

list->tree (p108-list-to-tree.scm) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(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个元素的表所需的步数以什么量级增长?

解答

partial-tree是一个递归函数,当n=0是这个递归函数的退出条件。partial-tree 先是将表中前(quotient (- n 1) 2)个元素通过partial-tree递归构造成一棵平衡树, 然后这棵平衡树作为所需要树的左子树;同理,将剩下的元素变成根节点和右子树。最后返 回需要的结果。

(1 3 5 7 9 11)产生的树如下:

1
2
(list->tree '(1 3 5 7 9 11))
;Value 38: (5 (1 () (3 () ())) (9 (7 () ()) (11 () ())))

练习2.64

过程list->tree所需要的步数以$\Theta (n)$的量级增长。

draft

« sicp-ex2-63 sicp-ex2-65 »

Comments