La asignatura Estructura de Datos es un curso desarrollado

en forma teórica-práctica, que describe las diferentes

formas de organizar y almacenar los datos en la memoria
del computador, de tal forma que pueden ser
posteriormente recuperados y utilizados de manera
eficiente.
PROGRAMACION MODULAR Y
RECURSIVIDAD LISTAS

Manejo de
Tipos de datos Introducción a las Operaciones
memoria estática
abstractos (TDA) listas. sobre listas
y dinámica

Implementación
Definición de Recursividad vs Listas simple y
de listas estáticas
Recursividad Iteratividad doblemente
y dinámicas
enlazadas
usando arreglos.

Implementación
Ejemplos de listas estáticas Ejercicios
Prácticos y dinámicas Prácticos
usando Nodos
 PILAS Y COLAS ÁRBOLES Y COLECCIONES

Introducción a las Operaciones con Conceptos

Pilas. LIFO. Pilas Generales de Arboles binarios
árboles

Algoritmos de
Introducción a la Operaciones con creación,
Arboles
Colas. FIFO. Colas inserción,
multicamino
recorrido y
búsqueda.

Ejemplos Ejercicio práctico

Prácticos Collection
usando árboles.
Tipos de datos abstractos (TDA)
 Tipos de datos abstractos (TDA)

Objetivos
 Entender los conceptos fundamentales de
abstracción, encapsulamiento, modularización y
acoplamiento.
 Entender el concepto de tipo de dato abstracto.
 Conocer las diferentes implementaciones o
herramientas que se utilizan en lenguajes de
programación para alcanzar algunas de las
características de los tipos de datos abstractos.
 Tipos de datos abstractos (TDA)

 Un Tipo de Dato Abstracto (TDA) es un modelo matemático de estructuras

de datos que define valores, operaciones que se pueden realizar sobre esos
datos y los tipos de parámetros de esas operaciones.

 Se denomina abstracto ya que la intención es que quien lo utiliza, no

necesita conocer los detalles de la representación interna o bien el cómo
están implementadas las operaciones.

 El grado de abstracción que provee permite desacoplar al código que usa

un TDA de aquel código que lo implementa.

 El concepto de abstracción nos permite la posibilidad de considerar la

resolución de un problema sin tener en cuenta los detalles por debajo de
cierto nivel.
 Tipos de datos abstractos (TDA)
La Figura muestra un
TDA que consiste en
TDA
una estructura de datos
Estructura de dato abstracto abstracta con
operaciones. Solamente
Operaciones Interfaz
las operaciones son
visibles desde afuera,
pero definen la interfaz.

 Los TADs ponen a disposición del programador un conjunto de objetos

junto con sus operaciones básicas que son independientes de la
implementación elegida.
 El TDA es independiente del lenguaje en el que se quiera implementar, es
decir, que el TDA puede implementarse en cualquier lenguaje de
programación: PASCAL, C, C + +, C#, JAV A, python, etc.
 Conjunto de
operaciones (funciones)
al cual se denomina
interfaz la cual
representa el
comportamiento de un
TDA.

Los TDA son los que

reflejan cierto
comportamiento La parte privada del
organizado en una TDA es la
cierta variedad de implementación la
datos estructurados, cual esta oculta al
En esta forma de programa cliente
almacenar los datos que lo usa.
será característica de
cada TDA.
 Es la simplificación de un
objeto o de un proceso de la
realidad en la que sólo se Destacar los
consideran los aspectos más aspectos
relevantes del
relevantes. objeto

 El objetivo de usar TDA's es Ignorar los aspectos irrelevantes del

conseguir una mayor mismo (la irrelevancia depende del nivel
de abstracción, ya que si se pasa a niveles
abstracción. El código que más concretos, es posible que ciertos
aspectos pasen a ser relevantes).
utiliza el TDA no conoce ni
depende de la implementación
de las operaciones. Aspectos
complementarios.
 Como dijimos un TDA está compuesto por:

 la definición de los valores

 la definición de las operaciones que aplican
sobre esos valores.

 Sabemos que
Encapsulamiento
desacoplan el código cliente de los detalles de la
implementación. Ahora, para lograr el objetivo de la flexibilidad y luego
facilitar los cambios, necesitamos cierta forma de agrupar las
implementaciones de las operaciones en componentes. A esto se lo llama
encapsulamiento.
 El mecanismo concreto para encapsular va a depender del paradigma en el
que estemos trabajando, así como también del lenguaje en particular.
 Por ejemplo, los lenguajes orientados a objetos, proveen naturalmente un
mecanismo para el encapsulamiento, ya que un objeto es justamente una
entidad que contiene tanto el estado como el comportamiento.
 Ocultamiento de la Información
(Information Hiding)
 Muchas veces se confunde
el encapsulamiento con la ocultación de
la información. La diferencia es sutil, pero importante.
 Encapsular, es decir agrupar comportamiento y estado, no necesariamente
significa ocultar. A veces se dice que estamos rompiendo el
encapsulamiento. Lo que está sucediendo es que estamos accediendo a un
detalle de implementación.
 Conceptualmente se refiere a la idea de ocultar detalles de implementación
porque son susceptibles a cambios y no queremos que impacten otras
partes del sistema.
 De nuevo, aquí dependerá del paradigma y del lenguaje el mecanismo a
utilizar para lograr el ocultamiento. Hay lenguajes que permiten definir
visibilidad a sus miembros.
 Al decir privado estamos definiendo que estos miembros solo pueden ser
vistos o accedidos desde las operaciones internas, y no desde "fuera".
 Modularización
 La idea de modularización
se puede pensar como la de ocultamiento y
encapsulamiento, pero a aplicadas a un nivel más amplio o
general de la aplicación.
 Al agruparlos y dividirlos definimos módulos.
 Por ejemplo:
