Download Estructuras de datos

Teoría y Aplicación de la Informática I
Definiciones
Tipos de datos
 Un tipo de dato determina el conjunto de valores al que pertenece
una constante, o que puede tomar una variable o expresión, o que
pueden ser generados por un operador o función
 También determina el conjunto de operaciones que se puede
aplicar al conjunto de valores
Cardinalidad
 El número de valores distintos que pertenecen a un tipo T se llama
cardinalidad de T
 La cardinalidad proporciona una medida de la cantidad de memoria
que se necesita para representar una variable x de tipo T
_____________________________________________________________________
Estructuras de datos
1
Teoría y Aplicación de la Informática I
Tipos de Datos Elementales
Son tipos atómicos, sin estructura interna
 Tipos elementales normalizados, estándar o predefinidos
o Comprenden típicamente:
 los números enteros (integer)
 los números fraccionarios (real)
 los valores lógicos, falso y verdadero (boolean)
 caracteres de escritura (char)
o Incorporan un conjunto adecuado de operadores elementales.
Entre ellos son muy importantes, y en general se aplican a
todos los tipos de datos:
 Comprobación de igualdad:
x=y
 Asignación a una variable x: x := y
El tipo integer
o Comprende un subconjunto de los enteros, cuyo tamaño varía
de computador a computador
o Todas las operaciones con datos de este tipo son exactas
o El proceso de cálculo se interrumpe cuando aparece un
resultado que está fuera del conjunto de números
representables en el computador
o Operadores normalizados:
 +
  *
 div (división entera)
 mod (resto de la división entera)
_____________________________________________________________________
Estructuras de datos
2
Teoría y Aplicación de la Informática I
El tipo real
o Designa un subconjunto de los números reales
o En la aritmética de tipo real se permite una cierta imprecisión,
dentro de los límites del error de redondeo producido por el
cálculo con un número finito de dígitos
o Operadores normalizados:
 +
  *
 /
El tipo boolean
o Sus dos valores correspondientes son: true y false
o Operadores:
 u or
 o and
  o not
(unión lógica)
(conjunción lógica)
(negación lógica)
El tipo char
o Comprende el conjunto de caracteres imprimibles
o El código ASCII es el más ampliamente admitido
o En general se puede asumir que:
 Contiene las 26 letras del alfabeto latino, los 10 dígitos
de la numeración árabe y signos de puntuación
 Contiene un carácter blanco o espacio
_____________________________________________________________________
Estructuras de datos
3
Teoría y Aplicación de la Informática I
 Tipos elementales definidos por el usuario
Enumeración
o Definido por enumeración del conjunto de todos los posibles
valores
type T = (c1, c2, …, cn)
card (T) = n
o Ejemplos:
type forma = (rectángulo, cuadrado, elipse, círculo)
card (forma) = 4
var f: forma
f := rectángulo
type color = (rojo, amarillo, verde)
card (color) = 3
var c: color
c := verde
Subrango
o Útil cuando una variable puede tomar valores de cierto tipo en
un intervalo específico
type T = min .. max
o Ejemplo:
type año = 1900 .. 1999
card (año) = 100
var a: año
r := 1998
_____________________________________________________________________
Estructuras de datos
4
Teoría y Aplicación de la Informática I
Tipos de Datos Estructurados
 Se definen nuevos tipos de datos en función de otros definidos
previamente
 Los valores de los tipos estructurados son usualmente
agrupaciones de valores componentes de los tipos constituyentes
definidos previamente
 Si solamente hay un tipo constituyente, esto es, si todos los
componentes son del mismo tipo, entonces éste se denomina tipo
base. Este es el caso de un array
 Como los tipos constituyentes, a su vez, pueden también ser
estructurados, pueden construirse jerarquías de estructuras. Los
componentes últimos de una estructura deben ser atómicos
 La cardinalidad de un tipo estructurado es el producto de las
cardinalidades de sus componentes
 Tipos de Datos Estructurados Estáticos
o Son las estructuras más básicas:
 arreglo o array
 registro o record
 fichero secuencial
o Son estáticos en la memoria
 Tipos de Datos Estructurados Dinámicos
o Estructuras más complicadas:
 Pila o stack
 Cola o queue
 lista enlazada o linked list
 árbol o tree
 grafo
