UPDATE
Эта проблема на самом деле оказалась значительно более сложной, чем я первоначально предполагал, учитывая требование повторения всего дерева для каждого пути. Я просто удалил старый код, потому что больше не хочу путать.
Я хочу сохранить это в записи, что использование рекурсивной структуры данных делает это проще:
public class MyRecursiveObject
{
public MyRecursiveObject Parent { get; set; }
public string Name { get; set; }
public List<MyRecursiveObject> Children { get; set; }
}
Вы очень ясно увидите , почему это проще после прочтения кода ниже:
private void PopulateTree(IEnumerable<MyObject> items)
{
var groupedItems =
from i in items
group i by i.Parent into g
select new { Name = g.Key, Children = g.Select(c => c.Child) };
var lookup = groupedItems.ToDictionary(i => i.Name, i => i.Children);
foreach (string parent in lookup.Keys)
{
if (lookup.ContainsKey(parent))
AddToTree(lookup, Enumerable.Empty<string>(), parent);
}
}
private void AddToTree(Dictionary<string, IEnumerable<string>> lookup,
IEnumerable<string> path, string name)
{
IEnumerable<string> children;
if (lookup.TryGetValue(name, out children))
{
IEnumerable<string> newPath = path.Concat(new string[] { name });
foreach (string child in children)
AddToTree(lookup, newPath, child);
}
else
{
TreeNode parentNode = null;
foreach (string item in path)
parentNode = AddTreeNode(parentNode, item);
AddTreeNode(parentNode, name);
}
}
private TreeNode AddTreeNode(TreeNode parent, string name)
{
TreeNode node = new TreeNode(name);
if (parent != null)
parent.Nodes.Add(node);
else
treeView1.Nodes.Add(node);
return node;
}
Прежде всего, я понял, что словарь будет содержать ключи для промежуточных узлов, а также только корневые узлы, поэтому нам не нужны два рекурсивных вызова в рекурсивном методе AddToTree, чтобы получить «B» узлы как корни; первоначальная прогулка в методе PopulateTree уже делает это.
Что нам нужно сделать , чтобы защититься от этого, это добавить листовые узлы в начальной прогулке; используя рассматриваемую структуру данных, их можно обнаружить, проверяя, есть ли ключ в родительском словаре. С рекурсивной структурой данных это было бы намного проще: просто проверьте Parent == null. Но рекурсивная структура - это не то, что у нас есть, поэтому мы должны использовать приведенный выше код.
AddTreeNode - это в основном служебный метод, поэтому нам не нужно повторять эту логику проверки на нуль позже.
Настоящее уродство - во втором, рекурсивном AddToTree методе. Поскольку мы пытаемся создать уникальную копию каждого отдельного поддерева, мы не можем просто добавить узел дерева и затем выполнить рекурсию с этим узлом в качестве родительского. У «A» здесь только один ребенок, «B», но у «B» есть два ребенка, «C» и «D». Должно быть две копии «A», но нет никакого способа узнать об этом, когда «A» первоначально передается методу AddToTree.
Итак, что мы на самом деле должны сделать, это не создавать каких-либо узлов до финальной стадии и сохранять временный путь, для которого я выбрал IEnumerable<string>, потому что он неизменен и, следовательно, невозможно испортить , Когда нужно добавить еще детей, этот метод просто добавляет путь и рекурсоры; когда дочерних элементов больше нет, он проходит по всему сохраненному пути и добавляет узел для каждого.
Это крайне неэффективно, потому что теперь мы создаем новый перечислимый при каждом вызове AddToTree. Для большого количества узлов, это может занять много памяти. Это работает, но это было бы намного эффективнее с рекурсивной структурой данных. Используя пример структуры в верхней части, вам вообще не придется сохранять путь или создавать словарь; когда не осталось детей, просто пройдите по пути в цикле while, используя ссылку Parent.
Во всяком случае, я думаю, что это академично, потому что это не рекурсивный объект, но я подумал, что в любом случае стоило указать на то, что следует иметь в виду для будущих проектов. Код выше будет давать именно те результаты, которые вы хотите, я пошел дальше и протестировал его на реальном TreeView.
UPDATE 2 - Получается, что приведенная выше версия довольно жестока по отношению к памяти / стеку, скорее всего, в результате создания всех этих IEnumerable<string> экземпляров. Хотя это не очень хороший дизайн, мы можем устранить эту конкретную проблему, изменив переменную List<string>. Следующий фрагмент демонстрирует различия:
private void PopulateTree(IEnumerable<MyObject> items)
{
// Snip lookup-generation code - same as before ...
List<string> path = new List<string>();
foreach (string parent in lookup.Keys)
{
if (lookup.ContainsKey(parent))
AddToTree(lookup, path, parent);
}
}
private void AddToTree(Dictionary<string, IEnumerable<string>> lookup,
IEnumerable<string> path, string name)
{
IEnumerable<string> children;
if (lookup.TryGetValue(name, out children))
{
path.Add(name);
foreach (string child in children)
AddToTree(lookup, newPath, child);
path.Remove(name);
}
// Snip "else" block - again, this part is the same as before ...
}