Exercise 2.63. Each of the following two procedures converts a binary tree to a list.
(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. Do the two procedures produce the same result for every tree? If not, how do the results differ? What lists do the two procedures produce for the trees in figure 2.16?
b. Do the two procedures have the same order of growth in the number of steps required to convert a balanced tree with n elements to a list? If not, which one grows more slowly?
树的表示
这个练习要把下面的几棵树使用代码表示出来。
trees:
7 3 5
/ \ / \ / \
/ \ / \ / \
/ \ / \ / \
3 9 1 7 3 9
/ \ \ / \ / / \
/ \ \ / \ / / \
/ \ \ / \ / / \
1 5 11 5 9 1 7 11
\
\
\
11下面是三个树的表示
(load "set-as-binary-tree.scm")
(define tree1 (make-tree 7
(make-tree 3
(make-tree 1 '() '())
(make-tree 5 '() '()))
(make-tree 9
'()
(make-tree 11 '() '()))))
(define tree2 (make-tree 3
(make-tree 1 '() '())
(make-tree 7
(make-tree 5 '() '())
(make-tree 9
'()
(make-tree 11 '() '())))))
(define tree3 (make-tree 5
(make-tree 3
(make-tree 1 '() '())
'())
(make-tree 9
(make-tree 7 '() '())
(make-tree 11 '() '()))))注意，每一个点都必须是一个 tree 结构。这也是为什么一个简单的叶子节点也必须使用 (make-tree entry ‘() ‘()) 来表示的原因
两个过程产生的结果
对这些树，使用 tree->list 的结果：
1 ]=> (tree->list-1 tree1)
;Value 2: (1 3 5 7 9 11)
1 ]=> (tree->list-1 tree2)
;Value 3: (1 3 5 7 9 11)
1 ]=> (tree->list-1 tree3)
;Value 4: (1 3 5 7 9 11)
1 ]=> (tree->list-2 tree1)
;Value 5: (1 3 5 7 9 11)
1 ]=> (tree->list-2 tree2)
;Value 6: (1 3 5 7 9 11)
1 ]=> (tree->list-2 tree3)
;Value 7: (1 3 5 7 9 11)
两个结果一样，但从递归的角度，第一种方法更明了。
第二种方法采用迭代式递归，result-list 位置存放了每一次迭代产生的结果，但这个位置看似只对 entry 和 right-branch 进行了操作，需要细细分析才能知道最后的结果会是什么。
两种方法的比较
两个都是 O(n)