Построение дерева с использованием списка объектов

Question

У меня есть список объектов с идентификатором свойства и 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, вы получаете большую гибкость и простоту сортировки, добавления, удаления, сохранения в БД и т. Д.

Вам действительно нужна функция 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) в модели представления