Grafos Un grafo en el ámbito de las ciencias de la computación es una estructura de datos, en concreto un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. El concepto de grafo TAD desciende directamente del concepto matemático de grafo. Informalmente se define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E, las aristas (edges en inglés). Formalmente, un grafo, G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y E es un conjunto que consta de dos elementos de V. Un grafo está formado por un conjunto de nodos(o vértices) y un conjunto de arcos. Cada arco en un grafo se especifica por un par de nodos. TERMINOLOGÍA *.-Al número de nodos del grafo se le llama orden del grafo. *.-Un grafo nulo es un grafo de orden 0 (cero). *.-Dos nodos son adyacentes si hay un arco que los une. *.-En un grafo dirigido, si A es adyacente de B, no necesariamente B es adyacente de A *.-Camino es una secuencia de uno o mas arcos que conectan dos nodos. *.-Un grafo se denomina conectado cuando existe siempre un camino que une dos nodos cualesquiera y desconectado en caso contrario. *.-Un grafo es completo cuando cada nodo esta conectado con todos y cada uno de los nodos restantes. *.-El camino de un nodo así mismo se llama ciclo. Grafos dirigidos Un grafo dirigido G, también llamado digrafo o grafo, es lo mismo que un multigrafo, solo que cada arista e de G tiene una dirección asignada o , en otras palabras ,cada arista e está identificada por un par ordenado (u,v) de nodos G en vez del par desordenado [u.v]. Suponga que G es un grafo dirigido con una arista dirigida e=(u,v).Entonces e también se llama arco . Más aún se usa la siguiente terminología: (1) e empieza en u y termina en v (2) u es el origen o punto inicial de e ,y v es el destino o punto terminal de e . (3) u es un predecesor de v y v es un sucesor o vecino de u (4) u es adyacente hacia v y v es adyacente a u El grado de salida de un nodo u de G, escrito gradsal(u), es el número de aristas que empiezan en u similarmente , el grado de entrada u, escrito gradent(u), es el número de aristas que terminan en u. Un nodo u se llama fuente si tiene un grado de salida positivo y un grado de entrada nulo . Similarmente u se le llama sumidero si tiene un grado de salida nulo y un grado de entrada positivo. GRAFOS Y MULTIGRAFOS Un grafo G consiste en dos cosas: (1) Un conjunto V de elementos llamados nodos (o puntos o vértices) (2) Un conjunto E de aristas tales que cada arista e de E esta identificada por un único (desordenado) par [u,v] de nodos de V, denotado por e-[v,u]. A veces denotamos un grafo escribiendo G=(V,E) Suponga que e =[u,v]. entonces los nodos u y v se llaman extremos de e, y u y v se dice que son nodos adyacentes o vecinos. El grado de un nodo u, escrito grad(u), es el número de artistas que contienen a u.si grad(u)= 0, o sea, si u no pertenece a ninguna arista--- entonces se dice que u es un nodo aislado. Un camino P de longitud n desde un nodo u se define como la secuencia de n +1 nodos.

