使用对象列表构建树形结构

Question

我有一个对象列表，其中包含id和parent_id属性。
我希望构建一棵树来连接这些子父关系。
一个父类可能有多个子类，并且有一个对象将是所有对象的祖先。
最快的算法是什么？
我使用C#作为编程语言，但其他语言也可以。

- Billy

---

父母节点在列表中排在子节点之前吗？ - Bart van Heukelom

我很愿意研究一下。不过我并没有真正接触过树结构。 - Muhammad Maqsoodur Rehman

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类型，并且对于根节点为null）

注：Nullable是指可以为null的int类型。

- Thomas Levesque

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]);
}

- dtb

Answer 3

我更喜欢这种结构。通过维护一个单一的项目列表（您可能希望使用字典或类似的东西来提高速度），并将其传递到GetChildItems函数中，您可以获得更大的灵活性和易于排序、添加、删除、保存到数据库等操作。

只有在呈现列表到视图并且您想要树形结构以便于编辑时，您才真正需要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)。

- Ewan