Как получить уровень каждого узла из дерева, показанного в словаре?

Question

У меня есть древовидная структура данных, представленная в списке следующим образом:

Dictionary<int, List<int>> // Key, list of children

Data(1) = { 2 } // root
Data(2) = { 3 }
Data(3) = { 4, 5 }
Data(4) = { 5 }
Data(5) = {   } // leaf

Интересно, не могли бы вы помочь мне в создании словаря Предметов и уровней:

Dictioanry<ItemID, Level>

Answer 1

Если вы использовали этот класс узла , вы можете просто сделать это:

nodes.All.ToDictionary(n => n.Value, n => n.Level);

Вам нужно заполнить дерево немного по-другому (см. Информацию в ссылке)

Answer 2

Не уверен, что это лучшее решение, но должно работать:

        var data = new Dictionary<int, List<int>>();
        data[1] = new List<int> { 2 };
        data[2] = new List<int> { 3 };
        data[3] = new List<int> { 4, 5 };
        data[4] = null;
        data[5] = new List<int> { 6, 7 };
        data[6] = new List<int> { 8 };
        data[7] = null;
        data[8] = null;

        var allparents = new Dictionary<int, int>(data.Count);

        foreach (var node in data) {
            if (node.Value != null) {
                foreach (var child in node.Value) {
                    allparents[child] = node.Key;
                }
            }
        }

        int root = data.Keys.Except(allparents.Keys).First();
        int maxdepth = 1;
        foreach (int child in allparents.Keys) {
            int depth = 1;
            int parent = child;
            while (parent != root) {
                ++depth;
                parent = allparents[parent];
            }
            if (depth > maxdepth) {
                maxdepth = depth;
            }
        }
        Console.WriteLine(maxdepth);