问题描述:Ocaml help tree traversal
R. Borist教授研究树木。他保留了所有他喜欢的树的前序,前序和后序遍历记录。然而,他的办公室发生的火灾摧毁了他存放顺序遍历的文件柜。他仍然有他所有最喜欢的树的前序和后序遍历,这是足够的信息来重建丢失的inorder遍历吗?
您必须为以下任务设计和实现一个程序:输入将由 两列数字组成。第一个列表是某棵树T的前序遍历。第二个列表是对同一棵树T的后序遍历。输出应该是T的序遍历。如果输入不确定唯一的树,则任何一致的inorder遍历可以退货。
如果它帮助设计你实现,你可以假设:
- 没有树有超过1000个节点。
- 没有树为多个节点使用相同的标签。
- 节点的标签是从0到10,000的数字。
的样本数据
Input:
2 6 7 1 11 8 5 10 3 4 9
7 8 5 11 10 1 6 4 9 3 2
Output:
7 6 8 11 5 1 10 2 4 3 9
提示
给出一个在树的前序后序&遍历,你可以推断出哪个元素是 根源在哪里?哪些元素必须来自左侧的子树?从正确的子树?递归。
首先解决树中的每个节点都保证有2个或者0个 孩子的问题。一些节点只有一个孩子的情况有点棘手。
注意
在你的书面记录,你并不需要分析解决方案的效率/运行时间(这将是未来项目的要求)。但是要分析它的正确性;即清楚地解释为什么你的算法是正确的。
问题我马上就要理解如何从前置和后置构建inorder遍历。我试图找出一些有5个和7个节点的小例子,就像提示一样,但没有看到这个模式。帮帮我!
UPDATE 所以我想我想出了如何想出另外两个列表的inorder遍历。我需要知道左子树右子树和根。根始终在帖子订单的末尾和预订的开始。左边的子树可以在这两个列表中找到,但是我认为从后序得到的结果更容易使它在前面。其次是右侧子树和根。在预定顺序中,左子树在根子之后,右子树。我只需要帮助把想法变成代码...
你可以使用ocaml中的索引提取特定元素吗?
我很难分辨在子树开始和结束,怎么可以拉出信息,并返回一个列表出了两
像我知道的X名单:: XS翻出第一要素了名单和这样的简单的事情......
任意一个帮助或可提供提示和建议我只考虑一个情况下,我有两个或没有节点作为孩子
更新:我没有用ocaml编写程序我可以使用任何我想要的语言。我熟悉java,所以我想在java中实现解决方案。
我有一个很好的了解如何获取所需信息的形式先和后顺序列表打造以让我觉得我解决了这个逻辑的一部分,但需要帮助把我的想法转换成Java代码任何一个可以帮助?
这似乎更像是一个逻辑难题而不是OCaml问题。关键是节点是唯一编号的。这个提示看起来相当不错:节点左子树的根从前序非常明显。一个节点的一个右子树的根从后序是相当明显的。但是,如果这些结果是同一个节点,这意味着什么?你可以继续递归获得整棵树(看起来像 - 我没有真正解决它!)。 – 2012-08-15 21:09:31