¿Qué es un árbol binario completo?
Un árbol binario completo se puede definir como un árbol binario en el que todos los nodos tienen 0 o dos hijos. En otras palabras, el árbol binario completo se puede definir como un árbol binario en el que todos los nodos tienen dos hijos excepto los nodos hoja.
El siguiente árbol es un árbol binario completo:
El árbol anterior es un árbol binario completo ya que todos los nodos, excepto los nodos hoja, tienen dos hijos.
Teorema completo del árbol binario:
Considere un árbol binario T como un árbol no vacío entonces:
- Sea I nodos internos en un árbol y L sea un nodo hoja en un árbol, entonces el número de nodos hoja sería igual a:
L = Yo + 1 - Si T tiene I número de nodos internos y N es el número total de nodos, entonces el número total de nodos sería igual a:
norte = 2yo + 1 - Si T contiene 'N' el número total de nodos y 'I' es el número de nodos internos, entonces el número de nodos internos sería igual a:
Yo = (N-1)/2 - Si 'T' tiene 'N' un número total de nodos y 'L' es un número de nodos hoja, entonces el número de nodos hoja sería igual a:
L = (N+1)/2 - Si 'T' contiene un número 'L' de nodos hoja, entonces el número total de nodos sería igual a:
norte = 2L - 1 - Si 'T' tiene un número 'L' de nodos hoja y 'I' es un número de nodos internos, entonces el número de nodos internos sería igual a:
Yo = L - 1
¿Qué es un árbol binario completo?
Se dice que un árbol binario es un árbol binario completo cuando todos los niveles están completamente llenos excepto el último nivel, que se llena desde la izquierda.
El siguiente árbol es un árbol binario completo:
El árbol binario completo es similar al árbol binario completo excepto por las dos diferencias que se detallan a continuación:
- El llenado del nodo de la hoja debe comenzar desde el lado más izquierdo.
- No es obligatorio que el último nodo hoja tenga el hermano correcto.
Entendamos los puntos anteriores a través de un ejemplo:
Considere el siguiente árbol:
java xor
El árbol anterior es un árbol binario completo, pero no un árbol binario completo ya que el nodo 6 no tiene su hermano derecho.
Creación de árbol binario completo
Supongamos que tenemos una matriz de 6 elementos que se muestra a continuación:
La matriz anterior contiene 6 elementos, es decir, 1, 2, 3, 4, 5, 6. Los siguientes son los pasos que se utilizarán para crear un árbol binario completo:
Paso 1: Primero, seleccionaremos el primer elemento de la matriz, es decir, 1, y crearemos un nodo raíz del árbol. El número de elementos disponibles en el primer nivel es 1.
Paso 2: Ahora seleccionaremos el segundo y tercer elemento de la matriz. Mantenga el segundo elemento y el tercer elemento de la matriz como hijo izquierdo y derecho del nodo raíz respectivamente, como se muestra a continuación:
Como podemos observar arriba, la cantidad de elementos disponibles en el segundo nivel es 2.
Paso 3: Ahora, seleccionaremos los siguientes dos elementos de la matriz, es decir, 4 y 5. Mantenga estos dos elementos a la izquierda y a la derecha del nodo 2 como se muestra a continuación:
Como podemos observar arriba, los nodos 4 y 5 son los hijos izquierdo y derecho del nodo 2 respectivamente.
Etapa 4: Ahora, seleccionaremos el último elemento de la matriz, es decir, 6, y lo mantendremos como hijo izquierdo del nodo 3, ya que sabemos que en un árbol binario completo, los nodos se llenan desde el lado izquierdo, como se muestra a continuación:
Como podemos observar, el segundo nivel contiene 3 elementos.
Entendamos las diferencias entre árbol binario completo y completo a través de las imágenes.
desactivar el modo desarrollador android
- El árbol binario que se muestra a continuación no es un árbol binario completo ni completo. No es un árbol binario completo porque el nodo 3 tiene un solo hijo. Tampoco es un árbol binario completo ya que los nodos deben llenarse desde el lado izquierdo, pero el nodo 3 tiene un hijo derecho y no tiene un hijo izquierdo.
- El árbol binario, que se muestra a continuación, es un árbol binario completo pero no un árbol binario completo. Es un árbol binario completo porque todos los nodos tienen 0 o 2 hijos. No es un árbol binario completo porque el nodo 3 no tiene hijos mientras que el nodo 2 tiene sus hijos y sabemos que los nodos deben llenarse desde el lado izquierdo en un árbol binario completo.
- El árbol binario que se muestra a continuación es un árbol binario completo, pero no un árbol binario completo. Es un árbol binario completo ya que todos los nodos quedan llenos. No es un árbol binario completo ya que el nodo 2 tiene un solo hijo.
- El árbol binario que se muestra a continuación es un árbol binario completo y completo. Es un árbol binario completo ya que todos los nodos quedan llenos. Es un árbol binario completo ya que todos los nodos tienen 0 o 2 hijos.
