estructura de datos (ii bimestre abril agosto 2011)
TRANSCRIPT
![Page 1: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/1.jpg)
ESTRUCTURA DE DATOS
ESCUELA:
NOMBRES:
Escuela de Ciencias de la Computación
Ing. Manuel Sucunuta E.
BIMESTRE: Segundo
ABRIL AGOSTO 2011
![Page 2: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/2.jpg)
Agenda
• Arboles– Terminología de árboles– Representación– Arboles binarios
• Recorridos
• Grafos– Dirigidos– No dirigidos
![Page 3: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/3.jpg)
Terminología de árboles
G IH
B C D
E F
A RaízNivel 0
Nivel 1
Nivel 2
Rama AD
Hoja
Padres: A, B, D Hermanos: {B, C, D}, {E, F}, {G, H, I}Hijos: B, C, D, E, F, G, H, I Hojas: E, F, C, G, H, I}Profundidad: 3
![Page 4: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/4.jpg)
Terminología de árboles - ejemplo
G IH
B C D
E F
A Camino: ADG. Compuesta por dos ramas AD Y DG.
Longitud de un camino: 2 (nodos-1)
Profundidad (o altura) = 3
![Page 5: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/5.jpg)
Arbol binario
A
B
D E
H I J K
C
F G
• Ningún nodo puede tener más de dos sub-arboles.
• Cada nodo puede tener; 0, 1 o 2 hijos.
• Se identifican el hijo izquierdo y el hijo derecho
• Es una estructura recursiva
![Page 6: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/6.jpg)
Ejemplos de árbol binario
A
B
D E
K
C
F
Profundidad 4
A
E
K
C
F
Profundidad 5
![Page 7: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/7.jpg)
• Cada nodo del arbol binario contiene:– Una referencia a su información– Un apuntador a su hijo izquierdo– Un apuntador a su hijo derecho
Arbol binario
B D
A
![Page 8: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/8.jpg)
Representación de un árbol binarioA
CB
D E
F
A
C NULLNULLB
E NULLNULLD
F NULLNULL
![Page 9: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/9.jpg)
Representación de un árbol binario en C
Definición
![Page 10: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/10.jpg)
Arboles de expresión
* (a+b)*(c-d)
(a+b) (c-d)
• Operandos: Las hojas
• Operadores: Raíz y nodos internos
• Los subárboles son subexpresiones
![Page 11: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/11.jpg)
Ejemplo de árbol de expresión
+
-*
x -
y
a b
z
(x * (y – z)) + (a – b)
![Page 12: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/12.jpg)
Recorrido de un árbol - binario
Los recorridos se clasifican de acuerdo al momento en que se visita la raíz del árbol y los subárboles izquierdo y derecho.
Existen tres recorridos:
Recorrido en Preorden
Recorrido en orden simétrico o inorden
Recorrido en orden final o Postorden
![Page 13: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/13.jpg)
Recorrido Preorden
A
D E F G
CB
D
B
E
A
F
C
G
Recorrido:2. Raíz.3. Subárbol izquierdo en preorden.4. Subárbol derecho en preorden.
A B D E C F G
![Page 14: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/14.jpg)
Recorrido Inorden
A
D E F G
CB
D
B
E
A
F
C
G
Recorrido2. Subárbol izquierdo en simétrico. 3. Raíz.4. Subárbol derecho en simétrico.
D B E A F C G
![Page 15: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/15.jpg)
Recorrido Postorden
A
D E F G
CB
D
B
E
A
F
C
G
Recorrido2. Subárbol izquierdo en orden final. 3. Subárbol derecho en orden final.4. Raíz.
D E B F G C A
![Page 16: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/16.jpg)
Grafos• Son estructuras de datos• Representan relaciones entre objetos• No jerárquicas• Son aplicables en:
QuímicaGeografíaIng. Eléctrica e Industrial, etc.Modelado de Redes
De alcantarilladoEléctricasEtc.
Impresora
Modem
PC2
Servidor
PC1
![Page 17: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/17.jpg)
Grafos
• Un grafo G = (V,A)
• V, el conjunto de vértices o nodos• Representan los objetos.
• A, el conjunto de arcos• Representan las relaciones
G1={V1, A1} V1={1, 2, 3, 4, 5} G1={<1, 2>,<1, 5>,<1, 4>,<2, 3>,<3, 5>,<4, 3>,<4,5>}
![Page 18: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/18.jpg)
Grafos dirigidosG1={V1, A1} V1={1, 2, 3, 4, 5} G1={<1, 2>,<1, 5>,<1, 4>,<2, 3>,<3, 5>,<4, 3>,<4,5>}
![Page 19: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/19.jpg)
Grafos dirigidosG2={V2, A2} V2={a, b, c, d, e, f, g} G2={(a, b), (a, c), (a, d), (a, e), (b, d), (b, e), (c, f), (c, g), (d, e), (f, g)}
![Page 20: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/20.jpg)
![Page 21: ESTRUCTURA DE DATOS (II Bimestre Abril Agosto 2011)](https://reader033.vdocumento.com/reader033/viewer/2022060205/55a146461a28abac048b4807/html5/thumbnails/21.jpg)
PROGRAMA: Tutoría (Nombre de Tutoría) Carrera:
Fecha:
Docente:
Hora Inicio: Hora Final:
GUIÓN DE PRESENTACIÓN
Puntos de la Presentación
Intervienen Duración Aprox. en minutos
Material de Apoyo
- Presentación- Agenda
Manuel Sucunuta • 2 minutos• 3 minutos
Diapositiva 1Diapositiva 2
- Arboles- Grafos
Manuel Sucunuta • 35 minutos Diapositivas (cambios cada 5 seg.), videos, otro o ningún material.
- Preguntas
- Despedida (Contactos, Sugerencias)
Manuel Sucunuta •15 minutos (Si no existen, proponer y dar solución)• 5 minutos
Correo, teléfono, ext, horario de tutoría.