在COMMON LISP中使用預先訂購和訂購的樹重建

Question

正如我一直在學習LISP和閱讀實用的常見lisp，我發現了問題並試圖解決它們，我一直在困擾這個特定的問題，我不確定如何接近它，所以會像一些幫助/建議。

我需要能夠從它的前序和中序

例如，創建一個後序樹如果下面給出：

預購：ABDECF

中序：DBEACF

輸出將是後序：DEBFCA

從我可以看到inorder的第一個元素始終是第一個後序的元素，所以我已經開始寫代碼，以反映這一點：

(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中的根元素開始的子列表。我們用它來得到inorder對應於我們的 左子樹和一塊inorder對應我們的右 子樹。知道我們的左子樹的大小，我們很容易地得到 片preorder。

現在，當我們有一棵樹，做後序遍歷很簡單：

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

似乎工作。