Download UNIDAD III ESTRUCTURAS DE DATOS

Algoritmos avanzados
Ing. Simón Onofre López
UNIDAD III
ESTRUCTURAS DE DATOS
3.1 CONCEPTOS FUNDAMENTALES
3.1.1 TIPOS DE DATOS
Cualquier lenguaje suministra una serie de tipos de datos simples, como son los números
enteros, caracteres, números reales. En realidad suministra un subconjunto de éstos,
pues la memoria del ordenador es finita. Los punteros (si los tiene) son también un tipo
de datos. El tamaño de todos los tipos de datos depende de la máquina y del compilador
sobre los que se trabaja.
En principio, conocer la representación interna de estos tipos de datos no es necesaria
para realizar un programa, pero sí puede afectar en algunos casos al rendimiento.
Por otra parte es posible definir otros tipos de estructuras de datos compuestos, entre las
cuales se encuentran los arreglos, registros y otros.
Los lenguajes de programación (LP) proporcionan herramientas para manejar distintos
tipos de datos.
Tipos predefinidos:
proporcionados por el LP
sólo nos preocupamos de su uso
Tipos definidos por el usuario:
Se puede elegir y definir una estructura de datos de las proporcionadas por el
LP para su representación
Se debe elegir y definir operaciones de manipulación
Se debe garantizar el correcto comportamiento del tipo
3.1.2 ESTRUCTURA DE DATOS
Se trata de un conjunto de variables de un determinado tipo agrupadas y organizadas de
alguna manera para representar un comportamiento. Lo que se pretende con las
estructuras de datos es facilitar un esquema lógico para manipular los datos en función
del problema que haya que tratar y el algoritmo para resolverlo. En algunos casos la
dificultad para resolver un problema radica en escoger la estructura de datos adecuada.
Y, en general, la elección del algoritmo y de las estructuras de datos que manipulará
estarán muy relacionadas.
Según su comportamiento durante la ejecución del programa distinguimos estructuras de
datos:
o
o
Estáticas: su tamaño en memoria es fijo. Ejemplo: arrays.
Dinámicas: su tamaño en memoria es variable. Ejemplo: listas enlazadas con
punteros, ficheros, etc.
Las estructuras de datos que trataremos aquí son los arrays, las pilas y las colas, los
árboles, y algunas variantes de estas estructuras.
22
Algoritmos avanzados
Ing. Simón Onofre López
3.1.3 TIPOS ABSTRACTOS DE DATOS
Los tipos abstractos de datos (TAD) permiten describir una estructura de datos en
función de las operaciones que pueden efectuar, dejando a un lado su implementación.
Los TAD mezclan estructuras de datos junto a una serie de operaciones de
manipulación. Incluyen una especificación, que es lo que verá el usuario, y una
implementación (algoritmos de operaciones sobre las estructuras de datos y su
representación en un lenguaje de programación), que el usuario no tiene necesariamente
que conocer para manipular correctamente los tipos abstractos de datos.
Se caracterizan por el encapsulamiento. Es como una caja negra que funciona
simplemente conectándole unos cables. Esto permite aumentar la complejidad de los
programas pero manteniendo una claridad suficiente que no desborde a los
desarrolladores. Además, en caso de que algo falle será más fácil determinar si lo que
falla es la caja negra o son los cables.
Por último, indicar que un TAD puede definir a otro TAD. Por ejemplo, en próximos
apartados se indicará como construir pilas, colas y árboles a partir de arrays y listas
enlazadas. De hecho, las listas enlazadas también pueden construirse a partir de arrays
y viceversa.
3.2 RECURSIVIDAD
La recursión es una técnica para resolver problemas. Muchas veces resulta más fácil
desarrollar un algoritmo recursivo que uno iterativo.
Definición: Una función f es recursiva si en su cuerpo contiene
una aplicación de f, es decir, si se puede activarse a si misma.
Si la llamada sucede dentro de la propia función se dice que es directamente recursiva. En
cambio si la función llama a otra y esta a su vez llama a la primera se dice que es recursión
indirecta.
El objetivo del programa recursivo, es realizar una serie de llamadas hasta que la secuencia
se define en un punto.
Las directrices para una función recursiva son:
Cada vez que se hace una llamada recursiva en una función, el programa deberá comprobar
que se satisface una condición básica con un determinado parámetro puesto al valor mínimo.
Cada vez que se hace la llamada a la función, los parámetros enviados a la misma, deberán
ser de algún modo más “simple”, es decir, su valor debe tender a la condición básica.
Además por lo general en las funciones recursivas se suelen identificar dos casos:
Caso base, que implica el caso de parada de la recursión
Caso base, que implica realizar las llamadas recursivas
23
Algoritmos avanzados
Ing. Simón Onofre López
Ejemplo
La función Factorial puede ser desarrollada iterativamente o recursivamente1.
Matemáticamente de define como:
1
n! 
n(n  1)
si n  0 ó 1
si n  1
Análogamente su expresión funcional será la siguiente:
si n  0 ó 1
1
fac(n)  
n * fac(n  1) si n  1
Codificación
Como función la codificación es la siguiente:
Private Function factorial(ByVal n As Integer) As
Integer
If n = 1 Then
factorial = 1
Else
factorial = n * factorial(n - 1)
End If
End Function
Prueba
Para N=5
Llamadas recursiva
Factorial(5)=factorial(4)*5
Factorial(4)=factorial(3)*4
Factorial(3)=factorial(2)*3
Factorial(2)=factorial(1)*2
Factorial(1)=1
Evaluación de resultados
Factorial(1)=1
Factorial(2)=factorial(1)*2 =
Factorial(3)=factorial(2)*3 =
Factorial(4)=factorial(3)*4 =
Factorial(5)=factorial(4)*5 =
1*2 =2
2*3 =6
6*4 =24
24*5 =120
24
Algoritmos avanzados
Ing. Simón Onofre López
Como procedimiento se tiene la siguiente codificación:
Private Sub fac(ByVal n As Integer, ByRef resul As Integer)
Dim resp_aux As Integer
If n = 1 OR n = 0 Then
resul = 1
Else
fac n - 1, resp_aux
resul = resp_aux * n
End If
End Sub
Ejemplo: Otro ejemplo clásico es la secuencia de fibonacci cuyos términos son 1, 1, 2, 3, 5,
8, ... los cuales se determinan por la función:
Expresión funcional
si n  1 ó 2
1
fib(n)  
 fib(n  1)  fib(n  2) si n  2
