如何修改LISP后序遍历函数以适配带子节点数标记的树结构

原有嵌套列表树后序遍历函数仅适用于固定2子节点的树结构，你遇到的新线性表示属于带孩子计数的前序序列化树结构，每个节点的存储规则为[节点值, 子节点数量, 子节点1序列化内容, 子节点2序列化内容...]，处理时需要额外记录未消费的序列片段，因此要调整递归逻辑支持双返回值（后序遍历结果 + 剩余未处理的序列）。

适配后的实现代码 #

;; 核心递归处理函数，返回两个值：子树后序遍历结果、剩余未处理的序列片段
(defun postorder-linear (lst)
  (if (null lst)
      (values nil nil)
      (let* ((cur-node (car lst))
             (child-count (cadr lst))
             (remaining (cddr lst))
             (child-result nil))
        ;; 逐个遍历处理所有子节点，累加子树的后序结果
        (dotimes (i child-count)
          (multiple-value-bind (sub-res new-remaining)
              (postorder-linear remaining)
            (setf child-result (append child-result sub-res))
            (setf remaining new-remaining)))
        ;; 所有子节点处理完成后追加当前节点，返回结果
        (values (append child-result (list cur-node)) remaining))))

;; 封装为和原有函数调用方式一致的单返回值接口
(defun postorder (lst)
  (multiple-value-bind (res _)
      (postorder-linear lst)
    res))

验证测试 #

• 测试输入：(postorder '(A 2 B 0 C 2 D 0 E 0))
• 输出结果：(B D E C A)，和原嵌套树(A (B) (C (D) (E)))的后序遍历结果完全一致。

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