Estructura no lineal: árboles, definición, operaciones básicas

[pic 1]

ESTRUCTURA NO LINEAL: ÁRBOLES, DEFINICIÓN, OPERACIONES BÁSICAS.

CURSO:

ESTRUCTURA DE DATOS

ÁRBOLES

Un árbol es una estructura en el que los datos se organizan de modo que los elementos de información están relacionados entre sí y a través de ramas.

Características y propiedades de los árboles

[pic 2]

Raíz = A

Padres =A – B – C – D – F - H

Hermanos=

B-C (Padre A)

D-E-F (Padre B)

J-K (Padre F)

G-H (Padre C)

L-M (Padre H)

Terminales o nodos hoja= I – E – J – K – G – L -  M (subárboles sin descendientes)

Interiores o nodos no terminales= A-B-C-D-F-H

Grado =

• de A: 2
• de B: 3
• de D: 1
• de E: 0 (grado de las terminales =0)
• de F: 2
• de C: 2
• de H: 2

Grado del árbol = 3

Nivel =

Nivel 0 = A (Raíz)

Nivel 1 = B – C (Hermanos)

Nivel 2 = D – E – F – G - H

Nivel 3 = I – J – K – L - M

Altura o profundidad = 4

ARBOLES BINARIOS

Árboles binarios completos

Aquellos en el que todos excepto los terminales tienen 2 hijos.

Ejemplo:[pic 3]

Tipo: Árbol perfectamente equilibrado o árbol binario completo

Altura (h) = 3

Numero de nodos = [pic 4]

                   =[pic 5]

                  = 7

Numero de nodos por nivel = [pic 6]

        Nivel 0: (altura = 1) [pic 7]

        Nivel 1: (altura = 2) [pic 8]

        Nivel 2: (altura = 3) [pic 9]

Conversión de un Árbol General en Árbol Binario

NOTA: Un árbol binario ningún nodo puede tener más de dos subárboles.

Ejemplo:

[pic 10]

Resultados:

[pic 11]

Recorrido en Árboles Binarios

Ejemplo 01:

[pic 12]

1. Pre-orden: A-B-D-E-C-F-G
2. In-orden: D-B-E-A-F-C-G
3. Post-orden: D-B-E-F-G-C-A

Ejemplo 02:

[pic 13]

1. Pre-orden: A-B-D-G-K-C-E-H-I-F-J
2. In- orden: K-G-D-B-A-H-E-I-C-F-J
3. Post-orden: K-G-D-B-H-I-E-J-F-C-A

...