Codificación
Private Function fibonacci(ByVal n As Integer) As
Integer
If n = 0 Or n = 1 Then
fibonacci = 1
Else
fibonacci = fibonacci(n - 1) + fibonacci(n - 2)
End If
End Function
Prueba
Para fib(5) se tienen las siguientes entradas y salidas.
Llamadas recursiva
Fibonacci(5)=fibonacci(4)+ fibonacci(3)
Fibonacci(4)=fibonacci(3)+ fibonacci(2)
Fibonacci(3)=fibonacci(2)+ fibonacci(1)
Fibonacci(2)=1
Fibonacci(1)=1
Evaluación de resultados
Fibonacci(1)=1
Fibonacci(2)=1
Fibonacci(3)=fibonacci(2)+ fibonacci(1)=1+1=2
Fibonacci(4)=fibonacci(3)+ fibonacci(2)=2+1=3
Fibonacci(5)=fibonacci(4)+ fibonacci(3)=3+2=5
25
Algoritmos avanzados
Ing. Simón Onofre López
En este caso se puede observar que la solución planteada de fibonacci es impracticable para
valores de n grandes. Cada fibonacci() realiza dos llamadas, por lo que el número de
llamadas aumenta en proporción geométrica.
¿ Conviene usar recursión siempre?¿ Qué pasa con la memoria?
Veamos el caso de implementar la misma secuencia de fibonacci iterativamente:
Private Function fiboRec(ByVal n As Integer) As Integer
Dim a As Integer, b As Integer, c As Integer, i As
Integer
a = 0
b = 1
c = 1
Print c
For i = 2 To n
c = a + b
Print c
a = b
b = c
Next i
fiboRec = c
End Function
EL lector podrá verificar la eficiencia de la versión recursiva con respecto de la iterativa
3.2.1 EJERCICIOS RESUELTOS
Ejercicio 1 Multiplicar dos números por sumas sucesivas
Solución
Como es sabido, “la multiplicación es una suma abreviada”, en tal sentido se puede realizar
la operación de la siguiente forma:
A*B = A+A+A+ . . . . . . . . . +A , Es decir sumar A, B veces
Entonces para el caso general:
A * B  Multi( A, B)  i 1 A  i 1 A  A
B
B 1
Es decir A*B se puede expresar como la sumatoria desde 1 hasta B de A, lo cual si se saca
de la expresión al último termino, el resto continua siendo sumatoria.
26
Algoritmos avanzados
Ing. Simón Onofre López
El caso base es mucho más simple, nos preguntamos cuál es el valor más qequeño que
puede toma B, para que el resultado sea trivial, es posible elegir entre las siguientes
alternativas
O
A*B=A cuando B=1
A*B=0 cuando B=0
Cualquiera de estas expresiones puede representar al caso base.
Expresión funcional
si B  1
A
Multi ( A, B)  
Multi ( A, B  1)  A
si B  1
Algoritmo
Private Function multiplica(ByVal A As Integer, ByVal
B As Integer) As Integer
If B = 1 Then
multiplica = A
Else
multiplica = multiplica(A, B - 1) + A
End If
End Function
27
Algoritmos avanzados
Ing. Simón Onofre López
Codificación completa
Option Explicit
Dim num As Integer
Dim num2 As Integer
Private Function multiplica(ByVal A As Integer, ByVal B As Integer)
As Integer
If B = 1 Then
multiplica = A
Else
multiplica = multiplica(A, B - 1) + A
End If
End Function
Private Sub Command1_Click()
num = Val(Text1.Text)
num2 = Val(Text2.Text)
MsgBox "El resulatdo es " & multiplica(num, num2), vbCritical,
"RESULTADO"
End Sub
Private Sub Command2_Click()
End
End Sub
Private Sub Text1_KeyPress(KeyAscii As Integer)
Select Case KeyAscii
Case 13
Text2.SetFocus
Case Asc(0) To Asc(9)
Case Else
KeyAscii = 0
End Select
End Sub
28
Algoritmos avanzados
Ing. Simón Onofre López
Private Sub Text2_KeyPress(KeyAscii As Integer)
Select Case KeyAscii
Case 13
Command1.SetFocus
Case Asc(0) To Asc(9)
Case Else
KeyAscii = 0
End Select
End Sub
Ejercicio 2 intercalar los dígitos de dos números, los números tiene la misma longitud.
Solución
La función modulo nos permite sacar el último digito de cada número y componer un nuevo
numero, cuando numA y numB sean de un solo dígito, es decir menores a 10 se habrá
llegado al caso base.
Expresión funcional
si A  10 ó B  10
A *10  B
Intercala ( A, B)  
Intercala ( Adiv10, Bdiv10) *100  ( A mod 10) *10  ( B mod 10) eoc
Algoritmo
Private Function intercala(ByVal numA As Integer, ByVal numB As
Integer) As Double
Dim ma As Integer, mb As Integer, nuevoNum As Integer
If numA < 10 Then
intercala = numA * 10 + numB
Else
ma = numA Mod 10
mb = numB Mod 10
nuevoNum = ma * 10 + mb
intercala = intercala(numA \ 10, numB \ 10) * 100 + nuevoNum
End If
End Function
Prueba
Intercala(345,796) = Intercala(34,79)*100 + 56 =3749*100 + 56 = 374956
Intercala(34,79)
Intercala(3,7)
= Intercala(3,7)*100 + 49 = 37*100 +49 = 3749
= 37
29
Algoritmos avanzados
Ing. Simón Onofre López
Ejercicio 3 Hallar la sumatoria de los N primero números pares
Solución
La sumatoria de los n primero números pares está dada por:
SumaPares(n) = 2 + 4 + 6 + . . . . . .+ 2*(n-1) + 2*n
Sacando el ultimo elemento de la sumatoria, logramos identificar el caso general:
SumaPares(n) = SumaPares(n-1)+ 2*n
Para el caso general, se considera que valor debe tomar n para generar el primer numero
par.
Algoritmo
Private Function sumaPares(n As Integer)
If n = 1 Then
sumaPares = 2
Else
sumaPares = sumaPares(n - 1) + 2 * n
End If
End Function
Codificación completa
Option Explicit
Dim num As Integer
Private Function sumaPares(ByVal n As Integer) As Integer
If n = 1 Then
sumaPares = 2
List1.AddItem 2
Else
sumaPares = sumaPares(n - 1) + 2 * n
List1.AddItem (2 * n)
End If
End Function
30
Algoritmos avanzados
Ing. Simón Onofre López
Private Sub Form_Load()
Option1.Value = False
Option2.Value = True
End Sub
Private Sub Option1_Click()
num = Val(Text1.Text)
MsgBox sumaPares(num), vbExclamation
End Sub
Private Sub Option2_Click()
Text1 = ""
List1.Clear
End Sub
Private Sub Option3_Click()
End
End Sub
Ejercicio 4
naturales.
Ejemplo:
N=1
N=2
N=3
Dado un número entero generar otro número solo compuesto por los números
genera
genera
genera
1
12
123
Expresión funcional
si n  1
1
Genera(n)  
Genera(n  1) *10  n si n  1
Algoritmo
Prueba
Private Function genera(ByVal n
Integer) As Double
If n = 1 Then
genera = 1
Else
genera = genera(n - 1) * 10 + n
End If
End Function
As
Para n=5
31
Algoritmos avanzados
Ing. Simón Onofre López
Llamadas recursiva
genera(5) = genera(4)
5
genera(4) = genera(3)
4
genera(3) = genera(2)
3
genera(2) = genera(1)
2
genera(1) = 1
Evaluación de resultados
* 10 + genera(1) = 1
genera(2) = genera(1) * 10 + 2 = 1*10+2 = 12
* 10 + genera(3) = genera(2) * 10 + 3 = 12*10+3=123
genera(4) = genera(3) * 10 + 4 = 123*10+4=1234
* 10 + genera(5) = genera(4) * 10 + 5 = 1234*10+5=
.....................12345
* 10 +
Ejercicio 5 Invertir un vector
Solución
ini
fin
1 2 3 4 5 6 7
La solución consiste en cambiar el primer V(ini) y último V(fin) elementos usando un auxiliar:
aux = v(ini)
v(ini) = v(fin)
v(fin) = aux
luego realizar la llamada recursiva de manera de cambiar el segundo V(ini+1) con el
penúltimo V(fin-1) elemento:
Invierte ini + 1, fin - 1
el proceso se repite mientras ini sea menor o igual que fin.
Algoritmo
Private Sub Invierte(ByVal ini As Integer,
ByVal fin As Integer)
Dim aux As Integer
If ini < fin Then
aux = v(ini)
v(ini) = v(fin)
v(fin) = aux
Invierte ini + 1, fin - 1
End If
End Sub
Codificación completa
32
Algoritmos avanzados
Ing. Simón Onofre López
Dim tam As Integer
Dim v(1 To 10) As String
Private Sub LlenaVector(ByVal n As Integer)
Dim i As Integer
List1.Clear
For i = 1 To n
v(i) = InputBox("Ingrese el elemento V[" & i & "] =>", "Ingreso de
datos al Vector", 0)
List1.AddItem v(i)
Next
End Sub
Private Sub MostrarLista2(ByVal n As Integer)
Dim i As Integer
List2.Clear
For i = 1 To n
List2.AddItem v(i)
Next
End Sub
Private Sub Invierte(ByVal ini As Integer, ByVal fin As Integer)
Dim aux As String
If ini < fin Then
aux = v(ini)
v(ini) = v(fin)
v(fin) = aux
Invierte ini + 1, fin - 1
End If
End Sub
Private Sub Command1_Click()
tam = Val(InputBox("Ingrese tamaño del vector ", "TAMAÑO DEL VECTOR",
0))
LlenaVector tam
End Sub
33
Algoritmos avanzados
Ing. Simón Onofre López
Private Sub Command2_Click()
Invierte 1, tam
MostrarLista2 tam
End Sub
Private Sub Command3_Click()
End
End Sub
3.3 ARREGLOS
Supongamos que nos enfrentamos a un problema como este: “Una empresa que cuenta con
150 empleados, desea establecer una estadística sobre los salarios de sus empleados, y
quiere saber cual es el salario promedio, y también cuantos de sus empleados gana entre
$1250.00 y $2500.00”.
Si tomamos la decisión de tratar este tipo de problemas con datos simples, pronto nos
percataríamos del enorme desperdicio de tiempo, almacenamiento y velocidad. Es por eso
que para situaciones de este tipo la mejor solución son los datos estructurados.
Un arreglo puede definirse como un grupo o una colección finita, homogénea y ordenada de
elementos. Los arreglos pueden ser de los siguientes tipos:
o
o
o
De una dimensión.
De dos dimensiones.
De tres o más dimensiones
3.4 PILAS
Una pila (stack) es una colección ordenada de elementos en la cual se
pueden insertar nuevos elementos por un extremo y se pueden retirar
otros por el mismo extremo; ese estremos se llama ``la parte superior'' de
la pila.
34
Algoritmos avanzados
Ing. Simón Onofre López
Si tenemos un par de elementos en la pila, uno de ellos debe estar en la parte superior de la
pila, que se considera ``el más alto'' en la pila que el otro. En la figura 3.1 el elemento F es el
más alto de todos los elementos que están en la pila. El elemento D es el más alto de los
elementos A,B,C, pero es menor que los elementos E y F.
Figura 3.1: Pila con 6 elementos
Para describir cómo funciona esta estructura, debemos agregar un nuevo elemento, el
elemento G. Después de haber agregado el elemento G a la pila, la nueva configuración es
la que se muestra en la figura 3.2
Figura 3.2: Operación de insertar el elemento G en la pila P
De acuerdo con la definición, existe solamente un lugar en donde cualquier elemento puede
ser agregado a la pila. Después de haber insertado el nuevo elemento, G ahora es el
elemento en la cima. Debemos aclarar en qué pila deseamos insertar elementos, puesto que
es posible tener más de una pila al mismo tiempo.
Cuando se desea retirar un elemento de la pila, solo basta ordenar que sea retirado un
elemento; no podemos decir ``retira C de la pila'', porque C no está en la cima de la pila y
solamente podemos retirar el elemento que está en la cima. Para que la sentencia ``retira C
de la pila'' tenga sentido, debemos replantear las órdenes a algo como:
Retira de la pila hasta que el elemento retirado sea C.
Y solamente se puede sacar un elemento a la vez.
Siguiendo nuestro ejemplo, ahora deseamos retirar de la pila P. La configuración global de la
pila es como se muestra en la figura 3.3
35
Algoritmos avanzados
Ing. Simón Onofre López
Figura 3.3: Operación de retirar de la pila P
El concepto de pila es muy importante en computación y en especial en teoría de lenguajes
de programación. En lenguajes procedurales como Pascal o C, la pila es una estructura
indispensable, debido a las llamadas a función.
Resulta que el flujo de instrucciones va de arriba hacia abajo, y cuando ocurre una llamada a
alguna función, el estado global del sistema se almacena en un registro y éste en una pila.
Así que la pila va a contener todas las llamadas a procedimientos que se hagan.
Cuando se termina de ejecutar algún procedimiento, se recupera el registro que está en la
cima de la pila. En ese registro están los valores de las variables como estaban antes de la
llamada a la función, o algunas pueden haber cambiado si valor, dependiendo del ámbito de
las variables.
Cada elemento en la pila que es retirado, significa que se ha terminado de ejecutar alguna
función. Cuando se termina de ejecutar el programa, la pila de llamadas a subprogramas
debe haber quedado en 0 también, de otro modo podría causar algun tipo de error.
La manera en cómo entran los datos a la estructura de datos y cómo salen, se denomina fifo,
que viene del ingés first in first out (primero en entrar, primero en salir).
3.5 COLAS
Las colas son una estructura de datos similar a las pilas. Recordemos que las pilas
funcionan en un depósito en donde se insertan y se retiran elementos por el mismo
extremo. En las colas sucede algo diferente, se insertan elementos por un extremo
y se retiran elementos por el otro extremo. De hecho a este tipo de dispositivos se
les conoce como dispositivos ``fifo'' (first in, first out) porque funcionan como una
tubería, lo que entra primero por un extremo, sale primero por el otro extremo.
En una cola hay dos extremos, uno es llamado la parte delantera y el otro extremo se llama
la parte trasera de la cola. En una cola, los elementos se retiran por la parte delantera y se
agregan por la parte trasera.
36
Algoritmos avanzados
Ing. Simón Onofre López
Figura 3.4: Dinámica de una cola.
a) estado actual con una cola con tres
elementos a,b,c;
b) estado de la cola cuando se agrega el
elemento d;
c) estado de la cola cuando se elimina el
elemento a del frente de la cola
En la figura 3.4 se muestra una actividad típica
de la cola, en donde se muestra que se agregan
datos por la parte trasera de la cola y se eliminana datos por el frente de la cola.
Si Q es una cola y x es un elemento, se pueden hacer tres operaciones básicas con las
colas:
o
insert(Q,x), que inserta el elemento x en la parte trasera de la cola Q.
o
x=remove(Q), que almacena en x el valor del elemento retirado de la parte
frontal de la cola Q.
o
empty(Q), que es un predicado de valor booleano, y es true cuando la cola Q
tiene 0 elementos, y es false cuando la cola Q tiene al menos un elemento, en
cuyo caso, ese único elemento es la parte frontal y la parte trasera de la cola
al mismo tiempo.
Teóricamente no hay límite para el tamaño de la cola, asi que siempre se debería poder
insertar elementos a una cola, sin embargo, al igual que las pilas, normalmente se deja un
espacio de memoria para trabajar con esta estructura. Por el contrario, la operación remove
solamente se puede hacer si la cola no está vacía.
3.6 LISTAS
Una lista es una estructura de datos secuencial.
Una manera de clasificarlas es por la forma de acceder al siguiente elemento:
o
o
lista densa: la propia estructura determina cuál es el siguiente elemento de la lista.
Ejemplo: un array.
lista enlazada: la posición del siguiente elemento de la estructura la determina el
elemento actual. Es necesario almacenar al menos la posición de memoria del primer
elemento. Además es dinámica, es decir, su tamaño cambia durante la ejecución del
programa.
37
Algoritmos avanzados
Ing. Simón Onofre López
Una lista enlazada o encadenada es una colección de elementos ó
nodos, en donde cada uno contiene datos y un enlace o liga.
Un nodo es una secuencia de caracteres en memoria dividida en campos (de cualquier
tipo). Un nodo siempre contiene la dirección de memoria del siguiente nodo de
información si este existe.
Un apuntador es la dirección de memoria de un nodo
La figura siguiente muestra la estructura de un nodo:
El campo liga, que es de tipo puntero, es el que se usa para establecer la liga con el
siguiente nodo de la lista. Si el nodo fuera el último, este campo recibe como valor
NIL (vacío).
A continuación se muestra el esquema de una lista :
3.7 ÁRBOLES
3.7.1 ÁRBOLES BINARIOS
A los árboles ordenados de grado dos se les conoce como árboles binarios ya que cada
nodo del árbol no tendrá más de dos descendientes directos. Las aplicaciones de los
árboles binarios son muy variadas ya que se les puede utilizar para representar una
estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.
3.7.1.1 Representación
La representación gráfica de un árbol binario es la siguiente:
Hay dos formas tradicionales de representar un árbol binario en memoria:
38
Algoritmos avanzados
o
o
Ing. Simón Onofre López
Por medio de datos tipo punteros también conocidos como variables
dinámicas o listas.
Por medio de arreglos.
Sin embargo la más utilizada es la primera, puesto que es la más natural para tratar
este tipo de estructuras. Los nodos del árbol binario serán representados como
registros que contendrán como mínimo tres campos. En un campo se almacenará la
información del nodo. Los dos restantes se utilizarán para apuntar al subarbol
izquierdo y derecho del subarbol en cuestión.
Cada nodo se representa gráficamente de la siguiente manera:
3.7.1.2 Clasificación de Árboles Binarios
Existen cuatro tipos de árbol binario:.
a.
b.
c.
d.
B. Distinto.
B. Similares.
B. Equivalentes.
B. Completos.
A continuación se hará una breve descripción de los diferentes tipos de árbol binario
así como un ejemplo de cada uno de ellos.
a. A. B. DISTINTO
Se dice que dos árboles binarios son distintos cuando sus estructuras son
diferentes. Ejemplo:
b. A. B. SIMILARES
Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la
información que contienen sus nodos es diferente. Ejemplo:
39
Algoritmos avanzados
Ing. Simón Onofre López
c. A. B. EQUIVALENTES
Son aquellos árboles que son similares y que además los nodos contienen la
misma información. Ejemplo:
d. A. B. COMPLETOS
Son aquellos árboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos
hijos; el subárbol izquierdo y el subárbol derecho.
3.7.1.3 Recorrido de un Arbol Binario
Hay tres manera de recorrer un árbol : en inorden, preorden y postorden. Cada una
de ellas tiene una secuencia distinta para analizar el árbol como se puede ver a
continuación:
INORDEN
Recorrer el subarbol izquierdo en inorden.
Examinar la raíz.
Recorrer el subarbol derecho en inorden.
PREORDEN
Examinar la raíz.
Recorrer el subarbol izquierdo en preorden.
recorrer el subarbol derecho en preorden.
POSTORDEN
Recorrer el subarbol izquierdo en postorden.
Recorrer el subarbol derecho en postorden.
Examinar la raíz.
A continuación se muestra un ejemplo de los diferentes recorridos en un árbol
binario.
Inorden: GDBHEIACJKF
Preorden: ABDGEHICFJK
Postorden: GDHIEBKJFCA
40
Algoritmos avanzados
Ing. Simón Onofre López
3.7.1.4 Árboles Enhebrados
Existe un tipo especial de árbol binario llamado enhebrado, el cual contiene hebras
que pueden estar a la derecha o a la izquierda. El siguiente ejemplo es un árbol
binario enhebrado a la derecha.
ARBOL ENHEBRADO A LA DERECHA. Este tipo de árbol tiene un apuntador a la
derecha que apunta a un nodo antecesor.
ARBOL ENHEBRADO A LA IZQUIERDA. Estos árboles tienen un apuntador a la
izquierda que apunta al nodo antecesor en orden.
3 .7.1.5 Árboles binarios de búsqueda
Un árbol de búsqueda binaria es una estructura apropiada para muchas de las
aplicaciones que se han discutido anteriormente con listas. La ventaja especial de
utilizar un árbol es que se facilita la búsqueda.
Un árbol binario de búsqueda es aquel en el que el hijo de la izquierda (si existe) de
cualquier nodo contiene un valor más pequeño que el nodo padre, y el hijo de la
derecha (si existe) contiene un valor más grande que el nodo padre.
Un ejemplo de árbol binario de búsqueda es el siguiente:
41
Algoritmos avanzados
Ing. Simón Onofre López
3.7.2 ÁRBOLES GENERALES
Los árboles representan las estructuras no lineales y dinámicas de datos más
importantes en computación . Dinámicas porque las estructuras de árbol pueden
cambiar durante la ejecución de un programa. No lineales, puesto que a cada
elemento del árbol pueden seguirle varios elementos.
Los árboles pueden ser construidos con estructuras estáticas y dinámicas. Las
estáticas son arreglos, registros y conjuntos, mientras que las dinámicas están
representadas por listas.
La definición de árbol es la siguiente:
es una estructura jerárquica aplicada sobre una colección de elementos
u objetos llamados nodos; uno de los cuales es conocido como raíz.
además se crea una relación o parentesco entre los nodos dando lugar a
términos como padre, hijo, hermano, antecesor, sucesor, ansestro, etc..
Formalmente se define un árbol de tipo T como una estructura
homogénea que es la concatenación de un elemento de tipo T junto con
un número finito de arboles disjuntos, llamados subarboles. Una forma
particular de árbol puede ser la estructura vacía.
La figura siguiente representa a un árbol general.
Se utiliza la recursión para definir un árbol porque representa la forma más apropiada y
porque además es una característica inherente de los mismos.
Los árboles tienen una gran variedad de aplicaciones. Por ejemplo, se pueden utilizar
para representar fórmulas matemáticas, para organizar adecuadamente la información,
para construir un árbol genealógico, para el análisis de circuitos eléctricos y para numerar
los capítulos y secciones de un libro.
3.7.2.1 Terminología
La terminología que por lo regular se utiliza para el manejo de arboles es la siguiente:
42
Algoritmos avanzados
o
o
o
o
o
o
o
o
o
o
o
Ing. Simón Onofre López
HIJO. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice
que X es descendiente directo de Y.
PADRE. X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que
X es antecesor de Y.
HERMANO. Dos nodos serán hermanos si son descendientes directos de un
mismo nodo.
HOJA. Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones
(hijos).
NODO INTERIOR. Es un nodo que no es raíz ni terminal.
GRADO. Es el número de descendientes directos de un determinado nodo.
GRADO DEL ARBOL Es el máximo grado de todos los nodos del árbol.
NIVEL. Es el número de arcos que deben ser recorridos para llegar a un
determinado nodo. Por definición la raíz tiene nivel 1.
ALTURA. Es el máximo número de niveles de todos los nodos del árbol.
PESO. Es el número de nodos del árbol sin contar la raíz.
LONGITUD DE CAMINO. Es el número de arcos que deben ser recorridos para
llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y
sus descendientes directos longitud de camino 2 y así sucesivamente.
3.7.2.2 Transformación de un Árbol Gral. en un Árbol Binario.
En esta sección estableceremos los mecanismos necesarios para convertir un árbol
general en un árbol binario. Para esto, debemos seguir los pasos que se describen a
continuación:
o
o
o
Enlazar los hijos de cada nodo en forma horizontal (los hermanos).
Enlazar en forma vertical el nodo padre con el nodo hijo que se encuentra más a
la izquierda. Además, debe eliminarse el vínculo de ese padre con el resto de sus
hijos.
Rotar el diagrama resultante aproximadamente 45 grados hacia la izquierda, y así
se obtendrá el árbol binario correspondiente
3.8 GRAFOS
Un grafo dirigido G consiste en un conjunto de vértices V y un conjunto de arcos o aristas A.
Los vertice se denominan también nodos o puntos.
Un arco, es un par ordenado de vértices(V,W) donde V es el vértice inicial y W es el vértice
terminal del arco. Un arco se expresa como: V-->W y se representa de la siguiente manera:
Los vértice de un grafo pueden usarse para representar objetos. Los arcos se utilizan para
representar relaciones entre estos objetos.
Las aplicaciones más importantes de los grafos son las siguientes:
o
o
o
Rutas entre ciudades.
Determinar tiempos máximos y mínimos en un proceso.
Flujo y control en un programa.
43
Algoritmos avanzados
Ing. Simón Onofre López
3.8.1 TERMINOLOGIA
o La terminología que manejaremos regularmente para el uso de grafos es la siguiente:
o CAMINO.Es una secuencia de vértices V1, V2, V3, ... , Vn, tal que cada uno de estos
V1-&gtV2, V2-&gtV3, V1-&gtV3.
o LONGITUD DE CAMINO. Es el número de arcos en ese camino.
o CAMINO SIMPLE. Es cuando todos sus vértices, excepto tal vez el primero y el
último son distintos.
o CICLO SIMPLE. Es un camino simple de longitud por lo menos de uno que empieza
y termina en el mismo vértice.
o ARISTAS PARALELAS. Es cuando hay más de una arista con un vértice inicial y uno
terminal dados.
o GRAFO CICLICO. Se dice que un grafo es cíclico cuando contiene por lo menos un
ciclo.
o GRAFO ACICLICO. Se dice que un grafo es aciclíco cuando no contiene ciclos.
o GRAFO CONEXO. Un grafo G es conexo, si y solo si existe un camino simple en
cualesquiera dos nodos de G.
o GRAFO COMPLETO ó FUERTEMENTE CONEXO.Un grafo dirigido G es completo si
para cada par de nodos (V,W) existe un camino de V a W y de W a V (forzosamente
tendrán que cumplirse ambas condiciones), es decir que cada nodo G es adyacente a
todos los demás nodos de G.
o GRAFO UNILATERALMENTE CONEXO.Un grafo G es unilateralmente conexo si
para cada par de nodos (V,W) de G hay un camino de V a W o un camino de W a V.
o GRAFO PESADO ó ETIQUETADO. Un grafo es pesado cuando sus aristas
contienen datos (etiquetas). Una etiqueta puede ser un nombre, costo ó un valor de
cualquier tipo de dato. También a este grafo se le denomina red de actividades, y el
número asociado al arco se le denomina factor de peso.
o VERTICE ADYACENTE. Un nodo o vértice V es adyacente al nodo W si existe un
arco de m a n.
o GRADO DE SALIDA.El grado de salida de un nodo V de un grafo G, es el número de
arcos o aristas que empiezan en V.
o GRADO DE ENTRADA.El grado de entrada de un nodo V de un grafo G, es el
número de aristas que terminan en V.
o NODO FUENTE.Se le llama así a los nodos que tienen grado de salida positivo y un
grado de entrada nulo.
o NODO SUMIDERO.Se le llama sumidero al nodo que tiene grado de salida nulo y un
grado de entrada positivo.
3.8.2 EJEMPLOS DE GRAFOS
081.- Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo
llamaremos k-regular.
Por ejemplo, el primero de los siguientes grafos es 3-regular, el segundo es 2-regular
y el tercero no es regular
44
Algoritmos avanzados
Ing. Simón Onofre López
2.- Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos
disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto
Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es
3.- Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo con n
vértices se denota Kn.
A continuación pueden verse los dibujos de K3, K4, K5 y K6
Todo grafo completo es regular porque cada vértice tiene grado |V|-1 al estar conectado con
todos los otros vértices.
Un grafo regular no tiene por qué ser completo.
4.- Un grafo bipartido regular se denota Km,n donde m, n es el grado de cada conjunto
disjunto de vértices.
A continuación ponemos los dibujos de K1,2, K3,3, y K2,5
45
Algoritmos avanzados
Ing. Simón Onofre López
3.8.3 REPRESENTACION DE GRAFOS
46