树的前序遍历和中序遍历（多于两个子节点的情况）

Question

我们知道，对于二叉树而言，给定的前序遍历和中序遍历能够唯一确定一棵树。那么对于拥有超过两个子节点的一般树而言，前序遍历和中序遍历是否也与树的结构具有一一对应的关系呢？

换句话说，对于一棵一般树的元组（前序遍历，中序遍历），它是否唯一对应一棵树，或者会存在多棵树拥有相同的前序遍历和中序遍历的元组？

- ABHISHEK

---

我认为这是一个CS.SE的问题。无论如何，您应该为非二叉树定义先序遍历和中序遍历。 - default locale

通过对一般树进行中序遍历，我指的是对树进行深度优先遍历，并相应地打印节点。 - ABHISHEK

@ABHISHEK 这没有任何意义。您可以以相同的方式描述先序遍历和后序遍历（先序遍历执行深度优先搜索并在进入节点时打印，后序遍历执行深度优先搜索并在退出节点时打印）。中序遍历意味着您在访问左子树和右子树之前访问根节点。没有逻辑方法将其推广到任意树。 - Vincent van der Weele

Answer 1

中序遍历（先访问左子树，再访问根节点，最后访问右子树）不能用于非二叉树（没有左子树和右子树）。显然，前序遍历不能唯一定义树。路径“A，B，C”和以A为根、B和C为子节点的树之间没有区别。然而，前序遍历和后序遍历的组合可以唯一定义树（假设所有节点都是唯一的）。我们可以通过归纳法来证明这一点。显然，空字符串可以唯一定义一个空树。现在，给定一个非空的前序遍历和后序遍历字符串，很明显，前序字符串中的第一个节点（后序字符串中的最后一个节点）是树的根节点R。现在我们需要做的就是识别根节点R的子节点所在的子树（以及相应的前序遍历和后序遍历字符串），因为我们可以通过归纳假设找到它们的结构。设RAaaaaaBbbbbb是前序字符串，aaaaaAbbbbbBR是后序字符串（a和b是任意节点）。显然，A是R的第一个子节点的根节点，因为它是前序字符串中的第一个后继节点。在后序遍历中，该子树以A结束（按照后序遍历的定义）。我们切掉该部分并发现R的第二个子节点必须是B。因为B是后序字符串中的最后一个节点，所以没有更多的子节点。现在我们有两个较小的子问题：Aaaaaa、aaaaaA和Bbbbbb、bbbbbB。我们可以通过归纳假设来解决它们。

- Vincent van der Weele

Answer 2

你可以将普通树简单地转换成二叉树（参考这里），然后对其进行遍历。

- Rsh