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 '())
  )
​x
 
#<undef>

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

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

a) 先做个实验吧。

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

 
(define entry car)
(define left-branch cadr)
(define right-branch caddr)
 
#<undef>

再把 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
 
(7 (3 (1 nil nil) (5 nil nil)) (9 nil (11 nil nil)))

 
tree-2
 
(3 (1 nil nil) (7 (5 nil nil) (9 nil (11 nil nil))))

 
tree-3
 
(5 (3 (1 nil nil) nil) (9 (7 nil nil) (11 nil nil)))

现在对这三个二叉树分别应用 tree->list-1 和 tree->list-2：

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

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

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

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

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

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

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

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