Árbol binario de decisión para NPCs

[GabrielEValenzuela]

Objectivo

En Refugio 33, cada NPC mercader toma decisiones de interacción con el jugador basadas en condiciones internas como confiabilidad, precios o defensa del refugio. Para modelar esta lógica, utilizamos un árbol binario de decisión, una estructura eficiente y extensible usada frecuentemente en sistemas de IA en videojuegos.

Esta tarea consiste en implementar la estructura completa de este árbol binario, con las operaciones fundamentales que permitan su correcto uso dentro del motor del juego.

---

¿Qué es un árbol binario?

Un árbol binario es una estructura de datos jerárquica en la que cada nodo tiene hasta dos hijos (izquierdo y derecho). Es ideal para representar decisiones encadenadas, realizar búsquedas ordenadas o estructurar información jerárquica.

---

Detalles

Implementar una clase DecisionTree en C++ que represente un árbol binario de decisión. Este árbol debe permitir:

1. Crear el árbol (construcción desde cero).
2. Insertar nuevos nodos.
3. Buscar nodos por contenido.
4. Eliminar nodos.
5. Verificar si el árbol está vacío.
6. Recorrer el árbol en preorden (simulando decisiones).
7. Destruir correctamente el árbol liberando la memoria.

Estructura

struct Nodo {
    std::string decision;
    Nodo* izquierda;
    Nodo* derecha;

    Nodo(const std::string& d)
        : decision(d), izquierda(nullptr), derecha(nullptr) {}
};

Clase esperada

class DecisionTree {
public:
    DecisionTree();
    ~DecisionTree();

    void insertar(const std::string& decision);
    bool buscar(const std::string& decision) const;
    void eliminar(const std::string& decision);
    bool estaVacio() const;
    void recorrerPreorden() const;

private:
    Nodo* raiz;

    void insertar(Nodo*& nodo, const std::string& decision);
    bool buscar(Nodo* nodo, const std::string& decision) const;
    void eliminarNodo(Nodo*& nodo, const std::string& decision);
    void recorrerPreorden(Nodo* nodo) const;
    void destruir(Nodo* nodo);
};

Podés asumir que las decisiones tienen un criterio de orden lexicográfico.

---

Definition of Done (DoD)

• La clase DecisionTree implementa todos los métodos requeridos.
• El árbol puede crearse, modificarse, buscarse y recorrerse sin errores.
• Se libera correctamente toda la memoria al destruir el árbol.
• Se prueban los métodos con al menos 5 nodos.
• El diseño es modular y cumple con buenas prácticas de C++.

Tips de IA & gaming

• Esta estructura puede adaptarse fácilmente a árboles de comportamiento (BTs), ampliamente utilizados en IA de enemigos o aliados.
• También puede ser útil para estructurar diálogos ramificados, árboles de habilidades o decisiones de combate.