Создайте список типов дерева путем рекурсивного проверки отношений родитель-ребенок С#

У меня есть один класс, который имеет свой список, поэтому его можно представить в древовидной структуре.

Я вынимаю плоский список этих классов и хочу его развязать.

public class Group
{
     public int ID {get;set;}

     public int? ParentID {get;set;}

     public List<Group> Children {get;set;}

}

Я хочу иметь возможность сделать следующее

List<Group> flatList = GetFlatList() //I CAN ALREADY DO THIS
List<Group> tree = BuildTree(flatList);

ParentID связан с свойством ID в его родительской группе, если это не было очевидно.

ИЗМЕНИТЬ

Существует некоторая путаница в том, почему я возвращаю список, а не один объект.

Я создаю элемент пользовательского интерфейса, который имеет список элементов, каждый из которых имеет дочерний элемент. Таким образом, в исходном списке нет корня node. Кажется, все решения пока не работают.

Это означает, что мне по существу нужен список структур типа дерева с использованием класса Group.

Ответы

Ответ 1

Я понятия не имею, почему вы хотите вернуть метод BuildTree List<Group> - дерево должно иметь root node, поэтому вы должны ожидать, что он вернет один элемент Group, а не список.

Я бы создал метод расширения на IEnumerable<Group>:

public static class GroupEnumerable
{
    public static IList<Group> BuildTree(this IEnumerable<Group> source)
    {
        var groups = source.GroupBy(i => i.ParentID);

        var roots = groups.FirstOrDefault(g => g.Key.HasValue == false).ToList();

        if (roots.Count > 0)
        {
            var dict = groups.Where(g => g.Key.HasValue).ToDictionary(g => g.Key.Value, g => g.ToList());
            for (int i = 0; i < roots.Count; i++)
                AddChildren(roots[i], dict);
        }

        return roots;
    }

    private static void AddChildren(Group node, IDictionary<int, List<Group>> source)
    {
        if (source.ContainsKey(node.ID))
        {
            node.Children = source[node.ID];
            for (int i = 0; i < node.Children.Count; i++)
                AddChildren(node.Children[i], source);
        }
        else
        {
            node.Children = new List<Group>();
        }
    }
}

Использование

var flatList = new List<Group>() {
    new Group() { ID = 1, ParentID = null },    // root node
    new Group() { ID = 2, ParentID = 1 },
    new Group() { ID = 3, ParentID = 1 },
    new Group() { ID = 4, ParentID = 3 },
    new Group() { ID = 5, ParentID = 4 },
    new Group() { ID = 6, ParentID = 4 }
};


var tree = flatList.BuildTree();

Ответ 2

Здесь вы можете сделать это в одной строке:

static void BuildTree(List<Group> items)
{
    items.ForEach(i => i.Children = items.Where(ch => ch.ParentID == i.ID).ToList());
}

Вы можете просто называть его следующим образом:

BuildTree(flatList);

Если в конце вы хотите получить узлы, родительский элемент которых является нулевым (то есть узлы верхнего уровня), вы можете просто сделать это:

static List<Group> BuildTree(List<Group> items)
{
    items.ForEach(i => i.Children = items.Where(ch => ch.ParentID == i.ID).ToList());
    return items.Where(i => i.ParentID == null).ToList();
}

И если вы хотите сделать его методом расширения, вы можете просто добавить this в подпись метода:

static List<Group> BuildTree(this List<Group> items)

Затем вы можете вызвать его так:

var roots = flatList.BuildTree();

Ответ 3

Я пробовал предлагаемые решения и выяснил, что они дают нам сложность O (n ^ 2).

В моем случае (у меня есть около 50 тыс. элементов, которые нужно встроить в дерево), это было совершенно неприемлемо.

Я пришел к следующему решению (предполагая, что каждый элемент имеет только один родительский элемент и все родители существуют в списке) со сложностью O (n * log (n)) [n раз getById, getById имеет O (log (n) ) сложность]:

static List<Item> BuildTreeAndReturnRootNodes(List<Item> flatItems)
{
    var byIdLookup = flatItems.ToLookup(i => i.Id);
    foreach (var item in flatItems)
    {
        if (item.ParentId != null)
        {
            var parent = byIdLookup[item.ParentId.Value].First();
            parent.Children.Add(item);
        }
    }
    return flatItems.Where(i => i.ParentId == null).ToList();
}

Полный фрагмент кода:

class Program
{
    static void Main(string[] args)
    {
        var flatItems = new List<Item>()
        {
            new Item(1),
            new Item(2),
            new Item(3, 1),
            new Item(4, 2),
            new Item(5, 4),
            new Item(6, 3),
            new Item(7, 5),
            new Item(8, 2),
            new Item(9, 3),
            new Item(10, 9),
        };
        var treeNodes = BuildTreeAndReturnRootNodes(flatItems);
        foreach (var n in treeNodes)
        {
            Console.WriteLine(n.Id + " number of children: " + n.Children.Count);
        }
    }
    // Here is the method
    static List<Item> BuildTreeAndReturnRootNodes(List<Item> flatItems)
    {
        var byIdLookup = flatItems.ToLookup(i => i.Id);
        foreach (var item in flatItems)
        {
            if (item.ParentId != null)
            {
                var parent = byIdLookup[item.ParentId.Value].First();
                parent.Children.Add(item);
            }
        }
        return flatItems.Where(i => i.ParentId == null).ToList();
    }
    class Item
    {
        public readonly int Id;
        public readonly int? ParentId;

        public Item(int id, int? parent = null)
        {
            Id = id;
            ParentId = parent;
        }
        public readonly List<Item> Children = new List<Item>();
    }
}