¿Diferencia entre “árbol binario completo”, “árbol binario estricto”, “árbol binario completo”?

80

Estoy confundido acerca de la terminología de los árboles de abajo, he estado estudiando el Árbol y no puedo distinguir entre estos árboles:

a) Árbol binario completo

b) Árbol binario estricto

c) Árbol binario completo

Ayúdame a diferenciar entre estos árboles. ¿Cuándo y dónde se utilizan estos árboles en la estructura de datos?

data-structures tree binary-tree kTiwari
fuente
2
¿ En.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees no responde a su pregunta?
Rodion
7
no, no, hay mucha confusión entre estos
kTiwari
1
Árbol binario estricto: cada nodo puede tener 2 hijos o ningún nodo en absoluto
vikkyhacks

Respuestas:

73

Wikipedia cedió

Un árbol binario completo (a veces un árbol binario adecuado o un árbol de dos o un árbol estrictamente binario) es un árbol en el que cada nodo, excepto las hojas, tiene dos hijos.

Entonces no tiene nodos con solo 1 hijo. Parece ser lo mismo que un árbol binario estricto.

Aquí hay una imagen de un árbol binario completo / estricto, de Google:

enter image description here

Un árbol binario completo es un árbol binario en el que todos los niveles, excepto posiblemente el último, están completamente llenos 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.

enter image description here

Soy Sam dice Reincorporar a Monica
fuente
34
Su ejemplo de árbol completo también cumple con los criterios de ser un árbol binario completo, por lo que la diferencia aparentemente es borrosa, en mi opinión, es posible que desee dar un ejemplo de un árbol completo que no sea un árbol binario completo y viceversa, eso haría que el respuesta completa :)
0decimal0
1
Existe una diferencia entre el árbol binario completo y el árbol estrictamente binario. Consulte la respuesta: stackoverflow.com/a/32064101/5237727
Saurabh Bhatia
2
Además, aunque todos los árboles completos son árboles equilibrados, no todos los árboles equilibrados son necesariamente árboles completos.
sfarbota
1
¿Qué significa que todos los niveles están completamente llenos?
lolololol ol
2
@lololololol significa que todos los nodos que posiblemente puedan estar en ese nivel están presentes.
Soy Sam dice Reincorporar a Monica
87

Árbol perfecto:

       x
     /   \
    /     \
   x       x
  / \     / \
 x   x   x   x
/ \ / \ / \ / \
x x x x x x x x

Árbol completo:

       x
     /   \
    /     \
   x       x
  / \     / \
 x   x   x   x
/ \ /
x x x

Árbol estricto / completo:

       x
     /   \
    /     \
   x       x
  / \ 
 x   x 
    / \
    x x
japreiss
fuente
4
¿Por árbol binario perfecto te refieres al árbol binario completo referido por el OP?
RBT
3
El árbol binario perfecto es tanto un árbol binario estricto / completo como un árbol binario completo, pero viceversa puede no ser siempre cierto.
neo
51

Hay una diferencia entre un ÁRBOL BINARIO ESTRICTO y COMPLETO.

1) ÁRBOL BINARIO COMPLETO: Un árbol binario de altura h que contiene exactamente (2 ^ h) -1 elementos se llama árbol binario completo . (Ref: Pg 427, Estructuras de datos, algoritmos y aplicaciones en C ++ [University Press], segunda edición de Sartaj Sahni).

o en otras palabras

En un ÁRBOL BINARIO COMPLETO cada nodo tiene exactamente 0 o 2 hijos y todos los nodos hoja están en el mismo nivel.

Por ejemplo: El siguiente es un ÁRBOL BINARIO COMPLETO:

          18
       /      \   
     15       30    
    /  \     /   \   
  40    50  100  40

2) ÁRBOL BINARIO ESTRICTO: Cada nodo tiene exactamente 0 o 2 hijos.

Por ejemplo: El siguiente es un ÁRBOL BINARIO ESTRICTO:

         18
       /     \   
     15       30    
    /  \          
  40    50

Creo que no hay confusión en la definición de un árbol binario completo, aún para la integridad de la publicación, me gustaría decir qué es un árbol binario completo.

3) ÁRBOL BINARIO COMPLETO: Un árbol binario es un árbol binario completo si todos los niveles están completamente llenos excepto posiblemente el último nivel y el último nivel tiene todas las claves a la izquierda como sea posible.

Por ejemplo: El siguiente es un ÁRBOL BINARIO COMPLETO:

           18
       /       \  
     15         30  
    /  \        /  \
  40    50    100   40
 /  \   /
8   7  9

Nota: Lo siguiente también es un árbol binario completo:

         18
       /     \   
     15       30    
    /  \     /   \   
  40    50  100  40
