如何在Scheme中遍历N叉树？新手求助代码调试

嘿，作为Scheme新手碰到这种递归树的问题太正常啦，我来帮你一步步梳理代码、找出问题，再给出可行的解决方案！

首先先看看你原代码里的几个明显问题：

• getchilds函数没写完，末尾缺了闭合括号和逻辑收尾
• 递归查找节点的分支判断有点绕，对树结构的处理逻辑不够清晰

先明确你的树结构：从你定义的atree来看，每个节点要么是带括号的列表（格式为(节点值 子节点1 子节点2 ...)），要么是单个数字（叶子节点，没有子节点）。比如(6)是值为6的节点（无子女），(2 (4 ...) (12 ...) (16))是值为2的节点，它的子节点是(4 ...)、(12 ...)、(16)。

第一步：补全并修正getchilds函数 #

这个函数的作用是把一堆子节点（比如((4 (9 ...)) (12 ...) (16))）转换成它们的节点值列表，比如返回(4 12 16)。修复后的代码如下：

(define (getchilds child-nodes)
  (cond
    ((null? child-nodes) '())
    (else
     ; 每个子节点都是列表，取第一个元素作为节点值
     (cons (caar child-nodes)
           (getchilds (cdr child-nodes))))))

第二步：重构children函数 #

你的核心需求是根据节点值elem，找到它的所有子节点的数值列表。我们用深度优先搜索的逻辑来遍历树，修复后的代码如下：

; 先保留你的树定义
(define atree '(10 (2 (4 (9 (3)) (12 (1 (2))) (16))) (5 (7) (21)) (6)))

(define (children elem tree)
  (cond
    ((null? tree) '())          ; 空树，直接返回空列表
    ((number? tree) '())         ; 碰到叶子节点（单个数字），无子女，返回空
    ((eqv? (car tree) elem)     ; 当前节点就是目标，返回它的子节点值列表
     (getchilds (cdr tree)))
    (else                        ; 不是目标，递归遍历当前节点的所有子节点
     (let loop ((subtrees (cdr tree)) (result '()))
       (if (null? subtrees)
           result
           (let ((sub-result (children elem (car subtrees))))
             (if (not (null? sub-result))
                 sub-result
                 (loop (cdr subtrees) result))))))))

测试一下效果 #

现在可以运行几个测试用例验证：

• (children 2 atree) → 返回 (4 12 16)（符合预期，2的子节点是4、12、16）
• (children 4 atree) → 返回 (9 12 16)（4的子节点是9、12、16）
• (children 6 atree) → 返回 ()（6是叶子节点，无子女）
• (children 10 atree) → 返回 (2 5 6)（根节点10的子节点是2、5、6）

额外扩展：处理重复节点值 #

如果你的树里可能有多个值相同的节点，想要收集所有匹配节点的子节点，可以用这个版本的函数：

(define (children-all elem tree)
  (cond
    ((null? tree) '())
    ((number? tree) '())
    ((eqv? (car tree) elem)
     (cons (getchilds (cdr tree)) (children-all elem (cdr tree))))
    (else
     (append (children-all elem (car tree)) (children-all elem (cdr tree))))))

比如如果树里有两个值为2的节点，它会返回所有匹配节点的子节点列表组成的列表。

顺便说下N叉树的遍历 #

如果需要遍历整个N叉树，比如前序遍历（先访问节点，再遍历子节点），可以用这个简单的实现：

(define (preorder tree)
  (cond
    ((null? tree) '())
    ((number? tree) (list tree))
    (else
     (cons (car tree)
           (append-map preorder (cdr tree))))))

调用(preorder atree)会得到前序遍历的结果：(10 2 4 9 3 12 1 2 16 5 7 21 6)。

慢慢来，Scheme的递归逻辑需要多练，多测试小例子很快就能上手啦！

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