2

我有优势，我想用它建一棵树。

问题是我只能在边缘处于特定顺序时才能构建我的树结构。订单示例：

(vertex, parent_vertex)

good:              bad:
(0,  ) <-top       (3, 2)
(1, 0)             (1, 0)
(2, 1)             (3, 2)
(3, 2)             (0,  ) <-top

我迭代抛出边缘和当前顶点试图在创建的树中找到它的父节点，然后我构造节点并插入它。

result tree:

0 - 1 - 2 - 3

因此，对于新添加的顶点，树中总是必须存在一个父节点。问题是如何对输入边进行排序。Voices 告诉我关于拓扑排序，但它是针对顶点的。是否可以正确排序？

4

1 回答 1

2

@mirt 感谢您指出我的方法的优化，您有更好的吗？我将把下面的算法作为参考

最初构造一个哈希映射来存储树中的元素：H，添加根（在您的情况下为空/或任何代表该根的东西）

取一对 (_child, _parent)

  1. 循环遍历整个列表。在列表中。（每一对都是元素）
  2. 对于每一对，查看哈希映射 H 中是否存在 _child 和 _parent，如果找不到，则为缺少的创建树节点并将它们添加到 H 中，并将它们与父子关系链接。
  3. 您将在迭代结束时留下树。

复杂度为 O(n)。

于 2012-08-08T09:25:44.767 回答