nodos internos de un árbol binario completo

Question

Probar o refutar: el número de nodos internos en un árbol binario completo de $K$ nodos es $\lfloor K/2 \rfloor$ .

Intenté usar la inducción:

Base: 1 nodo $\rightarrow$ $0$ nodos internos

Supuesto: sea el número de nodos internos en un árbol binario completo de $L$ nodos es $\lfloor L/2 \rfloor$

Paso inductivo: para $L+2$ tenemos un nuevo nodo interno y $\lfloor L/2 \rfloor + 1 = \lfloor (L+2)/2 \rfloor $ y hemos terminado.

Pero para $L+1$ Como un gráfico completo puede tener una hoja, me confundo.

¿Alguien puede ayudarme?

Answer 1

SUGERENCIA: Cuando se añade un nuevo nodo, al tratarse de un árbol binario completo, se dan dos casos:

1. O bien el nuevo nodo es el primero de una nueva fila,
2. o el nuevo nodo se añade al último no terminado.

En el primer caso, el número de nodos internos se incrementa en uno, al igual que el número total de nodos. El número de nodos internos era de la forma $N - 1$ mientras que el número de nodos totales era $2N - 1$ . Entonces, de hecho, tenemos que $N = \left\lfloor\frac{2N}{2}\right\rfloor$ .

En el segundo caso...