algorithm - 有两个以上孩子的树的前序和有序

Question

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

换句话说，给定一个通用树的元组 (preorder,inorder) 它对于通用树是唯一的，还是可以有许多树具有相同的 preorder 和 inorder 遍历元组？

Answer 1

对于非二叉树（没有左右子树）没有定义中序遍历（访问左子树、访问根、访问右子树）。

显然，预购并没有唯一地定义树。A, B, C路径与具有根A和子B的树之间没有区别C。

但是，预购和后购的组合唯一地定义了您的树（假设所有节点都是唯一的）。我们可以通过归纳来证明这一点。显然，空字符串唯一地定义了一个空树。

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

让RAaaaaaBbbbbb是前序字符串和aaaaaAbbbbbBR后序字符串（a并且b是任意节点）。显然，A是 的第一个孩子的根R，因为它是预排序字符串中的第一个后继。在后序中，该子树结束于A（根据后序的定义）。我们剪掉那部分，看到Rmust be的第二个孩子B。没有更多的子节点R，因为B是后序字符串中的最后一个节点。我们现在有两个较小的子问题：Aaaaaa,aaaaaA和Bbbbbb, bbbbbB。我们可以通过归纳假设来解决这些问题。

Answer 2

您可以简单地将您的一般树变成二叉树（通过查看此处），然后遍历它。