在 COMMON LISP 中使用先序和中序重建树

Question

当我一直在学习 LISP 并阅读实用的 Common Lisp 时，我发现了问题并试图解决它们，但我陷入了这个特定问题，并且不确定如何解决它，因此需要一些帮助/建议。

我需要能够从其前序和中序创建后序树

例如，如果给出以下内容:

预购:A B D E C F

顺序:DB E A C F

输出将是后序:D E B F C A

据我所知，中序的第一个元素始终是后序的第一个元素，因此我开始编写代码来反射(reflect)这一点:

(defun tree-recovery (preorder inorder)
  (let (root)
    (setf root (first inorder))))

但我不确定从这里去哪里，任何帮助将不胜感激!谢谢

Answer 1

如果我们将函数命名为tree-recovery，让它恢复树 而不是构建后序序列。 (比我聪明的人 需要在不实际重建的情况下解决问题 树)。

中序和后序以相同的元素开头，但该元素是 不是根:预序序列的第一个元素是根。

让我们恢复树，假设所有序列元素都是 可通过 EQL 进行比较的非零原子。我们将叶子表示为 原子的值，其他节点为(list root left right)，以及一个空 子树为 NIL。

(defun tree-recovery (preorder inorder)
  (if (rest preorder)
      (let* ((root (pop preorder))
             (inorder-root-tail
               (member root inorder))
             (inorder-left
               (ldiff inorder inorder-root-tail))
             (left-length
               (length inorder-left))
             (inorder-right
               (rest inorder-root-tail))
             (preorder-left
               (subseq preorder 0 left-length))
             (preorder-right
               (subseq preorder left-length)))
        (list root
              (tree-recovery preorder-left inorder-left)
              (tree-recovery preorder-right inorder-right)))
      (first preorder)))

对于空树，我们返回 NIL。对于一个叶节点的平凡树，我们 返回一个值。

对于其他树，我们首先从 preorder 中弹出根元素(其中 这是第一个)。然后我们找到一个以根元素开始的子列表 有序。我们用它来获取与我们的对应的inorder 左子树和对应于右子树的一 block inorder 子树。知道左子树的大小，我们就可以得到左子树和右子树 轻松预订。

现在，当我们有一棵树时，进行后序遍历就很容易了:

(defun postorder (tree)
  (and tree ;; non-empty
       (if (consp tree) ;; non-leaf
           (destructuring-bind (root left right) tree
             (append (postorder left)
                     (postorder right)
                     (postorder root)))
           (list tree))))

让我们尝试一下:

(postorder 
 (tree-recovery '(a b d e c f)
                '(d b e a c f)))
=> (D E B F C A)

似乎有效。