• Módulo de colecciones: provee un conjunto de TDA's para manipular
conjuntos y estructuras de datos como listas, colas, diccionarios, etc.
• Módulo de interfaz de usuario: en mi aplicación podría separar la lógica del
dominio de aquella que modela la interfaz de usuario.
 Lo importante es que sirven para abstraer a otras partes de la aplicación de
decisiones de diseño que podrían sufrir cambios.
 Un módulo es una unidad de
programa donde están
implementados una colección
de recursos que pueden ser
utilizados por uno o más
programas.

Encapsulamiento
Los módulos se compilan por Cuando un programa
separado y se caracterizan por su necesita un recurso importa
interfaz y su implementación. un módulo.

Las bibliotecas no son Dependiendo del lenguaje se

programas, por lo que no importa toda la biblioteca o
pueden ser ejecutadas recursos sueltos.
independientemente.
 Resumiendo
• Encapsulamiento
• Agrupar estado y comportamiento. No necesariamente es ocultamiento de la
información (information hiding).
• En general se refiere a los elementos básicos del paradigma, unidades, como un Tipo,
u objeto. (a diferencia de la idea de módulo)
• Ocultamiento de la información
• Separación entre detalles de implementación de la definición.
• para tener menor impacto ante cambios
• para "proteger" a las otras partes del sistema.
• Modularización
• Ocultar decisiones difíciles de diseño, o aquellas que podrían estar sujetas a cambios.
(lleva a desacoplamiento)
• Involucra el encapsulamiento y el ocultamiento de la información, pero a escalas
mayores. En general un módulo no es una unidad, si no un conjunto de los elementos
del paradigma (un conjunto de funciones, o un conjunto de clases, etc).
• Abstracción
• Acá nos referimos a la idea de simplificar una operación o un concepto modelándola
con los elementos del lenguaje (una función, o un objeto) de modo de:
• poder reutilizarla en diferentes partes del programa, evitando duplicados
• poder encapsular su comportamiento y ocultar la información, para lograr mayor flexibilidad.
Manejo de memoria estática y
dinámica
 Tipos de Memoria
• Contiene al programa Ejecutable
Memoria de mismo
Código

• reservado al inicio del programa,

Memoria de contiene las variables estáticas.
Datos Estáticos

• Gestionada automáticamente,
contiene los contextos para cada
Memoria de función en tiempos de ejecución.
Pila

• manipulable por el programa

para reservar memoria en tiempo
Memoria Heap de ejecución (dinámica).
 Variables y Memoria

 Una variable es un elemento de nuestro programa,

que nos permite representar un dato y manipularlo. El
lenguaje mismo se encarga de asociar el nombre de la
variable con el valor. Y además nos da operaciones
sobre esa variable para manipularlo, por ejemplo para
cambiar ese valor.
 Ahora, este valor, debe estar guardado en algún lado,
si puedo consultarlo y modificarlo. Esto es, en la
memoria.
 Variables y Memoria

Entonces, vamos a tratar de pensar a más bajo

nivel, cómo el lenguaje manipula la memoria
 Variables y Memoria

1
2

resultado

3
 Pasaje de parámetros

A este tipo de pasaje se le

denomina pasaje de parámetros por
valor.

 Acabamos de ver que al retornar de una función, lo que sucede es que se hace
una copia del valor. Es decir que no se devuelve la misma referencia o posición a
memoria, ya que todo el contexto que contiene todo lo que se reservó dentro
de la función, se descarta.
 Al momento de ingresar a la función, se crea un nuevo contexto reservando
memoria con referencias propias a los parámetros (más allá de que en este caso
tengan el mismo nombre que las variables del main, no tienen nada que ver).
 Además de reservar los slots, se copiaron los valores (línea punteada).
Acá vemos que ya los valores pasan a ser independientes. Si dentro de la función
se altera el valor de "costo", estaríamos alterando el valor de esa posición de
memoria, y no de la que está apuntada por la variable costo que está "fuera".
 Punteros

Las variables que contienen

direcciones a memoria, se
denominan de tipo puntero.

 C provee transparencia en el uso y manipulación de la memoria.

 Toda variable tiene una dirección de memoria la cual podemos
obtener programáticamente (es decir desde el mismo programa)
 Las direcciones de memoria se pueden almacenar a su vez en
variables.
 Dada una dirección de memoria, podemos acceder a su contenido o
modificarlo.
Punteros

& Obtener la
dirección de
una variable

* Acceder al
valor
referenciado
 Casos de uso comunes de punteros

 Pasaje por referencia.-Para esto

se utilizando punteros. En lugar
de pasar la variable como
parámetro, pasamos su
dirección de memoria. Con ésta,
la función podrá alterar el
contenido/valor.
 Memoria Dinámica

•En la cual cada programa tiene

que explícitamente pedir más
memoria cuando la necesita, pero
también encargarse de liberarla
Gestión cuando no la necesita más. Pedir memoria: malloc()
Manual Liberar memoria: free()

•En la cual se utiliza un modelo o

convención, que permite al
lenguaje ejecutar los pedidos de
más memoria y la liberación, y
evita que nosotros tengamos que
Gestión hacerlo en nuestro programa en
Automática forma explícita.
 Gestión Manual en Lenguaje C

 La función malloc definida en stdlib.h permite reservar memoria

de un tamaño dado.
 Reserva la cantidad de memoria especificada por parámetro.
 Retorna la dirección de la porción de memoria que reservó. Es
decir que retorna un puntero.
 Gestión Manual en Lenguaje C
La llamada a malloc podría "fallar"
si por algún motivo el sistema operativo no puede darle la cantidad de
memoria especificada a nuestro programa. Cuando esto sucede malloc
retorna NULL.

Ejemplo
Gestión Manual en Lenguaje C
 Gestión Manual en Lenguaje C
