Sesión 15_Mg Orleans Gálvez Tapia

Vista previa del material en texto

ANÁLISIS DE ALGORITMOS Y 
ESTRATEGIAS DE PROGRAMACIÓN
Docente: 
Mg. Gálvez Tapia Orleans Moisés
CIP. 171497
UNIDAD 1: 
LA COMPLEJIDAD ALGORÍTMICA Y 
PRINCIPALES ESTRATEGIAS DE 
PROGRAMACIÓN
SEMANA 15: Árboles Binarios
 
¿Qué entiende por 
árbol binario de 
búsqueda?
SABERES PREVIOS
AGENDA:
1. Árbol binario
2. Inserción de un nuevo nodo
3. Poblar árbol binario
4. Recorrido de un árbol binario en pre-orden
5. Recorrido de un árbol binario en entre-orden
6. Recorrido de un árbol binario en post-orden
7. Referencias Bibliográficas
LOGRO DE LA SESIÓN
Al término de la clase, el estudiante implementa algoritmos en Java que 
permitan administrar un árbol binario de búsqueda, demostrando 
dominio del lenguaje y un lógica coherente.
Ej. Analicemos si se trata de un árbol binario ordenado:
Para el nodo que tiene el 50
¿Los nodos del subárbol izquierdo son todos menores a 50? 8, 25, 30 Si
¿Los nodos del subárbol derecho son todos mayores a 50? 70 Si
Para el nodo que tiene el 25
¿Los nodos del subárbol izquierdo son todos menores a 25? 8 Si
¿Los nodos del subárbol derecho son todos mayores a 25? 30 Si
Un árbol es binario si para cada nodo
del árbol, los nodos ubicados a la
izquierda son inferiores al que
consideramos raíz para ese momento y
los nodos ubicados a la derecha son
mayores que la raíz (no existe nodos
repetidos).
25
308
70
50
ÁRBOL BINARIO
Recorrer: Pasar a través del árbol enumerando cada uno de sus nodos una vez.
Visitar: Realizar algún procesamiento del nodo
Pre-orden
- Visitar la raíz.
- Recorrer el subárbol izquierdo en pre-orden.
- Recorrer el subárbol derecho en pre-orden.
Entre-orden
- Recorrer el subárbol izquierdo en entre-orden.
- Visitar la raíz.
- Recorrer el subárbol derecho en entre-orden.
Post-orden
- Recorrer el subárbol izquierdo en post-orden.
- Recorrer el subárbol derecho en post-orden.
- Visitar la raíz.
RECORRIDOS EN ÁRBOLES BINARIOS
PRINCIPALES ALGORITMOS EN ÁRBOLES BINARIOS
PRINCIPALES ALGORITMOS EN ÁRBOLES BINARIOS
400
* *
raiz
null
nuevo
PRINCIPALES ALGORITMOS EN ÁRBOLES BINARIOS
auxanterior
null
300
* *
nuevo
PRINCIPALES ALGORITMOS EN ÁRBOLES BINARIOS
aux
anterior
300
* *
nuevo
PRINCIPALES ALGORITMOS EN ÁRBOLES BINARIOS
aux
anterior
300
* *
nuevo
PRINCIPALES ALGORITMOS EN ÁRBOLES BINARIOS
aux
anterior
300
* *
nuevo
PRINCIPALES ALGORITMOS EN ÁRBOLES BINARIOS
300
* *
nuevo
anterior
aux
null
PRINCIPALES ALGORITMOS EN ÁRBOLES BINARIOS
300
* *
nuevo
anterior
aux
null
PRINCIPALES ALGORITMOS EN ÁRBOLES BINARIOS
90
* *
nuevo
auxanterior
null
OTRO EJEMPLO DE INSERCIÓN DE UN NODO (90)
90
* *
nuevo
aux
anterior
OTRO EJEMPLO DE INSERCIÓN DE UN NODO (90)
90
* *
nuevo
aux
anterior
OTRO EJEMPLO DE INSERCIÓN DE UN NODO (90)
90
* *
nuevo
aux
anterior
OTRO EJEMPLO DE INSERCIÓN DE UN NODO (90)
90
* *
nuevo
anterior
aux
OTRO EJEMPLO DE INSERCIÓN DE UN NODO (90)
90
* *
nuevo
anterior
aux
null
OTRO EJEMPLO DE INSERCIÓN DE UN NODO (90)
El orden de impresión de la información es:
400 - 100 - 50 - 75 - 200 - 700
private void recorrerPre (Nodo raiz)
{
if (raiz!= null)
{
System.out.print(raiz.info + " ");
recorrerPre (raiz.izq);
recorrerPre (raiz.der);
}
}
ALGORITMO PARA RECORRER EL ÁRBOL EN PRE-ORDEN
El orden de impresión de la información es:
50 - 75 - 100 - 200 - 400 - 700
private void recorrerEntre (Nodo raiz)
{
if (raiz != null)
{ 
recorrerEntre (raiz.izq);
System.out.print(raiz.info + " ");
recorrerEntre (raiz.der);
}
}
ALGORITMO PARA RECORRER EL ÁRBOL EN ENTRE-ORDEN
El orden de impresión de la información es:
75 - 50 - 200 - 100 - 700 - 400
private void recorrerPost (Nodo raiz)
{
if (raiz != null)
{
recorrerPost (raiz.izq);
recorrerPost (raiz.der);
System.out.print(raiz.info + " ");
}
}
ALGORITMO PARA RECORRER EL ÁRBOL EN POST-ORDEN
raiz
null
false ← exite(raiz,400)
true/false ← exite(raiz,400)
PRINCIPALES ALGORITMOS EN ÁRBOLES BINARIOS
true/false ← exite( raíz , 400 )
PRINCIPALES ALGORITMOS EN ÁRBOLES BINARIOS
Solamente si el dato que queremos 
insertar NO EXISTE en el árbol 
binario, se insertará.
PRINCIPALES ALGORITMOS EN ÁRBOLES BINARIOS
PRINCIPALES ALGORITMOS EN ÁRBOLES BINARIOS
REFERENCIAS BIBLIOGRÁFICAS
REFERENCIA ENLACE 
Una introducción a las matemáticas para el 
análisis y diseño de algoritmos 
https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/35059
Manual de algorítmica: recursividad, complejidad y 
diseño de algoritmos 
https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/56561
Introducción práctica a la programación con 
Python 
https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/124259
Criptografía sin secretos con Python https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/106497
ACM UVA Online http://uva.onlinejudge.org/
ACM ICPC Competition https://icpc.global/compete/preparation 
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/35059
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/35059
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/56561
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/56561
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/124259
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/124259
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/106497
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/106497
http://uva.onlinejudge.org/
https://icpc.global/compete/preparation
	Diapositiva 1
	Diapositiva 2
	Diapositiva 3: UNIDAD 1: LA COMPLEJIDAD ALGORÍTMICA Y PRINCIPALES ESTRATEGIAS DE PROGRAMACIÓN
	Diapositiva 4
	Diapositiva 5
	Diapositiva 6
	Diapositiva 7
	Diapositiva 8
	Diapositiva 9
	Diapositiva 10
	Diapositiva 11
	Diapositiva 12
	Diapositiva 13
	Diapositiva 14
	Diapositiva 15
	Diapositiva 16
	Diapositiva 17
	Diapositiva 18
	Diapositiva 19
	Diapositiva 20
	Diapositiva 21
	Diapositiva 22
	Diapositiva 23
	Diapositiva 24
	Diapositiva 25
	Diapositiva 26
	Diapositiva 27
	Diapositiva 28
	Diapositiva 29
	Diapositiva 30
	Diapositiva 31
	Diapositiva 32