o Son generadas dinámicamente durante la ejecución del
programa, y pueden variar de tamaño y de forma
_____________________________________________________________________
Estructuras de datos
5
Teoría y Aplicación de la Informática I
La Estructura Array
 Estructura homogénea, todos sus componentes son del mismo
tipo base
 Estructura de acceso aleatorio, todos sus componentes pueden
seleccionarse arbitrariamente y son igualmente accesibles
 La definición de un tipo array T especifica tanto un tipo base T0
como un tipo índice Ti.
type T = array [ Ti ] of T0
Ejemplo:
type Fila = array [1..5] of real
var x: Fila
Operaciones con los arrays
o Asignación mediante un constructor
x := T (c1, c2, … ,cn)
Ejemplo : x := Fila (0.5, 0.25, 0.125, 0.0625, 0.03125)
o Selección de un componente individual del array
x [i]
Ejemplo:
Fila [2]
o Asignación o actualización selectiva
x [i] := y
Ejemplo:
Fila [2] := 0.003
 Cardinalidad de un array T = array [ Ti ] of T0
card(T) = (card(T0)) card(Ti)
Ejemplo :
card(Fila) = (card(real)) 5
_____________________________________________________________________
Estructuras de datos
6
Teoría y Aplicación de la Informática I
 Los elementos constituyentes de un array pueden estar a su vez
estructurados
 Una variable de tipo array cuyos componentes son también arrays
se denomina matriz
Ejemplos:
M: array [1..10] of Fila
M: array [1..10] of array [1..5] of real
M: array[1..10, 1..5] of real
card (M) = (card (real)) 50
 M[i][j], o bien M[i, j] designa el componente j de la fila M[i], que es el
componente i de M
 Un array puede ser definido de n-dimensiones ampliando los
conceptos y definiciones directamente
Ejemplo:
N: array [1..10, 1..5, 1..2, 1..3] of real
var multi: N;
multi [3, 3, 3, 3] := 3
card (N) = (card (real)) 300
_____________________________________________________________________
Estructuras de datos
7
Teoría y Aplicación de la Informática I
La Estructura Registro
 Un registro es una colección de información relativa a una entidad
particular
 Un campo es un ítem o elemento de datos elementales. Está
caracterizado por su tipo de datos
 Un registro es una colección de campos lógicamente relacionados,
que pueden ser tratados como una unidad por un programa
 Los registros organizados en campos se denominan registros
lógicos.
 Un registro físico o bloque es la cantidad más pequeña de datos
que pueden transferirse en una operación de entrada/salida
 Un registro lógico puede ocupar menos de un registro físico, un
registro físico o más de un registro físico
 Un archivo o fichero es una colección de registros relacionados
entre sí y organizados para un propósito específico
 La cardinalidad del tipo estructurado registro es el producto de las
cardinalidades de los tipos componentes
 El tipo registro T se define de la forma siguiente:
type T =
record
s1: T1;
s2: T2;
…
sn: Tn
end
card (T) = card (T1) * card (T2) * … * card (Tn)
_____________________________________________________________________
Estructuras de datos
8
Teoría y Aplicación de la Informática I
Ejemplos :
type Fecha =
record
día : 1..31 ;
mes : 1..12 ;
año :1..2500
end
type Persona = record
nombre: array [1 .. 40] of char;
apellido: array [1 .. 40] of char;
nacimiento: Fecha ;
sexo: (masculino, femenino) ;
estadocivil: (soltero, casado, viudo)
end
 Ahora se pueden declarar las variables