Realloc
Esta función se utiliza para, dado un espacio de memoria, del cual tenemos un
puntero a él, redimensionarlo, ya sea para hacerlo más chico o más grande.

 Recibe el puntero a redimensionar y el nuevo tamaño. Y retorna un puntero a la

dirección de memoria del nuevo tamaño
 Por qué retorna un puntero ? Porque internamente la función quizás
deba reubicar el segmento a una nueva dirección.
 Los casos posibles serían:
 Si se intenta "agrandar" el espacio: y hay lugar contiguo, se mantendrá el
mismo puntero.
 si las posiciones de memoria contiguas ya están utilizadas, la función va a:
 alocar otra sección nueva por el tamañano "nuevo"
 copiar el contenido de la anterior (es decir que mantiene el contenido)
 liberar la porción anterior que ya no necesitamos.
 Si no hay memoria suficiente devolverá NULL (como ya vimos en malloc)
 Si se intenta "achicar" el espacio, simplemente va a liberar la sección "extra" de
memoria para uso futuro.
 Gestión Automática de Memoria
Ciertos lenguajes (Java, Python, LISP, etc.)
liberan automáticamente la memoria que no se sigue utilizando.

El mecanismo clásico de gestión implícita de memoria es el que se denomina garbage

collector .
 Durante la ejecución del programa, cuando se crea un nuevo objeto (digo objeto en sentido
abstracto. Podría ser un número, un string, un caracter, etc), se va a reservar un sector de
memoria para almacenarlo, automáticamente. El programador no necesita saber cuánto
espacio ocupa dicho objeto.
 Estos objetos son referenciados por variables. Que de una forma transparente para nosotros
referencian al valor. Sin que sepamos ni podamos acceder a la dirección de memoria ni nada
por el estilo.
 Cuando uno de estos objetos deja de ser referenciado (es decir que no hay ninguna variable
activa que lo esté referenciando), pasan a ser detectados por el garbage collector, quien va
a liberar el sector de memoria que ocupaban.

Hay dos técnicas de liberación automática de memoria:

 uso de contadores de referencia (Reference Counting)
 técnicas de marcado.
 Gestión Automática de Memoria
Reference Counting
Cada bloque lleva un contador de los punteros que le apuntan. Cada vez que se hace una
asignación a un puntero, se decrementa el contador del bloque al que apuntaba y se incrementa
el contador del nuevo bloque. Cuando el contador vale cero, el bloque se libera.

 tenemos dos bloques de memoria, el

primero está apuntado por p y q y el
segundo por r

 Si se produce la asignación q:=r, la

situación cambia a:

 Tras la asignación p:= q, el contador del

primer bloque se anula y podemos
liberarlo:
 Gestión Automática de Memoria
Reference Counting
El problema de los contadores de referencia es que no
pueden liberar correctamente estructuras circulares.
Imaginemos que tenemos una lista circular:

Si hacemos que p apunte a NIL, nos encontramos con que las

cuentas de los bloques no se anulan, aunque sean inaccesibles:
 Gestión Automática de Memoria
Técnicas de marcado.

Con las técnicas de marcado, cada cierto tiempo se detiene la ejecución del
programa de usuario y se ejecuta una rutina que marca todos los bloques
como “libres” para, a continuación, recorrer todos los punteros del programa
para ir marcando como “utilizados” los bloques apuntados; finalmente, los
bloques que han quedado marcados como “libres” se liberan.

El principal problema de estas técnicas es que si no se implementan con

suficiente eficiencia, la detención periódica del programa puede resultar muy
molesta para el usuario.
Se puede aliviar el problema en parte mediante el empleo de threads
paralelos que se encarguen del marcado y liberación.

De todas formas, la implementación eficiente es muy compleja.

 A B
2 3
Datos Primitivos
Int a =2; stack
Int b = 3; A B
A = b; 3 3
B=4;
A B
3 4
Bart Simpson
heap
12FF
Persona1 Persona2
stack
12FF 12FF

Homero Simpson
heap
12FF
Persona1 Persona2
stack
12FF 12FF
Definición de Recursividad
 Recursividad

Un método es recursivo
cuando entre sus
instrucciones se
encuentra una llamada a
sí mismo.
• La solución iterativa es fácil de
entender. Utiliza una variable para
acumular los productos y obtener la
solución.
• En la solución recursiva se realizan
llamadas al propio método con
valores de n cada vez más pequeños
para resolver el problema.
Recursividad

Cada vez que se Un método recursivo

Cada llamada supone debe contener:
produce una nueva
hacerlo a un método
llamada al método se • Uno o más casos base:
diferente, copia del
crean en memoria de casos para los que existe
original, que se ejecuta una solución directa.
nuevo las variables y
y devuelve el resultado • Una o más llamadas
comienza la ejecución
a quien lo llamó. recursivas: casos en los
del nuevo método.
que se llama sí mismo
Recursividad
SI n=4 entonces
Factorial(4) retorna = 4* factorial(3)
n =4*6
= 24
SI n=3 entonces
n-1 Factorial(3) retorna = 3 * factorial(2)
=3*2
=6
SI n=2 entonces
n-2 Factorial(2) retorna = 2 * factorial(1)
=2*1
=2
n-3 SI n=1 entonces
Factorial(1) retorna = 1 * factorial(O)
=1*1
=1
n-4
SI n=O entonces Factorial(O) retorna =1
 Recursividad

• Las soluciones recursivas suelen ser

