从邻接列表创建树的最有效方法

我有一个对象的邻接列表（从SQL数据库加载的行，带有密钥和它的父键），我需要用它来构建无序树。 它保证没有周期。

这花费的时间太长了（在大约5分钟内仅处理了870K节点中的〜3K）。 在我的工作站Core 2 Duo上运行，有足够的RAM。

关于如何加快速度的任何想法？

public class StampHierarchy { private StampNode _root; private SortedList _keyNodeIndex; // takes a list of nodes and builds a tree // starting at _root private void BuildHierarchy(List nodes) { Stack processor = new Stack(); _keyNodeIndex = new SortedList(nodes.Count); // find the root _root = nodes.Find(n => n.Parent == 0); // find children... processor.Push(_root); while (processor.Count != 0) { StampNode current = processor.Pop(); // keep a direct link to the node via the key _keyNodeIndex.Add(current.Key, current); // add children current.Children.AddRange(nodes.Where(n => n.Parent == current.Key)); // queue the children foreach (StampNode child in current.Children) { processor.Push(child); nodes.Remove(child); // thought this might help the Where above } } } } public class StampNode { // properties: int Key, int Parent, string Name, List Children } 

Answer 1

1. 将节点放入排序列表或字典中。

2. 扫描该列表，选取每个节点，在同一列表中找到其父节点（二进制搜索或字典查找），将其添加到父节点的Children集合中。

没有必要将Stack放入树中。

Answer 2

SortedList不是在此上下文中使用的好容器。 对于插入操作（重复调用Add（）），它是O（n），因为它在内部表示为平面列表。 使用Dictionary而不是SortedList将是一个很大的改进，因为它是O（1）摊销的插入时间。