List<Node> organizations = new List<Node>(); //объявляем коллекции родительских и дочерних узлов List<Node> parentNodes = new List<Node>(); List<Node> childNodes = new List<Node>(); //в коллекцию родительских узлов добавляем корневой узел – это наша организация parentNodes.Add(rootNode); //цикл будет выполняться, пока не пуста коллекция родительских элементов while (parentNodes.Count > 0) { //проходим по родительским элементам foreach (Node parentNode in parentNodes) { //у каждого родителя проходим по дочерним элементам foreach (Node child in parentNode.Nodes) { childNodes.Add(child); } } //добавляем в итоговую коллекцию organizations.AddRange(childNodes); //в этом месте делаем хитрый обмен, теперь дочерние элементы становятся родительскими ListТаким образом, мы плавно, итеративно, уровень за уровнем спускаемся вниз. По возможности следует избегать использования рекурсии там, где в ней нет необходимости, так как её неосторожное применение может негативно сказаться на программе, например привести к переполнению стека.tempNodes = parentNodes; parentNodes = childNodes; childNodes = tempNodes; childNodes.Clear(); } //Теперь все организации содержатся в коллекции organizations.
четверг, 20 октября 2011 г.
Нерекурсивный обход дерева
Когда я был стажером, мой наставник показал мне, как можно обойтись без рекурсии при обходе дерева. У меня была задача, - получить список департаментов организации «X». В организации есть множество департаментов и подразделений с различным уровнем вложенности. Вместо того чтобы рекурсивно сделать обход дерева, он предложил следующее решение: использовать цикл While и две коллекции. Node – это класс, описывающий структуру организации: название, количество служащих, дочерние подразделения, которые также описываются классами Node и т.д.
Подписаться на:
Комментарии к сообщению (Atom)
А цель у доп. массивов и их обмена туда обратно ? Тут же достаточно счетчика обрабатываемой позиции, и добавления всех нод напрямую в organizations на каждом шаге.
ОтветитьУдалитьhttp://en.wikipedia.org/wiki/Breadth-first_search не?
ОтветитьУдалитьP.S. в шарпе есть Queue и Stack
Судя по всему цикл while выполнится один раз всего, так как
ОтветитьУдалитьparentNodes = childNodes;
childNodes.Clear();
приведет к тому, что parentNodes не будет содержать узлов.
Этот комментарий был удален автором.
ОтветитьУдалитьНемного не в тему, но хотелбы поделиться своим любимым способом префиксного обхода деревьев в стиле LINQ:
ОтветитьУдалитьstatic IEnumerable<TItem> TreeToInfixList(this TItem root, Func<TItem, IEnumerable<TItem>> getChildrenFunc)
{
yield return root;
foreach (var child in getChildrenFunc(root))
{
foreach (var subItem in TreeToInfixList(child, getChildrenFunc))
{
yield return subItem;
}
}
}
пример использования:
Есть класс вида
class ExampleTreeItem
{
public ExampleTreeItem()
{
this.Children = new List<ExampleTreeItem>();
}
public List<ExampleTreeItem> Children { get; set; }
public string Name { get; set; }
}
есть дерево, построенное из элементов такого класса
var tree = new ExampleTreeItem() {/*Заполняем дерево ...*/};
необходимо выбрать все элементы, с именем начинающимся на "Prefix string"
Решение:
IList<ExampleTreeItem> itemsStartedWithPrefixString = tree.TreeToInfixList(x => x.Children).Where(x => x.Name.StartsWith("Prefix string")).ToList();
Еще есть вариант функции TreeToInfixList для героиновых наркоманов (делает тоже самое, но запись в одну строчку):
ОтветитьУдалитьstatic IEnumerable<TItem> TreeToInfixList<TItem>(this TItem root, Func<TItem, IEnumerable<TItem>> getChildrenFunc)
{
return new[] {root}.Union(getChildrenFunc(root).SelectMany(x => TreeToInfixList(x, getChildrenFunc)));
}
danilka, не понял насчет счетчика. А цель - пройтись по уровням потомков. Обмениваются конечно же только ссылки, а не списки целиком.
ОтветитьУдалитьDarkWalker, примерно то =)
Мурадов Мурад, спасибо, поправил. Ошибка вкралась, когда код выдергивался из рабочего проекта...
Mavrinsky, согласен, с LINQ и рекурсией можно красиво обойти дерево!
"итератор" уже не подходит?
ОтветитьУдалитьВ примере как раз и показан итеративный обход.
ОтветитьУдалитьСпасибо большое за пример!
ОтветитьУдалить