más lentas que las iterativas por el
tiempo empleado en la gestión de las
Para medir la eficacia de un algoritmo sucesivas llamadas a los métodos.
recursivo se tienen en cuenta tres factores: • Consumen más memoria ya que se
•Tiempo de ejecución guardan los contextos de ejecución
•Uso de memoria de cada método que se llama.
•Legibilidad y facilidad de comprensión • La recursividad conduce a soluciones
que son mucho más fáciles de leer y
comprender que su correspondiente
solución iterativa. En estos casos una
mayor claridad del algoritmo puede
compensar el coste en tiempo y en
ocupación de memoria.
 La recursividad y la pila de llamadas a métodos
A
Fibonacci(3)

B
E Fibonacci(1)
Fibonacci(2)

C D
Return 1
Fibonacci(1) Fibonacci(0)

Return 1 Return 0 1) 2) 3) 4)
Parte Parte Parte Parte
Superior de Superior de Superior de Superior de
la Pila la Pila la Pila la Pila

Llamada al Llamada al Llamada al Llamada al

método A, método C, método D, método E,
número = 3 número = 1 número = 0 número = 1

Llamada al Llamada al Llamada al

método B, método B, método A,
número = 2 número = 2 número = 3

Llamada al Llamada al
método A, método A,
número = 3 número = 3
Ejemplos Prácticos
Tipos de datos abstractos (TDA)

Clase: Esfera
atributos
->radio
Métodos
C=2.π.r Constructor (r)
Perímetro
Área
volumen
Tipos de datos abstractos (TDA)
Tipos de datos abstractos (TDA)
Tipos de datos abstractos (TDA)
Struct: Un struct en C es una forma
de agrupar miembros, es decir
variables, bajo un mismo nombre.
DEFINICIÓN: USO:

MÉTODOS:
Tipos de datos abstractos (TDA)
TypeDef: En C podemos definir tipos
como alias a otros tipos. Es decir, definir otro
nombre para un tipo ya existente.
DEFINICIÓN:

EJEMPLO SIN TYPEDEF:

Tipos de datos abstractos (TDA)
EJEMPLO CON TYPEDEF:
Listas enlazadas: simples y dobles
Listas enlazadas: simples y dobles
Una clase autorreferenciada contiene una variable de instancia que hace referencia a
otro objeto del mismo tipo de clase.
Listas enlazadas: simples y dobles
Una lista enlazada es una colección lineal
(es decir, una secuencia) de objetos de una clase autorreferenciada, conocidos como
nodos, que están conectados por enlaces de referencia; es por ello que se utiliza el
término lista “enlazada”.

 Una lista enlazada es apropiada cuando el número de elementos de datos que se

van a representar en la estructura de datos es impredecible.
 Un arreglo puede declararse de manera que contenga más elementos que el
número de elementos esperados, pero esto desperdicia memoria. Las listas
enlazadas proporcionan una mejor utilización de memoria en estas situaciones. Las
listas enlazadas permiten al programa adaptarse a las necesidades de
almacenamiento en tiempo de ejecución.
 La inserción en una lista enlazada es rápida; sólo hay que modificar dos referencias
(después de localizar el punto de inserción). Todos los objetos nodo existentes
permanecen en sus posiciones actuales en memoria.
 Las listas enlazadas pueden mantenerse en orden con sólo insertar cada nuevo
elemento en el punto apropiado de la lista. Los elementos existentes en la lista no
necesitan moverse.
Listas enlazadas: simples y dobles
 Por lo general, los elementos de un arreglo están contiguos en memoria. Esto
permite un acceso inmediato a cualquier elemento del arreglo, ya que la dirección
de cualquier elemento puede calcularse directamente como su desplazamiento a
partir del inicio del arreglo.
 Las listas enlazadas no permiten dicho acceso inmediato a sus elementos; para
acceder a ellos se tiene que recorrer la lista desde su parte inicial.
 Clase Lista
 Nodo primerNodo
 Nodo ultimoNodo
 Constructor
 insertarAlFrente
 insertarAlFinal
 eliminarDelFrente
 eliminarDelFinal
 estaVacia
Listas enlazadas: simples y dobles
Insertar al Frente
Listas enlazadas: simples y dobles
Insertar al Final
Listas enlazadas: simples y dobles
EliminarDelFrente.
Listas enlazadas: simples y dobles
Recorrer una lista.
Listas enlazadas: simples y dobles
Insertar en una lista.
Listas enlazadas: simples y dobles
Enlace doble en una lista.

En una lista de doble enlace se agrega una segunda referencia al nodo

previo, lo que permite recorrer la lista en ambos sentidos, y en general se
implementa con una referencia al primer elemento y otra referencia al
último elemento.
Listas enlazadas: simples y dobles
Listas Circulares
Pilas
Pilas

 Una pila (stack) es una colección

ordenada de elementos a los que
sólo se puede acceder por un único
lugar o extremo de la pila.
 Los elementos de la pila se añaden
o quitan (borran) de la misma sólo
por su parte superior (cima) de la
pila.

 Las entradas de la pila deben ser eliminadas

en el orden inverso al que se situaron en la
misma. Por ejemplo, se puede crear una pila
de libros, situando primero un diccionario,
encima de él una enciclopedia y encima de
ambos una novela de modo que la pila tendrá
la novela en la parte superior.
Pilas

 Debido a su propiedad específica

“último en entrar, primero en
salir” se conoce a las pilas como
estructura de datos LIFO (last-
in/first-out).

 La pila se puede implementar

guardando los elementos en un
arreglo en cuyo caso su dimensión
o longitud es fija.

 La implementación consiste en construir una lista enlazada, cada elemento de la

pila forma un nodo de la lista; la lista crece o decrece según se añaden o se
extraen, respectivamente, elementos de la pila; ésta es una representación
dinámica y no existe limitación en su tamaño excepto la memoria de la
computadora.
Pila implementada con una lista enlazada

 Las operaciones que sirven para

definir una pila y poder manipular
su contenido son las siguientes:
 CrearPila
 Insertar (push)
 Quitar (pop)
 Pila vacía
 Limpiar
 CimaPila
 Tamaño de la pila

 La implementación consiste en
