Jak przemierzać drzewo bez korzystania z rekurencji?

Mam bardzo duże drzewo węzłów pamięci i muszę je przechodzić. Przekazywanie zwróconych wartości każdego węzła podrzędnego do ich węzła nadrzędnego. Należy to zrobić, dopóki wszystkie węzły nie będą miały bąbelków danych aż do węzła głównego.

Traversal działa w ten sposób.

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);
}

Działa to dobrze, ale martwię się, że stos wywołań ogranicza rozmiar drzewa węzłów.

Jak można przepisać kod, aby nie było wywołań rekurencyjnych Execute?

Oto implementacja przejścia drzewa ogólnego przeznaczenia, która nie korzysta z rekurencji:

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);
    }
}

W twoim przypadku możesz to tak nazwać:

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

Najpierw użyj Queuezamiast Stackoddechu zamiast głębokości. Użyj a, PriorityQueueaby uzyskać najlepsze pierwsze wyszukiwanie.

Jeśli masz wcześniej oszacowanie głębokości drzewa, może wystarczy, aby Twoja skrzynka dostosowała rozmiar stosu? W języku C # od wersji 2.0 jest to możliwe przy każdym uruchomieniu nowego wątku, patrz tutaj:

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

W ten sposób możesz zachować swój kod rekurencyjny, bez konieczności implementowania czegoś bardziej złożonego. Oczywiście, tworzenie nierekurencyjnego rozwiązania z własnym stosem może wymagać więcej czasu i pamięci, ale jestem prawie pewien, że kod nie będzie tak prosty jak na razie.

Nie można przechodzić przez strukturę danych w kształcie drzewa bez użycia rekurencji - jeśli nie używasz ramek stosu i wywołań funkcji dostarczonych przez Twój język, zasadniczo musisz zaprogramować własne wywołania stosu i funkcji, i jest to jest mało prawdopodobne, że uda ci się to zrobić w języku w bardziej efektywny sposób niż autorzy kompilatora na komputerze, na którym działałby twój program.

Dlatego unikanie rekurencji z obawy przed przekroczeniem limitów zasobów jest zwykle mylące. Oczywiście, przedwczesna optymalizacja zasobów jest zawsze mylona, ​​ale w tym przypadku prawdopodobne jest, że nawet jeśli zmierzysz i potwierdzisz, że użycie pamięci jest wąskim gardłem, prawdopodobnie nie będziesz w stanie poprawić jej bez zejścia do poziomu autor kompilatora.