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

Question

我试图按照级别顺序打印一个常见的Lisp树。

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

1. 1
2. 2 3
3. 4 5 6 7
4. 8 9 10
5. 11

这是树的快速模拟：

我试图通过执行广度优先搜索按此顺序打印此树。

我一直在想的是，我应该只是能够通过这棵树来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的输入将始终是子节点列表（它们本身就是列表）

从这里开始，我将把这个输入的childnodes列表称为input

1. qazxsw poi获得了qazxsw poi中每个子节点的第一个元素
2. mapcar 'car获取除input中每个子节点的第一个元素之外的所有其他元素

现在第2步的问题是，与mapcar 'cdr不同，它弹出一个很好的非列表元素（在这种情况下），input给了我一个列表

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

3. car将这个列表列表扁平化为一个列表列表（或列入子节点列表的子节点列表）
4. 将输出2（列表的列表||子节点列表）放回到traverse2中

Answer 2

这是cdr的近似副本：对于使用议程工作的树的任何类型的广度优先遍历。 apply 'append为这个问题提供了一系列日益复杂的方法，首先是一个简单易懂的议程，最后通过表明如果你换成不同的结构来进行议程，你可以进行不同类型的搜索，包括广度和深度 - 首先，使用相同的代码。

首先抽象树结构：它已经是20世纪70年代了，当它意味着别的东西时，我们不需要充满this question和my answer to the previous question的代码。事实上，你的树有一个不规则的结构，因为节点可以是（value。children）或只是原始值：

car

我没有打算做一个构建器，但我只是定义你的样本树：

cdr

现在这里是一个函数的实现，它将使用一个简单的列表议程以广度优先的顺序将访问者带到树上：

(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)))) 作为访问者：

(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)))

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