乐正

Actions speak louder than words.

Sicp-ex2-28

问题

写一个过程fringe,它以一个树(表示为表)为参数,返回一个表,表中的元素是这棵树 中所有的树叶,按照从左到右的顺序。例如:

1
2
3
4
5
6
7
(define x (list (list 1 2) (list 3 4)))

(fringe x)
(1 2 3 4)

(fringe (list x x))
(1 2 3 4 1 2 3 4)

解答

遍历这棵树的所有叶子节点时,会遇到三种情况:

  • 当树为空的时候,返回空表
  • 当树为叶子节点的时候,返回只具有单个元素的列表
  • 叶子有左右两颗子树的时候,对左右子树元素进行累加
练习2.28 (ex2-28.scm) download
1
2
3
4
5
6
7
8
9
;; Happy hacking Yuez - Emacs ♥ you!

(define (fringe items)
  (define (iter items result)
    (cond ((null? items) result)
          ((not (pair? items)) (append result (list items)))
          (else (iter (cdr items) (iter (car items) result)))))

  (iter items (list)))

测试

1
2
3
4
5
6
7
8
9
10
11
(define x (list (list 1 2) (list 3 4)))
;Value: x

(fringe x)
;Value 18: (1 2 3 4)

(fringe (list x x))
;Value 19: (1 2 3 4 1 2 3 4)

(fringe (list 1 (list 3 4 (list 4 5 6) (list 3 4))))
;Value 21: (1 3 4 4 5 6 3 4)

draft

« sicp-ex2-27 sicp-ex2-29 »

Comments