construir una lista enlazada, cada
elemento de la pila forma un nodo de la
lista; la lista crece o decrece según se
añaden o se extraen, respectivamente,
elementos de la pila; ésta es una
representación dinámica y no existe
limitación en su tamaño excepto la
Colas
Colas

 Una cola es una estructura de

datos que almacena elementos en
una lista y permite acceder a los
datos por uno de los dos extremos
de la lista.
 Un elemento se inserta en la cola
(parte final) de la lista y se suprime
o elimina por el frente (parte
inicial, frente) de la lista.
 Las aplicaciones utilizan una cola
para almacenar elementos en su
orden de aparición o concurrencia.
Colas

 Los elementos se eliminan (se quitan) de la cola en el mismo orden en que se

almacena, por ello una cola es una estructura de tipo FIFO (first-in/first-out, primero
en entrar-primero en salir o bien primero en llegar-primero en ser servido).

 Una cola es una estructura de datos cuyos elementos mantienen un cierto orden,
tal que sólo se pueden añadir elementos por un extremo, final de la cola, y eliminar
o extraer por el otro extremo, llamado frente.
Cola implementada con una lista enlazada

 La implementación del TAD Cola con una lista enlazada permite ajustar el tamaño
exactamente al número de elementos de la cola;
 la lista enlazada crece y decrece según las necesidades, según se incorporen
elementos o se retiren.
 Utiliza dos apuntadores (referencias) para acceder a la lista, frente y fin, que son
los extremos por donde salen y por donde se ponen, respectivamente, los
elementos de la cola.
 La referencia frente apunta al primer elemento de la lista y por tanto de la cola (el
primero en ser retirado). La referencia fin apunta al último elemento de la lista y
también de la cola.
Arboles
Árboles

Los árboles son una de las estructuras de datos

no lineales más utilizada.
Sirve para representar estructuras de
información jerárquicas y direcciones o etiquetas
de una manera organizada.

 Organizar tablas de símbolos en compiladores

 Representar tablas de decisión
 Asignar bloques de memoria de tamaño variable
 Ordenar
 Buscar
 Solucionar juegos Los árboles permiten representar situaciones
 Probar teoremas de la vida diaria como son:

 organización de una empresa

 árbol genealógico de una persona
 organización de torneos deportivos
Árboles

Para dar una definición clara de árbol,

podríamos decir que un árbol es un
conjunto finito A de uno o más nodos tal
que:

 Existe un nodo especial llamado la raíz

del árbol

 Los nodos restantes están

particionados en m > 0 conjuntos
disjuntos A1,...,Am y cada uno de estos
conjuntos es a su vez un árbol.
o Un árbol tiene una definición  Los árboles A1,...,Am son llamados
recursiva. subárboles de la raíz
o La forma más común de representar  Cualquier nodo es la raíz de un subárbol
a los árboles es por medio de un que consiste de él y los nodos debajo de
grafo con la raíz hacia arriba. él.
Árboles
 Cada vértice o nodo del árbol puede
tener un nombre y puede tener una
información asociada; un arco es una
conexión entre dos vértices.

 Un camino en un árbol es una lista de

vértices diferentes en los que vértices
sucesivos están conectados por arcos
en el árbol. Una propiedad que define a
los árboles es que existe exactamente
un camino entre la raíz y cada uno de
los otros nodos en el árbol.

 Los nodos de un árbol pueden dividirse

en niveles; el nivel de un nodo es el
número de nodos en el camino de él a la
raíz. La altura de un árbol es el nivel
máximo de todos los nodos en el árbol,
es decir, la distancia máxima de la raíz a
cualquier nodo.
Árboles
 La longitud de un camino es el número de
nodos del camino menos uno. Por tanto, hay
un camino de longitud cero de cualquier
nodo a si mismo.

 Se dice que un nodo Y está abajo de un nodo

X, si X está en el camino de Y a la raíz.
Además, cada nodo, excepto la raíz, tiene
exactamente un nodo arriba de él, que es
llamado su padre; los nodos que están
exactamente abajo de él son llamados sus
hijos. Los hijos de un nodo específico se
llaman hermanos. Un nodo sin hijos se llama
nodo hoja.

 El número de hijos que cuelgan de un nodo

es llamado el grado del nodo. El grado de un
árbol es el grado máximo de los nodos del
árbol. Un nodo de grado cero es llamado
hoja, es decir, no tiene hijos.
Árboles Binarios
Los árboles cuyos nodos contienen dos
enlaces (uno de los cuales puede ser null) se
les conoce como árboles binarios.

Características:

 El nodo raíz es el primer nodo en un árbol.

 Cada enlace en el nodo raíz hace

referencia a un hijo. El hijo izquierdo es el
primer nodo en el subárbol izquierdo
(también conocido como el nodo raíz del
subárbol izquierdo), y el hijo derecho es el
primer nodo en el subárbol derecho
(también conocido como el nodo raíz del
subárbol derecho).
Árboles Binarios
Recorridos

El modo evidente de moverse a través de las

ramas de un árbol es siguiendo los punteros
(referencias), del mismo modo en que nos
movíamos a través de las listas.

Esos recorridos dependen en gran medida

del tipo y propósito del árbol, pero hay
ciertos recorridos que usaremos
frecuentemente. Se trata de aquellos
recorridos que incluyen todo el árbol.
Repertorio de Operaciones :
Hay tres formas de recorrer un árbol
 Añadir o insertar elementos. completo, y las tres se suelen implementar
 Buscar o localizar elementos. mediante recursividad. En los tres casos se
 Borrar elementos. sigue siempre a partir de cada nodo todas las
 Moverse a través del árbol. ramas una por una.
 Recorrer el árbol completo.
Árboles Binarios

