Un árbol es una estructura de datos ampliamente usada que emula la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o mas nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b, si existe un enlace desde a hasta b (en ese caso, también decimos que bes hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja.
El árbol También se define como una estructura de datos no lineal. Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos y tablas de contenidos. Entre otros tenemos un tipo especial de de árbol que es, llamado árbol binario, que puede ser implementado fácilmente en la computadora.
4.1.2 REPRESENTACION EN MEMORIA DE ARBOLES
Existen dos formas de representar un Arbol en Memoria:
1- Mediante Listas Enlazadas:
Utilizando la firma de las listas lineales. Los Nodos del arbolbinario serán representados como registros que contendran como minimo dos 3 campos. En un campo se almacenará la información del nodo y los dos campos restantes se utilizarán para apuntar los arboles izquierdo y derecho respectivamente del nodo en cuestión.
Dado el siguiente nodo T
| IZQ | INFO | DER |
Donde el IZQ es el campo donde se almacenara la dirección del subarbol iszquierdo, INFO Contendra la información del nodo y DER La dirección del subarbol derecho
2- Representacion Secuencial :
Se utiliza un arreglo simple en el cual la raíz ocupara la posición uno y sus hijos estaran en la posicion 2*k para el hijo izquierdo y 2*k+1 para el hijo derecho
Ejem:
 |
|
4.1.2.1 ARBOLES GENERALES
En ciencias de la computación, un árbol es una estructura de datos ampliamente usada que emula la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o mas nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b, si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja.
El árbol También se define como una estructura de datos no lineal. Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos y tablas de contenidos. Entre otros tenemos un tipo especial de de árbol que es, llamado árbol binario, que puede ser implementado fácilmente en la computadora.
4.1.2.2 ARBOLES BINARIOS
Árboles Binarios
Un árbol binario T se define como un conjunto finito de elementos, llamados nodos, de forma que:
- T es vacío ( en cuyo caso se llama árbol nulo o árbol vació) o
- T contiene un nodo distinguido R, llamado raíz de T, y los restantes nodos de T forman un par ordenado de árboles binarios disjuntos T1 y T2.
Si T contiene una raíz R, los dos árboles T1 y T2 se llaman, respectivamente, subárboles izquierdo y derecho de la raíz R. Si T1 no es vació , entonces su raíz se llama sucesor izquierdo de R; y análogamente, si T2 no es vació, su raíz se llama sucesor derecho de R.
Observe que :
- B es un sucesor izquierdo y C un sucesor derecho del nodo A.
- El subárbol izquierdo de la raíz A consiste en los nodos B, D, E y F, y el subárbol derecho de A consiste en los nodos C , G, H, J, K y L.
Figura (1)
Cualquier nodo N de un árbol binario T tiene 0, 1 ó 2 sucesores. Los nodos A,B,C y H tienen dos sucesores, los nodos R y J sólo tienen un sucesor , y los nodos D,F, G,L y K no tienen sucesores. Los nodos sin sucesores se llaman nodos terminales.
La definición anterior del árbol binario T es recursiva, ya que T se define en términos de los subárboles binarios T1 y T2. Esto significa, en particular, que cada nodo N de T contiene un subárbol izquierdo y uno derecho.
Dos árboles binarios T y T’ se dicen que son similares si tienen la misma estructura o, en otras palabras, si tienen la misma forma. Los árboles se dice que son copias si son similares y tienen los mismos contenidos en sus correspondientes nodos.
4.1.3 RECORRIDO EN ARBOL BINARIO EN PREORDEN
El recorrido en un árbol binario permite rescatar los datos en formas diferentes. Aunque existen varias maneras de hacerlo, aquí se verán las más conocidas : inorden , preorden , postorden.
Una de los recorridos más usados (inorden) es el que rescata los datos en forma ordenada (de menor a mayor).
La técnica que usualmente se usa para hacer el recorrido, es ir almacenando los datos en una estructura lineal : Cola , Lista o Pila.
El criterio para escoger una de las tres depende del problema , pero generalmente los criterios generales son los siguientes :
De aquí en adelante , las implementaciones de recorrido serán usando una Cola , ya que los problemas que vienen, requieren los datos en forma ordenada.
4.1.3.2 RECORRIDO EN ARBOL BINARIO INORDEN
Se declara una función que recibe como parámetros un arbol binario y una cola.
Las instrucciones de la función, siguen el concepto recursivo de la definición, teniendo en cuenta que el concepto de "visitar el elemento de la raiz" se reemplaza por : obtener la raíz e insertar el elemento en la cola y que la condición de la recursividad es que se encuentre con algún subárbol vacío.
*nota : Hay que tener cuidado en verificar que la cola que se pasa como parámetro sea no vacía. Las funciones serán implementadas en el archivo "funcArbin.h".
void inordenArbin(Arbin a,Cola col)
{
if (!vacioArbin(a))
{
inordenArbin(izqArbin(a),col);
TipoA raiz = raizArbin(a);
adicCola(col,raiz);
inordenArbin(derArbin(a),col);
}
}
4.1.3.3 RECORRIDO EN ARBOL BINARIO POSORDEN
- Recorrer el subarbol izquierdo en postorden.
- Recorrer el subarbol derecho en postorden.
- Examinar la raíz.
4.1.4 BALANCEO ARBOLES BINARIOS
En ciencias de la computación, un árbol binario de búsqueda auto-balanceable o equilibrado es un árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento, automáticamente. Esto es importante, ya que muchas operaciones en un árbol de búsqueda binaria tardan un tiempo proporcional a la altura del árbol, y los árboles binarios de búsqueda ordinarios pueden tomar alturas muy grandes en situaciones normales, como cuando las claves son insertadas en orden. Mantener baja la altura se consigue habitualmente realizando transformaciones en el árbol, como la rotación de árboles, en momentos clave.
Tiempos para varias operaciones en términos del número de nodos en el árbol n:
Para algunas implementaciones estos tiempos son el peor caso, mientras que para otras están amortizados.
Estructuras de datos populares que implementan este tipo de árbol:
| Operación | Tiempo en cota superior asintótica |
| Búsqueda | O(log n) |
| Inserción | O(log n) |
| Eliminación | O(log n) |
| Iteración en orden | O(n) |
4.1.5 CLASES PARA IMPLEMENTACION DE ARBOLES
-
Dado que los árboles binarios son de estructura fundamental en la teoría de los árboles, será preciso disponer de algún mecanismo que permita la conversión de un árbol general en árbol binario.
“Los árboles binarios son más fáciles de programar que los generales”. En esto es imprescindible deducir cuántas ramas o caminos se desprenden de un nodo en un momento dado. Por ello, y dado que de los árboles binarios siempre se cuelgan como máximo dos subárboles, su programación será más sencilla.
Afortunadamente, existe una técnica para convertir un árbol general a formato de un árbol binario. Ejemplo:
Supongamos que se tiene el árbol A y se quiere convertir en un árbol binario B. El árbol de conversión tiene 3 pasos fáciles:
1. - La raíz de B es la raíz de A
2. -
a) Enlazar un nodo raíz con el camino que conecta el nodo más a la izquierda (su hijo).
,. b) Enlazar éste nodo con los restantes descendientes del nodo raíz en su camino con lo que se forma el nivel 1.
c) A continuación, repetir los pasos a y b con los nodos del nivel 2, enlazando siempre en un mismo camino todos los hermanos (descendientes del mismo nodo). Repetir estos pasos hasta llegar al nivel más alto.
3.- Girar el diagrama resultante 45° para diferenciar entre los subárboles izquierdos y derecho.
Ejem:
T T
A A
B B
C C
D D
E E
4.2 GRAFOS DEFINICION
Definicion:
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:
711.jpg
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:
Rutas entre ciudades.
Determinar tiempos máximos y mínimos en un proceso.
Flujo y control en un programa.
Operaciones Sobre Grafos:
En esta sección analizaremos algunas de las operaciones sobre grafos, como :
Creación.
Inserción.
Búsqueda.
Eliminación.
En esta sección, continuaremos utilizando los apuntadores que se usaron en las secciones anteriores. TOP para hacer referencia al primer nodo, LD para indicar liga derecha y LA para indicar liga abajo, por último usaremos los apuntadores P y Q para hacer referencia a los nuevos nodos que vayan a ser usados.
4.2.3 REPRESENTACION DE GRAFOS EN MEMORIA
Los grafos se representan en memoria enlazada mediante listas de adyacencia.
Una lista de adyacencia, se define de la siguiente manera: Para un vértice i es una lista en cierto orden formada por todos los vértices adyacentes [a,i]. Se puede representar un grafo por medio de un arreglo donde cabeza de i es un apuntador a la lista de adyacencia al vértice i.
Veamos el siguiente grafo dirigido:
La lista de adyacencia, que se obtuvo a partir del grafo anterior es la siguiente:
En un grafo se tiene un circuito de Hamilton cuando se inicie en un nodo y termina en el mismo pasando exactamente una vez por cada nodo.
CIRCUITO DE VENN EULER
Este circuito se da en grafos donde se realiza un camino donde se puede pasar solo una vez por cada arco.
El factor de peso o Ponderación se da en un grafo en el cual hay datos asociados con un arco.
Este comentario ha sido eliminado por el autor.
ResponderEliminar