Arboles Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos. También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles. Esto son definiciones simples. Pero las características que implican no lo son tanto. Definiremos varios conceptos. En relación con otros nodos: Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'. Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'. Los árboles con los que trabajaremos tienen otra característica importante: cada nodo sólo puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre. Esto hace que estos árboles estén fuertemente jerarquizados, y es lo que en realidad les da la apariencia de árboles. En cuanto a la posición dentro del árbol: Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'. Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'. Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'. Otra característica que normalmente tendrán nuestros árboles es que todos los nodos contengan el mismo número de punteros, es decir, usaremos la misma estructura para todos los nodos del árbol. Esto hace que la estructura sea más sencilla, y por lo tanto también los programas para trabajar con ellos. Tampoco es necesario que todos los nodos hijos de un nodo concreto existan. Es decir, que pueden usarse todos, algunos o ninguno de los punteros de cada nodo. Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbol completo. En una cosa, los árboles se parecen al resto de las estructuras que hemos visto: dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente. Es decir, un nodo cualquiera puede ser considerado como la raíz de un árbol completo. Existen otros conceptos que definen las características del árbol, en relación a su tamaño: Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc. Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos. Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3. Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc. Los árboles de orden dos son bastante especiales, de hecho les dedicaremos varios capítulos. Estos árboles se conocen también como árboles binarios. Frecuentemente, aunque tampoco es estrictamente necesario, para hacer más fácil moverse a través del árbol, añadiremos un puntero a cada nodo que apunte al nodo padre. De este modo podremos avanzar en dirección a la raíz, y no sólo hacia las hojas. Es importante conservar siempre el nodo raíz ya que es el nodo a partir del cual se desarrolla el árbol, si perdemos este nodo, perderemos el acceso a todo el árbol. Los árboles tienen aplicaciones en diferentes ámbitos como por ejemplo: Diseño de compiladores, sistemas expertos, sistemas evolutivos, sistemas conscientes, manejo de directorios por ejemplo Mi PC dentro de Windows. Representación de un árbol genealógico. índices de bases de datos y mucha más Sin lugar tiene muchas aplicaciones, aunque su implementación no es tan usada como las base de datos tradicionales, pero actualmente existen modelos mediante los cuales un árbol puede ser representado en una lista dinámica simplemente o doblemente ligada, este modelo se presentará posteriormente. ¿Qué pueden almacenar? Si los árboles se implantan en estructuras de datos dinámicas, pueden contener los que se requiera, aunque también se pueden implantar en arreglos estáticos. Por ejemplo si se usa el lenguaje C y se opta por estructuras dinámicas en especial por la lista doblemente ligada, se puede definir un objetos llamado nodo de la siguiente forma: class nodo { public: //A continuacion los datos necesario para la propuesta(tonahtiu,2009) tipo de implantacion int padre, id; nodo *anterior, *siguiente; // A continuación los datos u objetos que se quieran almacenar en nodo int algun_dato; }; Como se puede apreciar en el programa anterior de agrega el dato algun_dato se aquí se pueden definir cualquier tipo y cantidad de datos que se requieran o bien otros objetos. Por lo cual se puede adaptar perfectamente a las necesidades del problema. ¿Cómo se pueden implantar? Existen tantas manera de representar estructuras de árbol como ideas surjan, por lo cual aquí solo se presenta una propuesta que considero que es sencilla y sirven para árboles de diversos niveles, grados de árbol y que puede cargarse en una lista simplemente ligada, misma que ya se ha presentado. http://www.youtube.com/watch?v=R06UpamwpgA

Pilas

Una pila en palabras sencillas es un lugar donde se almacenan datos, es igual que un Array pero una pila tiene una entrada y una salida de datos. Se utiliza la filosofia LIFO (Last In First Out, ultimo en entrar, primero en salir)


Operaciones

Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.

* Crear: se crea la pila vacía.
* Apilar: se añade un elemento a la pila.(push)
* Desapilar: se elimina el elemento frontal de la pila.(pop)
* Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)
* Vacía: devuelve cierto si la pila está vacía o falso en caso contrario.


Tipos de Pila
* Estatica
* Dinamica

*Programa de pila convertida a cola*

Compila el siguiente programa de Pila Estática, analiza el funcionamiento del código línea.