Recorrido Pre-orden:

En este tipo de recorrido, el valor del

nodo se procesa antes de recorrer
las ramas:

void RecorrerArbol (NodoDeArbol a)

{
if (a == NULL) return;
Procesar(dato);
RecorrerArbol([Link]);
RecorrerArbol([Link]);
}
Árboles Binarios

Recorrido In-orden:

En este tipo de recorrido, el valor del

nodo se procesa después de recorrer
la primera rama y antes de recorrer la
última. Esto es muy útil en arboles
ordenados.

void RecorrerArbol (NodoDeArbol a)

{
if (a == NULL) return;
RecorrerArbol([Link]);
Procesar(dato);
RecorrerArbol([Link]);
}
Árboles Binarios

Recorrido Post-orden:

En este tipo de recorrido, el valor del

nodo se procesa después de recorrer
todas las ramas:

void RecorrerArbol (NodoDeArbol a)

{
if (a == NULL) return;
RecorrerArbol([Link]);
RecorrerArbol([Link]);
Procesar(dato);
}
Árboles Ordenados
Un árbol ordenado, en general,
es aquel a partir del cual se puede obtener una secuencia ordenada siguiendo uno de los
recorridos posibles del árbol: inorden, preorden o postorden.

En estos árboles es importante que la secuencia se mantenga ordenada aunque se

añadan o se eliminen nodos.

Existen varios tipos de árboles ordenados, que veremos a continuación:

 árboles binarios de búsqueda (ABB): son árboles de orden 2 que mantienen una
secuencia ordenada si se recorren en inorden.
 árboles AVL: son árboles binarios de búsqueda equilibrados, es decir, los niveles de
cada rama para cualquier nodo no difieren en más de 1.
 árboles perfectamente equilibrados: son árboles binarios de búsqueda en los que el
número de nodos de cada rama para cualquier nodo no difieren en más de 1. Son por
lo tanto árboles AVL también.
 árboles 2-3: son árboles de orden 3, que contienen dos claves en cada nodo y que
están también equilibrados. También generan secuencias ordenadas al recorrerlos en
inorden.
 árboles-B: caso general de árboles 2-3, que para un orden M, contienen M-1 claves.
Árboles Binarios
Operaciones:

1. Comprobar si un árbol está vacío.

Un árbol está vacío si su raíz es NULL.

2. Calcular el número de nodos.

Tenemos dos opciones para hacer esto, una es llevar siempre la cuenta de nodos en
el árbol al mismo tiempo que se añaden o eliminan elementos. La otra es,
sencillamente, contarlos.
Para contar los nodos podemos recurrir a cualquiera de los tres modos de recorrer
el árbol: inorden, preorden o postorden, como acción sencillamente incrementamos
el contador.

3. Comprobar si el nodo es hoja.

Esto es muy sencillo, basta con comprobar si tanto el árbol izquierdo como el
derecho están vacíos. Si ambos lo están, se trata de un nodo hoja. O marcar con una
propiedad bolean en verdadero cuando el nodo es insertado y como falso cuando se
inserta un nodo hijo.
Árboles Binarios

Operaciones

5. Buscar un nodo.
• Empezamos con el nodo auxiliar apuntando a Raíz.
• Si el valor del nodo auxiliar es igual al del elemento que buscamos,
terminamos la búsqueda y retornamos el valor del nodo.
• Si el valor del nodo raíz es mayor que el elemento que buscamos,
continuaremos la búsqueda en el árbol izquierdo.
• Si el valor del nodo raíz es menor que el elemento que buscamos,
continuaremos la búsqueda en el árbol derecho.
6. Calcular el camino hacia un nodo x
Lo que haremos es buscar el nodo del que queremos averiguar su camino. Cada
vez que avancemos un nodo guardamos el valor del nodo.
7. Calcular el nivel de un nodo
8. Calcular la altura de un árbol
9. Calcular la longitud de un nodo
10. Una función de devuelve si un nodo X esta debajo de un nodo Y
Árboles Binarios
ELIMINAR UN NODO

Caso 1 (Borrar un Nodo sin hijos) :

Caso 2 (Borrar un Nodo con un subárbol hijo) :

Árboles Binarios
ELIMINAR UN NODO

Caso 3 (Borrar un Nodo con dos subárboles hijos) :

1. Tomar el hijo derecho del Nodo

que queremos eliminar

2. Recorrer hasta el hijo más a la

izquierda ( hijo izquierdo y si
este tiene hijo izquierdo repetir
hasta llegar al último nodo a la
izquierda)
Árboles Binarios
ELIMINAR UN NODO

Caso 3 (Borrar un Nodo con dos subárboles hijos) :

3. Reemplazamos el valor del nodo

que queremos eliminar por el nodo
que encontramos ( el hijo más a la
izquierda )

El nodo que encontramos por ser el

más a la izquierda es imposible que
tenga nodos a su izquierda pero si
que es posible que tenga un
subárbol a la derecha
Árboles Binarios
ELIMINAR UN NODO

Caso 3 (Borrar un Nodo con dos subárboles hijos) :

4. Para terminar solo nos queda

proceder a eliminar este nodo de las
formas que conocemos ( caso 1,
caso 2 ) y tendremos la eliminación
completa.
Expresiones Lambda
Expresiones Lambda
DEFINICION:

Una expresión lambda

