前，后和阶顺序化的哪些组合是唯一的？

Question

我们知道后订单，

post L(x)     => [x]
post N(x,l,r) => (post l) ++ (post r) ++ [x]

和预订

pre L(x)     => [x]
pre N(x,l,r) => [x] ++ (pre l) ++ (pre r)

和术中遍历。顺序化。

in L(x)     => [x]
in N(x,l,r) => (in l) ++ [x] ++ (in r)

即使我们假设成对不同的键/标签，也可以很容易地看到，即使我们假设唯一地描述了给定的树。

这三个组合可以用于该目的，哪些不能使用？

正面答案应包括（有效的）算法以重建树和证明（想法）为什么是正确的。负答案应提供反示例，即具有相同表示形式的不同树。

Answer 1

首先，我假设所有元素都是不同的。没有任何顺序化可以告诉您带有元素的树的形状 [3,3,3,3,3]. 。当然，可以重建一些具有重复元素的树木；我不知道有什么好的条件。

继续以负面的结果进行负面的结果，您不能仅从其预订单和后顺序化中充分重建二进制树。 [1,2] 预购， [2,1] 后订单必须 1 在根本上，但是 2 可以是左孩子或右孩子。如果您不关心这种歧义，则可以使用以下算法重建树：

• 令$ [x_1， dots，x_n] $为预购遍历，$ [y_n， ldots，y_1] $是后级遍历。我们必须有$ x_1 = y_1 $，这是树的根。
• $ x_2 $是根的最左边的孩子，$ y_2 $是最右边的孩子。如果$ x_2 = y_2 $，则root节点是一致的；重复$ [x_2， ldots，x_n] $和$ [y_n， ldots，y_2] $，以构建单个子树。
• 否则，令$ i $和$ j $为索引，例如$ x_2 = y_i $和$ y_2 = x_j $。 $ [x_2， ldots，x_ {j-1}] $是左子树的预订遍历，$ [x_j， ldots，x_n] $ the右子树的$ 。左子树具有$ j-2 = n-i+1 $元素，右子树具有$ i-2 = n-j+1 $元素。每个子树一次重复一次。
  顺便说一句，该方法将其推广到具有任意分支的树木。通过任意分支，找出左子树的范围，并从两个列表中切断其$ J-2 $元素，然后重复以从左侧切断第二个子树，依此类推。

如前所述，运行时间为$ o（n^2）$，带有$ theta（n^2）$最糟糕的情况（在有两个孩子的情况下，我们搜索每个列表nistery）。如果您将列表预处理到构建$ n ， mathrm {lg}（n）$有限的地图结构从元素值到位置，则可以将其转换为$ o（n ， mathrm {lg}（n））$在输入列表中。还使用数组或有限映射从索引到值；坚持全球索引，以便递归电话会收到整个地图，并以范围为论点来知道该采取什么行动。

使用预订的遍历$ [x_1， ldots，x_n] $和订购遍历$ [z_1， ldots，z_n] $，您可以如下重建树：

• 根是预订遍历$ x_1 $的头。
• 令$ k $为索引，以便$ z_k = x_1 $。然后$ [z_1， ldots，z_ {k-1}] $是左儿童的订购遍历，$ [z_ {k+1}， ldots，z_n] $是the正确的孩子。按照元素的数量，$ [x_2， ldots，x_k] $是左子女的预订遍历，$ [x_ {k+1}， ldots，x_n] $。反复构建左右子树。

同样，该算法是$ o（n^2）$，并且可以在$ o（n ， mathrm {lg}（n））（n））$中执行，如果将列表预先处理为有限映射，则从值到位置的有限映射。

后订单加上秩序当然是对称的。