在Scheme中实现树结构有序叶子节点提取及相关问题咨询

问题1解答 #

处理嵌套列表/树结构的空值场景有非常通用的固定模式：所有结构遍历逻辑第一步优先判断输入是否为null?，空值直接返回基础结果（比如提取叶子的场景就返回空列表），再处理非空的两种情况：car是叶子/是子树。
这类空值判断在Scheme编程中属于高频场景：因为Scheme的列表本质是nil终止的点对链，不管是单层线性列表还是嵌套的树结构，所有分支最终都会走到空值终止节点，只要涉及结构遍历的代码都需要做对应空值处理，这是Scheme数据结构的基础特性决定的。

问题2解答 #

Scheme中函数的返回值是函数体内部最后一个执行的表达式的求值结果。你写的iter函数前面两个都是无else分支的if表达式：

• 第一个if的两个分支，要么返回set!的结果（Scheme中set!的返回值属于未定义的实现相关值，不是你累积的列表），要么返回内部递归调用iter的结果
• 第二个if如果条件成立返回iter递归调用的结果，条件不成立时无else分支，返回值同样是未定义的
  如果删掉末尾单独的L表达式，iter的返回值就是第二个if的求值结果，不可能拿到你用set!累积好的结果列表。只有把L作为函数体最后一个表达式，才会将累积后的列表作为iter的返回值。

问题3解答 #

你目前的迭代版本有两个可优化点：一是用set!维护可变状态不符合函数式风格，二是add-element-to-list每次添加元素都要遍历全表，时间复杂度达到O(n²)。可以改用尾递归+累积器的纯函数写法，代码更简洁，效率也更高，优化后示例如下：

(define (fringe lst)
  (define (iter remaining acc)
    (cond
      ((null? remaining) acc)
      ((pair? (car remaining))
       (iter (cdr remaining) (iter (car remaining) acc)))
      (else
       (iter (cdr remaining) (cons (car remaining) acc)))))
  (reverse (iter lst '())))

这个版本不需要额外的辅助函数，也没有可变变量，天然处理了空值输入的边界情况，整体时间复杂度为O(n)，和递归版本的计算效率一致，同时因为是尾递归实现，不会有栈溢出风险。

内容的提问来源于stack exchange，提问作者David542