puede entenderse como
una representación
concisa de una función
anónima que se puede Anonymous Function
transmitir: no tiene un
nombre, pero tiene una
lista de parámetros, un
cuerpo, un tipo de retorno
y posiblemente una lista de
excepciones.
Passed
Concise
around
Expresiones Lambda
DEFINICION: •Es anónimo porque no tiene un
nombre explícito como un
•ES función porque una lambda
no está asociada con una clase en
método normalmente tendría particular como lo está un
método.
Una expresión lambda •Pero como un método, una
lambda tiene una lista de
parámetros, un cuerpo, un tipo
puede entenderse como de retorno y una posible lista de
excepciones
una representación
concisa de una función Anonymous Function
anónima que se puede
transmitir: no tiene un
nombre, pero tiene una •una expresión lambda puede
pasarse como argumento a un
•no es necesario que escribas
mucho código repetitivo como lo
lista de parámetros, un método o almacenarse en una
variable
haces para las clases anónimas

cuerpo, un tipo de retorno

y posiblemente una lista de
excepciones.
Passed
Concise
around
Expresiones Lambda
COMPONENTES:

A list of
parameters

An arrow

The body of
the lambda
Expresiones Lambda
COMPONENTES:
Expresiones Lambda
SYNTAXIS:
Expresiones Lambda
Expresiones Lambda
EJEMPLOS:
Interfaces Funcionales
Interfaces Funcionales
QUE ES ?
Interfaces Funcionales
Para recordar.
 Las expresiones Lambda solo se
pueden usar donde se espera una
interfaz funcional!
 Las expresiones Lambda le permiten
proporcionar la implementación del
método abstracto de una interfaz
funcional directamente en línea y
tratar la expresión completa como
una instancia de una interfaz
funcional
Interfaces Funcionales

Interfaces funcionales comunes de java 8

BinaryOperator
Predicate <T> Function <T, R> Supplier <T> Consumer <T>
<T>
Interfaces Funcionales

Interfaces funcionales comunes de java 8

Stream
Stream

Definición
Un Stream es una secuencia de elementos que provienen de una fuente y soporta
operaciones de procesamiento de datos.
Stream

Características
El Api de Stream nos permite crear código:
1. En forma declarativa
2. Es más conciso
3. Podría procesarse en paralelo
Stream
Comparación
Programación Estructurada

Programación Funcional
Stream
Librería

1.-la lista de alumnos la

convertimos en un flujo
de datos mediante la
llamada al método
2.-utilizamos un método stream.
que se puede aplicar a
los streams que es filtro
y pasándole una 3.- después lo coleccionamos a una lista.
expresión lambda le
decimos qué
condiciones son las que
tienen que aplicar sobre
los datos que vienen en
ese stream. 4.- después podemos imprimir la lista
Stream
Ejercicios:
Crear una clase para el menú de un restaurant y llenarlo.
1.-Mediante programación funcional devolver (tipo, nombre, No Calorías y si es
vegetariano) los platos que tienen menos de 350 calorías.

Menu
Nombre Es vegetariano Calorias Tipo
Cerdo No 800 Carne
Res No 700 Carne
Pollo No 400 Carne
Papas Fritas Si 530 Otros
Arroz Si 350 Otros
Jugo Frutas Si 120 Otros
Pizza Si 550 Otros
Salmon No 300 Pescado
Corvina No 450 Pescado
Stream
Iteración externa e interna

llamamos a una iteración externa cuando un programador escribe de forma

explícita algún bucle como por ejemplo un Do While, for , etc.
Sin embargo la programación funcional nos permite acceder a los elementos
Alumno sin el uso de iteraciones.

Al usar filter o forEach por ejemplo, no escribimos ningún ciclo con el cual se
realizará una iteración para aplicar una condición o instrucción como imprimir.
De esto se encarga solita la máquina virtual de Java a partir de su versión 8.
Entonces lo que se hace mediante filter en streams se le conoce como una iteración
interna.
Stream
Operaciones Intermedias y Terminales

1.- Con map me voy a ayudar para hacer una transformación dentro de mi stream; es
decir filter lo que me devuelve es una stream de alumnos y yo al final necesito nada
más conocer el nombre de los alumnos que cumplen la condición ingresada en
filter. Entonces para esa transformación utilizó map y ahora le tengo que decir qué
tarea realizar, y para cada elemento del stream y es colocar el nombre de la clase y
con:: acceder al método que retorna el nombre.

Nota: Alumno::getNombre es una forma reducida de las expresiones lambda y se

conoce como referencia a un método.

2.- ForEach también recibe una expresión lambda reducida, ya que invoca al método
println de la clase System.
Stream
Operaciones Intermedias y Terminales

 Tanto filter como map se les conoce en Java como operaciones intermedias.
 A la operación ForEach se le conoce como una operación terminal.

Todos aquellos métodos terminales que vayas a incorporar dentro de tu

programación siempre los vas a colocar al final.

La ayuda de Java también te

indica cuando u método o
acción es una operación
terminal.
Stream
+ Operaciones Intermedias

 Limit, es una operación intermedia que nos ayuda a limitar la cantidad de datos
que recibimos del método anterior.

 skip, es una operación intermedia que después de descartar los primeros n

elementos; esos elementos los especificamos con el número que le pasamos al
método como parámetro; retorna los restantes.
Stream
+ Operaciones terminales

 Count, es una operación

terminal que devuelve
la cantidad de
elementos que tiene el
flujo de stream.
Stream
+ Operaciones terminales
 anyMatch.- retorna true o false, si algún elemento del stream cumple una
condición dada con una expresión lambda.
Stream
+ Operaciones terminales
allMatch.- retorna true o false, si todos los elementos del stream cumplen una
cierta condición.
Stream
Test
Stream
Test
Stream
Test
Stream
Test
Stream
Test
Stream
El método Collect
• Es una operación terminal
• Se invoca sobre un stream
• Lanza una operación de reducción
• La operación de reducción queda definida por métodos de la clase
Collectors.

Los métodos de la clase Collectors ofrecen 3 funcionalidades principales:

1. Reducir y resumir los elementos de un stream a un solo valor

