将二叉树的预订列表转换为后序,反之亦然

Question

如果仅给出后序列表,我怎样才能找到树的预订列表,反之亦然.此外,在树中,每个非叶节点都有两个子节点(即每个节点有两个或零个子节点.)

编辑:另一个给定的假设是每个节点的标签是唯一的,并且有一个字段,将其标识为内部节点或叶子.我认为应该摆脱单个预订单或后序的模糊性能够唯一地识别树.

Answer 1

如果不假设树中的节点具有将其自身标识为内部或叶子的字段,则无法为您的问题找到唯一的答案.该假设或有序列表必须可用于查找唯一树.在这种情况下,要找到一个可能的答案,您可以构建一个下面显示的表格树,以匹配任何给定的后序列表:(假设后序列表为:1 2 3 4 5 6 7 8 9)

9[7[5[3[1,2],4],6],8]

现在,您可以使用此树进行预订列表.

假设树中的节点有一个标识为内部或叶子的字段,我们可以使用此算法从这种树的后序列表中创建一个唯一的树:

1. 从postorder列表的开头扫描并找到第一个内部节点.此节点将在后序列表中具有正好位于此节点之前的两个叶子节点.
2. 在您的树结构中添加该内部节点,并在列表中将两个前面的节点作为其子节点.
3. 从列表中删除这两个子节点,并使该内部节点成为叶子.
4. 转到步骤1并重复直到列表变空.