Un árbol binario completo es una estructura combinatoria que se construye a partir de un punto inicial (la raíz), del que parten dos segmentos (las ramas, o aristas) que alcanzan dos nuevos puntos (los nodos), de los que parten otros dos segmentos, y así sucesivamente. Los nodos sucesivos se distribuyen en filas; los nodos de la fila n son aquellos a los que se llega recorriendo n segmentos desde la raíz. Los nodos de la última fila, de los que ya no parten ramas, son las hojas del árbol.
Las nociones así definidas se parecen mucho a las correspondientes en los árboles de verdad (los de madera); la principal diferencia formal es que, en combinatoria, los árboles suelen tener la raíz arriba y las hojas abajo…
Etiquetemos ahora cada rama según el camino que hay que seguir para alcanzarla desde la raíz: escribimos 0 cuando se va a la izquierda y 1 cuando se va a la derecha. Esta etiqueta puede interpretarse como la escritura binaria de un número (véase el recuadro). Además, en el nodo inferior de cada arista escribimos en base 10 el valor del número correspondiente. El número 13, por ejemplo, es la escritura decimal de «1101», que es la etiqueta de la arista a la que se llega de este modo: desde la raíz, se va primero a la derecha (1), luego otra vez a la derecha (1), después a la izquierda (0) y, por último, a la derecha (1).
