我有边，我想用它建一棵树。
问题是，我只能在边按特定顺序排列的情况下构造树结构。
订单示例：
(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
因此，树中必须始终存在父节点用于新添加的顶点。
问题是如何对输入边进行排序。语音告诉我拓扑类型，但它是为顶点。能把它分类吗？
最佳答案
@谢谢你指出我的方法的优化，你有更好的吗？
我将把下面的算法作为参考
最初构造一个散列映射来存储树中的元素：H，添加根（在您的情况下为空/或任何表示该根的元素）
带着一对（孩子，父母）
循环浏览整个列表。
在名单上。（每对都是元素）
对于每一对，查看哈希映射H中是否存在子节点和父节点，如果找不到，则为缺少的子节点创建树节点并将它们添加到H中，然后将它们与父子关系链接起来。
迭代结束时，您将留下树。
复杂性是O（n）。
关于algorithm - 从边缘建立树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11741825/