var f : Fecha
var p : Persona
Operaciones con los registros
o Asignación mediante un constructor
x := T (x1, x2, …, xn)
donde los xi son valores de los tipos constituyentes Ti.
Ejemplos :
f := Fecha (4, 5, 1978)
p := Persona (‘Carlos’, ‘Acosta’, Fecha(10, 4, 1997),
masculino, soltero)
o Selección de un campo del registro
x.si
Ejemplos:
f.dia
p.nombre
p.estadocivil
_____________________________________________________________________
Estructuras de datos
9
Teoría y Aplicación de la Informática I
o Actualización o asignación a un campo de un registro
x.si := xi
donde xi es un valor o expresión de tipo Ti
Ejemplos:
f.mes := 10
p.nombre := ‘Juan’
p.nacimiento.año := 1991
Programa que muestra como utilizar las variables
registro
El siguiente programa tiene por objeto contar el número de personas,
representadas por la variable array personas, que son
simultáneamente femeninas y solteras
var personas: array [1..N] of Persona
contador, i: integer
contador := 0
for i := 1 to N do
if ((personas[i].sexo = femenino) and
(personas [i].estadocivil = soltero)) then
contador := contador + 1
end if
end for
Variante con la instrucción with
var personas: array [1..N] of Persona
contador, i: integer
contador := 0
for i := 1 to N do
with persona[i] do
if ((sexo = femenino) and (estadocivil = soltero)) then
contador := contador + 1
end if
end with
end for
_____________________________________________________________________ 10
Estructuras de datos
Teoría y Aplicación de la Informática I
Listas Ordenadas
 Ejemplos:
o Los días de la semana
(Domingo, Lunes, Martes, Miércoles, Jueves, Viernes, Sábado)
o Los valores de los naipes
(2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, As)
 Una lista ordenada puede estar vacía, o puede ser escrita como:
(a1, a2, a3, …, an)
donde ai son átomos de un conjunto S
 Operaciones que pueden ser ejecutadas en las listas ordenadas:
o
o
o
o
o
Encontrar la longitud, n, de la lista
Leer la lista de izquierda a derecha, o de derecha a izquierda
Recuperar el i-ésimo elemento, 1 i n
Almacenar un nuevo valor en la i-ésima posición, 1 i n
Insertar un nuevo valor en la posición i, 1 i n+1, causando
que los elementos numerados i, i+1, …, n tengan la
numeración i+1, i+2, …, n+1
o Borrar el elemento de la posición i, 1 i n, causando que los
elementos numerados i+1, i+2, …, n tengan la numeración i,
i+1, …, n-1
 Una manera de implementar una lista ordenada, es utilizando un
array, asociando el elemento de la lista ai con el índice i del array
_____________________________________________________________________ 11
Estructuras de datos
Teoría y Aplicación de la Informática I
Tipo Abstracto o Abstracción
 Una abstracción se caracteriza por un conjunto de operadores
definido por el programador
 Su representación consiste de:
o Declaración de las variables cuyos valores definen un estado
del tipo
o Declaración de los procedimientos o funciones que
implementan las operaciones del tipo
o Código de inicialización
 Este tipo de mecanismo está disponible en varios Lenguajes de
Programación de Alto Nivel
_____________________________________________________________________ 12
Estructuras de datos
Teoría y Aplicación de la Informática I
 Los tipos Abstractos o Abstracciones se definen así:
type class-name = abstracción
variable declarations
procedure P1 (…)
begin
…
end
procedure P2 (…)
begin
…
end
.
.
.
procedure Pn (…)
begin
…
end
begin
código de inicialización
end
 Si queremos definir una variable A del tipo class-name:
var A: class-name
 Para ejecutar cualquiera de la operaciones:
A.P1 (…)
A.P2 (…)
.
.
.
A.Pn (…)
_____________________________________________________________________ 13
Estructuras de datos
Teoría y Aplicación de la Informática I
 Ejemplo:
Se define el tipo abstracto árbol
type árbol = abstracción
var altura: integer
procedure REGAR_Y_CRECER ()
begin
altura := altura + 1
end
procedure ABONAR_Y_CRECER ()
begin
altura := altura + 2
end
procedure IMPRIMIR_ALTURA_ÁRBOL ()
begin
print (altura)
end
begin
altura := 2
end
Se declara una variable de tipo árbol
var mi_árbol: árbol
_____________________________________________________________________ 14
Estructuras de datos
Teoría y Aplicación de la Informática I
Se ejecutan los procedimientos en un fragmento de un
programa
.
.
.
mi_árbol.IMPRIMIR_ALTURA_ÁRBOL ()
mi_árbol.ABONAR_Y_CRECER ()
mi_árbol.IMPRIMIR_ALTURA_ÁRBOL ()
mi_árbol.REGAR_Y_CRECER ()
mi_árbol.IMPRIMIR_ALTURA_ÁRBOL ()
mi_árbol.ABONAR_Y_CRECER ()
mi_árbol.REGAR_Y_CRECER ()
mi_árbol.IMPRIMIR_ALTURA_ÁRBOL ()
.
.
.
La salida del fragmento del programa es:
.
.
.
2
4
5
8
.
.
.
_____________________________________________________________________ 15
Estructuras de datos
Teoría y Aplicación de la Informática I
Pilas (Stacks)
 Una pila es una lista ordenada en la cual todas las inserciones y
