我的边缘，我想用它构建树。

I have the edges and i want to build a tree with it.

现在的问题是，我可以建立我的树形结构，只有当边是特定的顺序。  订单的示例：

The problem is that i can construct my tree structure only when edges are in specific order. Example of orders:

(vertex, parent_vertex)

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

我重复抛出的边缘和当前顶点试图找到它的父在创建树，然后我构建节点，然后将其插入。

I iterate throw the edges and for current vertex trying to find it's parent in created tree, then i construct the node and insert it.

result tree:

0 - 1 - 2 - 3

所以总是必须存在一个家长树为新增加的顶点。 现在的问题是如何将输入的边缘进行排序。声音告诉我关于拓扑排序，但它的顶点。是否有可能进行排序是正确的？

So there is always must exist a parent in the tree for the new added vertex. The question is how to sort the input edges. Voices tells me about the topological sort, but it's for vertexes. Is it possible to sort it right?

推荐答案

@mirt感谢您指出我的方法的优化，你有什么更好的？ 我会把下面的算法中的参考文献

@mirt thanks for pointing out the optimizations on my approach, have you got any better? i will put the below algo for ref

首先构造一个哈希映射存储元件是否有树：H加根（空你的情况/或任何重新present该根）

initially construct a hash map to store elements that are there in tree : H, add the root (null in your case/ or anything that represent that root)

取对（_child，_parent）

taking the pair (_child, _parent)

在整个列表循环。 在列表中。 （每对是元素） 对于每一对，看是否_child和_parent有没有在哈希表H，如果你不找，创建树节点，缺少的，并将它们添加到H，并与父子关系将它们链接。 您将留下在迭代结束的树。 loop through the whole list. in the list. (each pair is the element) for each pair, see if the _child and _parent is there in the hash map H, if you dont find, create the tree node for the missing ones and add them to H , and link them with the parent child relationship. you will be left with the tree at the end of iteration.

复杂度为O（n）。