2. Agrupar elementos
3. Particionar elementos
Stream
El método maxBy
Stream
El método maxBy
Stream
El método maxBy
Stream
El método summingInt
Stream
El método summingInt
Stream
El método summarizingInt
Stream
El método summarizingInt
Stream
Operación terminal Collector
Test
Stream
Operación terminal Collector
Test
Stream
Resumen
Cuales son las interfaces funcionales incluidas en el paquete
[Link]?
Stream
Resumen
Cuales son las interfaces funcionales incluidas en el paquete
[Link]?

Las interfaces
funcionales difieren
principalmente en
función de la firma del
método abstracto que
utilizan.
Stream
Resumen
Un predicate prueba la condición dada y devuelve verdadero o falso;
por lo tanto, tiene un método abstracto llamado “test" que toma un
parámetro de tipo genérico T y devuelve el tipo booleano?
Stream
Resumen
Realice un ejercicio usando Predicate para validar si dada un string, la misma es null y si
no esta vacía.
Stream
Resumen
Realice un ejercicio usando Predicate para validar si dada un string, la misma es null y si
no esta vacía.
Stream
Resumen
Un consumidor "consumer" consume un objeto y no devuelve nada;
por lo tanto, tiene un método abstracto llamado “-----------------" que
toma un argumento de tipo genérico T y tiene un tipo de retorno
_______________.
Stream
Resumen
Un consumidor "consumer" consume un objeto y no devuelve nada;
por lo tanto, tiene un método abstracto llamado “accept" que toma un
argumento de tipo genérico T y tiene un tipo de retorno void.

Realice un ejercicio usando Consumer para imprimir un string dado en mayúsculas.

Stream
Resumen
Un consumidor "consumer" consume un objeto y no devuelve nada;
por lo tanto, tiene un método abstracto llamado “accept" que toma un
argumento de tipo genérico T y tiene un tipo de retorno void.

Realice un ejercicio usando Consumer para imprimir un string dado en mayúsculas.

Stream
Resumen
Una Function "opera" en el argumento y devuelve un resultado; por lo
tanto, tiene un método abstracto llamado ……………….. que toma un
argumento de tipo genérico T y tiene un tipo de devolución
……………………
Stream
Resumen
Una Function "opera" en el argumento y devuelve un resultado; por lo
tanto, tiene un método abstracto llamado apply que toma un argumento
de tipo genérico T y tiene un tipo de devolución genérico R

Realice un ejercicio usando Function para imprimir la longitud de un string dado.

Stream
Resumen
Una Function "opera" en el argumento y devuelve un resultado; por lo
tanto, tiene un método abstracto llamado apply que toma un argumento
de tipo genérico T y tiene un tipo de devolución genérico R

Realice un ejercicio usando Function para imprimir la longitud de un string dado.

Stream
Resumen
Un Supplier "suministra" no hace nada más que devolver algo; por lo
tanto, tiene un método abstracto llamado …………….. que
……………………y devuelve un tipo …………………………….
Stream
Resumen
Un Supplier "suministra" no hace nada más que devolver algo; por lo
tanto, tiene un método abstracto llamado "get" que no toma argumentos
y devuelve un tipo genérico T.

Realice un ejercicio usando Supplier para imprimir la fecha y tiempo actual

([Link]()).
Stream
Resumen
Un Supplier "suministra" no hace nada más que devolver algo; por lo
tanto, tiene un método abstracto llamado "get" que no toma argumentos
y devuelve un tipo genérico T.

Realice un ejercicio usando Supplier para imprimir la fecha y tiempo actual

([Link]()).
Stream
Resumen
Las interfaces integradas Predicate, Consumer, Function y Supplier
funcionan en objetos de tipo de referencia. Para los tipos primitivos,
hay especializaciones disponibles para los tipos …………, ………..
y …………… para estas interfaces funcionales.
Stream
Resumen
Las interfaces integradas Predicate, Consumer, Function y Supplier
funcionan en objetos de tipo de referencia. Para los tipos primitivos,
hay especializaciones disponibles para los tipos int, long y double
para estas interfaces funcionales.
Stream
Resumen
• Cuando la interfaz Stream se usa con tipos primitivos, resulta en
un …………. y ……………. innecesarios de los tipos primitivos a
sus tipos de contenedor. Esto da como resultado un código más
…………… y desperdicia ………………………. porque se crean
los objetos envoltorios innecesarios.

Por lo tanto, siempre que sea posible, prefiera usar las

especializaciones de tipo primitivo de las interfaces funcionales
Predicate, Consumer, Function y Supplier.
Stream
Resumen
• Cuando la interfaz Stream se usa con tipos primitivos, resulta en
un boxing y unboxing innecesarios de los tipos primitivos a sus
tipos de contenedor. Esto da como resultado un código más
lento y desperdicia memoria porque se crean los objetos
envoltorios innecesarios.
Por lo tanto, siempre que sea posible, prefiera usar las
especializaciones de tipo primitivo de las interfaces funcionales
Predicate, Consumer, Function y Supplier.
Stream
Resumen
• Las versiones primitivas de las interfaces funcionales ………….,
………………, ………………… y ……………….. están
disponibles solo para tipos int, long y double (y tipo boolean
además de estos tres tipos para …………………).

Debe usar conversiones implícitas a la versión ……………

relevante cuando necesite usar char, byte o tipos cortos; de manera
similar, puede usar la versión para …………………… tipo cuando
necesite usar float.
Stream
Resumen
• Las versiones primitivas de las interfaces funcionales Predicate,
Consumer, Function y Supplier están disponibles solo para tipos
int, long y double (y tipo boolean además de estos tres tipos
para Supplier).

Debe usar conversiones implícitas a la versión int relevante cuando

necesite usar char, byte o tipos cortos; de manera similar, puede
usar la versión para doble tipo cuando necesite usar float.
Stream
Test
Stream
Test
Stream
Test
Stream
Test