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

如果不假设树中的节点有一个字段将自己标识为内部或叶,您就无法为您的问题找到唯一的答案。该假设或无序列表必须可用,才能找到唯一的树。 在这种情况下,为了找到一个可能的答案,您可以构建一个如下所示的形式的树来匹配任何给定的Postorder列表:(假设Postorder列表是:1 2 3 4 5 6 7 8 9)

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

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

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

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

考虑预购遍历的递归结构:

T(r) = [r, T(r->left), T(r->right)]
where T(r) is the preorder traversal of tree rooted at node r

然后我们知道t(r)描述的树的根总是遍历中的第一个节点。

知道这一点,并且知道一个根在一个树中总是比它的子树高,那么考虑一下如何使用这些信息来重建树。递归地思考。

警告:只有当这是一个 二进制搜索树 ,它约束节点以便 left-child < root < right-child . 一般来说,树不能从单个遍历中重建。见 this excellent resource 更详细的解释。

无论0或2个子级的规则如何,仍存在歧义:

    4
   / \
  2   5
 / \ / \
 1 3 6 7

    4
   / \
  2   7
 / \
1   3
   / \
  5   6

两者都有预购遍历[4 2 1 3 5 6 7]

例如: 您需要将Postorder表单转换为Preorder表单。这可以通过以下方式完成。 邮购:DEBFCA 预购:ABDECF 我们看到A是根。从预排序我们可以确定节点B是左到A的,因此我们创建了两个子类,即(b e d)(c f)。现在,当我们遍历b时,我们把它作为根,我们看到,在b,d存在之后,它意味着d是左到b,e是右到b。现在,我们遍历c,把它作为根。然后f在c之后出现,所以它是左的。