count-leaves
函数用于计算一棵树的树叶数量,题目要求我们补充缺少的部分:
(define (count-leaves t)
(accumulate <??> <??> (map <??> <??>)))
根据题目给出的函数形式,猜测有两种可能的办法:
首先想到的办法可能是,用 map
函数枚举(enumerate)出所有树叶,然后 accumulate
对每个叶子进行 + 1 计数,从而计算出整棵树的树叶数量(类似于 练习 2.33 的 length
定义)。
使用 练习 2.28 的 fringe
函数,可以很好地完成枚举出所有树叶的工作:
;;; 28-fringe.scm
(define (fringe tree)
(cond ((null? tree) ; 空树
'())
((not (pair? tree)) ; 叶子
(list tree))
(else
(append (fringe (car tree)) ; 累积左子树所有元素
(fringe (cadr tree)))))) ; 累积右子树所有元素
组合 fringe
和 accumulate
(书本 78 页),就可以得出一个计算树叶数量的函数:
;;; 35-count-leaves-using-fringe.scm
(load "28-fringe.scm")
(load "p78-accumulate.scm")
(define (count-leaves tree)
(accumulate (lambda (current-leave remained-leaves-count)
(+ 1 remained-leaves-count))
0
(fringe tree)))
测试 count-leaves
:
1 ]=> (count-leaves (list (list 1 2) (list 3 4)))
;Value: 4
1 ]=> (count-leaves (list (list 1 (list 2 3)) (list (list 4 5) (list 6 7))))
;Value: 7
事实上,因为经过 fringe
处理的树已经是一个普通的(一维)列表了,我们实际上可以直接通过 length
函数计算这个列表的长度,从而得出树叶的数量(使用 MIT Scheme 内置的 length
或者 练习 2.33 实现的 length
都可以):
;;; 35-count-leaves-using-length.scm
(load "28-fringe.scm")
(define (count-leaves tree)
(length (fringe tree)))
试试这个新的 count-leaves
:
1 ]=> (load "35-count-leaves-using-length.scm")
;Loading "35-count-leaves-using-length.scm"...
; Loading "28-fringe.scm"... done
;... done
;Value: count-leaves
1 ]=> (count-leaves (list (list 1 2) (list 3 4)))
;Value: 4
上面定义的 count-leaves
可以很好地解决计算树叶的问题,但是它不符合题目给定的格式(只符合了一半):题目要求我们只使用 accumulate
和 map
来计算树叶数量,但是前面的 count-leaves
定义使用了 accumulate
和 fringe
。
定义 count-leaves
的另一种方法是, map
负责计算所有节点的树叶数量,而 accumulate
只须将所有节点的树叶数量加起来就行了: (accumulate + 0 ...)
。
当 map
在遍历树的时候,它会遇到两种情况:
1
,作为这个节点的树叶数量。count-leaves
函数的结果。根据这两条规则,现在可以写出相应的函数了:
;;; 35-count-leaves-using-recursion.scm
(load "p78-accumulate.scm")
(define (count-leaves tree)
(accumulate +
0
(map (lambda (sub-tree)
(if (pair? sub-tree) ; 如果这个节点有分支
(count-leaves sub-tree) ; 那么这个节点调用 count-leaves 的结果就是这个节点的树叶数量
1)) ; 遇上一个叶子节点就返回 1
tree)))
测试:
1 ]=> (load "35-count-leaves-using-recursion.scm")
;Loading "35-count-leaves-using-recursion.scm"...
; Loading "p78-accumulate.scm"... done
;... done
;Value: count-leaves
1 ]=> (count-leaves (list (list 1 2) (list 3 4)))
;Value: 4
1 ]=> (count-leaves (list (list 1 (list 2 3)) (list (list 4 5) (list 6 7))))
;Value: 7
这个 count-leaves
定义可以很好地完成计算树叶数量的工作,而且只使用了 map
和 accumulate
,符合了题目的要求。