eliminaciones se hacen en un extremo, llamado tope (top)
 Sea la pila S = (a1, a2, …, an)
o a1 es el elemento que está en el fondo de la pila
o ai se encuentra por encima del elemento ai-1, 1 i n
 Si un stack se carga con los elementos A, B, C, D, E, en ese orden,
entonces el primer elemento a ser eliminado es E
E
D
C
B
A
 El último elemento que fue insertado en la pila, es el primero que
debe salir. Por este motivo las pilas son llamadas listas LIFO (Last
In, First Out)
_____________________________________________________________________ 16
Estructuras de datos
Teoría y Aplicación de la Informática I
Ejemplo del Uso de Pilas en la solución de problemas
relacionados con la computación
Procesamiento de las llamadas a subrutinas y sus retornos
 Tenemos un procedimiento principal y tres rutinas
 Los retornos se deben hacer en orden inverso a las llamadas
 Entonces, las direcciones de retorno se van almacenando en una
pila, y cada vez que termina una ejecución se retorna a la dirección
indicada en el tope de la pila
_____________________________________________________________________ 17
Estructuras de datos
Teoría y Aplicación de la Informática I
Operaciones con las Pilas
 ADD (item, stack)  stack
Inserta item en stack, y devuelve el stack modificado
 DELETE (stack)  stack
Elimina el elemento del tope de stack, y devuelve el stack
modificado
 TOP (stack)  item
Devuelve el ítem ubicado en el tope de stack. No modifica stack
 ISEMPTY (stack)  boolean
Devuelve ‘true’ si stack está vacío, y “false” en caso contrario
Implementación de una pila
Supongamos que utilizamos un lenguaje que admite la definición de
tipos por medio de abstracción. Entonces, podríamos definir el tipo
stack así:
type stack = abstracción
const N = 1000
var top: integer
var s: array [1..N] of integer
procedure ADD (item)
begin
if top  N then
call STACK_FULL
else
top := top + 1
s [top] := item
end if
end
_____________________________________________________________________ 18
Estructuras de datos
Teoría y Aplicación de la Informática I
procedure DELETE ()
begin
if top  0 then
call STACK_EMPTY
else
top := top – 1
end if
end
procedure TOP ()
begin
if TOP = 0 then
return (error)
else
return (s [top])
end if
end
procedure ISEMPTY ()
begin
if top = 0 then
return (true)
else
return (false)
end if
end
begin { inicialización }
top := 0
end
Si queremos usar esta definición:
var p: snack
begin
p.ADD (1)
p.ADD (2)
p.ADD (3)
p.DELETE()
print (p.TOP())
end
_____________________________________________________________________ 19
Estructuras de datos
Teoría y Aplicación de la Informática I
Colas (Queues)
 Una cola es una lista ordenada en la cual todas las inserciones se
hacen en un extremo, el final (rear), mientras que las eliminaciones
se hacen en el otro extremo, el frente (front)
 Sea la cola S = (a1, a2, …, an)
o a1 es el elemento que está al frente de la cola
o an es el elemento que está al final de la cola
o ai+1 se encuentra atrás del elemento ai, 1 i n
 La cola requiere que el primer elemento que se inserta sea el
primero que se saque. Por esto, son conocidas como listas FIFO
(First In, First Out)
Ejemplo del Uso de Colas en la solución de problemas
relacionados con la computación
Planificación del procesador
 Cada vez que un proceso está listo para ejecutarse, se incorpora al
final de una cola de Listos (ready queue)
 El CPU scheduler selecciona el proceso que está al frente de la
cola de Listos para asignarle la CPU
_____________________________________________________________________ 20
Estructuras de datos
Teoría y Aplicación de la Informática I
Operaciones con las Colas
 ADDQ (item, queue)  queue
