es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Encuentra el camino más largo en un árbol binario de búsqueda utilizando C.

18 Jul, 2023 Programación

Estoy teniendo problemas para encontrar el código para encontrar el camino más largo de un árbol binario de búsqueda utilizando una función recursiva.

void maxDepth(bst_node *node)
{
    ....
}

El bst_node es un nodo del árbol binario de búsqueda.

La condición para salir de la recursión es muy simple:

if(node->leftChild==NULL && node->rightChild==NULL)
{
    return;
}

Antes de entrar en la recursión, imprime el valor del nodo:

printf("%d ",node->value);

Si, por ejemplo, un nodo en la profundidad x tiene solo un hijo izquierdo, entonces el camino más largo pasa por el hijo izquierdo del nodo y, utilizando la recursión, podemos escribirlo de la siguiente manera:

if(node->rightChld==NULL)
{
    maxDepth(node->leftChild);
}

Si un nodo en la profundidad x tiene solo un hijo derecho, entonces el camino más largo pasa por el hijo derecho del nodo y, utilizando la recursión, podemos escribirlo de la siguiente manera:

if(node->leftChild==NULL)
{
    maxDepth(node->rightChild);
}

Pero, ¿qué sucede si el nodo tiene tanto un hijo izquierdo como un hijo derecho? No puedo entender cómo puedo hacer esto.

Por ejemplo, con este árbol de búsqueda binario, la salida debería ser:

Binary Search Tree

“11 13 57 25 17”

Se agradece la ayuda.

Tags:  , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para encontrar el camino más largo de un árbol binario de búsqueda utilizando una función recursiva, puedes modificar la función maxDepth de la siguiente manera:

    int maxDepth(bst_node *node)
{
    if (node == NULL) {
        return 0;
    }

    int leftDepth = maxDepth(node->leftChild);
    int rightDepth = maxDepth(node->rightChild);

    // encuentra la longitud máxima entre el subárbol izquierdo y derecho
    int maxSubtree = (leftDepth > rightDepth) ? leftDepth : rightDepth;

    // calcula la longitud máxima incluyendo el nodo actual
    int maxLength = maxSubtree + 1;

    // imprime el valor del nodo
    printf("%d ", node->value);

    return maxLength;
}

    La función maxDepth ahora devuelve la longitud máxima del camino que comienza desde el nodo actual. Se llama recursivamente a sí misma en los subárboles izquierdo y derecho y encuentra la longitud máxima entre ellos. La longitud máxima incluyendo el nodo actual se calcula sumando 1 a la longitud máxima del subárbol. Finalmente, se imprime el valor del nodo antes de devolver la longitud máxima.

    Para usar la función maxDepth e imprimir el camino más largo, puedes llamarla en el nodo raíz y ignorar su valor de retorno:

    bst_node *root = createBinarySearchTree();
printf("Camino más largo: ");
maxDepth(root);

    Esto imprimirá el camino más largo del árbol binario de búsqueda desde el nodo raíz hasta el nodo hoja con la máxima profundidad. Por ejemplo, para el árbol binario de búsqueda en la pregunta, la salida será:

    Camino más largo: 11 13 57 25 17

Comments are closed.