**Un albero binario completo *è una struttura combinatoria che si costruisce a partire da un punto iniziale (la radice), da cui partono due segmenti (i rami, o spigoli) che raggiungono due nuovi punti (i nodi), da cui partono altri due segmenti, e così via. I nodi successivi sono distribuiti in livelli, e i nodi del livello n sono quelli raggiunti percorrendo n segmenti a partire dalla radice. I nodi dell’ultimo livello, da cui non partono 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 ciascun ramo in base al percorso da seguire per raggiungerlo a partire dalla radice, segnando 0 quando si va a sinistra e 1 quando si va a destra. Questa etichetta può essere interpretata come la scrittura binaria di un numero (vedi riquadro). Inoltre, sul nodo inferiore di ogni spigolo scriviamo in base 10 il valore del numero corrispondente. Il numero 13, per esempio, è la scrittura decimale di «1101», che è l’etichetta dello spigolo raggiunto in questo modo: partendo dalla radice, si va prima a destra (1), poi ancora a destra (1), quindi a sinistra (0) e infine a destra (1).