Inserta item al final de la cola, y devuelve la cola modificada
 DELETEQ (queue)  queue
Saca el elemento que está al frente de la cola, y devuelve la cola
modificada
 FRONT (queue)  item
Devuelve el elemento que está al frente de la cola sin modificarla
 ISEMPTYQ (queue)  boolean
Devuelve ‘true’ si la cola está vacía, y ‘false’ en caso contrario
Implementación de una Cola
Para implementar la cola usando arrays se necesita:
o Un array de una dimensión
o Las variables front y rear
o Vamos a adoptar la convención de que front apunta a una
posición antes del comienzo real de la cola, y rear apunta al
último elemento de la cola
o Inicialmente front = rear = 0
o La cola está vacía cuando front = rear
Podemos definir la cola como sigue:
const N = 1000
var front, rear: integer
var Q: array [1..N] of integer
front := 0
rear := 0
_____________________________________________________________________ 21
Estructuras de datos
Teoría y Aplicación de la Informática I
procedure ISEMPTYQ (Q)
begin
if front = rear then
return (true)
else
return (false)
end if
end
procedure FRONT (Q)
begin
if ISEMPTYQ (Q) then
return (error)
else
return (Q [front + 1])
end if
end
procedure ADDQ (item, Q, N, rear)
begin
if rear = N then
call QUEUE_FULL
else
rear := rear + 1
Q [rear] := item
end if
end
procedure DELETEQ (Q, front, rear)
begin
if front = rear then
call QUEUE_EMPTY
else
front := front + 1
end if
end
¿Por qué esta implementación (o representación) de las colas no
es eficiente?
_____________________________________________________________________ 22
Estructuras de datos
Teoría y Aplicación de la Informática I
Una representación más eficiente de la cola se consigue haciendo
que el vector Q sea circular
o El vector Q tiene índices que van de 0 a N-1
o Cuando rear = N-1, el próximo elemento entraría a Q(0), si
ese lugar está vacío
o front apunta una posición antes del primer elemento de Q
o La cola está vacía cuando front = rear
o Inicialmente, front = rear = 0
Ejercicio: Re-escribir los procedimientos anteriores considerando
Q como vector circular
*Hay dos posibilidades:
- Usar solo N-1 posiciones del vector
front = rear  cola vacía
front = (rear + 1) mod n  cola llena
- Usar las N posiciones del vector
front = rear  cola llena y/o vacía
Usar una bandera para distinguir entre cola llena y vacía
_____________________________________________________________________ 23
Estructuras de datos
Teoría y Aplicación de la Informática I
Listas Enlazadas (Linked Lists)
 En los arrays, y las pilas y colas implementadas con arrays,
estuvimos utilizando el mapeamiento secuencial, o listas
contiguas, en las que los elementos son adyacentes en la memoria
 Consideremos la siguiente lista ordenada de palabras en inglés
que terminan con AT:
(BAT, CAT, EAT, FAT, HAT, JAT, LAT, MAT, OAT, PAT, RAT,
SAT, TAT, VAT, WAT)
 Queremos insertar la palabra GAT entre FAT y HAT, y también
eliminar la palabra LAT
 Usando listas contiguas necesitaremos mover elementos de la
lista un lugar para arriba o para abajo
 Una lista enlazada es un conjunto de nodos en los que cada nodo
apunta al siguiente nodo de la lista
 Un nodo se estructura en campos
 Los campos pueden ser de:
o Datos: DATA1, DATA2, etc
o Enlace: LINK1, LINK2, etc. Estos apuntan al siguiente nodo
de la lista (contienen la dirección del siguiente nodo de la
lista)
 Cada nodo de una lista enlazada debe tener al menos un campo
DATA y un campo LINK
 El último nodo de la lista tiene LINK = 0
 Los nodos de una lista enlazada se pueden almacenar en
