首页 > 代码库 > [SICP] [CH 2.2] 层次性数据和闭包性质

[SICP] [CH 2.2] 层次性数据和闭包性质

2.2.2 层次性结构

计算叶节点

(leaves tree) = (leaves (car tree)) + (leaves (cdr tree)),

(leaves leave) = 1;

; 计算tree中叶节点数量
(define (leaves tree) (cond ((null? tree) 0) ((not (pair? tree)) 1) (else (+ (leaves (car tree)) (leaves (cdr tree))))))
; 计算叶节点的测试代码
(define x (cons (list 1 2) (list 3 4))) ; ((1 2) 3 4))(length x) ; 3(leaves x) ; 4(list x x) ; (((1 2) 3 4) ((1 2) 3 4))(length (list x x)) ; 2(leaves (list x x)) ; 8

 

Q 2.28

题目:给出过程定义fringe, 以一个树为参数, 返回一个由这棵树中所有叶节点组成的表, 从左到右排列。

思路:用到了一个全局变量记录结果,遍历树,将所有叶节点append到结果上。

(define (fringe tree)  (define (iter tree result)    (cond ((null? tree) result)                               ; 当前结点为空时,返回result          ((leaf? tree) (append result (list tree)))          ; 当前节点为叶时,封装为list,append至结果          (else (iter (cdr tree) (iter (car tree) result))))) ; 当前节点为根结点时,将右结点append到左结点上  (iter tree null))

 

[SICP] [CH 2.2] 层次性数据和闭包性质