¿Cómo atravieso un árbol sin usar la recursión?

Navega tus respuestas
14

Tengo un árbol de nodos de memoria muy grande y necesito atravesar el árbol. Pasando los valores devueltos de cada nodo hijo a su nodo padre. Esto debe hacerse hasta que todos los nodos tengan su burbuja de datos hasta el nodo raíz.

Traversal funciona así. 

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

Esto funciona bien, pero me preocupa que la pila de llamadas limite el tamaño del árbol de nodos.

¿Cómo se puede reescribir el código para que no se realicen llamadas recursivas a Execute ?

    
pregunta cgTag 30.01.2014 - 22:10

3 respuestas

4

Si tiene una estimación de la profundidad de su árbol de antemano, ¿quizás sea suficiente para su caso adaptar el tamaño de la pila? En C # desde la versión 2.0, esto es posible siempre que inicie un nuevo hilo, vea aquí:

enlace

De esa manera puedes mantener tu código recursivo, sin tener que implementar algo más complejo. Por supuesto, crear una solución no recursiva con su propia pila puede ser más eficiente en tiempo y memoria, pero estoy bastante seguro de que el código no será tan simple como lo es por ahora.

    
respondido por el Doc Brown 31.01.2014 - 08:39
20

Aquí hay una implementación de recorrido de árbol de propósito general que no usa la recursión: 

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

En tu caso, puedes llamarlo así: 

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

Use primero un Queue en lugar de un Stack para una respiración, en lugar de buscar primero la profundidad. Use un PriorityQueue para una mejor primera búsqueda.

    
respondido por el Servy 30.01.2014 - 22:43
-3

No puede atravesar una estructura de datos en la forma de un árbol sin usar la recursión. Si no usa los marcos de pila y las llamadas de función proporcionadas por su idioma, básicamente tiene que programar su propia pila de llamadas de función y función. y es poco probable que logre hacerlo dentro de el idioma de una manera más eficiente que los escritores del compilador en la máquina en la que se ejecutaría su programa.

Por lo tanto, evitar la recursión por temor a toparse con los límites de recursos suele ser erróneo. Para estar seguro, la optimización prematura de recursos es siempre mal orientada, pero en este caso es probable que incluso si mide y confirma que el uso de la memoria es el cuello de botella, probablemente no podrá mejorarlo sin Bajando al nivel del escritor compilador.

    
respondido por el Kilian Foth 30.01.2014 - 22:41

Lea otras preguntas en las etiquetas

¿Pueden los objetos construidos a partir de la misma clase tener definiciones de método únicas? ¿Hay alguna razón para usar tamaños VARCHAR redondeados a un desplazamiento de 128/256/4096 bytes?