tree - 在 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))

这意味着树基本上 split 了，(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

1. mapcar 'car 获取input中每个子节点的第一个元素
2. mapcar 'cdr 获取input中每个子节点的第一个元素以外的所有其他元素

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

因此列表列表(或子节点列表)现在转换为列表列表列表(或子节点列表列表)

1. apply 'append 将这个由列表组成的列表扁平化为一个列表列表(或将一个子节点列表扁平化为一个子节点列表)

2. 将2(列表列表||子节点列表)的输出放回traverse2