Saurabh Bhatia
fuente
¿Puede proporcionar una fuente para la definición completa del árbol binario? Contradice el de Wikipedia que proviene del NIST .
Calvin Li
@CalvinLi La fuente se menciona en la definición de ÁRBOL BINARIO COMPLETO. Aquí hay un enlace del pdf (pg 447 del pdf) - o6ucs.files.wordpress.com/2012/10/…
Saurabh Bhatia
@SaurabhBhatia, la última representación también es válida para el árbol binario completo. Corrígeme si estoy equivocado. ¿Cómo puede ser válida una representación para diferentes variedades?
Rose el
10

Descargo de responsabilidad- : la fuente principal de algunas definiciones es wikipedia, cualquier sugerencia para mejorar mi respuesta es bienvenida.

Aunque esta publicación tiene una respuesta aceptada y es buena, todavía estaba confundido y me gustaría agregar algunas aclaraciones más sobre la diferencia entre estos términos.

(1) ÁRBOL BINARIO COMPLETO: un árbol binario completo es un árbol binario en el que todos los nodos, además de las hojas, tienen dos hijos. También se denomina árbol estrictamente binario .

ingrese la descripción de la imagen aquí ingrese la descripción de la imagen aquí

Los dos anteriores son ejemplos de árbol completo o estrictamente binario.

(2) ÁRBOL BINARIO COMPLETO - Ahora, la definición de árbol binario completo es bastante ambigua, dice: - Un árbol binario completo es un árbol binario en el que cada nivel, excepto posiblemente el último , está completamente lleno, y todos los nodos son como lo más a la izquierda posible. Puede tener entre 1 y 2h nodos, lo más a la izquierda posible, en el último nivel h

Observe las líneas en cursiva.

La ambigüedad radica en las líneas en cursiva, "excepto posiblemente el último", lo que significa que el último nivel también puede estar completamente lleno, es decir, esta excepción no siempre debe cumplirse. Si la excepción no se cumple, es exactamente como la segunda imagen que publiqué, que también se puede llamar árbol binario perfecto . Por lo tanto, un árbol binario perfecto también está completo y completo, pero no al revés, lo que quedará claro con una definición más que debo indicar:

ÁRBOL BINARIO CASI COMPLETO: cuando se cumple la excepción en la definición de árbol binario completo, se le llama árbol binario casi completo o árbol binario casi completo. Es solo un tipo de árbol binario completo en sí mismo, pero es necesaria una definición separada para hacerlo más inequívoco.

Entonces, un árbol binario casi completo se verá así, puede ver en la imagen que los nodos están lo más a la izquierda posible, por lo que es más como un subconjunto del árbol binario completo, para decir más rigurosamente, cada árbol binario casi completo es un binario completo. árbol pero no al revés. :

ingrese la descripción de la imagen aquí

0decimal0
fuente
6

Concluyendo de las respuestas anteriores, aquí está la diferencia exacta entre árboles binarios completos / estrictamente, completos y perfectos

  1. Árbol completo / estrictamente binario : - Todos los nodos excepto los nodos hoja tienen dos hijos

  2. Árbol binario completo : - Todos los niveles, excepto el último, están completamente llenos y todos los nodos están justificados a la izquierda.

  3. Árbol binario perfecto : - Todos los nodos, excepto los nodos hoja, tienen dos hijos y cada nivel (también el último nivel) está completamente lleno.

pantech
fuente
2

Considere un árbol binario cuyos nodos se dibujan en forma de árbol. Ahora comience a numerar 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 con menos de n tienen dos hijos.

Si n tiene un hijo, debe ser el hijo izquierdo y todos los nodos menores de n tienen dos hijos. Además, ningún nodo con un número mayor que n tiene hijos.

Si n no tiene hijos, ningún nodo con un número mayor que n tiene hijos.

Se puede utilizar un árbol binario completo para representar un montón. Se puede representar fácilmente en la memoria contigua sin espacios (es decir, se utilizan todos los elementos de la matriz, salvo el espacio que pueda existir al final).

Craig Wright
fuente
2

El árbol binario completo es un árbol binario completo pero no es posible revertirlo, y si la profundidad del binario es n el no. de nodos en el árbol binario completo es (2 ^ n-1). No es necesario que en el árbol binario tenga dos hijos, pero en el binario completo cada nodo no tiene ni dos hijos.

