¿Por qué un árbol binario completo de $n$ las hojas tienen $2n-1$ ¿Nodos?

Question

Un árbol binario completo se define como un árbol en el que cada nodo tiene $2$ o $0$ niños.

Diversas fuentes han descrito la relación entre los nodos y las hojas como $2n-1$ donde $n$ es el número de hojas. Sin embargo, no he podido encontrar una descripción de cómo esta relación fue derivada.

Answer 1

Comience con una lista de $n$ nodos hoja: lo consideraremos como una lista de nodos a los que tenemos que dar padres, para construir un árbol binario completo.

Tome dos nodos cualesquiera $a,b$ de la lista, y darles un padre común $p$ . (Debemos tomarlos de dos en dos, para satisfacer la propiedad de completitud del árbol). Ahora esos dos nodos tienen padres, pero el nuevo nodo padre $p$ no lo hace; así que eliminamos $a$ y $b$ de la lista y añadir $p$ en. Esto reduce el tamaño de la lista en 1, independientemente de cómo elijamos los nodos a los que dar padres. A continuación, podemos repetir esto, dando un padre a otros dos nodos (donde uno de ellos es posiblemente el nodo $p$ que acabamos de insertar).

Sólo habremos terminado de construir el árbol cuando quede un nodo sin padre: el nodo raíz del árbol. Para ello es necesario $n-1$ etapas de creación de nuevos nodos padre. Así, para construir el árbol desde $n$ hojas, necesitábamos añadir $n-1$ nuevos nodos.

Answer 2

Si se añaden dos aristas a una hoja, se anula una hoja y se añaden dos nuevas hojas, mientras que si se añaden dos nodos, el número de nodos menos dos veces el número de hojas es un invariante. Dado que todo árbol binario puede construirse mediante un número finito de estos pasos y, para el árbol con un vértice y sin aristas, este invariante es $1-2\cdot1=-1$ para todo árbol binario el número de nodos más uno es el doble del número de hojas.

Esto, o Característica de Euler .

Answer 3

Esto se aplica tanto al árbol completo como al estrictamente binario

empezar con un árbol de 1 nodo. en el que

número de hojas = número de nodos

en el caso de un árbol estrictamente binario - para añadir una hoja más al árbol tenemos que añadir dos nodos al árbol, y para una más tenemos que añadir dos nodos más al árbol y así sucesivamente.

Así que para n hojas el número de nodos será 2*n -1

de la misma manera se puede ampliar para binario completo también.