posiciones de memoria que no son consecutivas
_____________________________________________________________________ 24
Estructuras de datos
Teoría y Aplicación de la Informática I
En la siguiente figura, los elementos de la lista están almacenados en
un array unidimensional llamado DATA. El array LINK almacena
punteros a los elementos del array DATA. F es un apuntador a la lista
enlazada y tiene valor 8, porque la lista comienza con BAT, que está
en DATA (8)
F=8
Representación gráfica de las listas enlazadas
_____________________________________________________________________ 25
Estructuras de datos
Teoría y Aplicación de la Informática I
Pasos para insertar GAT entre FAT y HAT
o Conseguir un nodo libre, sea X su dirección
o Poner en el campo DATA de ese nodo el valor GAT
o Poner en el campo LINK de ese nodo el valor del campo
LINK de FAT (el cual apunta a HAT)
o Poner en el campo LINK de FAT el valor X
En la siguiente figura se ven los arrays DATA y LINK después de
agregar GAT
Con la representación de listas enlazadas tenemos:
_____________________________________________________________________ 26
Estructuras de datos
Teoría y Aplicación de la Informática I
Pasos para eliminar el nodo que contiene GAT
o Identificar el nodo que precede al nodo cuyo campo DATA es
GAT (en este caso el nodo cuyo campo DATA es FAT)
o En el campo LINK del nodo identificado se debe poner el
valor que tiene el campo LINK del nodo cuyo campo DATA es
GAT
o Marcar el nodo eliminado como libre
Operaciones con las listas enlazadas
Primero definimos dos funciones auxiliares:
 GETNODE (X): devuelve un puntero X a un nodo libre, y si no hay
nodos libres, emite un mensaje de error y para
 RET(X): retorna el nodo X a la memoria
A continuación se definen procedimientos para insertar y eliminar
elementos de una lista enlazada
INSERT
 Sea T un puntero a una lista enlazada
 T = 0 si la lista no tiene nodos
 Sea X un apuntador a un nodo arbitrario de la lista T
 El siguiente algoritmo inserta un nodo con el campo DATA = item, a
continuación del nodo apuntado por X
_____________________________________________________________________ 27
Estructuras de datos
Teoría y Aplicación de la Informática I
procedure INSERT (T, X, item)
call GETNODE (I)
DATA (I) := item
if T = 0 then
T := I
LINK (I) := 0
else
LINK (I) := LINK (X)
LINK (X) := I
end if
end
DELETE
 Sea X un puntero a un nodo arbitrario de la lista enlazada T
 Sea Y el nodo que precede a X. (Y = 0 si X es el primer nodo en T,
esto es si X = T)
 El algoritmo siguiente suprime el nodo X de T
procedure DELETE (X, Y, T)
if Y = 0 then
T := LINK (T)
else
LINK (Y) := LINK (X)
end if
call RET (X)
end
_____________________________________________________________________ 28
Estructuras de datos
Teoría y Aplicación de la Informática I
Árboles (Trees)
Ejemplo
Definición
Un árbol es un conjunto finito de uno o más nodos, tal que,
o existe un nodo llamado raíz,
o el resto de los nodos están particionados en n 0 conjuntos
disjuntos T1, T2, …, Tn, donde cada uno de estos conjuntos
es, a su vez, un árbol. T1, T2, …, Tn se llaman subárboles
de la raíz
_____________________________________________________________________ 29
Estructuras de datos
Teoría y Aplicación de la Informática I
Terminología
 El nodo representa el o los ítems de información más las ramas a
los otros nodos. En la figura tenemos 13 nodos, A, B, C, …, M. La
raíz es A.
 El grado es el número de subárboles de un nodo. El grado de A es
3, de C es 1, de F es 0.
 Los nodos hojas o nodos terminales son los nodos que tienen
grado 0. {K, L, F, G, M, I, J} constituye el conjunto de nodos hojas.
 Los nodos no terminales son los nodos que no son hojas. Por
ejemplo, H es un nodo no terminal.
 Padres e Hijos: las raíces de los subárboles de un nodo X, son los
hijos de X. X es el padre de sus hijos.
Ejemplo: los hijos de D son, H, I, J; el padre de D es A.
 Los hijos de un mismo padre son hermanos.
Ejemplo: H, I, J son hermanos.
 El grado de un árbol es el máximo grado de los nodos del árbol.
El árbol de la figura tiene grado 3.
_____________________________________________________________________ 30
Estructuras de datos
Teoría y Aplicación de la Informática I
 Los antepasados de un nodo son todos los nodos a lo largo del
