Implementar la estructura de datos de árbol binario en C++

En C++, un árbol binario puede representarse mediante un nodo struct con un valor y dos enlaces a sus hijos. El ejemplo construye un árbol pequeño, cuenta sus nodos, mide su altura en aristas e imprime sus valores mediante un recorrido en orden.

Representar un árbol binario con un struct de nodo

Cada nodo de un árbol binario tiene como máximo dos hijos, llamados convencionalmente left y right. Un struct es un tipo de clase cuyos miembros son públicos de forma predeterminada, por lo que resulta práctico para esta pequeña estructura de datos. Cada nodo almacena un entero y es propietario de sus nodos hijos mediante std::unique_ptr; un puntero nulo indica que falta el enlace a un hijo. Eso no significa por sí solo que el nodo sea una hoja: una hoja es un nodo cuyos dos enlaces a hijos son nulos.

Un árbol binario lleno tiene cero o dos hijos en cada nodo. Un árbol binario perfecto es lleno y todas sus hojas están a la misma profundidad. El árbol del ejemplo es lleno, pero no completo: en su último nivel hay un espacio vacío antes de un nodo posterior. Estos términos describen formas distintas y no deben usarse indistintamente.

Construir un árbol binario pequeño

El programa crea esta forma determinista, con valores elegidos para que sea fácil seguir el recorrido: 8 (left: 3, right: 10 (left: 9, right: 14)). En esa notación, left y right identifican los enlaces izquierdo y derecho.

std::make_unique crea cada nodo y devuelve un puntero propietario. Al mover un puntero a un hijo se transfiere la propiedad, de modo que la raíz es propietaria de todo el árbol y sus nodos se liberan automáticamente cuando sale de ámbito. Así se evita la limpieza manual que requieren las asignaciones directas con new.

Ejecuta este ejemplo. Las etiquetas que muestra, como size, height e inorder, permanecen en inglés porque el bloque de código se conserva sin cambios.

#include <iostream>
#include <memory>

struct BinTreeNode {
    int data;
    std::unique_ptr<BinTreeNode> left;
    std::unique_ptr<BinTreeNode> right;

    explicit BinTreeNode(int value) : data(value) {}
};

int treeSize(const BinTreeNode* node) {
    if (node == nullptr) {
        return 0;
    }
    return 1 + treeSize(node->left.get()) + treeSize(node->right.get());
}

int treeHeight(const BinTreeNode* node) {
    if (node == nullptr) {
        return -1;
    }
    const int leftHeight = treeHeight(node->left.get());
    const int rightHeight = treeHeight(node->right.get());
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

void printData(const BinTreeNode* node) {
    if (node == nullptr) {
        return;
    }
    printData(node->left.get());
    std::cout << node->data << ' ';
    printData(node->right.get());
}

int main() {
    auto root = std::make_unique<BinTreeNode>(8);
    root->left = std::make_unique<BinTreeNode>(3);
    root->right = std::make_unique<BinTreeNode>(10);
    root->right->left = std::make_unique<BinTreeNode>(9);
    root->right->right = std::make_unique<BinTreeNode>(14);

    std::cout << "size = " << treeSize(root.get()) << '\n';
    std::cout << "height = " << treeHeight(root.get()) << '\n';
    std::cout << "inorder = ";
    printData(root.get());
    std::cout << '\n';
}

Las funciones reciben un puntero a un nodo sin adquirir su propiedad. Al llamarlas con root.get(), pueden acceder al árbol mientras el unique_ptr propietario sigue siendo responsable de su ciclo de vida. Las mismas definiciones recursivas sirven para árboles de cualquier forma.

Contar los nodos y calcular la altura del árbol

treeSize devuelve cero si el subárbol no existe. En caso contrario, cuenta el nodo actual y suma los tamaños de sus dos subárboles. treeHeight devuelve -1 si el subárbol no existe y luego suma uno a la mayor altura de los subárboles hijos. Con esta convención, la altura cuenta las aristas del camino más largo desde la raíz hasta una hoja: una hoja tiene altura 0 y el árbol del ejemplo tiene altura 2. Algunas definiciones cuentan nodos en lugar de aristas, por lo que una hoja tiene altura 1; elige una convención y úsala de forma coherente.

Imprimir los nodos mediante un recorrido en orden

printData visita el subárbol izquierdo, imprime el valor actual y luego visita el subárbol derecho. Este es un recorrido en orden; en un árbol binario de búsqueda imprime los valores ordenados, mientras que en un árbol binario general solo sigue ese orden de recorrido. Consulta la guía sobre el recorrido en orden para obtener más detalles.

Para seguir la recursión, observa lo que hace la función en cada nodo: primero desciende por la izquierda hasta que no hay ningún hijo, imprime al regresar al nodo padre y luego procesa el subárbol derecho. Por eso, los valores del ejemplo aparecen en el orden 3 8 9 10 14. El árbol tiene cinco nodos y su altura, medida en aristas, es dos. El programa es autónomo; puedes adaptar el tipo de valor de los nodos o añadir operaciones, manteniendo clara la propiedad de los nodos y la convención de altura elegida.