estructura de datos (ii bimestre abril agosto 2011)

ESTRUCTURA DE DATOS

ESCUELA:

NOMBRES:

Escuela de Ciencias de la Computación

Ing. Manuel Sucunuta E.

BIMESTRE: Segundo

ABRIL AGOSTO 2011

Agenda

• Arboles– Terminología de árboles– Representación– Arboles binarios

• Recorridos

• Grafos– Dirigidos– No dirigidos

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

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

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

Ejemplos de árbol binario

A

B

D E

K

C

F

Profundidad 4

A

E

K

C

F

Profundidad 5

• 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

Representación de un árbol binarioA

CB

D E

F

A

C NULLNULLB

E NULLNULLD

F NULLNULL

Representación de un árbol binario en C

Definición

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

Ejemplo de árbol de expresión

+

-*

x -

y

a b

z

(x * (y – z)) + (a – b)

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

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

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

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

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

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>}

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>}

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)}

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.