Diferencia entre árbol binario completo y completo

Un árbol binario es un tipo de estructura de datos en el que cada Node solo puede tener dos descendientes como máximo denominados como hijo «izquierdo» y «derecho» .

Un árbol binario

Hay diferentes tipos de árboles binarios, pero aquí vamos a discutir la diferencia entre el árbol binario completo y el árbol binario completo .

 Árbol binario completo:

Un árbol binario completo es un árbol binario en el que todos los Nodes tienen 0 o 2 descendientes . En otros términos, un árbol binario completo es un árbol binario en el que todos los Nodes, excepto los Nodes hoja, tienen dos descendientes.

Un árbol binario completo

Sea i el número de Nodes internos
 n el número total de Nodes
l sea el número de hojas
λ sea el número de niveles

Después,

El número de hojas es (i + 1) .
El número total de Nodes es (2i + 1) .
El número de Nodes internos es (n – 1) / 2 .
El número de hojas es (n + 1) / 2 .
El número total de Nodes es (2l – 1) .
El número de Nodes internos es (l – 1) .
El número de hojas es como máximo (2 ^λ – 1) .

Árbol binario completo:

Cuando todos los niveles de un árbol binario están completamente llenos, excepto el último nivel, que puede contener 1 o 2 Nodes secundarios y se llena desde la izquierda , se dice que es un árbol binario completo.

Un árbol binario completo

Hay 2 puntos que puedes reconocer desde aquí,  

1. El lado más a la izquierda del Node hoja siempre debe llenarse primero.
2. No es necesario que el último Node hoja tenga un hermano derecho.

Consulte los siguientes ejemplos para comprender mejor el árbol binario completo y completo.

Ejemplo 1:

Ni completa ni completa

• El Node C tiene solo un hijo, por lo tanto, no es un árbol binario completo. 
• El Node C también tiene un hijo derecho pero no un hijo izquierdo, por lo tanto, tampoco es un árbol binario completo. 

Por lo tanto, el árbol binario que se muestra arriba no es un árbol binario completo ni completo.

Ejemplo 2:

Completo pero no completo

• Todos los Nodes tienen 0 o 2 hijos, por lo tanto, es un árbol binario completo . 
• No es un árbol binario completo porque el Node B no tiene hijos, mientras que el Node C tiene hijos, y de acuerdo con un árbol binario completo, los Nodes deben llenarse desde el lado izquierdo .

Por lo tanto, el árbol binario que se muestra arriba es un árbol binario completo y no es un árbol binario completo.

Ejemplo 3:

Completo pero no completo

• Es un árbol binario completo ya que todos los Nodes se dejan llenos.
• El Node B tiene solo un hijo, por lo tanto, no es un árbol binario completo.

Por lo tanto, el árbol binario que se muestra arriba es un árbol binario completo y no es un árbol binario completo.

Ejemplo 4:

completo y lleno

• Es un árbol binario completo porque todos los Nodes se dejan llenos .
• Todos los Nodes tienen 0 o 2 hijos, por lo tanto, es un árbol binario completo .

Por lo tanto, el árbol binario que se muestra arriba es un árbol binario completo y completo.

S. No.	Árbol binario completo	Árbol binario completo
1.	En un árbol binario completo, un Node en el último nivel solo puede tener un hijo.	En un árbol binario completo, un Node no puede tener un solo hijo.
2.	En un árbol binario completo, el Node debe llenarse de izquierda a derecha.	No existe un orden para llenar los Nodes en un árbol binario completo.
3.	Los árboles binarios completos se utilizan principalmente en estructuras de datos basadas en montón.	El árbol binario completo no tiene aplicación como tal, pero también se le llama árbol binario propiamente dicho.
4.	Un árbol binario completo también se llama árbol binario casi completo.	Un árbol binario completo también llamado árbol binario propio o 2-tree.
5	Un árbol binario completo debe tener el Node de hojas completo en exactamente la misma profundidad.	En pleno árbol binario el nivel de la hoja no necesariamente tiene que estar en la misma profundidad.