tree - 在COMMON LISP中使用预排序和有序排序的树重构

由于我一直在学习LISP和阅读实用的常用LISP，我发现了一些问题并试图解决它们，我在这个特殊的问题上陷入了困境，不确定如何解决它，所以希望得到一些帮助/建议。
我需要能够从它的前序和序创建一个后序树
例如，如果给出以下内容：
预订单：A B D E C F
顺序：D B E A C F
输出为后序：D E B F C A
据我所见，inorder的第一个元素始终是postorder的第一个元素，因此我已经开始编写代码来反映这一点：

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

但我不知道从这里去哪里，任何帮助都将非常感谢谢谢

最佳答案

如果我们将函数命名为tree-recovery，让它恢复树
而不是建立后序序列（比我聪明的人
需要在没有实际重建的情况下解决问题
树）。
Inorder和postorder以同一个元素开头，但该元素是
不是根：预排序序列的第一个元素是根。
假设所有序列元素都是
非零原子可比EQL我们将代表一片叶子
atom的值，其他节点为(list root left right)，空
子树为零。

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

空树归零对于一个叶节点的平凡树，我们
返回值。
对于其他树，我们首先从preorder中弹出根元素（其中
这是第一次）然后我们在
inorder我们用它得到一个对应于
左子树和一块对应于我们的右子树的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)

似乎有用。