Árbol binario completo vs árbol binario completo
El árbol binario es un árbol donde cada nodo tiene uno o dos hijos. En un árbol binario, un nodo no puede tener más de dos hijos. En un árbol binario, los niños se nombran como niños “izquierdos” y “derechos”. Los nodos secundarios contienen una referencia a su padre. Un árbol binario completo es un árbol binario en el que cada nivel del árbol binario está completamente lleno excepto el último nivel. En el nivel sin llenar, los nodos se adjuntan comenzando desde la posición más a la izquierda. Un árbol binario completo es un árbol en el que cada nodo del árbol tiene dos hijos, excepto las hojas del árbol.
¿Qué es el árbol binario completo?
El árbol binario completo es un árbol binario en el que cada nodo del árbol tiene exactamente cero o dos hijos. En otras palabras, cada nodo del árbol, excepto las hojas, tiene exactamente dos hijos. La Figura 1 a continuación muestra un árbol binario completo. En un árbol binario completo, el número de nodos (n), el número de laves (l) y el número de nodos internos (i) están relacionados de una manera especial, de modo que si conoce alguno de ellos puede determinar los otros dos valores de la siguiente manera:
1. Si un árbol binario completo tiene i nodos internos:
- Número de hojas l = i + 1
- Número total de nodos n = 2 * i + 1
2. Si un árbol binario completo tiene n nodos:
- Número de nodos internos i = (n-1) / 2
- Número de hojas l = (n + 1) / 2
3. Si un árbol binario completo tiene l hojas:
- Número total de nodos n = 2 * l-1
- Número de nodos internos i = l-1
¿Qué es el árbol binario completo?
Como se muestra en la figura 2, un árbol binario completo es un árbol binario en el que todos los niveles del árbol están completamente llenos excepto el último nivel. Además, en el último nivel, los nodos deben adjuntarse comenzando desde la posición más a la izquierda. Un árbol binario completo de altura h satisface las siguientes condiciones:
- Desde el nodo raíz, el nivel por encima del último nivel representa un árbol binario completo de altura h-1
- Uno o más nodos en el último nivel pueden tener 0 o 1 hijos
- Si a, b son dos nodos en el nivel por encima del último nivel, entonces a tiene más hijos que b si y solo si a está situado a la izquierda de b
¿Cuál es la diferencia entre el árbol binario completo y el árbol binario completo?
Los árboles binarios completos y los árboles binarios completos tienen una clara diferencia. Mientras que un árbol binario completo es un árbol binario en el que cada nodo tiene cero o dos hijos, un árbol binario completo es un árbol binario en el que cada nivel del árbol binario está completamente lleno excepto el último nivel. Algunas estructuras de datos especiales, como montones, deben ser árboles binarios completos, mientras que no es necesario que sean árboles binarios completos. En un árbol binario completo, si conoce el número total de nodos o el número de laves o el número de nodos internos, puede encontrar los otros dos muy fácilmente. Pero un árbol binario completo no tiene una propiedad especial que relacione estos tres atributos.
