C – Cómo encontrar el número de nodos en una profundidad dada en un árbol N-ario?
Estoy tratando de encontrar el número total de nodos en una profundidad dada en un árbol N-ario, pero estoy atascado.
Esta es la estructura de datos:
typedef struct elem2 {
int value;
struct elem2 *firstChild;
struct elem2 *sibling;
} NTree_node;
typedef NTree_node *NTree;
La siguiente función debería recorrer el árbol de manera recursiva y devolver un entero no negativo:
int NTree<em>depth</em>nodes(NTree T, int depth) {
if (T == NULL) {
/* árbol vacío -> la profundidad es 0 */
return 0;
}
if (depth == 0) {
/* profundidad 0 significa que solo tenemos la raíz */
return 1;
}
int left = NTree<em>depth</em>nodes(T->firstChild, depth - 1);
int right = NTree<em>depth</em>nodes(T->sibling, depth - 1);
return 1 + (left + right);
}
Se ejecuta pero no devuelve la salida correcta ya que se basa en una función similar que funciona solo para árboles binarios.
¿Alguna pista sobre qué podría mejorar o cambiar? Creo que realmente no entiendo cuál podría ser el procedimiento correcto.
davy.ai
La implementación actual de la función solamente recorre los nodos hijos y hermanos del primer nivel, lo cual no es suficiente para un árbol N-ario. Para encontrar el número total de nodos en una profundidad dada en un árbol N-ario, necesitamos recorrer todos los hijos de cada nodo en la profundidad actual de forma recursiva.
Una posible solución podría ser modificar la función actual para incluir un bucle que recorra todos los hijos del nodo actual y llame a sí misma de forma recursiva para cada hijo, decrementando el valor de la profundidad en 1 en cada iteración. La función también debería mantener un contador que incremente cada vez que llegue a un nodo en la profundidad deseada.
Aquí tienes una implementación modificada de la función:
En esta implementación, utilizamos un bucle while para iterar sobre todos los hijos del nodo actual, y para cada hijo, llamamos a la función de forma recursiva con un valor de profundidad decrementado. Sumamos los valores de retorno de cada hijo y devolvemos la suma como resultado final. La implementación actual asume que el parámetro de profundidad es un número no negativo, por lo que no necesitamos manejar valores negativos.
Esta implementación debería funcionar correctamente para un árbol N-ario de cualquier grado, siempre que el valor de entrada para la profundidad esté dentro del rango de profundidades válidas para el árbol.