我试图按照级别顺序打印一个常见的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))
)。
我该怎么做才能正确?我真的被困在这里,并不知道如何继续。
我想在你的原始代码中你试图这样做:
(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
mapcar 'car
获取除input
中每个子节点的第一个元素之外的所有其他元素现在第2步的问题是,与mapcar 'cdr
不同,它弹出一个很好的非列表元素(在这种情况下),input
给了我一个列表
因此,列表列表(或子节点列表)现在转换为列表列表(或子节点列表列表)
car
将这个列表列表扁平化为一个列表列表(或列入子节点列表的子节点列表)这是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)))
我鼓励您查看旧答案中的其他实现,特别是明确迭代的实现。