camino que va desde la raíz hasta el nodo en cuestión.
Ejemplo: los antepasados de M son A, D, H.
 El nivel de un nodo se define, estableciendo inicialmente la raíz a
nivel 1. Si un nodo está en el nivel l, sus hijos están en el nivel l+1.
En la figura se señala el nivel de todos los nodos del árbol.
 Altura o profundidad de un árbol: es el máximo nivel de sus
nodos. El árbol de la figura tiene altura 4.
 Una floresta es un conjunto de n 0 árboles disjuntos. Si retiramos
la raíz de un árbol, obtenemos una floresta. En la figura, si
eliminamos A tenemos una floresta con 3 árboles.
Representación en memoria
Si queremos usar listas enlazadas, cada nodo tendrá un número
variable de campos LINK, dependiendo del número de ramas
DATA LINK 1 LINK 2 … LINK n
_____________________________________________________________________ 31
Estructuras de datos
Teoría y Aplicación de la Informática I
Árboles Binarios
Definición
Un árbol binario es un conjunto finito de nodos, que está vacío,
o:
o hay un nodo llamado raíz
o el resto de los nodos está particionado en dos conjuntos
disjuntos T1 y T2 tal que T1 y T2 son árboles binarios. T1 es
el subárbol izquierdo y T2 el subárbol derecho.
Diferencias entre los árboles y los árboles binarios
 Los árboles binarios no tienen ningún nodo con grado mayor que 2
 Existe el árbol binario vacío (sin ningún nodo), pero no existe el
árbol con cero nodos
 Los dos árboles binarios que aparecen abajo son distintos
_____________________________________________________________________ 32
Estructuras de datos
Teoría y Aplicación de la Informática I
Tipos especiales de árboles binarios
Árbol asimétrico (con asimetría izquierda)
Árbol binario completo
_____________________________________________________________________ 33
Estructuras de datos
Teoría y Aplicación de la Informática I
Propiedades
 El número máximo de nodos en el nivel i de un árbol binario es 2i-1,
i1
 El número máximo de nodos en un árbol binario de profundidad k
es 2k -1, k  1
 Para cualquier árbol binario no vacío, si n0 es el número de hojas
(nodos con grado 0) y n2 el número de nodos de grado 2, entonces
n0 = n2 + 1
Representación
Cada nodo tendrá tres campos
HIJO IZQ DATO HIJO DER
_____________________________________________________________________ 34
Estructuras de datos
Teoría y Aplicación de la Informática I
Ejemplos de Representación
Representación del Árbol asimétrico (con asimetría izquierda)
Representación del Árbol binario completo
_____________________________________________________________________ 35
Estructuras de datos
Teoría y Aplicación de la Informática I
Recorrido del árbol binario
Existen tres ordenamientos principales, que surgen de la forma natural
de los árboles, con los que se puede procesar o visitar los nodos de un
árbol. Ellos son: Orden
Pre-orden
Post-orden
Supongamos que tenemos la representación de árbol de la expresión
( ( A / ( B ** ( - C ) ) ) * D + E )
Recorrido en Orden
1- Recorrer el subárbol izquierdo en Orden
2- Visitar la raíz
3- Recorrer el subárbol derecho en Orden
Si consideramos que visitar corresponde a la operación print
tendremos:
A / B ** - C * D + E
que es la notación convencional infija, aunque sin los paréntesis que
se necesitan para aclarar las precedencias
_____________________________________________________________________ 36
Estructuras de datos
Teoría y Aplicación de la Informática I
Recorrido en Pre-orden
1- Visitar la raíz
2- Recorrer el subárbol izquierdo en Pre-orden
3- Recorrer el subárbol derecho en Pre-orden
Si al visitar vamos imprimiendo tendremos:
+ * / A ** B – C D E
que es la notación prefija de la expresión
Recorrido en Post-orden
1- Recorrer el subárbol izquierdo en Post-orden
2- Recorrer el subárbol derecho en Post-orden
3- Visitar la raíz
Si al visitar vamos imprimiendo tendremos:
A B C - ** / D * E +
que es la notación postfija de la expresión
_____________________________________________________________________ 37
Estructuras de datos
Teoría y Aplicación de la Informática I
Grafos
Definición y terminología
 Un grafo G consiste de dos conjuntos:
