estructuras no-lineales

Programación II

Mauricio Paletta

Coordinación General de Pregrado

UNIVERSIDAD NACIONAL EXPERIMENTAL DE GUAYANA

INGENIERÍA EN INFORMÁTICA

Programación II

Estructuras de Datos No Lineales

Presentación

Programación II

Definición

Son aquellas que ocupan bloques de

memoria no continuos / lineales. Para lidiar

con el problema de la fragmentación y, sobre

todo del crecimiento dinámico.

Los bloques deben estar enlazados unos con

otros para poder “navegar” por la estructura,

es decir, tener acceso a otro(s) dato(s) a

partir del actual.

Programación II

Definición

Las ventajas de las estructuras lineales son

desventajas en las estructuras no lineales y

viceversa.

Para los enlaces se requiere utilizar

direcciones de memoria / apuntadores.

Dos tipos de estructuras:

1) Listas enlazadas: simples, dobles.

2) Árboles: binarios, genéricos, grafos.

Programación II

Listas enlazadas

Estructura formada por nodos que se enlazan

entre sí partiendo de un nodo inicial cuya

referencia lleva el nombre de cabecera y una

posible referencia al nodo final o cola.

Si cada nodo apunta sólo a su siguiente se

dice que la lista enlazada es simple. Si

también se incluye una referencia al nodo

anterior, entonces la lista enlazada es doble.

Programación II

Listas enlazadas

NOTA: La mejor forma de entender

estructuras enlazadas es manejar el

diagrama de bloques y sus respectivos

enlaces.

Perder o no manejar bien un enlace

provoca la pérdida de información a partir

del bloque correspondiente.

Programación II

Listas enlazadas

Data Data Data…

Cabecera

NULO

Cola

Data Data DataNULO

NULO

CabeceraCola

…

Programación II

Listas enlazadas

Programación II

Listas enlazadas

Programación II

Listas enlazadas

Programación II

Listas enlazadas

Programación II

Listas enlazadas

Programación II

Listas enlazadas

Programación II

Conjunto

Programación II

Grafo

Estructura formada por un conjunto de nodos

o vértices y un conjunto de aristas o lados.

A ser usados por cualquier problema donde

se observa un conjunto de objetos y

conexiones entre ellos: mapa de rutas de

transporte, red de computadoras,

organigrama, diagrama de actividades

/prelaciones, etc.

Programación II

Grafo

Programación II

Grafo

Programación II

Grafo

Programación II

Árboles

Tipo particular de grafo acíclico (sin ciclos)

formada por nodos en la cual cada uno de

ellos puede apuntar a uno o varios otros

nodos.

De forma recursiva, cada nodo puede apuntar

a otro árbol (sub-árbol).

Entre los nodos se establece una relación de

ascendencia / descendencia.

Programación II

Árboles

Nodo padre: nodo que contiene un apuntador

a otros nodos.

Nodo hijo: nodo que es apuntado por otro

nodo.

Nodo raíz: sólo se comporta como padre; él

mismo no tiene padre (no es hijo de nadie).

Nodo hoja: sólo se comporta como hijo; él

mismo no tiene hijos (no es padre de nadie).

Programación II

Árboles

Raíz

Hojas

Subárbol

Hijos /

descendiente

s de B

Padre /

ascendente

de G

Programación II

Árboles

Orden: número potencial de hijos que puede

tener cada nodo.

Grado: número de hijos que tiene el nodo con

más hijos en el árbol.

Nivel de un nodo: nivel de descendencia o

distancia a la raíz. El nivel de la raíz es 0.

Altura: nivel del nodo de mayor nivel.

Programación II

Árboles

Tres tipos de recorridos:

1) Preorden: primero raíz y luego hijos

empezando por hijo izquierdo.

2) Postorden: primero hijos empezando por hijo

izquierdo y luego raíz.

3) Inorden: primero hijo izquierdo, luego raíz y

finalmente el resto de los hijos.

Programación II

Árbol binario

Tipo particular de árbol de orden 2 (todo nodo

tiene un máximo de dos hijos: izquierdo y

derecho).

Programación II

Árbol binario

Programación II

Árbol binario

Programación II

Árbol binario

Un ejemplo muy común es la representación

de expresiones.

Preorden:

* + 1 2 - 3 4

Postorden:

1 2 + 3 4 - *

Inorden:

1 + 2 * 3 - 4

Programación II

Árbol binario

Programación II

Árbol binario

Otro ejemplo es el árbol binario de búsqueda

(para nodos con datos enteros o que

contenga una clave que pueda ser

comparada): para cada nodo, su valor

siempre es mayor que los valores de los

nodos de su descendencia del subárbol

izquierdo y menor que los valores de los

nodos de su descendencia del subárbol

derecho.

Programación II

Árbol binario

Buscar un elemento:

• Si el árbol está vacío el elemento no está.

• Si el elemento coincide con el de la raíz listo.

• Si el elemento es menor que el de la raíz se busca en

el subárbol izquierdo, caso contrario se busca en el

subárbol derecho.

Programación II

Árbol binario

Agregar un elemento:

• Si el elemento está en el árbol no se agrega.

• Si el elemento no está, éste se inserta a continuación

del último nodo visitado en la búsqueda, respetando la

regla de construcción del árbol, a la izquierda o

derecha del nodo dependiendo si el valor a agregar es

menor o mayor respectivamente que el del nodo.

Programación II

Árbol binario

Suprimir un elemento:

• Si el elemento no está en el árbol no se puede

suprimir.

• Si el elemento está y es un nodo hoja se borra

directamente cuidando de que la referencia del nodo

padre correspondiente se anule.

• Si no es un nodo hoja, hay que buscar el nodo más a

la izquierda del subárbol derecho o el más a la

derecha del subárbol izquierdo e intercambiar los

valores con el nodo (eliminación lógica).

• El nodo intercambiado se elimina físicamente.

Programación II

Árbol binario

Programación II

Árbol binario