Uso de la inducción para demostrar árboles binarios completos

Question

Demuestra que un árbol binario completo tiene un número impar de vértices.

Mi intento de solución:

Paso de base: Un árbol binario con una altura de 0 es un solo vértice. Esto haría que el árbol tuviera un número impar de vértices (1). Es correcto.

Hipótesis inductiva: Un árbol binario completo con una altura mayor que 0 y menor que k tiene un número impar de vértices.

Pruébalo: Un árbol binario con una altura de k+1 tendría un número impar de vértices.

Un árbol binario completo de altura k+1 estará formado por dos árboles binarios completos k1 y k2. K1 y K2 son árboles binarios completos, lo que significa que tienen un número impar de vértices. Se pueden representar con (2m+1) y (2n+1). Un árbol con la altura de k+1 puede ser representado por (2m+1) + (2n+1) más 1 vértice de conexión. Como (2m+1)+(2n+1) = (2m+2n+2) = 2(m+n+1) podemos ver que el número de vértices en k1+k2 es par. Añadiendo el vértice de unión obtenemos 2(m+n+1)+1. Un número impar. Por lo tanto, un árbol con la altura de k+1 tiene un número impar de vértices.

¿Funciona esto o me he equivocado?

Answer 1

¡Se ve bien! Tenga en cuenta que su hipótesis inductiva debe decir "menor o igual a $k$ " y no sólo "menos de $k$ ". Además, yo quizás reformularía la parte del "vértice de conexión". Comienza tu paso de inducción diciendo algo como:

Considere un árbol binario completo $T$ con una altura de $k + 1$ . Observe que $T$ se compone de un nodo raíz $r$ con dos subárboles $T_1$ y $T_2$ cada uno de los cuales es un árbol binario completo con una altura de $k$ . Pero entonces, por la hipótesis de la inducción, sabemos que...