2

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

树的格式是这样的：

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

2 回答 2

1

这里一种可能的方法是首先从前序符号构造树。为了表示二叉树节点，我们可以使用三元素列表（三元组）。三元组中的第一项是符号：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)

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

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

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

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

注意：cond在解释器中可以替换为typecase或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，有两个孩子(B)和(C (D) (E))。(B)表示没有子节点的 B 节点，所以 Forth ... 请原谅双关语！

这个结果结构可以轻松地以任何顺序行走。

这是前序遍历，使用回调函数来处理节点中的符号。“访问”意味着将符号传递给回调。该函数的用户指定一个函数，该函数执行某些操作，例如收集传递给回调的符号：

(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 留给读者作为一个简单的练习。

于 2015-12-10T03:55:02.593 回答
1

通过调整该问题的解决方案可以找到另一个解决方案：Transforming trees in lisp，其中需要将树从您的表示法转换为列表表示法(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每次调用的辅助函数接收列表的其余部分，并返回几个值：

  1. 包含与当前递归调用竞争的部分的顺序的列表，以及

  2. 包含必须分析的其余元素的列表。

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

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

于 2015-12-10T08:37:08.780 回答