從邊緣構建樹

Question

我有邊緣，我想用它構建一棵樹。

問題是我只能在邊緣按特定順序構建我的樹結構。訂單 例子：

(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 

因此，樹中總是必須存在父添加的頂點。 問題是如何對輸入邊進行排序。聲音告訴我關於拓撲排序，但它是針對頂點。是否有可能對它進行排序？

Answer 1

@mirt感謝您指出我的方法的優化，你有什麼更好的？ 我會把下面的算法中對裁判

初步構建一個哈希表來存儲在樹中存在的元素：H，添加根（空你的情況/或任何代表根）

回吐（_child，_parent）

1. 循環遍歷整個列表。 在列表中。 （每對都是元素）
2. 對於每一對，查看散列圖H中是否存在_child和_parent，如果沒有找到，爲缺少的節點創建樹節點並將它們添加到H，並將它們鏈接起來與父母的子女關係。
3. 你將在迭代結束時留下樹。

複雜度爲O（n）。