public class PilaEstatica{ // el nombre de la clase
public static void main(String[] args) {
int dato;
int pila[]=new int[5]; // se ingresan los valores de la pila (en este caso 5)
Scanner teclado=new Scanner(System.in); // se declara el objeto Scanner
for(int tope=0;tope<=4;tope++){ // el arreglo de la pila System.out.println("Proporciona datos para la pila"); // ingresa los datos de la pila dato=teclado.nextInt(); // devuelve el valor ingresado al Scanner pila[tope]=dato; // se introduce un nuevo elemento a la pila } for (int tope=4;tope>=0;tope--) // el arreglo de la pila
System.out.println("La pila tiene los siguientes datos: "+pila[tope]); // muesta los datos que contiene la pila
}
}

Arreglos

Definicion de Arreglo
Los arreglos en Java son dinámicos, pero no extensibles, lo cual significa que deben ser creados con el tamaño que tendrán hasta el final de su vida.
Un arreglo se declara de la siguiente forma:

[] ;

O sea, para declarar, por ejemplo, un arreglo de númerosenteros utilizaremos la siguiente sentencia:

int[] arrInt;

Es importante notar que el arreglo aún no ha sido creado, sinomeramente declarado. Para crear el arreglo (reservar sumemoria e inicializarlo) deberemos recurrir al operadornew:

arrInt = new int[10];


Programa de Arreglo

import java.util.Scanner;
public class jugadores {
public static void main(String[] args) {
int NUM = 10;

double peso []=new double[NUM];
double parcial;
System.out.println("Por favor introduzca el peso de los jugadores:");
for(int j=0;j {

Scanner pesos = new Scanner (System.in);

parcial=pesos.nextDouble();
peso[j]=parcial;


peso[j]= peso[j]/2;
}
for(int i=0;i {
System.out.println("Peso de jugadores en kilos");
System.out.println(""+peso[i]);
}

}

}



Matrices

Las matrices se definen, como un arreglo bidimensional, en donde tenemos un número de reglones N y un número de columnas M. La representación matemática de una matriz es :

Programacion Orientada a Objetos

* Objeto
Un objeto es una entidad con la cual se puede interactuar.
Un objeto es una variable a la cual se le asignan ciertos atributos y con estos se puede realizar un procedimiento o calculo.

Ejemplo:


* Clase
Una clase es un conjunto de objetos que comparten los mismos atributos.

Ejemplo:
class Perro{
int peso;
char nombre[20];
char raza[15];
void dormir (int tiempo){delay(tiempo);}
void comer (int cantidad){peso +=cantidad;}
};

La clase perro describe el conjunto de características (peso, nombre, raza) y comportamiento (dormir, comer) para un conjunto de mascotas que pertenezcan a dicha clase. Esta descripción sólo es una plantilla para el objeto, pero no genera objetos por sí sola, para ello es necesario definir una variable de la clase definida:

Perro Cachupín, Pluto;

Tras esta declaración se han creado dos objetos de la clase Perro, Cachupín y Pluto quienes quedan disponibles para ser utilizados en el programa donde fueron declarados.

Búsqueda Secuencial (segunda parte)

1.Método de ordenamiento

Es la operación de arreglar los elementos de un determinado vector en algún orden secuencial
de acuerdo a un criterio de ordenamiento.
El propósito principal de un ordenamiento es el de facilitar las búsquedas
de los miembros del conjunto ordenado.

Al hablar de ordenación nos referimos a mostrar los datos en forma
ordenada de manera que tengan un mejor orden, ya que al momento que
el usuario ingresa los datos estos pueden ser ingresados en forma desordenada.

Metodos de Ordenacion
Ordenacion por Seleccion Ordenacion por Seleccion
Ordenacion por Insercion
Búsqueda Secuencial
Búsqueda Binaria
Metodo de Intercambio ó Burbuja
Ordenación por Selección


El proceso de la selección es el siguiente:
1)Captura el Número más pequeño (si se desea ordenar los elementos de
menor a mayor) o el número más grande (si se desea ordenar de mayor a menor).
2)El número capturado es colocado en la primera posición, teniendo en
cuenta que un Array empieza desde la posición Cero.
3)El Proceso se repite para todos los datos sobrantes hasta llegar al
último de ellos.
4)Finalmente los datos quedan ordenados ya sea en forma ascendente o
descendente..


Ordenación por Inserción


