1

buen día. Estoy desarrollando un programa para resolver el siguiente problema.

Descripción

Alicia se sorprendió cuando vio al gato de Cheshire andando por las ramas de un árbol loco. Pero más se sorprendió cuando éste le dijo "Aquí todos estamos locos". "¿Cómo sabes que yo estoy loca?", le preguntó Alicia, a lo que el gato contestó "Debes estarlo, o no hubieras venido aquí". "¿Y cómo sabes que tú estás loco?", volvió a preguntar Alicia, a lo que el gato volvió a contestar "Debo estarlo, pues me gusta subir y bajar por las ramas de este árbol loco mientras hablo".

Alicia miró con cuidado el árbol loco y primero notó que el tronco se dividía en dos ramas y que cada rama también se dividía en dos ramas. Después notó que en los lugares de división había unas letras grabadas, todas distintas y guardando cierto orden. Finalmente, se dio cuenta que el gato subía y bajaba por las ramas mientras hablaba, caminando lo menos posible para llegar a cada letra que pronunciaba (pasando tal vez por otras letras en el camino).

Entrada

En el primer renglón, una cadena A formada por hasta 26 letras mayúsculas distintas. El árbol loco es el árbol binario de búsqueda que se construye insertando las letras de A en el orden dado. En el segundo renglón, una cadena G formada por hasta 1000 letras mayúsculas. Esta cadena es la pronunciada por el gato mientras habla. Puedes suponer que el gato sólo pronuncia letras que sí existen en el árbol loco.

Salida

La secuencia de movimientos del gato en el árbol, suponiendo que el gato inicia en la raíz del árbol. El gato puede subir a la izquierda (a una letra menor que la actual), subir a la derecha (a una letra mayor que la actual) o bajar por una rama que lo acerca a la raíz. Estos movimientos se representarán por las letras I, D y B, respectivamente.

Dado que estamos tratando con un árbol binario de búsqueda, que es una estructura de datos ordenada. Lo cuál implemente de mejor manera para poder resolver el problema:

  1. Definí la estructura de un árbol binario llamado "Node" conteniendo un valor "data", punteros a los hijos izquierdo "left" y derecho "right"
  2. Una función "insert" para insertar un valor en el árbol binario de búsqueda.
  3. Implemente una función search para buscar un valor en el árbol y determinar los movimientos necesarios para encontrarlos.

Con esto implementado me podría facilitar la búsqueda entre las letras pronunciadas por el gato, lo que me permite determinar los movimientos necesarios para encontrar cada letra del árbol.

El problema de mi programa son las salidas.

introducir la descripción de la imagen aquí

Mi salida:

introducir la descripción de la imagen aquí

Mi código es el siguiente:

#include <iostream>
#include <string>

using namespace std;

// Definición de la estructura de un nodo del árbol binario de búsqueda
struct Node {
    char data; // Valor del nodo (letra)
    Node* left; // Puntero al hijo izquierdo
    Node* right; // Puntero al hijo derecho
    Node(char _data) : data(_data), left(nullptr), right(nullptr) {} // Constructor para inicializar el nodo con un valor dado
};

// Función para insertar un valor en el árbol binario de búsqueda
void insert(Node*& root, char value) {
    if (root == nullptr) { // Si el árbol está vacío, crea un nuevo nodo
        root = new Node(value);
    } else if (value < root->data) { // Si el valor es menor que el valor del nodo actual, inserta en el subárbol izquierdo
        insert(root->left, value);
    } else { // Si el valor es mayor o igual que el valor del nodo actual, inserta en el subárbol derecho
        insert(root->right, value);
    }
}

// Función para buscar un valor en el árbol binario de búsqueda y determinar los movimientos del gato
string search(Node* root, char target) {
    string moves = ""; // Inicializa la cadena de movimientos como vacía
    while (root != nullptr && root->data != target) { // Mientras no se alcance el nodo objetivo
        if (target < root->data) { // Si el valor buscado es menor que el valor del nodo actual, sube por la izquierda
            moves += 'I';
            root = root->left;
        } else { // Si el valor buscado es mayor que el valor del nodo actual, sube por la derecha
            moves += 'D';
            root = root->right;
        }
        moves += 'B'; // Agrega el movimiento de "descenso hacia la raíz" después de cada búsqueda
    }
    return moves; // Devuelve la cadena de movimientos realizados
}

int main() {
    string A, G;
    cin >> A >> G; // Leer las cadenas A y G

    Node* root = nullptr; // Inicializar el puntero a la raíz del árbol como nulo

    // Construir el árbol binario de búsqueda a partir de la cadena A
    for (char c : A) {
        insert(root, c);
    }

    // Recorrer la cadena G pronunciada por el gato y obtener los movimientos
    for (char c : G) {
        cout << search(root, c) << endl; // Obtener los movimientos de búsqueda de la letra en el árbol
    }

    return 0;
}

