Como faço para percorrer uma árvore sem usar recursão?

14

Eu tenho uma grande árvore de nó na memória e preciso atravessar a árvore. Passando os valores retornados de cada nó filho para seu nó pai. Isso tem que ser feito até que todos os nós tenham seus dados enviados até o nó raiz.

Traversal funciona assim.

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

Isso funciona bem, mas estou preocupado que a pilha de chamadas limite o tamanho da árvore de nós.

Como o código pode ser reescrito para que nenhuma chamada recursiva para Execute seja feita?

    
por cgTag 30.01.2014 / 22:10
fonte

3 respostas

4

Se você tem uma estimativa da profundidade da sua árvore de antemão, talvez seja suficiente para o seu caso adaptar o tamanho da pilha? Em c # desde a versão 2.0, isso é possível sempre que você iniciar um novo thread, veja aqui:

link

Dessa forma, você pode manter seu código recursivo, sem precisar implementar algo mais complexo. É claro que criar uma solução não recursiva com sua própria pilha pode ser mais eficiente em termos de tempo e memória, mas tenho certeza de que o código não será tão simples quanto é por enquanto.

    
por 31.01.2014 / 08:39
fonte
21

Aqui está uma implementação de travessia de árvore de propósito geral que não usa recursão:

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

No seu caso, você pode ligar assim:

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

Use Queue em vez de Stack para uma primeira respiração, em vez de profundidade primeiro, pesquisar. Use um PriorityQueue para uma melhor primeira pesquisa.

    
por 30.01.2014 / 22:43
fonte
-3

Você não pode percorrer uma estrutura de dados na forma de uma árvore sem usar recursão - se você não usar os quadros de pilha e as chamadas de função fornecidas pelo seu idioma, basicamente terá que programar suas próprias chamadas de pilha e função, e é improvável que você consiga fazê-lo dentro da maneira mais eficiente que os autores do compilador na máquina em que seu programa rodaria.

Portanto, evitar a recursão por medo de encontrar limites de recursos geralmente é equivocado. Para ter certeza, a otimização prematura de recursos é sempre equivocada, mas neste caso é provável que mesmo se você medir e confirmar que o uso da memória é o gargalo, provavelmente você não conseguirá melhorá-lo sem caindo para o nível do compilador.

    
por 30.01.2014 / 22:41
fonte