使用对象列表构建树

Question

我有一个包含属性id和parent_id的对象列表。
我想建立一棵树来连接这些孩子和父母。
1父母可能有几个孩子，并有一个对象将是所有对象的祖先。

什么是最快的算法来实现呢？
我使用C＃作为编程语言，但其他语言也可以。

Answer 1

类似的东西应该做的伎俩：

public List<Node> MakeTreeFromFlatList(IEnumerable<Node> flatList) 
{ 
    var dic = flatList.ToDictionary(n => n.Id, n => n); 
    var rootNodes = new List<Node>(); 
    foreach(var node in flatList) 
    { 
     if (node.ParentId.HasValue) 
     { 
      Node parent = dic[node.ParentId.Value]; 
      node.Parent = parent; 
      parent.Children.Add(node); 
     } 
     else 
     { 
      rootNodes.Add(node); 
     } 
    } 
    return rootNodes; 
} 

（假设的ParentId是Nullable<int>，并且是空的根节点）

Answer 2

你可以使用字典：

var dict = new Dictionary<Id, Node>(); 

foreach (var item in items) 
{ 
    dict[item.Id] = new Node(item); 
} 

foreach (var item in items) 
{ 
    dict[item.ParentId].AddChild(dict[item.Id]); 
} 

Answer 3

我更喜欢这种结构。通过维护一个列表（您可能希望使用字典或类似的速度）项目并将其传递到GetChildItems函数中，您可以更灵活地进行分类，添加，删除和保存到db等。

当您将列表渲染到视图时，您只需要GetChildItem函数，并且您希望树结构易于编辑，就像您说的那样。在这种情况下，你可以有完整的列表视图模型和传递到每一个项目视图

public class Item 
{ 
    public string Id { get; set; } 
    public string ParentId { get; set; } 

    public IEnumerable<Item> GetChildItems(List<Item> allItems) 
    { 
     return allItems.Where(i => i.Id == this.ParentId); 
    } 
} 

public class Tree 
{ 
    public List<Item> Items { get; set; } 

    public IEnumerable<Item> RootItems(List<Item> allItems) 
    { 
     return allItems.Where(i => i.ParentId == null); 
    } 
} 

注意的项目：上面的类结构设计模仿传统的复杂对象模式。这些天你可能会在视图模型中只有GetChildItems（List allItems，Item parentItem）