在 Lisp 中逐层遍历树（广度优先）

Question

我正在尝试按级别顺序打印普通 Lisp 中的树。

列表是(1 (2 4 (5 (8 11)) 6) (3 (7 9 10)))，意思是树是有序的：

这是树的快速模型：

我正在尝试通过执行广度优先搜索按此顺序打印这棵树。

我在这里一直在想的是，我应该能够 car 和 cdr 通过这棵树，但一直很难弄清楚如何做到这一点。这正是我在半伪代码中尝试过的。

(defun traverse (*cur-level*)
  (print (car *cur-level*)) ; print out the first element of the current level
    (if (cdr *cur-level*) ; if cdr of next level is not nil
      (setq *next-level* (cdr *cur-level*) ;set that to be the next level
      (traverse *next-level*)) ; recursively call until all levels traversed. 
                               ; else, simply do not do anything and terminate
                               ; the function.

我自己逐步遍历树，我发现在 第二个循环 这个算法失败了，因为

;first loop
(car *cur-level) = 1
(cdr *cur-level*)=((2 4 (5 (8 11)) 6) (3 (7 9 10)),

所以在下一个循环中

;second loop
(car *cur-level*) = (2 4 (5 (8 11)) 6)
(cdr *cur-level*) = (3 (7 9 10))

这意味着树本质上分裂了，(2 4 (5 (8 11)) 6)被忽略了。

另外，在同一个循环中，(car cur-level)不是单个元素，而是一个列表。意思是我需要做：

;still second loop
(car (car *cur-level*) = 2
(cdr (car *cur-level*) = (4 (5 (8 11)) 6)

所以我尝试包含一个检查关卡大小的条件：

(if (> (list-length (car *cur-level*)) 1)
  (print (car (car *cur-level*))
  (setq *next-level* (cdr (car *cur-level*))

但这并不能解决 (3 (7 9 10) 与树分开的事实，这意味着订单打印不正确，让我觉得我正在解决仅针对这棵树的问题，而不是适当的算法。

注意：这个问题发生了两次，一次在第二个循环上，另一次在树左侧的第四个循环上（(car cur-level) = (5 (8 11))）。

我怎样才能正确地做到这一点？我真的被困在这里，不知道如何继续。

Answer 1

我认为在您的原始代码中您正试图这样做：

(defun traverse (cur-level)
  (print (car cur-level)) ;print out the first element of the current level
  (when (cdr cur-level) ;if cdr of next level is not nil
    (setq next-level (cdr cur-level)) ;set that to be the next level
    (traverse next-level)))

我认为通过确保所有子节点都是列表可以使您的树表示更好，

像这样：(1 (2 (4) (5 (8 (11))) (6)) (3 (7 (9) (10)))))

(defun traverse2 (children)
  (when children
    (print (mapcar 'car children)) 
    (traverse2 (apply 'append (mapcar 'cdr children)))))

(defun traverse (tree)
  (print (car tree))
  (traverse2 (cdr tree)))

试试运行这个代码 here。

由于我不熟悉 Common Lisp，所以无法一概而论，但希望对您有所帮助。

编辑：进一步解释

记住 traverse2 的输入总是一个子节点列表（它们本身就是列表）

从这里开始，我将把这个子节点输入列表称为input

mapcar 'car获取input
mapcar 'cdr获取input

现在第 2 步的问题在于，不像 car 弹出一个很好的非列表元素（在本例中），cdr 给了我一个列表

因此列表列表（或子节点列表）现在转换为列表列表列表（或子节点列表列表）

apply 'append 将这个列表列表扁平化为列表列表（或子节点列表列表为子节点列表）
将 2（列表列表 || 子节点列表）的输出返回到 traverse2

Answer 2

这几乎是 this question: for any kind of breadth-first traversal of a tree you work using an agenda. my answer to the previous question 的重复，给出了解决这个问题的一系列越来越复杂的方法，从一个头脑简单的列表议程开始，最后展示了如果你交换不同的结构agenda 你可以使用相同的代码进行不同类型的搜索，包括广度优先和深度优先。

首先抽象树结构：已经是1970年代了，我们不需要充满car和cdr的代码这意味着别的东西。你的树实际上有一些不规则的结构，因为节点可以是 (value . children) 的 conses 或只是原始值：

(defun tree-node-value (node)
  ;; a node is either (value . children) or value
  (typecase node
    (cons
     (car node))
    (t node)))

(defun tree-node-children (node)
  ;; a node only has children if it is a cons
  (typecase node
    (cons
     (cdr node))
    (t '())))

(defun make-tree-node (value children)
  ;; only make consy nodes
  (cons value children))

我懒得做一个构建器，但我会定义你的示例树：

(defparameter *sample-tree* '(1 (2 4 (5 (8 11)) 6) (3 (7 9 10))))

现在这里是一个函数的实现，该函数将使用头脑简单的 listy 议程以广度优先顺序引导访问者在树上行走：

(defun walk-tree/breadth-first (tree visitor)
  ;; walk over a tree breadth-first, calling visitor on each node's
  ;; value, using an agenda represented explicitly as a list.
  (labels ((walk (agenda)
             (when (not (null agenda))
               ;; there is more to do
               (destructuring-bind (this . next) agenda
                 ;; call the visitor
                 (funcall visitor (tree-node-value this))
                 ;; and continue with the extended agenda
                 (walk (append next (tree-node-children this)))))))
    (walk (list tree))
    (values)))

我们可以在您的树上调用它，使用 print 作为访问者：

> (walk-tree/breadth-first *sample-tree* #'print)

1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11

我鼓励您查看旧答案中的其他实现，尤其是明确迭代的实现。

在 Lisp 中逐层遍历树（广度优先）

Traversing Tree Level by Level (Breadth First) in Lisp

tree

lisp

common-lisp

breadth-first-search