Asignar una profundidad a cada nodo

Question

He leído algunos otros artículos aquí que parecían similares, pero que no respondían del todo mi problema. Me han dado una pregunta para una tarea para asignar a cada nodo en un árbol binario su profundidad respectiva. Simplemente no puedo entenderlo.

de referencia, esta es mi código:

struct treeNode { 
    int item; 
    int depth; 
    treeNode *left; 
    treeNode *right; 
}; 
typedef treeNode *Tree; 

int assignDepth(Tree &T, int depth) 
{ 
    if(T!=NULL) 
    { 
     depth = assignDepth(T->left, depth++); 
     T->depth = depth; 
     depth = assignDepth(T->right, depth++); 
    } 
    else //leaf 
     return depth--; 
} 

Intenté funcionar a través de lápiz y papel y parecía que estaba bien, pero mi escritorio la verificación de conocimientos se carece de claridad.

¿Alguien puede indicarme la dirección correcta, por favor? Esta es la primera vez que uso árboles, y la recursividad no es mi punto fuerte.

Respuesta:

void treecoords(Tree &T, int depth) 
{ 
    static int count = -1; //set to -1 so the precrement before assignment doesn't give the wrong values 
    if(T!=NULL) 
    { 
     treecoords(T->left, depth+1); //depth decrements automatically once this function call is removed from the stack 
     count++; 
     T->x = count; 
      T->y = depth; 
     treecoords(T->right, depth+1); 
    } 
} 

Answer 1

Usted don' t necesidad

else //leaf 
    return depth--; 

También no desea incrementar la variable profundidad, sólo tiene que pasar la profundidad + 1 a la siguiente iteración.

Además, no es necesario devolver un valor.

Prueba esto:

void assignDepth(Tree T, int depth) 
{ 
    if(T!=NULL) 
    { 
     assignDepth(T->left, depth+1); 
     T->depth = depth; 
     assignDepth(T->right, depth+1); 
    } 
} 

Answer 2

Bueno, para empezar, que está utilizando post-incremento/decremento, es probable que significó ++depth/--depth para la asignación correcta y la otra de retorno;

Además, ¿por qué pasar un puntero como variable de referencia?

Answer 3

int assignDepth(Tree &T, int depth) 

Ha definido Tree como un puntero a una treeNode. No necesita pasarlo por referencia. Puede modificar el nodo que se apunta de todos modos.

{ 
    if(T!=NULL) 
    { 
     depth = assignDepth(T->left, depth++); 

El posfijo ++ asegura que estás pasando el original depth abajo. Eso no es lo que quieres. Incremente depth antes de esto, y olvídese de devolverlo como resultado de la función.

T->depth = depth; 

Esto está bien.

 depth = assignDepth(T->right, depth++); 

similares como para la llamada recursiva anterior, excepto que aquí no se debe modificar depth en absoluto, porque ya se ha incrementado.

} 
    else //leaf 
     return depth--; 

que no es necesario devolver cualquier información de profundidad (o es que un requisito no declarado?).

} 

Saludos & HTH.,

Answer 4

1. Una vez que haya llegado a un nodo hoja, que no se preocupan por su profundidad más, por lo que el valor de retorno parece no logran nada.

2. en dos estados:

   depth = assignDepth(T->left, depth++); 
   // and 
   depth = assignDepth(T->right, depth++); 
   

Usted tiene un comportamiento indefinido a partir de la modificación de depth dos veces sin un punto de secuencia intermedia (aunque parece que debe haber, hay no un punto de secuencia entre los lados derecho e izquierdo de una tarea).

Answer 5

1. ¿Por qué vuelves cuando el nodo es NULO? Según su especificación, no necesita devolver ninguna profundidad

2. En otro caso, solo necesita aumentar la profundidad y enviarla a la llamada a la función. Lo que sigue es mi versión del código

   vacío assignDepth (Árbol & T, int profundidad) { si (T == NULL) retorno; else { T-> profundidad = profundidad; if (T-> left! = NULL) assignDepth (T-> left, depth + 1); if (T-> right! = NULL) assignDepth (T-> right, depth + 1); }}

Answer 6

Tengo un diseño ligeramente más complicado con diferentes tipos de nodos y lo hizo, así que pensé acciones ID.

Si tiene un árbol que varía en tipo Nodo a Nodo (Binario, Unario, etc.), vale la pena simplificar el método tradicional para evitar que los desagradables IF incrustados comprueben el tipo de Nodos.

dos funciones:

• 1: Desde la raíz, se ejecutan a través de cada nodo y comprobar su distancia a la raíz llamando recursivamente en sí y la adición de 1 por cada padre. Dé a cada nodo una variable de profundidad para almacenar esto.
• 2: desde el conjunto completo de nodos en el árbol ejecute una comprobación MAX contra cada profundidad de nodos, el número más alto será igual a la profundidad del árbol.

El procesamiento de esta manera elimina la comprobación de tipos explícita y simplemente cuenta el Nodo sin importar si tiene uno, dos o cien hijos.

Espero que esto ayude a alguien!