Как пройти по дереву без использования рекурсии?

19

У меня очень большое в памяти дерево узлов и мне нужно пройти по дереву. Передача возвращенных значений каждого дочернего узла их родительскому узлу. Это должно быть сделано до тех пор, пока все узлы не получат свои пузырьки данных до корневого узла.

Обход работает так.

private Data Execute(Node pNode)
{
    Data[] values = new Data[pNode.Children.Count];
    for(int i=0; i < pNode.Children.Count; i++)
    {
        values[i] = Execute(pNode.Children[i]);  // recursive
    }
    return pNode.Process(values);
}

public void Start(Node pRoot)
{
    Data result = Execute(pRoot);
}

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

Как можно переписать код, чтобы не было рекурсивных вызовов Execute?

Reactgular
источник
8
Вы должны будете либо поддерживать свой собственный стек, чтобы отслеживать узлы, либо изменить форму дерева. См. Stackoverflow.com/q/5496464 и stackoverflow.com/q/4581576
Роберт Харви
1
Я также нашел много помощи в этом поиске Google , особенно Morris Traversal .
Роберт Харви
@RobertHarvey спасибо Роб, я не был уверен, на каких условиях это пойдет.
Reactgular
2
Вы можете быть удивлены требованиями к памяти, если вы сделали математику. Например, для идеально сбалансированного бинарного дерева teranode требуется стек всего 40 записей.
Карл Билефельдт
@KarlBielefeldt Это предполагает, что дерево идеально сбалансировано, хотя. Иногда вам нужно моделировать деревья, которые не сбалансированы, и в этом случае очень легко взорвать стек.
Servy

Ответы:

27

Вот реализация общего обхода дерева, которая не использует рекурсию:

public static IEnumerable<T> Traverse<T>(T item, Func<T, IEnumerable<T>> childSelector)
{
    var stack = new Stack<T>();
    stack.Push(item);
    while (stack.Any())
    {
        var next = stack.Pop();
        yield return next;
        foreach (var child in childSelector(next))
            stack.Push(child);
    }
}

В вашем случае вы можете назвать это так:

IEnumerable<Node> allNodes = Traverse(pRoot, node => node.Children);

Сначала используйте Queueвместо a Stackпоиск в дыхании, а не в глубину. Используйте PriorityQueueдля лучшего первого поиска.

Servy
источник
Правильно ли я думаю, что это просто сведет дерево в коллекцию?
Reactgular
1
@ MathewFoscarini Да, это его цель. Конечно, это не обязательно должно быть материализовано в фактическую коллекцию. Это просто последовательность. Вы можете выполнять итерации по нему для потоковой передачи данных без необходимости извлечения всего набора данных в память.
Servy
Я не думаю, что это решает проблему.
Reactgular
4
Он не просто просматривает график, выполняя независимые операции, такие как поиск, он собирает данные из дочерних узлов. Уплощение дерева уничтожает информацию о структуре, которая ему необходима для выполнения агрегации.
Карл Билефельдт
1
К вашему сведению, это правильный ответ, который ищут большинство людей, которые ищут этот вопрос. +1
Андерс Арпи
4

Если у вас есть предварительная оценка глубины вашего дерева, может быть, для вашего случая достаточно адаптировать размер стека? В C # начиная с версии 2.0 это возможно, когда вы начинаете новый поток, смотрите здесь:

http://www.atalasoft.com/cs/blogs/rickm/archive/2008/04/22/increasing-the-size-of-your-stack-net-memory-management-part-3.aspx

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

Док Браун
источник
Я только что сделал быстрый тест. На моей машине я мог сделать 14000 рекурсивных вызовов до достижения stackoverflow. Если дерево сбалансировано, нужно всего 32 вызова для хранения 4 миллиардов узлов. Если каждый узел составляет 1 байт (что не будет), то для хранения сбалансированного дерева высотой 32 потребуется 4 ГБ ОЗУ.
Эсбен Сков Педерсен,
Я должен был использовать все 14000 вызовов в стеке. Дерево будет занимать 2,6x10 ^ 4214 байт, если каждый узел имеет один байт (что не будет)
Эсбен Сков Педерсен
-3

Вы не можете просмотреть структуру данных в форме дерева без использования рекурсии - если вы не используете стековые фреймы и вызовы функций, предоставляемые вашим языком, вам, в основном, нужно программировать свой собственный стек и вызовы функций, и это маловероятно, что вам удастся сделать это в языке более эффективным способом, чем разработчики компилятора на компьютере, на котором будет работать ваша программа.

Поэтому избегание рекурсии из-за боязни ограничить ресурсы обычно ошибочно. Конечно, преждевременная оптимизация ресурсов всегда ошибочна, но в этом случае вполне вероятно, что даже если вы измеряете и подтверждаете, что использование памяти является узким местом, вы, вероятно, не сможете улучшить ее, не опустившись до уровня автор компилятора.

Килиан Фот
источник
2
Это просто ложь. Скорее всего, можно обойти дерево без использования рекурсии. Это даже не сложно . Вы также можете сделать это более эффективно, довольно тривиально, поскольку вы можете включать в явный стек только столько информации, сколько вам нужно для конкретного обхода, тогда как при использовании рекурсии вы в конечном итоге сохраняете больше информации, чем вам на самом деле нужно во многих случаев.
Servy
2
Это противоречие возникает время от времени здесь. Некоторые авторы считают, что сворачивание собственного стека не является рекурсией, в то время как другие отмечают, что они просто делают то же самое явно, что в противном случае среда выполнения сделала бы неявно. Нет смысла спорить о таких определениях.
Килиан Фот
Как вы определяете рекурсию тогда? Я бы определил это как функцию, которая вызывает себя в своем собственном определении. Вы наверняка можете пройтись по дереву, даже не делая этого, как я продемонстрировал в своем ответе.
Servy
2
Разве я злюсь от того, что наслаждаюсь актом нажатия на голосование против кого-то с таким высоким показателем? Это такое редкое удовольствие на этом сайте.
Reactgular
2
Давай @Mat, это детские вещи. Вы можете не согласиться, например, если вы боитесь бомбить дерево, которое слишком глубоко, это разумная проблема. Вы можете просто так сказать.
Майк Данлавей