Arboles

TEMA 5. ÁRBOLES (I)

Estructura de Datos

1º ETIS

1

Índice
1. Concepto de árbol 2. Árboles binarios
1. 2. 3. 4. 5. 6. 7. Especificación informal del TAD árbol binario Implementación del TAD árbol binario Recorrido de un árbol binario Árboles de expresión Árboles hilvanados o enhebrados Árboles parcialmente ordenados (Montículos) Árboles binarios de búsqueda

Estructura de Datos1º ETIS

2

1

• Estructuras de datos no lineales:

– Cada elemento puede tener varios anteriores y/o siguientes

• Ejemplos de árbol:
– – – –

Árboles gramaticales para analizar oraciones Árboles genealógicos Estructura jerárquica de una organización Organización de ficheros en directorios/carpetas según una estructura en árbol – Desarrollo de algoritmos – Recuperación de informaciónEstructura de Datos 1º ETIS 3

1. Concepto de árbol • Definición:
– Estructura de datos no lineal, con una organización jerárquica y elementos homogéneos donde cada elemento puede tener varios elementos sucesores, pero un único elemento antecesor

Estructura de Datos

1º ETIS

4

2

1. Concepto de árbol
• Conceptos:
– Nodo
• Cada uno de los componentes o elementos del árbol (1.1,1.2, …, 2.1, …, 3.3)

– Ascendiente
• Un nodo N1 es ascendiente de N2 si está en un nivel superior dentro de la estructura jerárquica del árbol. (1.3 es ascendiente de los nodos 1.4, 1.5, 1.6 y 1.7)

– Descendiente:
• Un nodo N1 es descendiente de N2 si está en un nivel inferior dentro de la estructura jerárquica del árbol. (3.3 es descendiente de 3.1 y 3.2)

Estructura de Datos

1ºETIS

5

1. Concepto de árbol
• Conceptos:
– Nodo Raíz
• Nodo inicial del árbol. Se encuentra en el nivel superior de la estructura jerárquica del árbol (nivel 1). Es el único que no tiene padre. (1.1, 2.1, 3.1) • Nodo terminal del árbol. Son todos aquellos nodos que no tienen descendientes y se encuentran en los niveles más bajos de la estructura jerárquica del árbol, aunque pueden estar endistintos niveles del mismo. (Árbol 1: 1.2, 1.5, 1.6 y 1.7) • Subconjunto de nodos de un árbol que a su vez tienen estructura de árbol. El árbol 1 tiene varios subárboles, por ejemplo: desde el nodo 1.3 y todos sus descendientes; desde el nodo 1.4. El árbol 2 no tiene ningún subárbol.

– Nodo Hoja

– Subárbol:

Estructura de Datos

1º ETIS

6

3

1. Concepto de árbol
• Conceptos:
–Nodo padre:
• Es el nodo ascendiente de sus subárboles. En un árbol cada nodo sólo puede tener un padre, excepto el nodo raíz, que es el único que no tiene padre. Son nodos padre:
– – – – 1.1 1.3 1.4 3.1 es es es es padre padre padre padre de de de de 1.2 y 1.3, siendo estos nodos hijos 1.4, 1.5 y 1.6, siendo estos nodos hijos 1.7, siendo este nodo hijo 3.2 y este a su vez es padre de 3.3

–Nodo hijo:

– Nodos hermanos:

• Es el nodo descendiente de otro nodo. En un árbol cada nodo puede tener varios hijos. • Dos nodos son hermanos si tienen el mismo padre. (1.2 y 1.3; 1.4, 1.5 y 1.6)

Estructura de Datos

1º ETIS

7

1. Concepto de árbol
• Conceptos:
– Nodo interno: – Camino:
• Es todo nodo que no es ni nodo raíz ni nodo hoja. Por ejemplo, 1.3, 1.4 y 3.2 • Secuenciade nodos del árbol donde se cumple que cualquier par de nodos consecutivos son padre e hijo. (1.3 1.4; 1.1 1.3 1.4) • Es el número de nodos menos 1 (r-1). Si r>0, se dice que el camino es propio. longitud(1.3 1.4)=1; longitud(1.1 1.3 1.4)=2 • Cualquier camino desde el nodo raíz del árbol hasta un nodo hoja. (1.1 1.2; 1.1 1.3 1.6; 3.1 3.2 3.3)

– Longitud del camino: – Rama:

Estructura de Datos1º ETIS

8

4

1. Concepto de árbol
• Conceptos:
– Nivel (profundidad): – Grado:
• De un nodo: Número de nodos que tiene el camino desde la raíz a dicho nodo. nivel(1.3)=2; nivel(1.7)=4; nivel(2.1)=1 • De un nodo: es el número de descendientes directos de dicho nodo o, lo que es lo mismo, el número de hijos que tiene dicho nodo. grado(1.3)=3; grado(2.1)=0; grado(3.2)=1 • De un...