Implementare la struttura dati ad albero binario in C++

In C++ un albero binario si può rappresentare con una struct che contiene un valore e due collegamenti ai figli. L’esempio seguente costruisce un piccolo albero, ne conta i nodi, ne misura l’altezza in archi e ne stampa i valori con una visita inordine.

Rappresentare un albero binario con una struct nodo

Un nodo di un albero binario può avere al massimo due figli, chiamati convenzionalmente left e right. Una struct è un tipo di classe i cui membri sono pubblici per impostazione predefinita, caratteristica che la rende pratica per questa piccola struttura dati. Ogni nodo memorizza un intero e possiede i propri nodi figli tramite std::unique_ptr; un puntatore nullo indica che manca un collegamento a un figlio. Questo, da solo, non significa che il nodo sia una foglia: una foglia è un nodo i cui due collegamenti ai figli sono entrambi nulli.

In un albero binario pieno, ogni nodo ha zero oppure due figli. Un albero binario perfetto è pieno e ha tutte le foglie alla stessa profondità. L’esempio costruito di seguito è pieno, ma non completo: all’ultimo livello c’è uno spazio vuoto prima di un nodo successivo. Questi termini descrivono forme diverse e non sono intercambiabili.

Costruire un piccolo albero binario

Il programma crea questa struttura deterministica, con valori scelti per rendere facile seguire la visita: 8 (left: 3, right: 10 (left: 9, right: 14)).

std::make_unique crea ogni nodo e restituisce un puntatore proprietario. Spostando un puntatore in un figlio se ne trasferisce la proprietà: così la radice possiede l’intero albero e i nodi vengono rilasciati automaticamente quando la radice esce dall’ambito. In questo modo si evita la pulizia manuale necessaria quando si usano allocazioni grezze con new.

Esegui questo esempio. Le etichette stampate, come size, height e inorder, restano in inglese:

#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';
}

Le funzioni ricevono un puntatore a un nodo senza assumerne la proprietà. Chiamandole con root.get() possono accedere all’albero, mentre il unique_ptr proprietario continua a gestirne il ciclo di vita. Le stesse definizioni ricorsive valgono per alberi di qualsiasi forma.

Contare i nodi e calcolare l’altezza dell’albero

treeSize restituisce zero se il sottoalbero non esiste. Altrimenti conta il nodo corrente e somma le dimensioni dei due sottoalberi figli. treeHeight restituisce -1 se il sottoalbero non esiste, quindi aggiunge uno all’altezza del figlio con il valore maggiore. Con questa convenzione, l’altezza corrisponde al numero di archi nel percorso più lungo dalla radice a una foglia: una foglia ha altezza 0 e l’albero qui sopra ha altezza 2. Alcune definizioni contano invece i nodi, assegnando altezza 1 a una foglia; scegli una convenzione e applicala con coerenza.

Stampare i nodi con una visita inordine

printData visita il sottoalbero sinistro, stampa il valore corrente e poi visita quello destro. È una visita inordine: in un albero binario di ricerca stampa i valori in ordine crescente, mentre in un albero binario generico segue soltanto quell’ordine di visita.

Per seguire la ricorsione, osserva la funzione a ogni nodo: prima scende a sinistra finché non trova più figli, stampa mentre risale verso il genitore e poi elabora il sottoalbero destro. I valori dell’esempio compaiono quindi nell’ordine 3 8 9 10 14. L’albero contiene cinque nodi e ha altezza due secondo la convenzione basata sugli archi. Il programma è autonomo: puoi adattare il tipo di valore dei nodi o aggiungere operazioni, mantenendo chiare la gestione della proprietà e la convenzione scelta per l’altezza.