o V: conjunto finito y no vacío de vértices
o E: conjunto de pares de vértices llamados lados
V(G) representa el conjunto de vértices del grafo G
E(G) representa el conjunto de lados del grafo G
G = (V, E) representa un grafo
 En un grafo dirigido cada lado es representado por un par
ordenado <v1, v2>. v1 es la cola y v2 la cabeza del lado. Por lo
tanto <v1, v2> y <v2, v1> representan dos lados diferentes
 En un grafo no dirigido los pares de vértices que representan un
lado no son pares ordenados, así que (v1, v2) y (v2, v1)
representan el mismo lado
o
o
o
o
o
o
o
G1 y G2 son grafos no dirigidos. G3 es un grafo dirigido
V(G1) = {1, 2, 3, 4}
E(G1) = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}
V(G2) = {1, 2, 3, 4, 5, 6, 7}
E(G2) = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7)}
V(G3) = {1, 2, 3}
E(G3) = {<1, 2>, <2, 1>, <2, 3>}
_____________________________________________________________________ 38
Estructuras de datos
Teoría y Aplicación de la Informática I
 Si (v1, v2) o <v1, v2> son lados de un grafo, entonces v1 v2
 Como E(G) es un conjunto, un grafo no puede tener múltiples
ocurrencias del mismo lado. Si se saca esta restricción se tiene un
multigrafo
 Ejemplo de multigrafo
 Un subgrafo de G es un grafo G’ tal que V(G’)  V(G) y
E(G’)  E(G)
 Ejemplos de subgrafos de G3
 Un camino del vértice vp al vértice vq en un grafo G es una
secuencia de vértices
vp, vi1, vi2, …, vin, vq
tal que (vp, vi1), (vi1, vi2), …, (vin, vq) son lados incluidos en E(G)
 Si (vi, vj) es un lado en E(G), entonces vi y vj son adyacentes y el
lado (vi, vj) es incidente en los vértices vi y vj
_____________________________________________________________________ 39
Estructuras de datos
Teoría y Aplicación de la Informática I
Representación de Grafos
Matriz de Adyacencia
 Sea G = (V, E) un grafo con n vértices, n 1
 La matriz de adyacencia de G es un arreglo A de n x n con la
propiedad de que:
o A(i, j) = 1 si y solo si (vi, vj) (<vi, vj> para un grafo dirigido) está
en E(G)
o A(i, j) = 0 si no existe ese lado en G
 Ejemplos
Matriz de adyacencia de G1
Matriz de adyacencia de G3
 La matriz de adyacencia de un grafo no dirigido es siempre
simétrica, pues el lado (vi, vj) está en E(G) si el lado (vj, vi) también
está en E(G)
 La matriz de adyacencia de un grafo dirigido no necesita ser
simétrica
 Los 1 en la fila i nos dan los lados que salen del vértice i y los unos
en la columna j nos dan los lados que llegan al vértice j
_____________________________________________________________________ 40
Estructuras de datos
Teoría y Aplicación de la Informática I
Listas de Adyacencia
 Las n filas de la matriz de adyacencia se representan por n linked
list
 Existe una lista por cada vértice en G
 Los nodos de la lista i representan los vértices a los cuales se
puede llegar desde el vértice i
 Ejemplos
Lista de adyacencia de G1
Lista de adyacencia de G3
_____________________________________________________________________ 41
Estructuras de datos
Teoría y Aplicación de la Informática I
Bibliografía
 WIRTH, Niklaus, Algoritmos + Estructuras de Datos
Programas, Madrid, Ediciones del Castillo, 1980, pp. 4 – 22.
=
 HOROWITZ, Ellis y SAHNI, Sartaj, Fundamentos de Estruturas
de Dados, 2da ed., Río de Janeiro, Editora Campus LTDA, 1986,
pp. 47 – 49, 77 – 85, 101 – 106, 197 – 211, 252 – 259.
 JOYANES AGUILAR, Luis, Fundamentos de Programación.
Algoritmos y Estructura de Datos, 2da ed., Madrid, McGraw-Hill,
1996, pp. 204 – 220, 260 – 264, 385 – 426, 439 – 455, 466 – 473.
_____________________________________________________________________ 42
Estructuras de datos