Raghvendra Singh Thakur
fuente
1
No puede decir estrictamente que "revertir no es posible", de hecho, esta misma suposición se desafía en el ejemplo de árbol completo en la respuesta aceptada ... debería decir que puede ser posible o no
0decimal0
1
si la profundidad del binario es n el no. de nodos en el árbol binario completo es (2 ^ n-1): pero una definición de árbol binario completo es un árbol en el que cada nodo es una hoja o tiene dos hijos. Entonces el máximo posible no. de niños es (2 ^ n-1) pero puede ser menos que eso.
mrida
2

Para comenzar con lo básico, es muy importante comprender el árbol binario en sí mismo para comprender los diferentes tipos de él.

Un árbol es un árbol binario si y solo si: -

- Tiene un nodo raíz, que puede no tener nodos secundarios (0 childnodes, árbol NULL)

–El nodo raíz puede tener 1 o 2 nodos secundarios. Cada uno de estos nodos forma un árbol abinario. 

–La cantidad de nodos secundarios puede ser 0, 1, 2 ....... no más de 2

–Hay una ruta única desde la raíz a todos los demás nodos

Ejemplo:

        X
      /    \
     X      X
          /   \
         X     X

Llegando a sus terminologías solicitadas:

Un árbol binario es un árbol binario completo (de altura h, tomamos el nodo raíz como 0) si y solo si: -

Los niveles 0 a h-1 representan un árbol binario completo de altura h-1

- Uno o más nodos en el nivel h-1 pueden tener 0 o 1 nodos secundarios

Si j, k son nodos en el nivel h-1, entonces j tiene más nodos hijos que k si y solo si j está a la izquierda de k, es decir, al último nivel (h) pueden 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 solo 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 solo si: -

Cada nodo no hoja tiene exactamente dos nodos secundarios

Todos los nodos hoja están al 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 deberías saber qué es un árbol binario perfecto.

Un árbol binario es un árbol binario perfecto si y solo si: -

- es un árbol binario completo

- Todos los nodos hoja están al 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, lamento no poder publicar imágenes porque no tengo 10 reputación. ¡Espero que esto te ayude a ti y a otros!

user2376267
fuente
2

En mi experiencia limitada con el árbol binario, creo:

  1. Árbol estrictamente binario : todos los nodos, excepto los nodos hoja, tienen dos hijos o solo tienen un nodo raíz.
  2. Árbol binario completo : un árbol binario de H estrictamente (o exactamente) que contiene 2 ^ (H + 1) -1 nodos , está claro que cada nivel tiene la mayor cantidad de nodos. O en resumen, un árbol binario estricto donde todos los nodos hoja están al mismo nivel.
  3. Árbol binario completo : es un árbol binario en el que todos los niveles, excepto posiblemente el último, están completamente llenos y todos los nodos están lo más a la izquierda posible.
BertKing
fuente
1
Su definición de un árbol binario completo es incorrecta, esa es la definición de un árbol binario perfecto. Un árbol binario completo es sinónimo de un árbol estrictamente binario. (fuente: ver árbol binario estrictamente: faculty.cs.niu.edu/~mcmahon/CS241/Notes/bintree.html ) (fuente: ver árbol binario perfecto: slideshare.net/ajaykumarc137151/… )
Keego
1
oh, Dios mío, estoy confundido en este momento, me aseguraré de esto. Muchas gracias.
BertKing
1
No hay problema :) Vea la respuesta de @Lotus a continuación , lo clavó. Solo recomendé modificaciones para que su respuesta refleje esto.
Keego
1

Consideremos un árbol binario de altura 'h'. Un árbol binario se llama árbol binario completo si todas las hojas están presentes a la altura 'h' o 'h-1' sin ningún número faltante en la secuencia.

                   1
                 /   \
              2       3
            /    \         
         4        5

Es un árbol binario completo. 

                   1
                 /   \
              2       3
            /        /    
         4         6

No es un árbol binario completo ya que falta el nodo del número 5 en la secuencia.

Ravi varma Indukuri
fuente
0

El árbol binario completo está lleno si cada nodo tiene 0 o 2 hijos. en binario completo, el número de nodos hoja es el número de nodos internos más 1 L = l + 1

harpreet kaur banga
fuente
0

Árbol binario completo: todos los niveles están completamente llenos, excepto el nivel más bajo y una cosa principal, todos los elementos de la hoja deben haber dejado al niño. Árbol binario estricto: en este árbol, todos los nodos que no son hojas no tienen hijos, es decir, ni a la izquierda ni a la derecha. Árbol binario completo: cada nodo tiene cero hijos o dos hijos (nunca tener un solo hijo).

Rohit RK
fuente
> En este árbol, todos los nodos que no son hojas no tienen hijos, es decir, ni los nodos no hojas a la izquierda ni a la derecha deben tener al menos un hijo, de lo contrario es un nodo hoja
nkrivenko