Обход дерева объектов в C#
У меня есть дерево, состоящее из нескольких объектов, где каждый объект имеет имя (string), идентификатор (int) и, возможно, массив дочерних элементов одного типа. Как пройти по всему дереву и распечатать все идентификаторы и имена?
Я новичок в программировании и, честно говоря, у меня проблемы с осознанием этого, потому что я не знаю, сколько там уровней. Прямо сейчас я использую цикл foreach для получения родительских объектов непосредственно под корнем, но это означает, что я не могу получить дочерние объекты.
Ответы 2
Алгоритм, использующий рекурсию, выглядит следующим образом:
printNode(Node node)
{
printTitle(node.title)
foreach (Node child in node.children)
{
printNode(child); //<-- recursive
}
}
Вот версия, которая также отслеживает, насколько глубоко вложена рекурсия (т.е. печатаем ли мы дочерние элементы корня, внуков, правнуков и т. д.):
printRoot(Node node)
{
printNode(node, 0);
}
printNode(Node node, int level)
{
printTitle(node.title)
foreach (Node child in node.children)
{
printNode(child, level + 1); //<-- recursive
}
}
Что ж, вы всегда можете использовать рекурсию, но в сценарии программирования «реального мира» это может привести к плохим вещам, если вы не будете отслеживать глубину.
Вот пример, используемый для двоичного дерева: http://www.codeproject.com/KB/recipes/BinarySearchTree.aspx
Я бы использовал Google связанные списки и другие древовидные структуры, если вы новичок во всей структуре данных. Здесь можно получить массу знаний.
Не могли бы вы проиллюстрировать альтернативу использованию рекурсии (т.е. нерекурсивную версию моего примера псевдокода)?
Думаю, он был бы крупноватым и громоздким. Ваш пример определенно самый простой и легкий для понимания. Я просто пытался подчеркнуть, что рекурсия обычно плохая идея в производственной среде.
Если вы установите надлежащие проверки, чтобы убедиться, что он никогда не повторяется бесконечно, почему это плохая идея? Мы используем рекурсию в нескольких местах в нашей производственной среде, но ограничиваем уровень рекурсии.
Вам нужно как-то отслеживать контекст: поэтому, если вы не собираетесь рекурсивно (сохраняя контекст в стеке программы), вам нужно сохранить его в куче (возможно, используя локальную переменную типа Stack)? Я не уверен, почему вы говорите, что это «обычно плохая идея», если допустить какое-то дерево с разумной глубиной?
Если вы реализуете это, как упомянул Том Андерсон, отслеживая глубину и ограничивая ее, то с этим не будет никаких серьезных проблем. Однако для начинающего программиста довольно легко попасть в ситуацию переполнения стека.
Согласен с Томом Андерсоном. Я не понимаю, почему это плохая идея, если вы проверяете конечные условия, то есть «знаете, когда остановиться». Одно дело сказать «остерегайтесь бесконечной рекурсии», а другое - категорически заявить, что это обычно плохая идея для использования в сценариях программирования «реального мира».
@Alex: Круто. Все еще привыкаю к потоку здесь, в SO. :) Плюс нужно было обновить.
Да, я знаю .. комментарии то появляются, то исчезают, кажется: P
Я согласен. Упростите использование рекурсии.