LISP中计算树的叶子节点总数的方法及现有实现替代方案问询
以下是一个返回树的叶子节点总数的程序,示例调用
(count-leaves '((1 2) () (3) (4 5 6)))的返回结果为6。我目前找到了如下代码,请问是否有其他方式可以实现相同功能?(define (count-leaves t) (cond ((null? t) 0) ((not (pair? t)) 1) (else (+ (count-leaves (car t)) (count-leaves (cdr t)))))) ; 该函数的通用逻辑如下: ; 若树为空,返回0 ; 若当前节点不是序对,说明是叶子节点,返回1 ; 其他情况则拆分序对,分别统计左右分支的叶子数后求和 ; 测试代码如下: 1 ]=> (load "hierarchical_structures_1.scm") ;Loading "hierarchical_structures_1.scm"... done ;Value: count-leaves 1 ]=> (define tree-1 (cons (list 1 2) (list 3 4))) ;Value: tree-1 1 ]=> tree-1 ;Value 11: ((1 2) 3 4) 1 ]=> (count-leaves tree-1) ;Value: 4
其他实现方案
你当前使用的是Scheme中统计树叶子节点最经典的递归拆分car/cdr实现,以下是几种功能完全一致的不同实现方式:
1. 高阶函数map+apply实现
利用map遍历列表的特性,省略手动拆分左右分支的逻辑,代码更简洁:
(define (count-leaves t) (cond ((null? t) 0) ((not (pair? t)) 1) (else (apply + (map count-leaves t)))))
测试验证:调用(count-leaves '((1 2) () (3) (4 5 6)))返回6,(count-leaves tree-1)返回4,和原实现结果完全一致。
2. 尾递归优化实现
通过内部迭代器把计数结果放在参数中传递,符合尾递归优化要求,适合处理层级极深的树,不会出现栈溢出问题:
(define (count-leaves t) (define (iter rest count) (cond ((null? rest) count) ((not (pair? rest)) (+ count 1)) (else (iter (car rest) (iter (cdr rest) count))))) (iter t 0))
3. 树打平后统计长度实现
先将嵌套的树结构展开为仅包含叶子节点的一维列表,直接求列表长度即可得到叶子总数,逻辑更直观,适合需要同时用到所有叶子节点的场景:
(define (count-leaves t) (length (fringe t))) ; 辅助函数:将树展开为叶子节点组成的列表 (define (fringe t) (cond ((null? t) '()) ((not (pair? t)) (list t)) (else (append (fringe (car t)) (fringe (cdr t))))))
该方案的缺点是append操作会带来额外的性能开销,不适合处理规模极大的树。
内容的提问来源于stack exchange,提问作者mp96
相关产品推荐
相关产品推荐

