Arboles

Árboles y esquemas
algorítmicos
Tema III

Bibliografía
• Tema III (lecciones 15 a 22) del libro “Campos Laclaustra, J.:
Estructuras de Datos y Algoritmos, Prensas Universitarias de
Zaragoza, Colección Textos Docentes, 1995 “
• Capitulo 5 del libro “X. Franch: Estructuras de datos.
Especificación, diseño e implementación, 3ª edición,
Ediciones UPC, 2001”
• Libro: “Joyanes, L.,Zahonero, I., Fernández, M. y Sánchez,
L.: Estructuras de datos. Libro de problemas, McGraw Hill,
1999.”, capítulos 8, 9 y 10
• Capítulos 6 a 8, y 11 a 15 del libro “Martí, Ortega, Verdejo:
Estructura de datos y métodos algorítmicos.
Ejercicios y problemas resueltos,
Pearson Prentice Hall, 2003.”,

• Y muchos otros....

Árboles: concepto y
especificación algebraica
(Lección 15…)Conceptos, definiciones y terminología básica
• Árbol:
– Conjunto de elementos de un mismo tipo,

denominados nodos, que pueden representarse
en un grafo no orientado, conexo y acíclico, en el
que existe un vértice destacado denominado raíz
• Por lo general es una estructura jerárquica…

– Definición recursiva:
• Un árbol n-ario (con n1) es un conjunto no vacío de

elementos del mismo tipo talque:
– Existe un elemento destacado llamado raíz del árbol
– el resto de los elementos se distribuyen en m subconjuntos

disjuntos (0 m n ), llamados subárboles del árbol original,
cada uno de los cuales es a su vez un árbol n-ario

Conceptos, definiciones y terminología básica
• Árbol ordenado:
– Si en el conjunto de subárboles de un árbol n-ario
se supone definida una relación deorden total, el
árbol se denomina ordenado

Árbol ordenado con raíz X y
subárboles A1 … Am
Leyenda:

Nodo

Árbol 3-ario de números enteros
Árbol

Conceptos, definiciones y terminología básica
• Hoja:
– Un árbol compuesto por un solo elemento se denomina
hoja
3

6

7

Raíz
Nodo
Árbol

9

33

51

Hoja
Hoja

15

55

Hoja

13

23

Hoja

Hoja

38

HojaEjemplo de árbol 3-ario

Conceptos, definiciones y terminología básica
• Camino: un camino es una secuencia de árboles A1,..As, s1,
tal que Ai+1 es subárbol de Ai, para todo 1is-1
• Longitud de camino: número de árboles en la secuencia del
camino, menos 1
• Por convenio: diremos que existe un camino de longitud 0, de
todo subárbol a si mismo
3

Camino desde
el árbol de raíz
elnodo 3,
hasta el árbol
cuya raíz es el
nodo 55, y su
7
longitud es 3
15

6

9

33

55

Camino desde
el nodo 9
hasta el 23, de
longitud 2

51

13

23

38

Conceptos, definiciones y terminología básica
• Si en un árbol A existe un camino desde el subárbol A1 hasta el
subárbol A2, se dice que A1 es antecesor de A2 y que A2 es
descendiente de A1

Antecesores delárbol
cuya raíz es el nodo
7, son los subárboles
que tienen como
raíces: el nodo 6, y el
del nodo 3, y sus
descendientes son
los subárboles que
tienen como raíces el
nodo 15, y el del 55

15

Antecesor del árbol
cuya raíz es el nodo
6, es el árbol cuya
raíz es el nodo 3
Descendientes del
árbol cuya raíz es el
nodo 6 son todos los
subárboles que
“cuelgan” de el.

3

6

7

933

55

51

13

23

38

Conceptos, definiciones y terminología básica
• Los antecesores o descendientes de un subárbol, distintos del
mismo subárbol, se denominan propios
• El padre de un subárbol, es su primer antecesor propio, si existe
• Los hijos de un subárbol, son sus primeros descendientes
propios, si existen
• Dos subárboles son hermanos, si tienen el mismo padre
3Su padre es
6

Sus hijos son
7

15

9

33

55

51

13

23

38

Sus hermanos son

Conceptos, definiciones y terminología básica
• La altura de un árbol es la longitud del camino más largo que
puede encontrarse en el árbol
• La profundidad de un subárbol en un árbol, es la longitud del
único camino existente desde el árbol hasta el subárbol
• Un nivel, es el...