4

如果只给出后序列表，我如何找到树的预订列表，反之亦然。此外，在树中，每个非叶节点都有两个子节点（即每个节点有两个或零个子节点。）

编辑：另一个给定的假设是每个节点的标签是唯一的，并且有一个字段将其标识为内部节点或叶子。我认为这应该消除单个预购或后购能够唯一识别一棵树的歧义。

4

3 回答 3

7

如果不假设树中的节点具有将自己标识为内部或叶子的字段，您将无法为您的问题找到唯一答案。该假设或有序列表必须可用于找到唯一的树。在这种情况下，要找到一个可能的答案，您可以构建如下所示形式的树来匹配任何给定的后订购列表：（假设后订购列表为：1 2 3 4 5 6 7 8 9）

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

现在您可以使用这棵树进行预订。

假设树中的节点有一个将自己标识为内部或叶子的字段，我们可以使用以下算法从此类树的后排序列表中创建一个唯一的树：

  1. 从后序列表的开头扫一扫，找到第一个内部节点。该节点将恰好有两个叶子子节点，它们在后序列表中位于该节点之前。
  2. 在您的树结构中添加该内部节点并使列表中的两个前面的节点成为其子节点。
  3. 从列表中删除这两个子节点，并使该内部节点成为叶子。
  4. 转到步骤 1 并重复，直到列表变为空。
于 2009-08-02T21:40:27.253 回答
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。一般来说，树不能从一次遍历中重建。有关更详细的说明，请参阅此优秀资源。

不管关于 0 或 2 个孩子的规则如何，歧义仍然存在：

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

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

两者都有前序遍历 [4 2 1 3 5 6 7]

于 2009-08-02T21:31:11.987 回答
1

例如：您需要将后购形式转换为预购形式。这可以通过以下方式完成。后序：DEBFCA 前序：ABDECF 我们看到 A 是根。从preorder我们可以确定节点B留给A。因此我们创建了两个子类（BED）（CF）。现在当我们遍历B时，我们将其作为根，我们看到在B之后，D IS PRESENT ，这意味着 D 在 B 左侧，E 在 B 右侧。现在我们遍历 C。将其作为根。然后 F 出现在 C 之后，因此将其作为左侧。

于 2014-03-12T06:05:45.733 回答