El método de ordenación por inserción es similar al proceso típico de
ordenar tarjetas de nombres (cartas de una baraja) por orden alfabético
, que consiste en insertar un nombre en su posición correcta dentro de una
lista o archivo que ya está ordenado. Cada elemento a insertar es considerado uno a la vez,
asimismo se insertan en su posición correspondiente.


Búsqueda Secuencial


Consiste en ingresar un dato a buscar, por lo cual el programa examina cada uno de los elementos del vector.
es decir, el elemento a buscar es comparado con cada uno de
los elementos que contiene el Array.
Si el Array tiene 100 elementos y el dato a Buscar esta en la
posicion 100, entonces se realizara 100 comparaciones puesto que conparará hasta llegar al final del Array,
sin embargo existe la posivilidad que el elemento a buscar
no pertenesca al Array, y la busqueda sera en vano


Búsqueda Binaria


Para poder ejecutar el Método de Búsqueda Binaria, se debe de contar con un Array ordenado. El procedimiento que se realiza es el siguiente:
•EL Programa internamente selecciona el elemento central del Array.
•Si el elemento a buscar es el dato central el proceso termina. •Si el elemento a buscar no coincide con el elemento central, continua la búsqueda:
•Se subdivide en dos partes al Array.
•Si el elemento a buscar es menor que el dato central, entonces selecciona la mitad de la parte izquierda.
•La parte seleccionada se subdivide nuevamente y se repite todo el proceso.
•El proceso termina cuando el dato es encontrado; teniendo en cuenta que el dato a buscar no puede encontrarse en el Array.


Método de Intercambio Ó Burbuja


El método de la Burbuja es menos eficiente puesto que realiza las pasadas necesarias en un array hasta que el Array quede ordenado. Su forma de ejecución es:
•En la primera pasada compara el primer elemento con el segundo elemento.
•En la misma pasada compara el segundo elemento con el tercer elemento.
•Se repite el mismo procedimiento hasta llegar al último elemento.
•Si una vez finalizada la primera pasada el Array sigue desordenado, entonces se realiza una segunda pasada.
•Se realiza el mismo procedimiento en la segunda pasada.
•Se repiten las pasadas necesarias hasta que el Array quede completamente ordenado.
Ejemplos
Ordenacion
int i,j,n;
double aux,x[];
System.out.println("Ingrese la cantidad de numeros a leer:");
n= Integer.parseInt(br.readLine());
x= new double[n];
for (i=0;i System.out.println("Elemento["+i+"]:");
x[i]=Double.parseDouble(br.readLine());} for(i=1;i for(j=n-1;j>=i;j--){
if (x[j-1]>x[j]){
aux=x[j-1];
x[j-1]=x[j];
x[j]=aux;}
}
}
System.out.println("Elemento Ordenado");
for (i=0;i System.out.println("Elemento["+i+"]:"+x[i]);}
}
}
Metodo De Busqueda
int i,n,band;
double x[],elem;
System.out.println("Ingrese los numeros a leer:");
n=Integer.parseInt(br.readLine());
x=new double[n];
System.out.println("Ingrese los elementos del vector:");
for(i=0;i System.out.println("Elemento["+i+"]:");
x[i]=Double.parseDouble(br.readLine());
} System.out.println("Ingrese el elemento a buscar:");
elem=Double.parseDouble(br.readLine());
band=0;
for(i=0;i if(x[i]==elem){
System.out.println("El elemento encontrado:"+i);
band=1;
}
}
if(band==0){
System.out.println("No se encontro el elemento:");
}
}
Media Geometrica
double media[]= new double[999];
double can,sum=1,resul=0;
can=Double.parseDouble(JOptionPane.showInputDialog(null,"Ingrese Cantida De Elementos: "));
for(int i=0;i {
media[i]=Double.parseDouble(JOptionPane.showInputDialog(null,"Ingrese Datos a la Media"));
sum=sum*media[i];
} resul=Math.pow(sum, 1.0/can);
System.out.println("La Media Es Geometrica :"+resul);
} }

Presentación: Búsqueda Secuencial

