乐正

Actions speak louder than words.

Sicp-ex2-63

问题

下面两个过程都能将树变换为表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(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)问中,对于任何树这两个过程产生的结果都是一样的,都是产生由小到大的排列的表。使 用图2-16中的那些树验证一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
;; (load p106-tree.scm)

(define a-tree (make-tree 7
                          (make-tree 3
                                     (make-tree 1 '() '())
                                     (make-tree 5 '() '()))
                          (make-tree 9
                                     '()
                                     (make-tree 11 '() '()))))
;Value: a-tree

(tree->list-1 a-tree)
;Value 16: (1 3 5 7 9 11)

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

对于n个节点的树,其深度为(n-1)。tree-list->1过程所需要的步数是$\Theta (2^{n-2})$, 其增长速度随着树深度增加而指数增长。tree-list->2过程所需要的步数是$\Theta (n)$。 所以,tree->list-2过程步数增长更慢。

draft

« sicp-ex2-62 sicp-ex2-64 »

Comments