lisp中的中序遍历

Question

我正在尝试在 Lisp 中按顺序遍历树。到目前为止，我设法构建了后序遍历，但中序让我头疼..

树的格式是这样的：

 A
/ \
B  C          (A 2 B 0 C 2 D 0 E 0)
  / \
 D   E   

 (defun traverseTreeMain (l)
  (traverseTree l nil)
)

(defun traverseTree (l lc)
 (cond
  ((and (null l) (null lc)) nil)

  ((null l) (append nil (traverseTree lc nil)))

  ((=(cadr l) 0) (append   (list (car l))  (traverseTree (cddr l) lc)  ))

  ((= (cadr l) 1) (append nil  (traverseTree (cddr l)   
                                                        (append (   list (car l)   (- (cadr l) 1)   ) lc)
                                )   
                    )
    )

   (t (append nil (traverseTree (cddr l) (append lc (list (car l) (- (cadr     l)                                                   1))))))
)
)
;;run: (traverseTreeMain '(A 2 B 0 C 2 D 0 E 0))  --POSTORDER
;;=> (B D E C A)

Answer 1

这里一个可能的方法是首先用预序符号构造树。为了表示二叉树节点，我们可以使用 three-element 列表（三元组）。三元组中的第一项是符号：A、B、...接下来的两个元素是左右引用。

现在，语法怎么转：

(A 2 B 0 C 2 D 0 E 0)

变成一棵树？一种方法是先反转语法：

(reverse '(A 2 B 0 C 2 D 0 E 0)) -> (0 E 0 D 2 C 0 B 2 A)

现在，我们将其视为使用简单的 stack-based 语言编写的小型计算机程序，其中包含两条指令：数字和符号。我们从左到右扫描语法。当我们看到一个数字时，我们将其压入堆栈。当我们看到一个符号时，我们弹出堆栈的顶部，它应该是一个数字。然后，该数字告诉我们要从堆栈中弹出多少个节点：0、1 或 2。我们按照指示进行操作，并根据符号和那么多 child 个节点构造一棵树。然后我们把树放在栈上。代码：

(defun build-tree (syntax)
  (let ((rs (reverse syntax))
        (stack))
    (dolist (item rs (pop stack))  ;; heart of the interpreter loop
      (cond ((integerp item) (push item stack))  ;; integer instruction
            ((symbolp item) (let ((num (pop stack)))  ;; sym instruction
                              ;; construct node using backquote, and
                              ;; put it on the stack.
                              (push `(,item ,@(loop repeat num
                                                    collect (pop stack)))
                                    stack)))))))

请注意，dolist 中的 (pop stack) 表达式计算 dolist 的结果值，即函数的 return 值。当我们解释完语法后，完整的树是堆栈中唯一剩下的项目，所以我们弹出它。

没有努力处理语法中的任何错误；我们假设语法是对树的 error-free 描述。

Note: cond in the interpreter can be replaced by typecase or etypecase.

测试：

(build-tree '(A 2 B 0 C 2 D 0 E 0)) -> (A (B) (C (D) (E)))

其他案例：

(build-tree nil) -> NIL

(build-tree '(B 0)) -> (B)

看起来不错。树根在A，有两个children(B)和(C (D) (E))。 (B) 表示没有 children 的 B 节点，所以 Forth ... 请原谅双关语！

生成的结构可以按任何顺序轻松走动。

这里是前序遍历，使用回调函数处理节点中的符号。 To "visit" 表示将符号传递给回调。函数的用户指定一个函数来做一些事情，比如收集传递给回调的符号：

(defun preorder (tree callback-fn)
  (when (consp tree)
    (preorder (second tree) callback-fn) ;; process children first
    (preorder (third tree) callback-fn)
    (funcall callback-fn (first tree)))) ;; then visit parent

测试：

(let ((output))
   (preorder (build-tree '(A 2 B 0 C 2 D 0 E 0))
             (lambda (item) (push item output)))
   (nreverse output))

--> (B D E C A) ;; correct

回调 lambda 将它接收到的项目推入输出列表，然后破坏性地反转。

Inorder 留作 reader 的一个小练习。

Answer 2

通过调整此问题的解决方案可以找到另一个解决方案：，其中需要将树从您的表示法转换为列表表示法 (node left-child right-child)。

解决方法如下：

(defun inorder(l)
  (if (null l)
      nil
      (inorder-sequence l)))

(defun inorder-sequence(l)
  (case (cadr l)
    (0 (values (list (car l)) (cddr l)))
    (1 (multiple-value-bind (left-subtree rest-of-list) (inorder-sequence (cddr l))
          (values (nconc left-subtree (list (car l))) rest-of-list)))
    (t (multiple-value-bind (left-subtree rest-of-list) (inorder-sequence (cddr l))
          (multiple-value-bind (right-subtree rest-of-rest) (inorder-sequence rest-of-list)
             (values (nconc left-subtree (list (car l)) right-subtree) rest-of-rest))))))

辅助函数 inorder-sequence 在每次调用时接收列表的其余部分，以及 returns 几个值：

包含与当前递归调用竞争的部分的顺序的列表，并且
包含必须分析的其余元素的列表。

这样，在每个递归步骤中，函数本身可以使用第二个值来生成相对中序。

请注意，此方法适用于作为树节点的任何类型的元素，包括整数。

lisp中的中序遍历

Inorder traversal in lisp

lisp

tree

traversal

common-lisp

inorder