有两个以上孩子的树的预订和顺序

我们知道一个二叉树的给定前序和中序遍历唯一地定义了树，那么一般树又如何，即具有两个以上子元素的树，前序和中序遍历与树结构有一对一的对应关系。有两个以上孩子的树的预订和顺序

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

来源

2014-07-01 ABHISHEK

我相信这是[CS.SE]（http://cs.stackexchange.com）的问题。无论如何，你应该为非二叉树定义前序和有序遍历。 –

通过遍历一棵树的遍历我的意思是先深度遍历树并相应地打印节点。 – ABHISHEK

@ABHISHEK这没有任何意义。您可以用相同的方式描述预购遍历和后期遍历（预订DFS并在输入时打印，后续订单执行DFS并在退出时打印）。按顺序意味着您在左子树之后和右子树之前访问根目录。没有合理的方式将其推广到任意树。 –

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

来源

2014-07-01 05:58:57 Rsh

未针对非二叉树（没有左右子树）定义有序遍历（访问左侧子树，访问根，访问右侧子树）。

很明显，预订并不是唯一定义树。路径A, B, C与根目录A和子目录B和C之间没有区别。

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

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

设RAaaaaaBbbbbb为预订字符串，aaaaaAbbbbbBR后序字符串（a和b为任意节点）。显然，A是R的第一个孩子的根，因为它是预订字符串中的第一个后继者。在后期订单中，该子树结束于A（按定义后的订单）。我们切断了那部分，看到R的第二个孩子必须是B。由于B是后序字符串中的最后一个节点，因此不再有R的子项。我们现在有两个较小的子问题：,aaaaaA和Bbbbbb, bbbbbB。我们可以通过归纳假设来解决这些问题。

来源

2014-07-01 05:59:04

有两个以上孩子的树的预订和顺序

回答

相关问题