Estructura de datos ISC Unidad 4 Arboles y Grafos

Unidad 4.- Estructuras no lineales.
4.1 Árboles.
4.1.1 Definición.
4.1.2 Representación en memoria de árboles.
4.1.2.1 Árboles generales.
4.1.2.2 Árboles binarios.
4.1.3 Recorridos en un árbol binario.
4.1.3.1 Preorden.
4.1.3.2 Inorden.
4.1.3.3 Posorden.
4.1.4 Balanceo de árboles binarios.
4.1.5 Clases para la implementación de árboles.
4.2 Grafos.
4.2.1 Definición.
4.2.2 Tipos de grafos.
4.2.3Representación de grafos en memoria.
4.2.4 Clases para la implementación de grafos.

Unidad 4. Estructuras no lineales.
4.1 Árboles.

Definición

Un árbol es una colección de elementos, llamados
nodos, uno de los cuales se distingue con el nombre
de raíz, los cuales mantienen una relación
(parentezco) que define una estructura jerárquica
entre ellos.

Unidad 4. Estructuras no lineales.
4.1Árboles.

Concepto de
 Estructura Jerárquica no lineal, dinámica.
árbol
 Relaciones padre-hijo entre nodos.
 Ejemplos: sistema de archivos, estructura de
un libro, diagrama organizacional, árboles
genealógicos, etc.

Unidad 4. Estructuras no lineales.
4.1 Árboles.

Concepto de
 Un árbol se caracteriza por estar formado por
árbol

un conjunto finito de nodos, conectados por una
serie de aristas,tales que verifican que:
 hay un único nodo especial llamado raíz.
 los nodos restantes se dividen en árboles mas
pequeños llamados subárboles.
 cada nodo, excepto la raíz, tiene un único nodo
padre.
 la definición de árbol implica tener una
estructura recursiva (por la división en
subárboles).
 la representación de los árboles se realiza con
notaciones típicas de los árboles genealógicos.
 hayun único camino desde la raíz hasta cada
nodo.

Unidad 4. Estructuras no lineales.
4.1 Árboles.

Terminología
 Raíz: único nodo sin padre. Ej.: nodo A
básica
 Nodo interno: tiene al menos un hijo. Ej.: nodos
B, F, C
 Nodo hoja (externo): nodo sin hijos. Ej.: nodos E,
I, J, K, G, H, D
 Descendiente directo: hijo.
Ej.: B es descendiente directo de A
 Descendiente: hijo, nieto,
etc…
Ej.: I esdescendiente de F, B y
A
 Subárbol: árbol formado
por
un nodo y sus descendientes.
Ej.: los nodos encerrados en

Unidad 4. Estructuras no lineales.
4.1 Árboles.

Unidad 4. Estructuras no lineales.
4.1 Árboles.

Terminología
 Grado de un nodo: Num. de descendientes
básica
directos. Ej.: el nodo B es grado 2.
 Grado de un árbol: el grado mayor de sus nodos.
Ej.: el nodo A y F son los de mayorgrado (3), por lo
tanto el árbol es grado 3.
 Árbol binario: árbol de grado 2,
cada nodo tiene como mucho dos
descendientes directos.
 Árbol multicamino: árbol
de grado mayor que 2, cada
nodo puede tener n
descendientes directos.

Unidad 4. Estructuras no lineales.
4.1 Árboles.

Terminología
 Profundidad de un nodo: Num. de
básica
predecesores. Ej.: profundidad de A es 0, profundidad
de H es2.
 Altura del árbol: es igual a la profundidad de su
nodo mas profundo + 1. Ej.: la profundidad de I, J y K
que son los nodos mas profundos es 3 por lo tanto la
altura de árbol es 3 + 1 = 4.

Unidad 4. Estructuras no lineales.
4.1 Árboles.

Terminología
 Camino: existe un camino del nodo X al nodo Y, si
básica
existe una sucesión de nodos que permita llegar
desde X hasta Y, su longitud es elnúmero de aristas
que lo conforman.

camino(A,K)= {A, B, F, K}
longitud 3
camino(C,K)= {} no hay
camino

Unidad 4. Estructuras no lineales.
4.1 Árboles.

Recorrido
 Se visita primero la raíz, luego el subárbol
Preorden
izquierdo y por ultimo el subárbol derecho, esto de
manera recursiva para cada subárbol partiendo de la
raíz.

Unidad 4. Estructuras no lineales.
4.1 Árboles.

Recorrido
 Se visitaprimero el subárbol izquierdo, luego la
Inorden
raíz y por ultimo el subárbol derecho, esto de manera
recursiva para cada subárbol partiendo de la raíz.

Unidad 4. Estructuras no lineales.
4.1 Árboles.

Recorrido
 Se visita primero el subárbol izquierdo luego el
Postorden
subárbol derecho y por ultimo la raíz, esto de manera
recursiva para cada subárbol partiendo de la raíz.

Unidad 4....