练习 2.35

count-leaves 函数用于计算一棵树的树叶数量,题目要求我们补充缺少的部分:

(define (count-leaves t)
    (accumulate <??> <??> (map <??> <??>)))

根据题目给出的函数形式,猜测有两种可能的办法:

方法一

首先想到的办法可能是,用 map 函数枚举(enumerate)出所有树叶,然后 accumulate 对每个叶子进行 + 1 计数,从而计算出整棵树的树叶数量(类似于 练习 2.33length 定义)。

使用 练习 2.28fringe 函数,可以很好地完成枚举出所有树叶的工作:

;;; 28-fringe.scm

(define (fringe tree)
    (cond ((null? tree)                         ; 空树
            '())
          ((not (pair? tree))                   ; 叶子
            (list tree))
          (else
            (append (fringe (car tree))         ; 累积左子树所有元素
                    (fringe (cadr tree))))))    ; 累积右子树所有元素

组合 fringeaccumulate (书本 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 可以很好地解决计算树叶的问题,但是它不符合题目给定的格式(只符合了一半):题目要求我们只使用 accumulatemap 来计算树叶数量,但是前面的 count-leaves 定义使用了 accumulatefringe

定义 count-leaves 的另一种方法是, map 负责计算所有节点的树叶数量,而 accumulate 只须将所有节点的树叶数量加起来就行了: (accumulate + 0 ...)

map 在遍历树的时候,它会遇到两种情况:

  1. 节点是叶子节点,如果是这样的话,那么返回 1 ,作为这个节点的树叶数量。
  2. 节点有左右两个分支,那么这个节点的树叶数量就是这个节点调用 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 定义可以很好地完成计算树叶数量的工作,而且只使用了 mapaccumulate ,符合了题目的要求。

讨论

blog comments powered by Disqus