algorithm - 有两个以上 child 的树的预序和中序

Question

我们知道一棵二叉树的给定前序和中序遍历唯一定义了这棵树，那么一般树，即有两个以上 child 的树，前序和中序遍历是否与树结构一一对应.

换句话说，给定一个一般树的元组(前序，中序)对于一般树来说是唯一的还是可以有许多树具有相同的前序和中序遍历元组？

Answer 1

非二叉树(没有左右子树)没有定义中序遍历(访问左子树，访问根，访问右子树)。

显然，预序并没有唯一地定义树。路径 A, B, C 与根 A 和 child B 和 C 的树没有区别>.

但是，前序和后序的组合唯一地定义了你的树(前提是所有节点都是唯一的)。我们可以通过归纳来证明这一点。显然，空字符串唯一地定义了一个空树。

现在，给定一个非空的前序和后序字符串，显然前序字符串中的第一个节点(和后序中的最后一个节点)是根 R 的树。我们现在需要做的就是识别以 R 的 child 为根的子树(以及相应的前序和后序字符串)，因为我们可以通过归纳假设找到它们的结构。

设 RAaaaaaBbbbbb 为前序字符串，aaaaaAbbbbbBR 为后序字符串(a 和 b是任意节点)。显然，A 是 R 的第一个 child 的根，因为它是前序字符串中的第一个后继者。在后序中，该子树以 A 结束(根据后序的定义)。我们截掉那部分，看到 R 的第二个 child 一定是 B。 R 不再有子节点，因为 B 是后序字符串中的最后一个节点。我们现在有两个较小的子问题:Aaaaaa、aaaaaA 和 Bbbbbb、bbbbbB。我们可以通过归纳假设来解决这些问题。