Creating a tree using a list of objects

Question

I have a list of objects with property id and parent_id.
I want to build a tree to connect these children and parents.
1 parent can have several children, and there is an object that will be the ancestor of all objects.

What is the fastest algorithm to implement?
I use C # as a programming language, but other languages ​​are good too.

Answer 1

Something like this should do the trick:

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

(assuming ParentId is Nullable<int>and is null for root nodes)

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)