¿Qué estoy implementando mal? ¿Mi lógica de búsqueda en la búsqueda de los nodos o en la generación de secuencia de los movimientos?

Les agradecería su ayuda, excelente día.

1 respuesta 1

1

El primer problema está en:

while (root != nullptr && root->data != target) { 
    if (target < root->data) {
        ...
    } else {
        ...
    }
    moves += 'B';  <<<<<<<<<<<<<<<<<<<<<<<<<<<<< 
 }

imprimes "B" siempre después de subir un nodo a la izquierda o la derecha. Por eso tu salida es

IBIBIBDB...
 ^ ^ ^ ^ 

Esto realmente es circunstancial, el problema real es otro:


No puedes recorrer tu árbol en dirección inversa, hacia abajo, solo con la referencia del nodo actual


Tus nodos no tienen ninguna referencia a su nodo raíz, si tu idea es intentar partir del nodo actual y buscar el camino al nodo de destino, eventualmente tendrás que bajar, pero no tienes forma de saber cual es el nodo raíz de un nodo dado, no si solo tienes la referencia de ese nodo.

De hecho en tu función de búsqueda cuando haces:

moves += 'B';

lo siguiente sería asignar a root su nodo raíz.

Tienes muchas formas de solucionar tu problema, la primera que se puede venir a la cabeza es agregar un nuevo campo a la estructura del nodo con una referencia a su raíz...

No obstante hay una solución muy simple sin modificar tu árbol. Teniendo en cuenta que siempre sabes el nodo actual en el que está el gato y el nodo al que debe ir a continuación, en cada desplazamiento:

  • Empiezas en la raíz y subes hasta encontrar el nodo en el que tienes que ir para un lado si quieres llegar al nodo donde está el gato actualmente y en dirección contraria para llegar al nodo de destino. Este es el nodo más bajo por el que el gato tiene que pasar para llegar al nuevo nodo.

  • Cuentas cuantos nodos hay desde este nodo de bifurcación hasta el que está el gato actualmente. Estas serán las bajadas necesarias.

  • Calculas el camino desde el nodo de bifurcación hasta el nodo de destino, básicamente como intentas hacer ahora en tu función de búsqueda, solo que ahora sabes seguro que no tienes que bajar.

  • Finalmente concatenas las bajadas con el camino Bifurcación -> Destino para obtener el camino completo.

Usando una implementación iterativa muy simple, podría ser algo así:

#include <iostream>
#include <string>


// Definición de la estructura de un nodo del árbol binario de búsqueda
struct Node {
    char data; // Valor del nodo (letra)
    Node* left; // Puntero al hijo izquierdo
    Node* right; // Puntero al hijo derecho
    Node(char _data) : data(_data), left(nullptr), right(nullptr) {} // Constructor para inicializar el nodo con un valor dado
};

// Función para insertar un valor en el árbol binario de búsqueda
void insert(Node*& root, char value) {
    if (root == nullptr) { // Si el árbol está vacío, crea un nuevo nodo
        root = new Node(value);
    } else if (value < root->data) { // Si el valor es menor que el valor del nodo actual, inserta en el subárbol izquierdo
        insert(root->left, value);
    } else { // Si el valor es mayor o igual que el valor del nodo actual, inserta en el subárbol derecho
        insert(root->right, value);
    }
}


std::string search(Node* root, char current_node, char target_node) {
    std::string path = "";

    // Llegar hasta el nodo de bifurcación
    while (true) {
        if (current_node > root->data && target_node > root->data) {
            root = root->right;
        } else if (current_node < root->data && target_node < root->data) {
            root = root->left;
        } else {
            break;
        }
    }
    
    Node* aux = root;
    // Bajadas necesarias desde el nodo actual al de bifurcación
    while (current_node != root->data) {
        root = current_node < root->data ? root->left : root->right;
        path += "B";
    }
    
    // Subidas desde el nodo de bifurcación al nodo de destino
    while (target_node != aux->data) {
        if (target_node > aux->data) {
            aux = aux->right;
            path += "D";
        } else {
            aux = aux->left;
            path += "I";
        }
    }
    
    return path;
}


int main() {
    std::string A, G;
    std::cin >> A >> G; // Leer las cadenas A y G

    Node* root = nullptr; // Inicializar el puntero a la raíz del árbol como nulo

    // Construir el árbol binario de búsqueda a partir de la cadena A
    for (char c : A) {
        insert(root, c);
    }

    // Recorrer la cadena G pronunciada por el gato y obtener los movimientos
    char current_node_c = root->data;
    for (char next_node_c : G) {
        std::cout << search(root, current_node_c, next_node_c); // Obtener los movimientos de búsqueda de la letra en el árbol
        current_node_c = next_node_c;
    }

    return 0;
}

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.