data-structures - complexity - binary tree online
¿Diferencia entre "árbol binario completo", "árbol binario estricto", "árbol binario completo"? (10)
Estoy confundido acerca de la terminología de los árboles debajo, he estado estudiando el Árbol, y no puedo distinguir entre estos árboles:
a) Completar el árbol binario
b) Estricto árbol binario
c) Árbol Binario Completo
Por favor, ayúdame a diferenciar entre estos árboles. ¿Cuándo y dónde se usan estos árboles en la estructura de datos?
árbol binario completo es un árbol binario completo, pero inversa no es posible, y si la profundidad de la binaria es n el no. de nodos en el árbol binario completo es (2 ^ n-1). No es necesario en el árbol binario que tiene dos hijos pero en el binario completo que todos los nodos no tienen o tienen dos hijos.
Concluyendo de respuestas anteriores, Aquí está la diferencia exacta entre los árboles binarios completos / estrictamente, completos y perfectos
Full / Estrictamente árbol binario: - Todos los nodos, excepto los nodos hoja tienen dos hijos
Árbol binario completo: - Todos los niveles, excepto el último nivel está completamente lleno y todos los nodos están justificados a la izquierda.
Árbol binario perfecto: - Todos los nodos, excepto los nodos hoja tiene dos hijos y todos los niveles (último nivel también) está completamente lleno.
Considere un árbol binario cuyos nodos se dibujan de una forma de árbol. Ahora empieza la numeración de los nodos de arriba a abajo y de izquierda a derecha. Un árbol completo tiene estas propiedades:
Si n tiene hijos, entonces todos los nodos numerados menor que n tiene dos hijos.
Si n tiene un niño que debe ser el niño a la izquierda y todos los nodos menor que n tiene dos hijos. Además no hay ningún nodo numerado mayor que n tiene niños.
Si n no tiene hijos, entonces no hay ningún nodo numerado mayor que n tiene niños.
Un árbol binario completo se puede utilizar para representar un montón. Puede ser fácilmente representado en memoria contigua sin huecos (es decir, todos los elementos de la matriz se utilizan Guardar para cualquier espacio que pueda existir en el extremo).
En mi experiencia limitada con el árbol binario, pienso:
- Árbol estrictamente binario: Cada nodo excepto los nodos hoja tienen dos hijos o sólo tienen un nodo raíz.
- Completo Árbol Binario: Un árbol binario de H estrictamente (o exactamente) que contiene 2 ^ h-1 nodos, está claro que el que cada nivel tiene el mayor número de nodos.
- Completar Árbol Binario: Es un árbol binario en el que todos los niveles, con la posible excepción de la última, está completamente lleno, y todos los nodos están tan a la izquierda como sea posible.
Hay una diferencia entre un árbol binario estricto y COMPLETO.
1) COMPLETA BINARIO árbol: Un árbol binario de la altura h que contiene exactamente (2 ^ h) -1 elementos se denomina un árbol binario completo. (Ref: Pg 427, estructuras de datos, algoritmos y aplicaciones en C ++ [University Press], segunda edición por Sartaj Sahni).
o en otras palabras
En un árbol binario completo cada nodo tiene exactamente 0 o 2 niños y todos los nodos de la hoja están en el mismo nivel.
Por ejemplo: La siguiente es un árbol binario COMPLETA:
18
/ /
15 30
/ / / /
40 50 100 40
2) árbol binario ESTRICTA: Cada nodo tiene exactamente 0 o 2 niños.
Por ejemplo: La siguiente es un árbol binario estricta:
18
/ /
15 30
/ /
40 50
Creo que no hay confusión en la definición de un árbol binario completo, todavía por la integridad de la post me gustaría decirle lo que es un árbol binario completo es.
3) árbol binario completo: Un árbol binario es completa árbol binario si todos los niveles están completamente llenos, excepto posiblemente el último nivel y el último nivel tiene todas las llaves como izquierda como sea posible.
Por ejemplo: La siguiente es un árbol binario completo:
18
/ /
15 30
/ / / /
40 50 100 40
/ / /
8 7 9
Nota: El siguiente es también un árbol binario completo:
18
/ /
15 30
/ / / /
40 50 100 40
Para comenzar con lo básico, es muy importante entender árbol binario en sí para comprender diferentes tipos de ella.
Un árbol es un árbol binario si y sólo si: -
- Dispone de un nodo raíz, que puede no tener ningún nodo hijo (0 childNodes, árbol NULL)
nodo -root puede tener 1 o 2 nodos secundarios. Cada una de tales formas de nodo abinary propio árbol
-Número de nodos hijos puede ser 0, 1, 2 ....... no más de 2
-No hay un único camino de la raíz a todos los demás nodos
Ejemplo:
X
/ /
X X
/ /
X X
Llegando a sus terminologías investigados:
Un árbol binario es un árbol binario completo (de altura h, tomamos como nodo raíz 0) si y sólo si: -
Nivel 0 a h-1 representa un árbol binario completo de la altura h-1
- Uno o más nodos en el nivel de h-1 pueden tener 0, o 1 nodos secundarios
Si j, k son nodos en el nivel de h-1, entonces j tiene más nodos secundarios que k si y sólo si j es a la izquierda de k, es decir, el último nivel (h) puede faltar nodos hoja, sin embargo los presentes deben ser movido a la izquierda
Ejemplo:
X
/ /
/ /
/ /
X X
/ / / /
X X X X
/ / / / / / / /
X X X X X X X X
Un árbol binario es un árbol estrictamente binario si y sólo si: -
Cada nodo tiene exactamente dos nodos secundarios o ningún nodo
Ejemplo:
X
/ /
X X
/ /
X X
/ / / /
X X X X
Un árbol binario es un árbol binario completo si y sólo si: -
Cada nodo no hoja tiene exactamente dos nodos secundarios
Todos los nodos de hoja están en el mismo nivel
Ejemplo:
X
/ /
/ /
/ /
X X
/ / / /
X X X X
/ / / / / / / /
X X X X X X X X
/ / / / / / / / / / / / / / / /
X X X X X X X X X X X X X X X X
También debe saber lo que es un árbol binario es perfecta?
Un árbol binario es un árbol binario perfecto si y sólo si: -
- es un árbol binario completo
- Todos los nodos de hoja están en el mismo nivel
Ejemplo:
X
/ /
/ /
/ /
X X
/ / / /
X X X X
/ / / / / / / /
X X X X X X X X
/ / / / / / / / / / / / / / / /
X X X X X X X X X X X X X X X X
Bueno, lo siento no puedo publicar imágenes que no tengo 10 reputación. Espero que esto le ayuda y otros!
Perfecto:
x
/ /
/ /
x x
/ / / /
x x x x
/ / / / / / / /
x x x x x x x x
Completar:
x
/ /
/ /
x x
/ / / /
x x x x
/ / /
x x x
Estricto:
x
/ /
/ /
x x
/ /
x x
/ /
x x
Un árbol binario completo (a veces el árbol binario apropiado o el árbol de 2 árboles o estrictamente binario) es un árbol en el que cada nodo, además de las hojas, tiene dos hijos.
Entonces no tienes nodos con solo 1 hijo. Parece ser el mismo árbol estricto binario.
Aquí hay una imagen de un árbol binario completo / estricto, de google:
Un árbol binario completo es un árbol binario en el que cada nivel, excepto posiblemente el último, está completamente lleno, y todos los nodos están lo más a la izquierda posible.
Parece significar un árbol equilibrado.
Aquí hay una imagen de un árbol binario completo, de Google, la parte completa del árbol de la imagen es una bonificación.
Completo árbol binario es un árbol binario en el que cada nodo tiene ya sea 0 o dos hijos. En otras palabras, cada nodo en el árbol, excepto las hojas tiene exactamente dos hijos.
Un árbol binario completo es un árbol binario en el que cada nivel del árbol se llena por completo, excepto el último nivel. También, en el último nivel, los nodos deben estar unidos a partir de más a la izquierda posición. Un árbol binario completo debe satisfacer las siguientes condiciones:
- Si a, b son dos nodos en el nivel por encima del último nivel, entonces A tiene más niños que b si y sólo si A está situado izquierda de b.
- Desde el nodo raíz, el nivel por encima del último nivel representa un árbol binario completo de la altura h-1.
- Uno o más nodos en último nivel pueden tener 0 o 1 niños.
DIVULGACIÓN- La principal fuente de algunas definiciones son Wikipedia, cualquier sugerencia para mejorar mi respuesta es bienvenida.
A pesar de que este post tiene una respuesta aceptada y es una buena idea que todavía estaba en la confusión y me gustaría añadir algo más de aclaración con respecto a la diferencia entre estos términos.
(1) COMPLETA BINARIO de árboles Un árbol binario completo es un árbol binario en el que cada nodo distinto de las hojas tiene dos niños.No también se llama árbol estrictamente binario.
Los dos anteriores son los ejemplos de árbol lleno o estrictamente binario.
(2) COMPLETA BINARIO de árboles Ahora, la definición de árbol binario completo es bastante ambigua, se indica: - Un árbol binario completo es un árbol binario en el que todos los niveles, con la posible excepción de la última, está completamente lleno, y todos los nodos son tan más a la izquierda posible. Puede tener entre 1 y nodos 2H, tan a la izquierda como sea posible, en el último nivel h
Observe las líneas en cursiva.
La ambigüedad se encuentra en las líneas en cursiva, "excepto posiblemente el último", que significa que el último nivel también puede estar completamente lleno, es decir, esta excepción no siempre tiene por qué ser satisfecho. Si la excepción no se cumple, entonces es exactamente igual que la segunda imagen que he publicado, que también puede ser llamado como árbol binario perfecto. Así, un árbol binario perfecto también es plena y completa, pero no a la inversa que será clara por una definición más necesito Estado:
CASI COMPLETA BINARIO de árboles Cuando la excepción en la definición de árbol binario completo sostiene entonces se le llama árbol binario casi completa o casi completa árbol binario. Es sólo un tipo de árbol binario completo en sí, sino una definición por separado es necesario para que sea más ambigua.
Por lo que un árbol binario casi completo se parecerá a esto, se puede ver en la imagen de los nodos están tan a la izquierda como sea posible por lo que es más como un subconjunto del árbol binario completo, por no decir más rigurosamente cada árbol binario casi completo es un binario completo árbol, pero no al revés. :