Un albero binario completo è una struttura combinatoria costruita a partire da un punto iniziale (la radice), dal quale si dipartono due segmenti (i rami, o archi) che raggiungono due nuovi punti (i nodi), dai quali si dipartono altri due segmenti, e così via. I nodi successivi sono distribuiti in righe; i nodi della riga n sono quelli che si raggiungono percorrendo n segmenti a partire dalla radice. I nodi dell’ultima riga, dai quali non si dipartono più rami, sono le foglie dell’albero.
Le nozioni così definite somigliano molto a quelle corrispondenti negli alberi veri (quelli di legno); la principale differenza formale è che, in combinatoria, gli alberi hanno per lo più la radice in alto e le foglie in basso…
Etichettiamo ora ogni ramo secondo il percorso da seguire per raggiungerlo dalla radice, segnando 0 quando si va a sinistra e 1 quando si va a destra. Possiamo interpretare questa etichetta come la scrittura binaria di un numero (vedi il riquadro). Inoltre, sul nodo inferiore di ogni arco scriviamo in base 10 il valore del numero corrispondente. Il numero 13, per esempio, è la scrittura decimale di «1101», che è l’etichetta dell’arco così raggiunto: partendo dalla radice, si va prima a destra (1), poi ancora a destra (1), quindi a sinistra (0) e infine a destra (1).
