由于我一直在学习LISP并阅读实用的常见Lisp,我发现了问题并试图解决它们,我陷入了这个特定问题,不确定如何处理它,所以需要一些帮助/建议。
我需要能够从其预序和序创建后序树
例如,如果给出以下内容:
预购: A B D E C F
序: D B E A C F
输出将是后序:D E B F C A
从我所看到的,inorder 的第一个元素始终是后序的第一个元素,所以我已经开始编写代码来反映这一点:
(defun tree-recovery (preorder inorder)
(let (root)
(setf root (first inorder))))
但我不确定从这里开始,任何帮助将不胜感激!谢谢
如果我们将函数命名为 tree-recovery
,让它恢复树而不是构建后序序列。(有人比我聪明需要解决问题而没有实际重建树(。
无序和后序以相同的元素开头,但该元素是非根:预序序列的第一个元素是根。
让我们恢复树,假设所有序列元素都是非零原子可比EQL
。我们将一片叶子表示为原子的值,其他节点作为(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)))
对于空树,我们返回 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)
似乎有效。