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:
- Definí la estructura de un árbol binario llamado "Node" conteniendo un valor "data", punteros a los hijos izquierdo "left" y derecho "right"
- Una función "insert" para insertar un valor en el árbol binario de búsqueda.
- 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.
Mi salida:
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.