Arboles

Diplomado en Informática Aplicada
Asignatura: Estructura de Datos Avanzada
Tema: Árboles

Centro de Estudio de Ingeniería de Sistemas (CEIS)
Instituto Superior Politécnico “José Antonio Echeverría” (CUJAE)

Tema 3: Árboles
Contenido
• Definición de árbol
• Árboles Binarios
• Recorridos en árboles binarios
• Árboles de búsqueda:
• Árboles lexicográficos
• Árboles hilvanados
• Implementación en unlenguaje de programación

Tema 3: Árboles
Contenido
• Árboles generales
• Transformación de árboles generales en binarios
• Implementación en un lenguaje de programación
• Colocación secuencial de árboles

io
l
b
Bi

fí
a
r
g

a

Bibliografía

• Data Structures / Algorithms in Java. Robert Lafore.
Páginas: 280-370

• Thinking in Java. Páginas: 395-445.
• Aprenda Java como si estuviera enprimero.
Páginas: 135-139.
• Aprenda Java en 21 días. Páginas: 135-151.
• El C++. Lenguaje de Programación. Bjarne
Stroustrup. Páginas 143-180 :.

Objetivos
Conozcan las estructuras de datos arbóreas y las
formas de trabajar con ellas en la solución de
problemas de mediana complejidad

Introducción
Estructuras de datos estudiadas:
Listas lineales y sus variantes.
Las relaciones entre los nodos deinformación son
lineales.
Todos los nodos tienen un único antecesor, excepto
el primero que no tiene antecesor.
•Todos los nodos tienen un único sucesor, excepto el
último que no tiene sucesor.

Introducción
?

¿Qué estructura de datos se debe utilizar
para representar estructuras jerárquicas o
taxonómicas?

Ejemplo:
Director
SubDir1

J´Dpto1

J´Dpto2

SubDir2

J´Dpto3

SubDir3

J´Dpto4

J´Dpto5Definición de Árbol
Un árbol (tree) es un T.D.A. que consta
de un
A
conjunto finito T de nodos y una relación R
(paternidad) entre los nodos tal que:
C
B
• Hay un nodo, especialmente designado, llamado la
A
raíz del árbol T.
G
E
F
D
• Los nodos restantes, excluyendo A
la raíz, son
C
B
particionados en m (m  0) conjuntos disjuntos T1, T2,
C un árbol,
B es, a su vez,
..., Tm, cada uno de los cuales
Gárbol T.
E de la
llamado subárbol
F raíz del
D
G
• A los nodos que no son D
F subárboles
raíces E
de otros
se les denomina hojas del árbol T, o sea, no tienen
sucesores o hijos.

Definición de Árbol
Si n es un nodo y A1, A2, A3, A4, A5, …, Ak son árboles
con raíces n1, n2, n3, n4,…, nk . Se puede construir un
nuevo árbol haciendo que n se constituya en padre
de los nodos n1, n2, n3, n4,…, nk.
Endicho árbol, n es la raíz y A1, A2, A3, A4, A5, …, Ak
son los subárboles de la raíz.
Los nodos n1, n2, n3, n4,…, nk reciben el nombre de
hijos del nodo n.

Aclaraciones
• Si el conjunto finito T de nodos del árbol es vacío,
entonces se trata de un árbol vacío.
• En esta estructura existe sólo un nodo sin padre,
que es la raíz del árbol.
• Todo nodo, a excepción del nodo raíz, tiene uno y
sólo unpadre.
• Los subárboles de un nodo son llamados hijos.

Ejemplos
A
C

B
D

E

F

G

• Padre de C:

A

• Padre de E:

B

• Padre de G

C

• Padre de A:
• Hijos de A:
• Hijos de C:
• Hijos de F:

NO
B

C

F

G

NO

Aclaraciones
• Para todo nodo k, distinto de la raíz, existe una
única secuencia de la forma:
–k0, k1, k2, k3, ..., kn, donde k0=raíz y kn=k
–Con n >= 1, donde.
ki es el sucesor deki-1,
para 1 <= i <= n, o sea, cada nodo ki de la
secuencia es la raíz de otro subárbol.

Ejemplos
Secuencias

A

• de A a G
C

B
D

E

F

• de A a E
G

• de A a F
C es sucesor de A y
F es sucesor de C

Otras definiciones
Grado de un nodo: cantidad de hijos de un nodo.
Grado de un árbol al mayor de los grados de todos
sus nodos.
Nodo hoja a un nodo sin hijos o con grado = 0.
Nodo rama a un nodo quetiene hijos, o sea, a la raíz
de un subárbol.

Ejemplos
Grado

A
C

B
E

D
H

I

F
J

G
K

• de A:

2

• de E:

3

• de G:

1

• de J:

0
Grado del árbol: 3
Nodos hojas:

D, H, I, J, F, K

Nodos ramas: A, B, C, E, G

Otras definiciones
Nivel de un nodo al nivel de su padre más uno. Por
definición, la raíz del árbol tiene nivel 0. Esta
definición es recursiva.

Ejemplos
Nivel

A
C

B
D

E

G...