I have a representation of a tree using lists. For example:
(1 ((2 (3)) (3 (2)))) (2 ((1 (3)) (3 (1)))) (3 ((1 (2)) (2 (1)))))`
Now I need to traverse it level by level while maintaining the hierarchy tree. For instance:
(1)(1 2) (1 3) (2 1) (3 1) (3 1) (3 2)(1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)I can't figure out how to do it in Lisp. Any help (even a pseudo code) is appreciated. I have thought of several approaches but none of them seems legit.
进行广度优先搜索的经典方法是维护议程：接下来要看的事情清单。然后，您只需将对象从议程的开头剥离，然后将其子对象添加到议程的末尾。解决此类议程的一种非常简单的方法是节点列表：将其添加到列表的末尾，然后使用append。
我无法理解您的树形结构（请问需要数据结构或算法的规范时要给出该规范：这是浪费每个人的时间进行第二次猜测），所以我自己做了一个列表的条件：一棵树是一个缺点，它的价值是汽车，而cdr是子列表。这里是制作和访问这种树结构和示例树的函数。
(defun tree-node-value (n)
(car n))
(defun tree-node-children (n)
(cdr n))
(defun make-tree-node (value &optional (children '()))
(cons value children))
(defparameter *sample-tree*
(make-tree-node
1
(list
(make-tree-node 2 (list (make-tree-node 3)))
(make-tree-node 4 (list (make-tree-node 5) (make-tree-node 6)))
(make-tree-node 7 (list (make-tree-node 8 (list (make-tree-node 9))))))))
现在，我不必再担心树的显式结构。
现在这是一个使用议程的函数，该议程将在树中搜索给定的节点值：
(defun search-tree/breadth-first (tree predicate)
;; search a tree, breadth first, until predicate matches on a node's
;; value. Return the node that matches.
(labels ((walk (agenda)
(if (null agenda)
;; we're done: nothing matched
(return-from search-tree/breadth-first nil)
(destructuring-bind (this . next) agenda
(if (funcall predicate (tree-node-value this))
;; found it, return the node
(return-from search-tree/breadth-first this)
;; missed, add our children to the agenda and
;; carry on
(walk (append next (tree-node-children this))))))))
(walk (list tree))))
为了进行比较，这里是深度优先搜索：
(defun search-tree/depth-first (tree predicate)
;; search a tree, depth first, until predicate matches on a node's
;; value
(labels ((walk (node)
(if (funcall predicate (tree-node-value node))
(return-from search-tree/depth-first node)
(dolist (child (tree-node-children node) nil)
(walk child)))))
(walk tree)))
现在，您可以通过有一个谓词来比较这些实现，该谓词可以打印其参数但始终失败，从而导致遍历整个树：
> (search-tree/breadth-first *sample-tree*
(lambda (v)
(print v)
nil))
1
2
4
7
3
5
6
8
9
nil
> (search-tree/depth-first *sample-tree*
(lambda (v)
(print v)
nil))
1
2
3
4
5
6
7
8
9
nil
这种幼稚的议程实施方式存在的一个问题是，我们最终一直append都在打电话。聪明的实现方式可以有效地将项目附加到末尾。这是一个这样的实现：
(defun make-empty-agenda ()
;; an agenda is a cons whose car is the list of items in the agenda
;; and whose cdr is the last cons in that list, or nil is the list
;; is empty. An empty agenda is therefore (nil . nil)
(cons nil nil))
(defun agenda-empty-p (agenda)
;; an agenda is empty if it has no entries in its list.
(null (car agenda)))
(defun agenda-next-item (agenda)
;; Return the next entry from the agenda, removing it
(when (agenda-empty-p agenda)
(error "empty agenda"))
(let ((item (pop (car agenda))))
(when (null (car agenda))
(setf (cdr agenda) nil))
item))
(defun agenda-add-item (agenda item)
;; add an item to the end of the agenda, returning it
(let ((item-holder (list item)))
(if (agenda-empty-p agenda)
(setf (car agenda) item-holder
(cdr agenda) item-holder)
(setf (cdr (cdr agenda)) item-holder
(cdr agenda) item-holder))
item))
请注意，无法复制提供的这些议程之一。
这是一个使用此“聪明”议程的显式迭代函数：
(defun search-tree/breadth-first/iterative (tree predicate)
(loop with agenda = (make-empty-agenda)
initially (agenda-add-item agenda tree)
while (not (agenda-empty-p agenda))
for node = (agenda-next-item agenda)
when (funcall predicate (tree-node-value node))
do (return-from search-tree/breadth-first/iterative node)
else do (loop for c in (tree-node-children node)
do (agenda-add-item agenda c))
finally (return nil)))
最后，任何基于议程的搜索都可以轻松地修改为可重新启动：它只需要在匹配的位置返回当前议程，并允许传递议程。这是上述功能的一种变体，它支持重新启动搜索：
(defun search-tree/breadth-first/iterative (tree predicate
&optional (agenda
(make-empty-agenda)))
;; search TREE using PREDICATE. if AGENDA is given and is not empty
;; instead restart using it (TREE is ignored in this case). Return
;; the node found, or nil, and the remaining agenda
(loop initially (unless (not (agenda-empty-p agenda))
(agenda-add-item agenda tree))
while (not (agenda-empty-p agenda))
for node = (agenda-next-item agenda)
when (funcall predicate (tree-node-value node))
do (return-from search-tree/breadth-first/iterative
(values node agenda))
else do (loop for c in (tree-node-children node)
do (agenda-add-item agenda c))
finally (return (values nil agenda))))
实际上，可以进一步推广基于议程的搜索树的方法。特别是：
这两种情况的实际搜索实现可以相同，这很简单。
下面是一些代码演示了这一点。这定义了用于树访问的通用功能（使用基于缺点的树的方法），因此无需在乎，还为带有两个具体类queue且stack具有适当方法的议程定义了协议。然后，搜索功能完全不知道是进行深度优先搜索还是宽度优先搜索，并且在两种情况下均可重新启动。
这是相当大量的代码：我将其留在此处，以防万一它对任何人都有用。
;;;; Trees
;;;
(defgeneric tree-node-value (n)
(:documentation "The value of a tree node"))
(defgeneric tree-node-children (n)
(:documentation "The children of a tree"))
;;;; Consy trees
;;;
(defmethod tree-node-value ((n cons))
(car n))
(defmethod tree-node-children ((n cons))
(cdr n))
(defun make-cons-tree-node (value &optional (children '()))
;; consy trees: I could do some clever EQL method thing perhaps to
;; abstract this?
(cons value children))
(defun form->tree (form &key (node-maker #'make-cons-tree-node))
(labels ((walk-form (f)
(destructuring-bind (value . child-forms) f
(funcall node-maker
value
(mapcar #'walk-form child-forms)))))
(walk-form form)))
(defparameter *sample-tree*
(form->tree '(1 (2 (3))
(4 (5) (6))
(7 (8 (9))))))
;;;; Agendas
;;;
(defclass agenda ()
())
(defgeneric agenda-empty-p (agenda)
(:documentation "Return true if AGENDA is empty"))
(defgeneric agenda-next-item (agenda)
(:documentation "Return the next item from AGENDA.
If there is no next item, signal an error: there is a before method which does this.")
(:method :before ((agenda agenda))
(when (agenda-empty-p agenda)
(error "empty agenda"))))
(defmethod initialize-instance :after ((agenda agenda) &key
(item nil itemp)
(items (if itemp (list item) '()))
(ordered nil))
(agenda-add-items agenda items :ordered ordered))
(defgeneric agenda-add-item (agenda item)
(:documentation "Add ITEM to AGENDA, returning ITEM.
There is an around method which arranges for ITEM to be returned.")
(:method :around ((agenda agenda) item)
(call-next-method)
item))
(defgeneric agenda-add-items (agenda items &key ordered)
(:documentation "Add ITEMS to AGENDA.
If ORDERED is true do so in a way that AGENDA-NEXT-ITEM will pull them
off in the same order. Return AGENDA (there is an around method which
arranges for this). The default method just adds the items in the
order given.")
(:method :around ((agenda agenda) items &key ordered)
(declare (ignorable ordered))
(call-next-method)
agenda)
(:method ((agenda agenda) items &key ordered)
(declare (ignorable ordered))
(loop for item in items
do (agenda-add-item agenda item))))
;;;; Queues are FIFO agendas
;;;
(defclass queue (agenda)
((q :initform (cons nil nil)))
(:documentation "A queue"))
(defmethod agenda-empty-p ((queue queue))
(null (car (slot-value queue 'q))))
(defmethod agenda-next-item ((queue queue))
(let* ((q (slot-value queue 'q))
(item (pop (car q))))
(when (null (car q))
(setf (cdr q) nil))
item))
(defmethod agenda-add-item ((queue queue) item)
(let ((q (slot-value queue 'q))
(item-holder (list item)))
(if (null (car q))
(setf (car q) item-holder
(cdr q) item-holder)
(setf (cdr (cdr q)) item-holder
(cdr q) item-holder))))
;;;; Stacks are LIFO agendas
;;;
(defclass stack (agenda)
((s :initform '()))
(:documentation "A stack"))
(defmethod agenda-empty-p ((stack stack))
(null (slot-value stack 's)))
(defmethod agenda-next-item ((stack stack))
(pop (slot-value stack 's)))
(defmethod agenda-add-item ((stack stack) item)
(push item (slot-value stack 's)))
(defmethod agenda-add-items ((stack stack) items &key ordered)
(loop for item in (if ordered (reverse items) items)
do (agenda-add-item stack item)))
;;;; Searching with agendas
;;;
(defun tree-search (tree predicate &key (agenda-class 'stack))
;; search TREE using PREDICATE. AGENDA-CLASS (default STACK)
;; defines the type of search: a STACK will result in a depth-first
;; search while a QUEUE will result in a breadth-first search. This
;; is a wrapper around AGENDA-SEARCH.
(agenda-search (make-instance agenda-class :item tree) predicate))
(defun agenda-search (agenda predicate)
;; Search using an agenda. PREDICATE is compared against the value
;; of a tree node. On success return the node matched and the
;; agenda, on failure return NIL and NIL. If the returned agenda is
;; not empty it can be used to restart the search.
(loop while (not (agenda-empty-p agenda))
for node = (agenda-next-item agenda)
when (funcall predicate (tree-node-value node))
do (return-from agenda-search
(values node agenda))
else do (agenda-add-items agenda (tree-node-children node)
:ordered t)
finally (return (values nil nil))))