Definición
Está diseñada para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.


Utilización
Se utiliza cuando algún elemento no está ordenado o no puede ser ordenado previamente.

Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del arreglo hasta encontrarlo, o hasta que se llegue al final.

La existencia se puede asegurar cuando el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del arreglo


Ventajas y Desventajas
DESVENTAJA.- en un vector de N posiciones este algoritmo va a buscar posición a posición hasta dar con el dato solicitado y en el caso de que no exista pues también va a recorrer todo el arreglo.

VENTAJA.- Lo bueno de este tipo de búsqueda es que es muy sencillo de implementar.


Programa
Si tenemos un vector ya definido con los siguientes datos: ["aarona","aashta","abelarda","abelia","abigail","abril"] , todos de tipo String y queremos saber si ya existe el nombre : "Abigail" en nuestro vector entonces tenemos que hacer lo siguiente: public class BSecuencial { public static void main(String[] args) throws IOException { BufferedReader entrada = new BufferedReader (new InputStreamReader(System.in)); int encontrados=0; String [] VectorNombres = {"Aarona","Aashta","Abelarda","Abelia","Abigail ", "Abril"}; System.out.print("Digite el nombre que desea buscar: "); String nombre = entrada.readLine(); // entrada de dato a buscar for (int i=0; i

Arboles

Arboles
Un árbol se define como una colección de nodos organizados en forma recursiva. Cuando hay 0 nodos se dice que el árbol esta vacío, en caso contrario el árbol consiste en un nodo denominado raíz, el cual tiene 0 o más referencias a otros árboles, conocidos como subárboles. Las raíces de los subárboles se denominan hijos de la raíz, y consecuentemente la raíz se denomina padre de las raíces de sus subárboles. Una visión gráfica de esta definición recursiva se muestra en la siguiente figura:


Los nodos que no poseen hijos se denominan hojas. Dos nodos que tienen el padre en común se denominan hermanos.
Un camino entre un nodo n₁ y un nodo n_k está definido como la secuencia de nodos n₁, n₂, ..., n_k tal que n_i es padre de n_i+1, 1 <= i < k. El largo del camino es el número de referencias que componen el camino, que para el ejemplo son k-1. Existe un camino desde cada nodo del árbol a sí mismo y es de largo 0. Nótese que en un árbol existe un único camino desde la raíz hasta cualquier otro nodo del árbol. A partir del concepto de camino se definen los conceptos de ancestro y descendiente: un nodo n es ancestro de un nodo m si existe un camino desde n a m; un nodo n es descendiente de un nodo m si existe un camino desde m a n.
Se define la profundidad del nodo n_k como el largo del camino entre la raíz del arbol y el nodo n_k. Esto implica que la profundidad de la raíz es siempre 0. La altura de un nodo n_k es el máximo largo de camino desde n_k hasta alguna hoja. Esto implica que la altura de toda hoja es 0. La altura de un árbol es igual a la altura de la raíz, y tiene el mismo valor que la profundidad de la hoja más profunda. La altura de un árbol vacío se define como -1.
La siguiente figura muestra un ejemplo de los conceptos previamente descritos:

• A es la raíz del árbol.
• A es padre de B, C y D.
• E y F son hermanos, puesto que ambos son hijos de B.
• E, J, K, L, C, P, Q, H, N y O son las hojas del árbol.
• El camino desde A a J es único, lo conforman los nodos A-B-F-J y es de largo 3.
• D es ancestro de P, y por lo tanto P es descendiente de D.
• L no es descendiente de C, puesto que no existe un camino desde C a L.
• La profundidad de C es 1, de F es 2 y de Q es 4.
• La altura de C es 0, de F es 1 y de D es 3.
• La altura del árbol es 4 (largo del camino entre la raíz A y la hoja más profunda, P o Q).

Tipos de Arbol
* Arbol Binario
* Arbol General

Arbol Binario
Un árbol binario es un árbol en donde cada nodo posee 2 referencias a subárboles (ni más, ni menos). En general, dichas referencias se denominan izquierda y derecha, y consecuentemente se define el subárbol izquierdo y subárbol derecho del arbol.


En este caso, la implementacion del nodo de un árbol binario es como sigue:

class NodoArbolBinario
{
  Object elemento;
  NodoArbolBinario izq;
  NodoArbolBinario der;
}

Los nodos en sí que conforman un árbol binario se denominan nodos internos, y todas las referencias que son null se denominan nodos externos.

Propiedades de los árboles binarios

Propiedad 1:
Si se define i = número de nodos internos, e = número de nodos externos, entonces se tiene que:


e = i+1

Arbol General
En un árbol general cada nodo puede poseer un número indeterminado de hijos. La implementación de los nodos en este caso se realiza de la siguiente manera: como no se sabe de antemano cuantos hijos tiene un nodo en particular se utilizan dos referencias, una a su primer hijo y otra a su hermano más cercano. La raíz del árbol necesariamente tiene la referencia a su hermano como null.

class NodoArbolGeneral
{
  Object elemento;
  NodoArbolGeneral hijo;
  NodoArbolGeneral hermano;
}

Nótese que todo árbol general puede representarse como un árbol binario, con la salvedad que el hijo derecho de la raíz es siempre null. Si se permite que la raíz del árbol tenga hermanos, lo que se conoce como bosque, entonces se tiene que el conjunto de los bosques generales es isomorfo al conjunto de los árboles binarios. En efecto, las propiedades vistas en los árboles binarios se siguen cumpliendo en los árboles generales.

Programa utilizando Arboles

public class Ejemplo {
public static void main(String[] args) {
Arbol arbol = null;
arbol = Arbol.insertar( arbol, new Integer(5));
arbol = Arbol.insertar( arbol, new Integer(2));
arbol = Arbol.insertar( arbol, new Integer(6));
arbol = Arbol.insertar( arbol, new Integer(1));
arbol = Arbol.insertar( arbol, new Integer(3));
arbol = Arbol.insertar( arbol, new Integer(4));
IAccion accion = new AccionAdapter(){
public void accion(Object dato) {
System.out.println(dato);
}
};
System.out.println( "\nListado Pre-Orden\n");
Arbol.inorden( arbol, accion );
System.out.println( "\nListado In-Orden\n");
Arbol.inorden( arbol, accion );
System.out.println( "\nListado Post-Orden\n");
Arbol.inorden( arbol, accion );
Arbol palabras = null;
palabras = Arbol.insertar( palabras, "San Luis Potosí");
palabras = Arbol.insertar( palabras, "Durango");
palabras = Arbol.insertar( palabras, "Coahuila");
palabras = Arbol.insertar( palabras, "Jalisco");
palabras = Arbol.insertar( palabras, "Aguascalientes");
palabras = Arbol.insertar( palabras, "Guanajuato");
System.out.println( "\nListado Pre-Orden\n");
Arbol.inorden(palabras, accion );
System.out.println( "\nListado In-Orden\n");
Arbol.inorden(palabras, accion );
System.out.println( "\nListado Post-Orden\n");
Arbol.inorden( palabras, accion );
}
}

Video. Aplicacion Arboles en Java

Arboles utilizando Java

Recorrido de un Arbol Binario

RECORRIDO DE UN ARBOL BINARIO
Si se desea manipular la información contenida en un árbol, lo primero que hay que saber es cómo se puede recorrer ese árbol, de manera que se acceda a todos los nodos del mismo solamente una vez. El recorrido completo de un árbol produce un orden lineal en la información del árbol. Este orden puede ser útil en determinadas ocasiones.

Cuando se recorre un árbol se desea tratar cada nodo y cada subárbol de la misma manera. Existen entonces seis posibles formas de recorrer un árbol binario.

(1) nodo - subárbol izquierdo - subárbol derecho

(2) subárbol izquierdo - nodo - subárbol derecho

(3) subárbol izquierdo - subárbol derecho - nodo

(4) nodo - subárbol derecho - subárbol izquierdo

(5) subárbol derecho - nodo - subárbol izquierdo

(6) subárbol derecho - subárbol izquierdo - nodo

Si se adopta el convenio de que, por razones de simetría, siempre se recorrera antes el subárbol izquierdo que el derecho, entonces tenemos solamente tres tipos de recorrido de un árbol, los tres primeros en la lista anterior. Estos recorridos, atendiendo a la posición en que se procesa la información del nodo, reciben, respectivamente, el nombre de recorrido prefijo, infijo y posfijo y dan lugar a algoritmos eminentemente recursivos.

Grafos



Un grafo en el ámbito de las ciencias de la computación es una estructura de datos, en concreto un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. El concepto de grafo TAD desciende directamente del concepto matemático de grafo.

Informalmente se define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E, las aristas (edges en inglés). Formalmente, un grafo, G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y E es un conjunto que consta de dos elementos de V.

Colas

Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserciónpush se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.

Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), dónde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento. Este tipo de estructura de datos abstracta se implementa en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas.

Uso

La particularidad de una estructura de datos de cola es el hecho de que sólo podemos acceder al primer y al último elemento de la estructura. Así mismo, los elementos sólo se pueden eliminar por el principio y sólo se pueden añadir por el final de la cola,

Operaciones con Colas

• Crear: se crea la cola vacía.
• Encolar (añadir, entrar, insertar): se añade un elemento a la cola. Se añade al final de esta.
• Desencolar (sacar, salir, eliminar): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.
• Frente (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primer elemento que entró.

Ejemplos de colas en la vida real serían: personas comprando en un supermercado, esperando para entrar a ver un partido de béisbol, esperando en el cine para ver una película, una pequeña peluquería, etc. La idea esencial es que son todos líneas de espera.

Ejemplo Cola.Java

public void inserta(Elemento x) {
        Nodo Nuevo;
        Nuevo = new Nodo(x, null);
        if (NodoCabeza == null) {
            NodoCabeza = Nuevo;
        } else {
            NodoFinal.Siguiente = Nuevo;
        }
        NodoFinal = Nuevo;
    }
 
    public Elemento cabeza() throws IllegalArgumentException {
        if (NodoCabeza == null) {
            throw new IllegalArgumentException();
        } else {
            return NodoCabeza.Info;
        }
    }
 
    public Cola() {
    // Devuelve una Cola vacía
        NodoCabeza = null;
        NodoFinal = null;
    }

Tipos de Colas


Colas circulares (anillos): en las que el último elemento y el primero están unidos.
Colas de prioridad: En ellas, los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen. Hay 2 formas de implementación:
Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.
Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.
Bicolas: son colas en donde los nodos se pueden añadir y quitar por ambos extremos; se les llama DEQUE (Double Ended QUEue). Para representar las bicolas lo podemos hacer con un array circular con Inicio y Fin que apunten a cada uno de los extremos. Hay variantes:
Bicolas de entrada restringida: Son aquellas donde la inserción sólo se hace por el final, aunque podemos eliminar al inicio ó al final.
Bicolas de salida restringida: Son aquellas donde sólo se elimina por el final, aunque se puede insertar al inicio y al final.

Video con Colas en Java

http://www.youtube.com/watch?v=PbDSfXH2DHc

Recursividad

La recursividad es una función que se llama a sí misma para dividir un problema en problemas más sencillos, el método recursivo debe estar compuesto de una caso base para el cual ya se conoce un resultado y una llamada al mismo método con una versión ligeramente más sencilla del problema inicial

ejemplo 1, factoriales:

Para todo n entero natural, se llama factorial n (n!) al producto de todos los enteros entre 1 y n:

n	n!
1	1	1	1
2	2 × 1	= 2 × 1!	= 2
3	3 × 2 × 1	= 3 × 2!	= 6
4	4 × 3 × 2 × 1	= 4 × 3!	= 24
5	5 × 4 × 3 × 2 × 1	= 5 × 4!	= 120
6	etc	etc

Código:

?

code

1 2 3 4 5 6

public void factoriales(long n){    if(n==1) return 1;    else return n*factoriales(n-1); }

El método factoriales se llama a sí mismo disminuyendo cada vez el numero inicial en una unidad hasta que llega a valer 1 y por lo tanto alcanza el caso base, en ese momento se devuelven todas las llamadas recursivas realizas al método factoriales retornando el valor del actual multiplicado por el valor anterior.

ejemplo 2, Fibonachi:

La sucesion de Fibonachi comienza por 0 y 1, y cada numero siguiente es la

suma de los dos anteriores:

0,1,1,2,3,5,8,13,21,34,55,89

Código:

?

code

1 2 3 4 5 6 7

public void fibonachi(long n){    if(n==0 || n==1) return n;    else return fibonachi(n-2)+fibonachi(n-1);   }

Este método esta compuesto de dos casos bases, y de dos llamadas recursivas al método, a esto se le denomina recursividad mútliple, a diferencia del método factoriales que sólo hace una llamada recursiva y se denomina recursividad simple. En ambos casos es de tipo directa, también es posible efectuar recursión indirectamente: una método puede llamar a otro quien, a su vez, acabe llamando al primero.

A continuación se expone un ejemplo de programa que utiliza recursión indirecta, y nos dice si un número es par o impar. Al igual que el programa anterior, hay otro método mucho más sencillo de determinar si un número es par o impar, basta con determinar el resto de la división entre dos. Por ejemplo: si hacemos par(2) devuelve 1 (cierto). Si hacemos impar(4) devuelve 0 (falso).
 

Código:

?

code

1 2 3 4 5 6 7 8 9 10 11

int par(int n) {   if (n == 0) return 1;   return impar(n-1); }   int impar(int n) {   if (n == 0) return 0;   return par(n-1); }

 Código: 

?

code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

int x[]={7,3,4,6,8,9,5};         int n = 7;         // Enviamos datos         max(n, x);      public static int max(int n, int x[])     {         if(n == 1)             return x[0];         if (x[n-1] > max(n-1, x))             return x[n-1];         else             return max(n-1, x);     }

Hay que apuntar que el factorial puede obtenerse con facilidad sin necesidad de emplear funciones recursivas, es más, el uso del programa anterior es muy ineficiente, pero es un ejemplo muy claro.

Dado un array constituido de números enteros, devolver la suma de todos los elementos. En este caso se desconoce el número de elementos. En cualquier caso se garantiza que el último elemento del array es -1, número que no aparecerá en ninguna otra posición.

Código:

?

code

1 2 3 4 5 6 7 8 9

private static int sumaArray2(int vector[], int n){        if(n==-1)return 0;        else return vector[n]+ sumaArray2(vector, n-1);      }   static int []array={1,2,3,4,5,6};   System.out.println(sumaArray2(array,array.length-1));

Dado un array constituido de números enteros y que contiene N elementos siendo N >= 1, devolver el elemento mayor.

Código:

?

code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

static int []array={510,41,300,4,25,6};    private static int mayor(int vector[], int n){        int aux;        if(n==-1)return 0;        else{            aux = mayor(vector, n-1);            if(vector[n]>aux)                return vector[n];            else                return aux;        }    }     System.out.println(mayor(array,array.length-1));

máximo comun divisor.

Código:

?

code

1 2 3 4 5 6 7 8 9 10

private static long mcd(long a, long b){        if(b==0)            return a;          else return mcd(b,a%b);    }     System.out.println(mcd(80,25));   resultado 5;

Video utilizando Recursividad

http://www.youtube.com/watch?v=Ri2eO8G4FNo&feature=results_video&playnext=1&list=PLAE6CF900D458C87E