Diagrama de Flujo
miércoles, 29 de abril de 2009
Árbol B+
un Árbol B+ es un tipo de estructura de datos de árboles. Representa una colección de datos ordenados de manera que se permite una inserción y borrado eficientes de elementos. Es un índice, multinivel, dinámico, con un límite máximo y mínimo en el número de claves por nodo.
Un árbol-B+ es una variación de un árbol-B. En un árbol-B+, en contraste respecto un árbol-B, toda la información se guarda en las hojas. Los nodos internos sólo contienen claves y punteros. Todas las hojas se encuentran en el mismo, más bajo nivel. Los nodos hoja se encuentran unidos entre sí como una lista enlazada para permitir búsqueda secuencial.
El número máximo de claves en un registro es llamado el orden del árbol-B+.
El mínimo número de claves por registro es la mitad del máximo número de claves. Por ejemplo, si el orden de un árbol-B+ es n, cada nodo (exceptuando la raíz) debe tener entre n/2 y n claves.
El número de claves que pueden ser indexadas usando un árbol-B+ está en función del orden del árbol y su altura.
Árbol AVL
Los árboles AVL están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha. Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O(log n). El factor de equilibrio puede ser almacenado directamente en cada nodo o ser computado a partir de las alturas de los subárboles.
Para conseguir esta propiedad de equilibrio, la inserción y el borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos.
Definición de la altura de un árbol
Sea T un árbol binario de búsqueda y sean Ti y Td sus subárboles, su altura H(T), es:
* 0 si el árbol T contiene solo la raíz.
* 1 + max(H(Ti),H(Td)) si contiene más nodos.
Definición de árbol AVL
Arboles balanceados o equilibrados: · Un árbol binario de búsqueda es k-equilibrado si cada nodo lo es. · Un nodo es k-equilibrado si las alturas de sus subárboles izquierdo y derecho difieren en no más de k. Arboles AVL (Adel’son, Vel’skii, Landis) · Un árbol binario de búsqueda 1-equilibrado se llama árbol AVL. Cabe destacar que un árbol AVL no es un Tipo de dato abstracto (TDA) sino una estructura de datos.
Arbol Binario No Equilibrado
Arbol Binario Equilibrado - AVL
Factor de equilibrio
Cada nodo, además de la información que se pretende almacenar, debe tener los dos punteros a los árboles derecho e izquierdo, igual que los árboles binarios de búsqueda (ABB), y además el dato que controla el factor de equilibrio.
El factor de equilibrio es la diferencia entre las alturas del árbol derecho y el izquierdo:
*FE = altura subárbol derecho - altura subárbol izquierdo;
*Por definición, para un árbol AVL, este valor debe ser -1, 0 ó 1.
Si el factor de equilibrio de un nodo es:
0 -> el nodo está equilibrado y sus subárboles tienen exactamente la misma altura.
1 -> el nodo está equilibrado y su subárbol derecho es un nivel más alto.
-1 -> el nodo está equilibrado y su subárbol izquierdo es un nivel más alto.
Si el factor de equilibrio Fe≥2 o Fe≤-2 es necesario reequilibrar.
Para conseguir esta propiedad de equilibrio, la inserción y el borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos.
Definición de la altura de un árbol
Sea T un árbol binario de búsqueda y sean Ti y Td sus subárboles, su altura H(T), es:
* 0 si el árbol T contiene solo la raíz.
* 1 + max(H(Ti),H(Td)) si contiene más nodos.
Definición de árbol AVL
Arboles balanceados o equilibrados: · Un árbol binario de búsqueda es k-equilibrado si cada nodo lo es. · Un nodo es k-equilibrado si las alturas de sus subárboles izquierdo y derecho difieren en no más de k. Arboles AVL (Adel’son, Vel’skii, Landis) · Un árbol binario de búsqueda 1-equilibrado se llama árbol AVL. Cabe destacar que un árbol AVL no es un Tipo de dato abstracto (TDA) sino una estructura de datos.
Arbol Binario No Equilibrado
Arbol Binario Equilibrado - AVL
Factor de equilibrio
Cada nodo, además de la información que se pretende almacenar, debe tener los dos punteros a los árboles derecho e izquierdo, igual que los árboles binarios de búsqueda (ABB), y además el dato que controla el factor de equilibrio.
El factor de equilibrio es la diferencia entre las alturas del árbol derecho y el izquierdo:
*FE = altura subárbol derecho - altura subárbol izquierdo;
*Por definición, para un árbol AVL, este valor debe ser -1, 0 ó 1.
Si el factor de equilibrio de un nodo es:
0 -> el nodo está equilibrado y sus subárboles tienen exactamente la misma altura.
1 -> el nodo está equilibrado y su subárbol derecho es un nivel más alto.
-1 -> el nodo está equilibrado y su subárbol izquierdo es un nivel más alto.
Si el factor de equilibrio Fe≥2 o Fe≤-2 es necesario reequilibrar.
Arborles B
Los árboles-B es que los nodos internos deben tener un número variable de nodos hijo dentro de un rango predefinido. Cuando se inserta o se elimina un dato de la estructura, la cantidad de nodos hijo varía dentro de un nodo. Para que siga manteniéndose el número de nodos dentro del rango predefinido, los nodos internos se juntan o se parten. Dado que se permite un rango variable de nodos hijo, los árboles-B no necesitan rebalancearse tan frecuentemente como los árboles binarios de búsqueda auto-balanceables, pero por otro lado pueden desperdiciar memoria, porque los nodos no permanecen totalmente ocupados. Los límites superior e inferior en el número de nodos hijo son definidos para cada implementación en particular.
Estructura de los nodos
Cada elemento de un nodo interno actúa como un valor separador, que lo divide en subárboles. Por ejemplo, si un nodo interno tiene tres nodos hijo, debe tener dos valores separadores o elementos a1 y a2. Todos los valores del subárbol izquierdo deben ser menores a a1, todos los valores del subárbol del centro deben estar entre a1 y a2, y todos los valores del subárbol derecho deben ser mayores a a2.
Los nodos internos de un árbol B, es decir los nodos que no son hoja, usualmente se representan como un conjunto ordenado de elementos y punteros a los hijos. Cada nodo interno contiene un máximo de U hijos y, con excepción del nodo raíz, un mínimo de L hijos. Para todos los nodos internos exceptuando la raíz, el número de elementos es uno menos que el número de punteros a nodos. El número de elementos se encuentra entre L-1 y U-1. El número U debe ser 2L o 2L-1, es decir, cada nodo interno está por lo menos a medio llenar. Esta relación entre U y L implica que dos nodos que están a medio llenar pueden juntarse para formar un nodo legal, y un nodo lleno puede dividirse en dos nodos legales (si es que hay lugar para subir un elemento al nodo padre). Estas propiedades hacen posible que el árbol B se ajuste para preservar sus propiedades ante la inserción y eliminación de elementos.
Operaciones
Búsqueda
La búsqueda es similar a la de los árboles binarios. Se empieza en la raíz, y se recorre el árbol hacia abajo, escogiendo el sub-nodo de acuerdo a la posición relativa del valor buscado respecto a los valores de cada nodo. Típicamente se utiliza la búsqueda binaria para determinar esta posición relativa.
Procedimiento
1 Situarse en el nodo raíz.
2 Comprobar si contiene la clave a buscar.
1. . Encontrada fin de procedimiento .
2. . No encontrada:
---------1. . La clave a buscar k <> ki y k < style="font-weight: bold;">Inserción
Todas las inserciones se hacen en los nodos hoja.
1. Realizando una búsqueda en el árbol, se halla el nodo hoja en el cual debería ubicarse el nuevo elemento.
2. Si el nodo hoja tiene menos elementos que el máximo número de elementos legales, entonces hay lugar para uno más. Inserte el nuevo elemento en el nodo, respetando el orden de los elementos.
3. De otra forma, el nodo debe ser dividido en dos nodos. La división se realiza de la siguiente manera:
---1. Se escoge el valor medio entre los elementos del nodo y el nuevo elemento.
---2. Los valores menores que el valor medio se colocan en el nuevo nodo izquierdo, y los valores mayores que el valor medio se colocan en el nuevo nodo derecho; el valor medio actúa como valor separador.
--3. El valor separador se debe colocar en el nodo padre, lo que puede provocar que el padre sea dividido en dos, y así sucesivamente.
Si las divisiones de nodos suben hasta la raíz, se crea una nueva raíz con un único elemento como valor separador, y dos hijos. Es por esto por lo que la cota inferior del tamaño de los nodos no se aplica a la raíz. El máximo número de elementos por nodo es U-1. Así que debe ser posible dividir el número máximo de elementos U-1 en dos nodos legales. Si este número fuera impar, entonces U=2L, y cada uno de los nuevos nodos tendrían (U-2)/2 = L-1 elementos, y por lo tanto serían nodos legales. Si U-1 fuera par, U=2L-1, así que habría 2L-2 elementos en el nodo. La mitad de este número es L-1, que es el número mínimo de elementos permitidos por nodo.
Un algoritmo mejorado admite una sola pasada por el árbol desde la raiz,hasta el nodo donde la inserción tenga lugar,dividiendo todos los nodos que estén llenos encontrados a su paso.Esto evita la necesidad de volver a cargar en memoria los nodos padres,que pueden ser caros si los nodos se encuentran en una memoria secundaria.Sin embargo,para usar este algoritmo mejorado, debemos ser capaces de enviar un elemento al nodo padre y dividir el resto U-2 elementos en 2 nodos legales,sin añadir un nuevo elemento.Esto requiere que U=2L en lugar de U=L-1,lo que explica por qué algunos libros de texto imponen este requisito en la definicion de árboles-B.
Eliminación
La eliminación de un elemento es directa si no se requiere corrección para garantizar sus propiedades. Hay dos estrategias populares para eliminar un nodo de un árbol B.
*localizar y eliminar el elemento, y luego corregir.
*hacer una única pasada de arriba a abajo por el árbol, pero cada vez que se visita un nodo, reestructurar el árbol para que cuando se encuentre el elemento a ser borrado, pueda eliminarse sin necesidad de continuar reestructurando.
Se pueden dar dos problemas al eliminar elementos: primero, el elemento puede ser un separador de un nodo interno. Segundo, puede suceder que al borrar el elemento número de elementos del nodo quede debajo de la cota mínima. Estos problemas se tratan a continuación en orden.
Eliminación en un nodo hoja
* Busque el valor a eliminar.
* Si el valor se encuentra en un nodo hoja, se elimina directamente la clave, posiblemente dejándolo con muy pocos elementos; por lo que se requerirán cambios adicionales en el árbol.
Eliminación en un nodo interno
ada elemento de un nodo interno actúa como valor separador para dos subárboles, y cuando ese elemento es eliminado, pueden suceder dos casos. En el primero, tanto el hijo izquierdo como el derecho tienen el número mínimo de elementos, L-1. Pueden entonces fundirse en un único nodo con 2L-2 elementos, que es un número que no excede U-1 y por lo tanto es un nodo legal. A menos que se sepa que este árbol B en particular no tiene datos duplicados, también se debe eliminar el elemento en cuestión (recursivamente) del nuevo nodillo.
En el segundo caso, uno de los dos nodos hijos tienen un número de elementos mayor que el mínimo. Entonces se debe hallar un nuevo separador para estos dos subárboles. Note que el mayor elemento del árbol izquierdo es el mayor elemento que es menor que el separador. De la misma forma, el menor elemento del subárbol derecho es el menor elemento que es mayor que el separador. Ambos elementos se encuentran en nodos hoja, y cualquiera de los dos puede ser el nuevo separador.
* Si el valor se encuentra en un nodo interno, escoja un nuevo separador (puede ser el mayor elemento del subárbol izquierdo o el menor elemento del subárbol derecho), elimínelo del nodo hoja en que se encuentra, y reemplace el elemento a eliminar por el nuevo separador.
* Como se ha eliminado un elemento de un nodo hoja, se debe tratar este caso de manera equivalente.
Rebalanceo después de la eliminación
Si al eliminar un elemento de un nodo hoja el nodo se ha quedado con menos elementos que el mínimo permitido, algunos elementos se deben redistribuir. En algunos casos el cambio lleva la deficiencia al nodo padre, y la redistribución se debe aplicar iterativamente hacia arriba del árbol, quizá incluso hasta a la raíz. Dado que la cota mínima en el número de elementos no se aplica a la raíz, el problema desaparece cuando llega a ésta.
La estrategia consiste en hallar un hermano para el nodo deficiente que tenga más del mínimo número de elementos y redistribuir los elementos entre los hermanos para que todos tengan más del mínimo. Esto también cambia los separadores del nodo padre.
* Si el nodo hermano inmediato de la derecha del nodo deficiente tiene más del mínimo número de elementos, escoja el valor medio entre el separador y ambos hermanos como nuevo separador y colóquelo en el padre.
* Redistribuya los elementos restantes en los nodos hijo derecho e izquierdo.
* Redistribuya los subárboles de los dos nodos . Los subárboles son trasplantados por completo, y no se alteran si se mueven a un otro nodo padre, y esto puede hacerse mientras los elementos se redistribuyen.
* Si el nodo hemano inmediato de la derecha del nodo deficiente tiene el mínimo número de elementos, examine el nodo hermano inmediato de la izquierda.
* Si los dos nodos hemanos inmediatos tienen el mínimo número de elementos, cree un nuevo nodo con todos los elementos del nodo deficiente, todos los elementos de uno de sus hermanos, colocando el separador del padre entre los elementos de los dos nodos hermanos fundidos.
* Elimine el separador del padre, y reemplace los dos hijos que separaba por el nuevo nodo fundido.
* Si esa acción deja al número de elementos del padre por debajo del mínimo, repita estos pasos en el nuevo nodo deficiente, a menos que sea la raíz, ya que no tiene cota mínima en el número de elementos.
-----------------
Estructura de los nodos
Cada elemento de un nodo interno actúa como un valor separador, que lo divide en subárboles. Por ejemplo, si un nodo interno tiene tres nodos hijo, debe tener dos valores separadores o elementos a1 y a2. Todos los valores del subárbol izquierdo deben ser menores a a1, todos los valores del subárbol del centro deben estar entre a1 y a2, y todos los valores del subárbol derecho deben ser mayores a a2.
Los nodos internos de un árbol B, es decir los nodos que no son hoja, usualmente se representan como un conjunto ordenado de elementos y punteros a los hijos. Cada nodo interno contiene un máximo de U hijos y, con excepción del nodo raíz, un mínimo de L hijos. Para todos los nodos internos exceptuando la raíz, el número de elementos es uno menos que el número de punteros a nodos. El número de elementos se encuentra entre L-1 y U-1. El número U debe ser 2L o 2L-1, es decir, cada nodo interno está por lo menos a medio llenar. Esta relación entre U y L implica que dos nodos que están a medio llenar pueden juntarse para formar un nodo legal, y un nodo lleno puede dividirse en dos nodos legales (si es que hay lugar para subir un elemento al nodo padre). Estas propiedades hacen posible que el árbol B se ajuste para preservar sus propiedades ante la inserción y eliminación de elementos.
Operaciones
Búsqueda
La búsqueda es similar a la de los árboles binarios. Se empieza en la raíz, y se recorre el árbol hacia abajo, escogiendo el sub-nodo de acuerdo a la posición relativa del valor buscado respecto a los valores de cada nodo. Típicamente se utiliza la búsqueda binaria para determinar esta posición relativa.
Procedimiento
1 Situarse en el nodo raíz.
2 Comprobar si contiene la clave a buscar.
1. . Encontrada fin de procedimiento .
2. . No encontrada:
---------1. . La clave a buscar k <> ki y k < style="font-weight: bold;">Inserción
Todas las inserciones se hacen en los nodos hoja.
1. Realizando una búsqueda en el árbol, se halla el nodo hoja en el cual debería ubicarse el nuevo elemento.
2. Si el nodo hoja tiene menos elementos que el máximo número de elementos legales, entonces hay lugar para uno más. Inserte el nuevo elemento en el nodo, respetando el orden de los elementos.
3. De otra forma, el nodo debe ser dividido en dos nodos. La división se realiza de la siguiente manera:
---1. Se escoge el valor medio entre los elementos del nodo y el nuevo elemento.
---2. Los valores menores que el valor medio se colocan en el nuevo nodo izquierdo, y los valores mayores que el valor medio se colocan en el nuevo nodo derecho; el valor medio actúa como valor separador.
--3. El valor separador se debe colocar en el nodo padre, lo que puede provocar que el padre sea dividido en dos, y así sucesivamente.
Si las divisiones de nodos suben hasta la raíz, se crea una nueva raíz con un único elemento como valor separador, y dos hijos. Es por esto por lo que la cota inferior del tamaño de los nodos no se aplica a la raíz. El máximo número de elementos por nodo es U-1. Así que debe ser posible dividir el número máximo de elementos U-1 en dos nodos legales. Si este número fuera impar, entonces U=2L, y cada uno de los nuevos nodos tendrían (U-2)/2 = L-1 elementos, y por lo tanto serían nodos legales. Si U-1 fuera par, U=2L-1, así que habría 2L-2 elementos en el nodo. La mitad de este número es L-1, que es el número mínimo de elementos permitidos por nodo.
Un algoritmo mejorado admite una sola pasada por el árbol desde la raiz,hasta el nodo donde la inserción tenga lugar,dividiendo todos los nodos que estén llenos encontrados a su paso.Esto evita la necesidad de volver a cargar en memoria los nodos padres,que pueden ser caros si los nodos se encuentran en una memoria secundaria.Sin embargo,para usar este algoritmo mejorado, debemos ser capaces de enviar un elemento al nodo padre y dividir el resto U-2 elementos en 2 nodos legales,sin añadir un nuevo elemento.Esto requiere que U=2L en lugar de U=L-1,lo que explica por qué algunos libros de texto imponen este requisito en la definicion de árboles-B.
Eliminación
La eliminación de un elemento es directa si no se requiere corrección para garantizar sus propiedades. Hay dos estrategias populares para eliminar un nodo de un árbol B.
*localizar y eliminar el elemento, y luego corregir.
*hacer una única pasada de arriba a abajo por el árbol, pero cada vez que se visita un nodo, reestructurar el árbol para que cuando se encuentre el elemento a ser borrado, pueda eliminarse sin necesidad de continuar reestructurando.
Se pueden dar dos problemas al eliminar elementos: primero, el elemento puede ser un separador de un nodo interno. Segundo, puede suceder que al borrar el elemento número de elementos del nodo quede debajo de la cota mínima. Estos problemas se tratan a continuación en orden.
Eliminación en un nodo hoja
* Busque el valor a eliminar.
* Si el valor se encuentra en un nodo hoja, se elimina directamente la clave, posiblemente dejándolo con muy pocos elementos; por lo que se requerirán cambios adicionales en el árbol.
Eliminación en un nodo interno
ada elemento de un nodo interno actúa como valor separador para dos subárboles, y cuando ese elemento es eliminado, pueden suceder dos casos. En el primero, tanto el hijo izquierdo como el derecho tienen el número mínimo de elementos, L-1. Pueden entonces fundirse en un único nodo con 2L-2 elementos, que es un número que no excede U-1 y por lo tanto es un nodo legal. A menos que se sepa que este árbol B en particular no tiene datos duplicados, también se debe eliminar el elemento en cuestión (recursivamente) del nuevo nodillo.
En el segundo caso, uno de los dos nodos hijos tienen un número de elementos mayor que el mínimo. Entonces se debe hallar un nuevo separador para estos dos subárboles. Note que el mayor elemento del árbol izquierdo es el mayor elemento que es menor que el separador. De la misma forma, el menor elemento del subárbol derecho es el menor elemento que es mayor que el separador. Ambos elementos se encuentran en nodos hoja, y cualquiera de los dos puede ser el nuevo separador.
* Si el valor se encuentra en un nodo interno, escoja un nuevo separador (puede ser el mayor elemento del subárbol izquierdo o el menor elemento del subárbol derecho), elimínelo del nodo hoja en que se encuentra, y reemplace el elemento a eliminar por el nuevo separador.
* Como se ha eliminado un elemento de un nodo hoja, se debe tratar este caso de manera equivalente.
Rebalanceo después de la eliminación
Si al eliminar un elemento de un nodo hoja el nodo se ha quedado con menos elementos que el mínimo permitido, algunos elementos se deben redistribuir. En algunos casos el cambio lleva la deficiencia al nodo padre, y la redistribución se debe aplicar iterativamente hacia arriba del árbol, quizá incluso hasta a la raíz. Dado que la cota mínima en el número de elementos no se aplica a la raíz, el problema desaparece cuando llega a ésta.
La estrategia consiste en hallar un hermano para el nodo deficiente que tenga más del mínimo número de elementos y redistribuir los elementos entre los hermanos para que todos tengan más del mínimo. Esto también cambia los separadores del nodo padre.
* Si el nodo hermano inmediato de la derecha del nodo deficiente tiene más del mínimo número de elementos, escoja el valor medio entre el separador y ambos hermanos como nuevo separador y colóquelo en el padre.
* Redistribuya los elementos restantes en los nodos hijo derecho e izquierdo.
* Redistribuya los subárboles de los dos nodos . Los subárboles son trasplantados por completo, y no se alteran si se mueven a un otro nodo padre, y esto puede hacerse mientras los elementos se redistribuyen.
* Si el nodo hemano inmediato de la derecha del nodo deficiente tiene el mínimo número de elementos, examine el nodo hermano inmediato de la izquierda.
* Si los dos nodos hemanos inmediatos tienen el mínimo número de elementos, cree un nuevo nodo con todos los elementos del nodo deficiente, todos los elementos de uno de sus hermanos, colocando el separador del padre entre los elementos de los dos nodos hermanos fundidos.
* Elimine el separador del padre, y reemplace los dos hijos que separaba por el nuevo nodo fundido.
* Si esa acción deja al número de elementos del padre por debajo del mínimo, repita estos pasos en el nuevo nodo deficiente, a menos que sea la raíz, ya que no tiene cota mínima en el número de elementos.
-----------------
PROGRAMA1. CONTRUCCION, RECORRIDO, ALTURA
import java.awt.Color;
import java.awt.Container;
import java.awt.FlowLayout;
import java.awt.Font;
import java.awt.TextArea;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.*;
public class PruebaArbol extends JFrame {Container c=getContentPane();private JMenuBar menu;private JMenu i1,i2;
private JMenuItem construye,mostrar,alt,hoj,anc,salir,creditos,nuevo,inor,pos,pre;
private int dato=0,nodos=0;
Arbol arbol;
String aux="R",fila=" ",columna="nn",cadena=new String();
private TextArea most;
public PruebaArbol(String cogollo){super(cogollo);c.setLayout(new FlowLayout());
menu = new JMenuBar();
i1 = new JMenu("ARCHIVO");
i2 = new JMenu("PROCESOS");
nuevo=new JMenuItem("NUEVO PROYECTO");
salir=new JMenuItem("SALIR");
construye=new JMenuItem("CONSTRUIR ARBOL");
mostrar=new JMenuItem("MOSTRAR ARBOL");
alt=new JMenuItem("ALTURA DEL ARBOL");
hoj=new JMenuItem("HOJAS DEL ARBOL");
anc=new JMenuItem("ANCESTROS DEL ARBOL");
inor=new JMenuItem("INORDEN");pre=new JMenuItem("PREORDEN");
pos=new JMenuItem("POSORDEN");
creditos=new JMenuItem("CREDITOS");
i1.add(nuevo);
i1.add(construye);
i1.add(mostrar);
i1.add(creditos);
i1.add(salir);
i2.add(alt);i2.add(hoj);
i2.add(anc);i2.add(inor);
i2.add(pos);i2.add(pre);
nuevo.addActionListener(new manejaEventos());
salir.addActionListener(new manejaEventos());
mostrar.addActionListener(new manejaEventos());
construye.addActionListener(new manejaEventos())
;alt.addActionListener(new manejaEventos());
anc.addActionListener(new manejaEventos());
hoj.addActionListener(new manejaEventos());
inor.addActionListener(new manejaEventos());
pre.addActionListener(new manejaEventos());
pos.addActionListener(new manejaEventos());
creditos.addActionListener(new manejaEventos());
menu.add(i1);
menu.add(i2);
c.setBackground(new Color(128,0,255));
setJMenuBar(menu);
setSize( 1024 , 768 );
setVisible( true );
}class manejaEventos implements ActionListener{public void actionPerformed(ActionEvent e){ if(e.getSource()==construye){arbol=new Arbol();
int valor=0;
nodos=Integer.parseInt( JOptionPane.showInputDialog(null,"ingrese el numero de nodos para el arbol") );for (int i=1;i
------------
PROGRAMA2 ARBOL GENERICO
public Arboles() {
System.out.println("Un árbol genérico");
}
public Arboles(String tipo) {
System.out.println("Un árbol tipo " + tipo);
}
public Arboles(int altura) {
System.out.println("Un árbol de " + altura + " metros");
}
public Arboles(int altura,String tipo) {
System.out.println("Un " + tipo + " de " + altura + " metros");
}
public static void main(String args[]) {
Arboles arbol1 = new Arboles(4);
Arboles arbol2 = new Arboles("Roble");
Arboles arbol3 = new Arboles();
Arboles arbol4 = new Arboles(5,"Pino");
}
}
----------
PROGRAMA
package pfc15;
import java.util.*;
import java.awt.*;
import javax.swing.*;
import java.awt.event.*;
import javax.swing.tree.*;
public class Arboles extends JPanel{
//elementos para crear el entorno grafico
private static JSplitPane oJSP1, oJSP2;
private static JTree arbol1,arbol2;
static int i=0;
DefaultMutableTreeNode raiz,raiz2,rama,seleccion;
DefaultTreeModel modelo,modelo2;
/////////////////////////////////////////
/** Creates a new instance of arboles */
public Arboles() {
//creamos el entorno grafico
oJSP1 = new JSplitPane(JSplitPane.HORIZONTAL_SPLIT);
oJSP2 = new JSplitPane(JSplitPane.HORIZONTAL_SPLIT);
raiz = new DefaultMutableTreeNode( "raiz" );
arbol1 = new JTree(raiz);
//////////////////////////////////////////////////////////////////
//codigo necesario en los arboles para controlar las acciones
// Se obtiene el modelo del árbol
modelo =(DefaultTreeModel)arbol1.getModel();
modelo.addTreeModelListener(new MiTreeModelListener());
arbol1.addTreeSelectionListener(new MiTreeSelectionListener());
arbol1.addTreeExpansionListener(new MiTreeExpansionListener());
////////////////////////////////////////////////////////////////
oJSP2.setRightComponent(new JScrollPane( arbol1));
oJSP2.setLeftComponent(new JScrollPane());
oJSP1.setRightComponent(oJSP2);
raiz2 = new DefaultMutableTreeNode( "raiz2" );
arbol2 = new JTree(raiz2);
//////////////////////////////////////////////////////////////////
//codigo necesario en los arboles para controlar las acciones
// Se obtiene el modelo del árbol
modelo2 =(DefaultTreeModel)arbol2.getModel();
modelo2.addTreeModelListener(new MiTreeModelListener());
arbol2.addTreeSelectionListener(new MiTreeSelectionListener());
arbol2.addTreeExpansionListener(new MiTreeExpansionListener());
////////////////////////////////////////////////////////////////
oJSP1.setLeftComponent(new JScrollPane(arbol2));
Dimension minimumSize = new Dimension(100, 540);
oJSP1.setDividerLocation(150);
oJSP1.setDividerSize(10);
oJSP1.setPreferredSize(new Dimension(500, 450));
this.add(oJSP1);
//creamos las tablas para almacenar las acciones
//
}
//anhade una nueva rama al nodo seleccionado
void nueva_rama(){
Estructura est;
String datos[][] = {
{ "Colores","Rojo","Verde","Azul" },
{ "Sabores","Salado","Dulce","Amargo" },
{ "Longitud","Corta","Media","Larga" },
{ "Intensidad","Alta","Media","Baja" },
{ "Temperatura","Alta","Media","Baja" },
{ "Volumen","Alto","Medio","Bajo" },
};
if( i == datos.length ) i = 0;
rama = new Rama( datos[i++] ).node();
// Control de la útlima selección realizada
if (MiTreeSelectionListener.oEstructura.getTree() == null) return;
seleccion = (DefaultMutableTreeNode)MiTreeSelectionListener.oEstructura.getTree().getLastSelectedPathComponent();
if( seleccion == null ) {
System.out.println("AKI LA CAGO!!!!!!!!!!");
seleccion = raiz;
}
// El modelo creará el evento adecuado, y en respuesta
// a él, el árbol se actualizará automáticamente
MiTreeSelectionListener.oEstructura.getModelo().insertNodeInto( rama,seleccion,0 );
}
//elimina la rama seleccionada
void elimina_rama(){
Estructura est;
//buscamos la rama seleccionada
rama = (DefaultMutableTreeNode) MiTreeSelectionListener.oEstructura.getTree().getLastSelectedPathComponent();
//comprobamos q la rama no sea nula
if (rama == null) return;
//comprobamos q no sea la rama raiz y la borramos
if ((rama !=raiz)&&(rama !=raiz2)) MiTreeSelectionListener.oEstructura.getModelo().removeNodeFromParent(rama);
}
}
import java.util.*;
import java.awt.*;
import javax.swing.*;
import java.awt.event.*;
import javax.swing.tree.*;
public class Arboles extends JPanel{
//elementos para crear el entorno grafico
private static JSplitPane oJSP1, oJSP2;
private static JTree arbol1,arbol2;
static int i=0;
DefaultMutableTreeNode raiz,raiz2,rama,seleccion;
DefaultTreeModel modelo,modelo2;
/////////////////////////////////////////
/** Creates a new instance of arboles */
public Arboles() {
//creamos el entorno grafico
oJSP1 = new JSplitPane(JSplitPane.HORIZONTAL_SPLIT);
oJSP2 = new JSplitPane(JSplitPane.HORIZONTAL_SPLIT);
raiz = new DefaultMutableTreeNode( "raiz" );
arbol1 = new JTree(raiz);
//////////////////////////////////////////////////////////////////
//codigo necesario en los arboles para controlar las acciones
// Se obtiene el modelo del árbol
modelo =(DefaultTreeModel)arbol1.getModel();
modelo.addTreeModelListener(new MiTreeModelListener());
arbol1.addTreeSelectionListener(new MiTreeSelectionListener());
arbol1.addTreeExpansionListener(new MiTreeExpansionListener());
////////////////////////////////////////////////////////////////
oJSP2.setRightComponent(new JScrollPane( arbol1));
oJSP2.setLeftComponent(new JScrollPane());
oJSP1.setRightComponent(oJSP2);
raiz2 = new DefaultMutableTreeNode( "raiz2" );
arbol2 = new JTree(raiz2);
//////////////////////////////////////////////////////////////////
//codigo necesario en los arboles para controlar las acciones
// Se obtiene el modelo del árbol
modelo2 =(DefaultTreeModel)arbol2.getModel();
modelo2.addTreeModelListener(new MiTreeModelListener());
arbol2.addTreeSelectionListener(new MiTreeSelectionListener());
arbol2.addTreeExpansionListener(new MiTreeExpansionListener());
////////////////////////////////////////////////////////////////
oJSP1.setLeftComponent(new JScrollPane(arbol2));
Dimension minimumSize = new Dimension(100, 540);
oJSP1.setDividerLocation(150);
oJSP1.setDividerSize(10);
oJSP1.setPreferredSize(new Dimension(500, 450));
this.add(oJSP1);
//creamos las tablas para almacenar las acciones
//
}
//anhade una nueva rama al nodo seleccionado
void nueva_rama(){
Estructura est;
String datos[][] = {
{ "Colores","Rojo","Verde","Azul" },
{ "Sabores","Salado","Dulce","Amargo" },
{ "Longitud","Corta","Media","Larga" },
{ "Intensidad","Alta","Media","Baja" },
{ "Temperatura","Alta","Media","Baja" },
{ "Volumen","Alto","Medio","Bajo" },
};
if( i == datos.length ) i = 0;
rama = new Rama( datos[i++] ).node();
// Control de la útlima selección realizada
if (MiTreeSelectionListener.oEstructura.getTree() == null) return;
seleccion = (DefaultMutableTreeNode)MiTreeSelectionListener.oEstructura.getTree().getLastSelectedPathComponent();
if( seleccion == null ) {
System.out.println("AKI LA CAGO!!!!!!!!!!");
seleccion = raiz;
}
// El modelo creará el evento adecuado, y en respuesta
// a él, el árbol se actualizará automáticamente
MiTreeSelectionListener.oEstructura.getModelo().insertNodeInto( rama,seleccion,0 );
}
//elimina la rama seleccionada
void elimina_rama(){
Estructura est;
//buscamos la rama seleccionada
rama = (DefaultMutableTreeNode) MiTreeSelectionListener.oEstructura.getTree().getLastSelectedPathComponent();
//comprobamos q la rama no sea nula
if (rama == null) return;
//comprobamos q no sea la rama raiz y la borramos
if ((rama !=raiz)&&(rama !=raiz2)) MiTreeSelectionListener.oEstructura.getModelo().removeNodeFromParent(rama);
}
}
--------
PROGRAMA ARBOL BINARIO
public class CArbolBinarioDeBusqueda extends CArbolBinB
{
public int comparar(Object obj1, Object obj2)
{
String str1=new String(((CDatos)obj1).obtenerNombre());
String str2=new String(((CDatos)obj2).obtenerNombre());
return str1.compareTo(str2);
}
public void procesar(Object obj)
{
String nombre=new String(((CDatos)obj).obtenerNombre());
Double nota=((CDatos)obj).obtenerNota();
System.out.println(nombre+" "+nota);
}
public void visitarInorden()
{
inorden(null, true);
}
public void visitarPosorden()
{
posorden(null, true);
}
public void visitarPreorden()
{
preorden(null, true);
}
}
-----------
PROGRAMA A. BINARIO
public abstract class CArbolBinB{
protected CNodo raiz=null;
private class CNodo{
private Object datos;
private CNodo izquierdo;
private CNodo derecho;
public CNodo(){
}
}
public static final int CORRECTO=000;
public static final int NO_DATOS=100;
public static final int YA_EXISTE=101;
public static final int NO_EXISTE=102;
public CArbolBinB(){
}
public abstract int comparar(Object obj1, Object obj2);
public abstract void procesar(Object obj);
public abstract void visitarInorden();
public abstract void visitarPosorden();
public abstract void visitarPreorden();
public Object buscar(Object obj){
CNodo actual=raiz;
int nComp=0;
while(actual!=null){
if((nComp=comparar(obj,actual.datos))==0)
return(actual.datos);
else if(nComp<0) actual="actual.izquierdo;" actual="actual.derecho;" ultimo="null," actual="raiz;" ncomp="0;" obj="=" ncomp="comparar(obj," ultimo="actual;" actual="actual.izquierdo;" actual="actual.derecho;" actual="=" nuevonodo="new" datos="obj;" izquierdo="nuevoNodo.derecho=" ultimo="=" raiz="nuevoNodo;" izquierdo="nuevoNodo;" derecho="nuevoNodo;" ultimo="null," actual="raiz;" marcado="null," sucesor="null;" nanteriorcomp="0," ncomp="0;" obj="=" nanteriorcomp="nComp;" ncomp="comparar(obj,actual.datos))=" ultimo="actual;" actual="actual.izquierdo;" actual="actual.derecho;" marcado="actual;" izquierdo="=" derecho="=" sucesor="null;" izquierdo="=" sucesor="actual.derecho;" derecho="=" sucesor="actual.izquierdo;" sucesor="actual=" actual="actual.izquierdo;" izquierdo="marcado.izquierdo;" izquierdo="sucesor;" derecho="sucesor;" raiz="sucesor;" actual="null;" actual="raiz;" actual="r;" actual="null;" actual="raiz;" actual="r;" actual="null;" actual="raiz;" actual="r;">
PROGRAMA7
public class CDatos
{
private String nombre;
private double nota;
public CDatos(){}
public CDatos(String nom, double n)
{
nombre=nom;
nota=n;
}
public void asignarNombre(String nom)
{
nombre=nom;
}
public String obtenerNombre()
{
return nombre;
}
public void asignarNota(double n)
{
nota=n;
}
public double obtenerNota()
{
return nota;
}
}
--------------
PROGRMA8A
import java.io.*;
public class Leer{
public static String dato(){
String sdato = "";
try{
InputStreamReader isr =
new InputStreamReader(System.in);
BufferedReader flujoE=
new BufferedReader(isr);
sdato = flujoE.readLine();
}
catch(IOException e){
System.err.println("Error: " + e.getMessage());
}
return sdato;
}
public static short datoShort(){
try{
return Short.parseShort(dato());
}
catch(NumberFormatException e){
return Short.MIN_VALUE;
}
}
public static int datoInt(){
try{
return Integer.parseInt(dato());
}
catch(NumberFormatException e){
return Integer.MIN_VALUE;
}
}
public static long datoLong(){
try{
return Long.parseLong(dato());
}
catch(NumberFormatException e){
return Long.MIN_VALUE;
}
}
public static float datoFloat(){
try{
Float f = new Float(dato());
return f.floatValue();
}
catch(NumberFormatException e){
return Float.NaN;
}
}
public static double datoDouble(){
try{
Double d = new Double(dato());
return d.doubleValue();
}
catch(NumberFormatException e){
return Double.NaN;
}
}
public static String datoString(){
return dato();
}
public static char datoChar(){
int c=0;
try{
InputStreamReader isr =
new InputStreamReader(System.in);
BufferedReader flujoE=
new BufferedReader(isr);
c=flujoE.read();
char car;
car=(char) c;
return car;
}
catch(IOException e){
return '\0';
}
}
}
---------
B I N A R I O S
PROGRAMADEARBOLESBINARIOS
import java.util.NoSuchElementException;
public class BinarySearchTree
implements SortedMap
{
private Branch root = null;
private int length = 0;
private Comparator comparator = null;
public BinarySearchTree( Comparator c )
{ comparator = c; }
public BinarySearchTree()
{ this( null ); }
public void clear()
{
root = null;
length = 0;
}
public boolean isEmpty()
{
return ( root == null );
}
public int size() // devuelve el número de elementos del mapa
{
return length;
}
public Object firstKey() // devuelve la clave del primer elemento;
// es null si el mapa está vacío
{
if ( root == null )
return null;
else
return root.first().key;
}
public Object lastKey() // devuelve la clave del último elemento;
// es null si el mapa está vacío
{
if ( root == null )
return null;
else
return root.last().key;
}
public Object get( Object k ) // devuelve el valor correspondiente a la clave k
// si ésta está en el árbol; de lo contrario, es null
{
Branch b = find( k );
return ( b == null ) ? null : b.value;
}
public Object put(Object k, Object v) // si ya hay un nodo correspondiente a
// k devuelve su valor y los sustituye por v;
// de lo contrario, inserta un nuevo nodo(k, v)
{
Branch p = null;
Branch b = root;
int c = 0;
// encuentra el nodo con clave k y conserva la referencia p al padre
while ( b != null )
{
p = b;
c = compare( k, b.key );
if ( c == 0 )
{
// lo ha encontrado; inserta el nuevo valor y devuelve el antiguo
Object oldValue = b.value;
b.value = v;
return oldValue;
}
------
import java.util.NoSuchElementException;
public class BinarySearchTree
implements SortedMap
{
private Branch root = null;
private int length = 0;
private Comparator comparator = null;
public BinarySearchTree( Comparator c )
{ comparator = c; }
public BinarySearchTree()
{ this( null ); }
public void clear()
{
root = null;
length = 0;
}
public boolean isEmpty()
{
return ( root == null );
}
public int size() // devuelve el número de elementos del mapa
{
return length;
}
public Object firstKey() // devuelve la clave del primer elemento;
// es null si el mapa está vacío
{
if ( root == null )
return null;
else
return root.first().key;
}
public Object lastKey() // devuelve la clave del último elemento;
// es null si el mapa está vacío
{
if ( root == null )
return null;
else
return root.last().key;
}
public Object get( Object k ) // devuelve el valor correspondiente a la clave k
// si ésta está en el árbol; de lo contrario, es null
{
Branch b = find( k );
return ( b == null ) ? null : b.value;
}
public Object put(Object k, Object v) // si ya hay un nodo correspondiente a
// k devuelve su valor y los sustituye por v;
// de lo contrario, inserta un nuevo nodo(k, v)
{
Branch p = null;
Branch b = root;
int c = 0;
// encuentra el nodo con clave k y conserva la referencia p al padre
while ( b != null )
{
p = b;
c = compare( k, b.key );
if ( c == 0 )
{
// lo ha encontrado; inserta el nuevo valor y devuelve el antiguo
Object oldValue = b.value;
b.value = v;
return oldValue;
}
------
B I N A R I O S 2
PROGRAMARBOLBANARIO2
import javax.swing.*;
import java.awt.event.*;
import java.awt.BorderLayout;
import java.awt.Color;
import java.util.NoSuchElementException;
public class BinarySearchTreeView
extends JPanel
implements ActionListener
{
private BinarySearchTree btree = new BinarySearchTree( );
private JLabel count;
private JTextField keyField;
private JTextField valueField;
public BinarySearchTreeView()
{
super();
setLayout( new BorderLayout() );
setBorder( BorderFactory.createLineBorder( Color.black, 2 ) );
JPanel buttons = new JPanel();
JButton clearBtn = new JButton( "clear" );
buttons.add( clearBtn );
clearBtn.addActionListener( this );
JButton firstBtn = new JButton( "first" );
buttons.add( firstBtn );
firstBtn.addActionListener( this );
JButton lastBtn = new JButton( "last" );
buttons.add( lastBtn );
lastBtn.addActionListener( this );
JButton getBtn = new JButton( "get" );
buttons.add( getBtn );
getBtn.addActionListener( this );
JButton putBtn = new JButton( "put" );
buttons.add( putBtn );
putBtn.addActionListener( this );
JButton removeBtn = new JButton( "remove" );
buttons.add( removeBtn );
removeBtn.addActionListener( this );
JButton iteratorBtn = new JButton( "iterator" );
buttons.add( iteratorBtn );
iteratorBtn.addActionListener( this );
add( buttons, BorderLayout.NORTH );
JPanel dataPanel = new JPanel( new BorderLayout() );
JPanel countPanel = new JPanel();
JLabel countLabel = new JLabel( "Count:" );
countPanel.add( countLabel, BorderLayout.WEST );
count = new JLabel( "0", JLabel.LEFT );
countPanel.add( count, BorderLayout.WEST );
dataPanel.add( countPanel, BorderLayout.WEST );
JPanel keyPanel = new JPanel( );
JLabel keyLabel = new JLabel( "Key:" );
keyPanel.add( keyLabel );
keyField = new JTextField( 12 );
keyPanel.add( keyField );
dataPanel.add( keyPanel, BorderLayout.CENTER );
JPanel valuePanel = new JPanel( );
JLabel valueLabel = new JLabel( "Value:" );
valuePanel.add( valueLabel );
valueField = new JTextField( 12 );
valuePanel.add( valueField, BorderLayout.EAST );
dataPanel.add( valuePanel, BorderLayout.EAST );
add( dataPanel, BorderLayout.CENTER );
}
public void actionPerformed( ActionEvent e )
{
String command = e.getActionCommand();
if ( command.equals( "clear" ) )
doClear();
else if ( command.equals( "first" ) )
doFirst();
else if ( command.equals( "last" ) )
doLast();
else if ( command.equals( "get" ) )
doGet();
else if ( command.equals( "put" ) )
doPut();
else if ( command.equals( "remove" ) )
doRemove();
else if ( command.equals( "iterator" ) )
doIterator();
updateView();
}
private void doClear()
{
btree.clear();
keyField.setText( null );
valueField.setText( null );
}
private void doFirst()
{
String key = (String) btree.firstKey();
keyField.setText( key );
valueField.setText( (String) btree.get( key ));
}
private void doLast()
{
String key = (String) btree.lastKey();
keyField.setText( key );
valueField.setText( (String) btree.get( key ));
}
private void doPut()
{
valueField.setText((String) btree.put( keyField.getText(),
valueField.getText()));
}
private void doGet()
{
valueField.setText( (String) btree.get( keyField.getText() ) );
}
private void doRemove()
{
valueField.setText( (String) btree.remove( keyField.getText() ) );
}
private void doIterator()
{
MapIterator iter = btree.iterator();
MapIteratorView iterView = new MapIteratorView( iter );
iterView.setVisible( true );
}
private void updateView()
{
count.setText( String.valueOf( btree.size() ));
}
}
--------------
import javax.swing.*;
import java.awt.event.*;
import java.awt.BorderLayout;
import java.awt.Color;
import java.util.NoSuchElementException;
public class BinarySearchTreeView
extends JPanel
implements ActionListener
{
private BinarySearchTree btree = new BinarySearchTree( );
private JLabel count;
private JTextField keyField;
private JTextField valueField;
public BinarySearchTreeView()
{
super();
setLayout( new BorderLayout() );
setBorder( BorderFactory.createLineBorder( Color.black, 2 ) );
JPanel buttons = new JPanel();
JButton clearBtn = new JButton( "clear" );
buttons.add( clearBtn );
clearBtn.addActionListener( this );
JButton firstBtn = new JButton( "first" );
buttons.add( firstBtn );
firstBtn.addActionListener( this );
JButton lastBtn = new JButton( "last" );
buttons.add( lastBtn );
lastBtn.addActionListener( this );
JButton getBtn = new JButton( "get" );
buttons.add( getBtn );
getBtn.addActionListener( this );
JButton putBtn = new JButton( "put" );
buttons.add( putBtn );
putBtn.addActionListener( this );
JButton removeBtn = new JButton( "remove" );
buttons.add( removeBtn );
removeBtn.addActionListener( this );
JButton iteratorBtn = new JButton( "iterator" );
buttons.add( iteratorBtn );
iteratorBtn.addActionListener( this );
add( buttons, BorderLayout.NORTH );
JPanel dataPanel = new JPanel( new BorderLayout() );
JPanel countPanel = new JPanel();
JLabel countLabel = new JLabel( "Count:" );
countPanel.add( countLabel, BorderLayout.WEST );
count = new JLabel( "0", JLabel.LEFT );
countPanel.add( count, BorderLayout.WEST );
dataPanel.add( countPanel, BorderLayout.WEST );
JPanel keyPanel = new JPanel( );
JLabel keyLabel = new JLabel( "Key:" );
keyPanel.add( keyLabel );
keyField = new JTextField( 12 );
keyPanel.add( keyField );
dataPanel.add( keyPanel, BorderLayout.CENTER );
JPanel valuePanel = new JPanel( );
JLabel valueLabel = new JLabel( "Value:" );
valuePanel.add( valueLabel );
valueField = new JTextField( 12 );
valuePanel.add( valueField, BorderLayout.EAST );
dataPanel.add( valuePanel, BorderLayout.EAST );
add( dataPanel, BorderLayout.CENTER );
}
public void actionPerformed( ActionEvent e )
{
String command = e.getActionCommand();
if ( command.equals( "clear" ) )
doClear();
else if ( command.equals( "first" ) )
doFirst();
else if ( command.equals( "last" ) )
doLast();
else if ( command.equals( "get" ) )
doGet();
else if ( command.equals( "put" ) )
doPut();
else if ( command.equals( "remove" ) )
doRemove();
else if ( command.equals( "iterator" ) )
doIterator();
updateView();
}
private void doClear()
{
btree.clear();
keyField.setText( null );
valueField.setText( null );
}
private void doFirst()
{
String key = (String) btree.firstKey();
keyField.setText( key );
valueField.setText( (String) btree.get( key ));
}
private void doLast()
{
String key = (String) btree.lastKey();
keyField.setText( key );
valueField.setText( (String) btree.get( key ));
}
private void doPut()
{
valueField.setText((String) btree.put( keyField.getText(),
valueField.getText()));
}
private void doGet()
{
valueField.setText( (String) btree.get( keyField.getText() ) );
}
private void doRemove()
{
valueField.setText( (String) btree.remove( keyField.getText() ) );
}
private void doIterator()
{
MapIterator iter = btree.iterator();
MapIteratorView iterView = new MapIteratorView( iter );
iterView.setVisible( true );
}
private void updateView()
{
count.setText( String.valueOf( btree.size() ));
}
}
--------------
PROGRAMA ARBOL BINARIO BUSQUEDA
public class CArbolBinarioDeBusqueda extends CArbolBinB
{
public int comparar(Object obj1, Object obj2)
{
String str1=new String(((CDatos)obj1).obtenerNombre());
String str2=new String(((CDatos)obj2).obtenerNombre());
return str1.compareTo(str2);
}
public void procesar(Object obj)
{
String nombre=new String(((CDatos)obj).obtenerNombre());
Double nota=((CDatos)obj).obtenerNota();
System.out.println(nombre+" "+nota);
}
public void visitarInorden()
{
inorden(null, true);
}
public void visitarPosorden()
{
posorden(null, true);
}
public void visitarPreorden()
{
preorden(null, true);
}
}
---------
ejemplo: recorrido en preorden de un arbol binario
// "raiz" es la referencia a la raiz del arbol
// llamado inicial: preorden(raiz)
// version recursiva
void preorden(Nodo nodo)
{
if (nodo!=null)
{
System.out.print(nodo.elemento);
preorden(nodo.izq);
preorden(nodo.der);
}
}
// primera version iterativa
void preorden(Nodo nodo)
{
Nodo aux;
Pila pila=new Pila(); // pila de nodos
pila.apilar(nodo);
while(!pila.estaVacia()) // mientras la pila no este vacia
{
aux=pila.desapilar();
if (aux!=null)
{
System.out.print(aux.elemento);
// primero se apila el nodo derecho y luego el izquierdo
// para mantener el orden correcto del recorrido
// al desapilar los nodos
pila.apilar(aux.der);
pila.apilar(aux.izq);
}
}
}
// segunda version iterativa
// dado que siempre el ultimo nodo apilado dentro del bloque if es
// aux.izq podemos asignarlo directamente a aux hasta que éste sea
// null, es decir, el bloque if se convierte en un bloque while
// y se cambia el segundo apilar por una asignacion de la referencia
void preorden(Nodo nodo)
{
Nodo aux;
Pila pila=new Pila(); // pila de nodos
pila.apilar(nodo);
while(!pila.estaVacia()) // mientras la pila no este vacia
{
aux=pila.desapilar();
while (aux!=null)
{
System.out.print(aux.elemento);
pila.apilar(aux.der);
aux=aux.izq;
}
}
}
--------
P R O G R A M A A R B O L L I S T A
import java.io.*;
public class Leer{
public static String dato(){
String sdato = "";
try{
InputStreamReader isr =
new InputStreamReader(System.in);
BufferedReader flujoE=
new BufferedReader(isr);
sdato = flujoE.readLine();
}
catch(IOException e){
System.err.println("Error: " + e.getMessage());
}
return sdato;
}
public static short datoShort(){
try{
return Short.parseShort(dato());
}
catch(NumberFormatException e){
return Short.MIN_VALUE;
}
}
public static int datoInt(){
try{
return Integer.parseInt(dato());
}
catch(NumberFormatException e){
return Integer.MIN_VALUE;
}
}
public static long datoLong(){
try{
return Long.parseLong(dato());
}
catch(NumberFormatException e){
return Long.MIN_VALUE;
}
}
public static float datoFloat(){
try{
Float f = new Float(dato());
return f.floatValue();
}
catch(NumberFormatException e){
return Float.NaN;
}
}
public static double datoDouble(){
try{
Double d = new Double(dato());
return d.doubleValue();
}
catch(NumberFormatException e){
return Double.NaN;
}
}
public static String datoString(){
return dato();
}
public static char datoChar(){
int c=0;
try{
InputStreamReader isr =
new InputStreamReader(System.in);
BufferedReader flujoE=
new BufferedReader(isr);
c=flujoE.read();
char car;
car=(char) c;
return car;
}
catch(IOException e){
return '\0';
}
}
}
-----------
public class Leer{
public static String dato(){
String sdato = "";
try{
InputStreamReader isr =
new InputStreamReader(System.in);
BufferedReader flujoE=
new BufferedReader(isr);
sdato = flujoE.readLine();
}
catch(IOException e){
System.err.println("Error: " + e.getMessage());
}
return sdato;
}
public static short datoShort(){
try{
return Short.parseShort(dato());
}
catch(NumberFormatException e){
return Short.MIN_VALUE;
}
}
public static int datoInt(){
try{
return Integer.parseInt(dato());
}
catch(NumberFormatException e){
return Integer.MIN_VALUE;
}
}
public static long datoLong(){
try{
return Long.parseLong(dato());
}
catch(NumberFormatException e){
return Long.MIN_VALUE;
}
}
public static float datoFloat(){
try{
Float f = new Float(dato());
return f.floatValue();
}
catch(NumberFormatException e){
return Float.NaN;
}
}
public static double datoDouble(){
try{
Double d = new Double(dato());
return d.doubleValue();
}
catch(NumberFormatException e){
return Double.NaN;
}
}
public static String datoString(){
return dato();
}
public static char datoChar(){
int c=0;
try{
InputStreamReader isr =
new InputStreamReader(System.in);
BufferedReader flujoE=
new BufferedReader(isr);
c=flujoE.read();
char car;
car=(char) c;
return car;
}
catch(IOException e){
return '\0';
}
}
}
-----------
PROGRAMAARBOLESB
package org.neos.arboles.binarios.dinamicos;
import java.util.ArrayList;
import org.neos.arboles.binarios.dinamicos.beans.Informacion;
import org.neos.arboles.binarios.dinamicos.beans.Nodo;
import org.neos.arboles.binarios.dinamicos.exceptions.ExceptionElementoDuplicado;
import org.neos.arboles.binarios.dinamicos.exceptions.ExceptionNoEncontrado;
/**
* @version 1.0
* @author Eugenio Flores
* Para cambiar la plantilla para este comentario de tipo generado vaya a
* Ventana>Preferencias>Java>Generación de código>Código y comentarios
*/
public class ArbolBinario {
private Nodo raiz;
private ArrayList recorrido;
/**
* Constructor que permite crear un árbol contenido en un vector de un
* tamaño definido por el parámetro recibido.
* @param num_elementos Número de elementos que podrá contener el vector.
* @throws ExceptionDimensionInvalida En caso de que el tamaño del vector
* no sea valido.
*/
public ArbolBinario() {
this.raiz = null;
this.recorrido = null;
}
/**
* Método útil para preguntar es nuestro árbol esta vacío o no.
* @return
*
*/
public boolean esArbolVacio() {
return (null == raiz) ? true : false;
}
/**
* Obtener la posición del nodo raíz.
* @return Posición del elemento que representa al nodo raíz. Se obtiene -1
* si el árbol esta vacío.
*/
public Nodo obtenerPosicionRaiz() {
return raiz;
}
/**
* Obtener respuesta a la pregunta ¿Existe el elemento en el árbol?
* @param info información a buscar dentro del árbol.
* @return
* la información especificada.
*
* contiene la información especificada.
public boolean existeElemento(Object info) {
Nodo nodo = obtenerElemento(info, raiz);
if(null != nodo) {
return true;
} else {
return false;
}
}
/**
* Obtener el elemento (Nodo) que contiene la información indicada.
* @param info Información que se busca dentro del árbol.
* @return
* la información existe dentro del árbol.
*
existe dentro del árbol.
*/
public Nodo obtenerElemento(Object info, Nodo raiz) {
if(null == raiz) {
return raiz;
} else {
Informacion obj_info = new Informacion(info);
Informacion obj_info_pa = new Informacion( raiz.getInformacion() );
if( obj_info_pa.equals(obj_info) ) {
return raiz;
} else if( obj_info.compareTo(obj_info_pa) < num_elems =" 0;" peso =" 0;" num_h_izq =" 0;" num_h_der =" 0;" num_h_izq =" obtenerNumeroElementos(nodo.getIzquierdo());" num_h_der =" obtenerNumeroElementos(nodo.getDerecho());" peso =" num_h_izq" altura =" 0;" altura_r_izq =" 0;" altura_r_der =" 0;" altura =" 1;" ref_h_izq =" nodo.getIzquierdo();" ref_h_der =" nodo.getDerecho();" altura_r_izq =" obtenerAltura(ref_h_izq);" altura_r_der =" obtenerAltura(ref_h_der);">= altura_r_der) { // tomar en cuenta solo la rama de mayor altura
altura += altura_r_izq;
} else {
altura += altura_r_der;
}
} else if( (ref_h_izq != null) && (ref_h_der == null) ) { // si solo tiene rama izquierda
altura += obtenerAltura(ref_h_izq);
} else if( (ref_h_izq == null) && (ref_h_der != null) ) { // si solo tiene rama derecha
altura += obtenerAltura(ref_h_der);
} else if( (ref_h_izq == null) && (ref_h_der == null) ) { // si el nodo es una hoja
altura -= 1;
}
}
return altura;
}
/**
* Método de apoyo a InsertarElemento(int). Este método se encarga de
* agregar el elemento dentro del vector que representa el árbol.
* @param info Información que contendrá el nuevo nodo.
* @param nodo Nodo contra el que se compara la información.
* @return La respuesta a la pregunta ¿Se inserto el elemento?
*/
private boolean insertarElemento(Object info, Nodo nodo) {
Nodo nuevo_nodo = null;
Informacion obj_info = new Informacion(info);
Informacion obj_info_pa = new Informacion( nodo.getInformacion() );
if( obj_info.compareTo(obj_info_pa) < nuevo_nodo =" new" nuevo_nodo =" new" se_inserto =" false;" raiz =" new" se_inserto =" true;" se_inserto =" insertarElemento(info," nodo =" null;" se_borro =" false;" nodo =" obtenerElemento(info," se_borro =" borrarNodoInterior(nodo);" se_borro =" borrarNodoHoja(nodo);" se_borro =" borrarNodoRaiz(nodo);" respuesta =" false;" nodo_padre =" nodo.getPadre();" nodo_izq =" nodo.getIzquierdo();" nodo_der =" nodo.getDerecho();" nodo_c =" null;" nodo_c =" new" nodo =" null;" nodo_izq =" null;" respuesta =" true;" nodo =" null;" respuesta =" true;" nodo =" null;" respuesta =" true;" se_borro =" false;" nodo_padre =" nodo.getPadre();" nodo =" null;" se_borro =" true;" se_borro =" false;" nodo_izq =" nodo.getIzquierdo();" nodo_der =" nodo.getDerecho();" nodo_c =" null;" raiz =" nodo_der;" nodo_c =" new" nodo =" null;" nodo_izq =" null;" se_borro =" true;" raiz =" nodo_izq;" nodo =" null;" se_borro =" true;" raiz =" nodo_der;" nodo =" null;" se_borro =" true;" raiz =" null;" se_borro =" true;" nodo ="="" recorrido =" new" nodo ="="" recorrido =" new" nodo ="="" recorrido =" new">
*/
public Nodo obtenerElemento(Object info, Nodo raiz) {
if(null == raiz) {
return raiz;
} else {
Informacion obj_info = new Informacion(info);
Informacion obj_info_pa = new Informacion( raiz.getInformacion() );
if( obj_info_pa.equals(obj_info) ) {
return raiz;
} else if( obj_info.compareTo(obj_info_pa) < num_elems =" 0;" peso =" 0;" num_h_izq =" 0;" num_h_der =" 0;" num_h_izq =" obtenerNumeroElementos(nodo.getIzquierdo());" num_h_der =" obtenerNumeroElementos(nodo.getDerecho());" peso =" num_h_izq" altura =" 0;" altura_r_izq =" 0;" altura_r_der =" 0;" altura =" 1;" ref_h_izq =" nodo.getIzquierdo();" ref_h_der =" nodo.getDerecho();" altura_r_izq =" obtenerAltura(ref_h_izq);" altura_r_der =" obtenerAltura(ref_h_der);">= altura_r_der) { // tomar en cuenta solo la rama de mayor altura
altura += altura_r_izq;
} else {
altura += altura_r_der;
}
} else if( (ref_h_izq != null) && (ref_h_der == null) ) { // si solo tiene rama izquierda
altura += obtenerAltura(ref_h_izq);
} else if( (ref_h_izq == null) && (ref_h_der != null) ) { // si solo tiene rama derecha
altura += obtenerAltura(ref_h_der);
} else if( (ref_h_izq == null) && (ref_h_der == null) ) { // si el nodo es una hoja
altura -= 1;
}
}
return altura;
}
/**
* Método de apoyo a InsertarElemento(int). Este método se encarga de
* agregar el elemento dentro del vector que representa el árbol.
* @param info Información que contendrá el nuevo nodo.
* @param nodo Nodo contra el que se compara la información.
* @return La respuesta a la pregunta ¿Se inserto el elemento?
*/
private boolean insertarElemento(Object info, Nodo nodo) {
Nodo nuevo_nodo = null;
Informacion obj_info = new Informacion(info);
Informacion obj_info_pa = new Informacion( nodo.getInformacion() );
if( obj_info.compareTo(obj_info_pa) < nuevo_nodo =" new" nuevo_nodo =" new" se_inserto =" false;" raiz =" new" se_inserto =" true;" se_inserto =" insertarElemento(info," nodo =" null;" se_borro =" false;" nodo =" obtenerElemento(info," se_borro =" borrarNodoInterior(nodo);" se_borro =" borrarNodoHoja(nodo);" se_borro =" borrarNodoRaiz(nodo);" respuesta =" false;" nodo_padre =" nodo.getPadre();" nodo_izq =" nodo.getIzquierdo();" nodo_der =" nodo.getDerecho();" nodo_c =" null;" nodo_c =" new" nodo =" null;" nodo_izq =" null;" respuesta =" true;" nodo =" null;" respuesta =" true;" nodo =" null;" respuesta =" true;" se_borro =" false;" nodo_padre =" nodo.getPadre();" nodo =" null;" se_borro =" true;" se_borro =" false;" nodo_izq =" nodo.getIzquierdo();" nodo_der =" nodo.getDerecho();" nodo_c =" null;" raiz =" nodo_der;" nodo_c =" new" nodo =" null;" nodo_izq =" null;" se_borro =" true;" raiz =" nodo_izq;" nodo =" null;" se_borro =" true;" raiz =" nodo_der;" nodo =" null;" se_borro =" true;" raiz =" null;" se_borro =" true;" nodo ="="" recorrido =" new" nodo ="="" recorrido =" new" nodo ="="" recorrido =" new">
lunes, 30 de marzo de 2009
ARBOLES
Es un conjunto de nodos en cada nodo hay información
Cada nodo pude contener ( Strings, alfanuméricos y caracteres especiales)
1.Nodo vacio T= Q => T = [ ]
2.Raíz = Se desprende los subarboles
3.Logitud: es el numero de ramas o aristas desde la raíz hasta el nodo en referencia.
4.Profundidad: Se cuentan los nodos desde la raíz hasta el ultimo nodo.
5.Grado: Cantidad de nodos que tiene la raíz.
6.Tamaño. Es el numero de nodos del orden
Nota: Los nodos vacios se llaman externos y los nodos llenos se llaman internos.
Otras características:
Recorridos
•Preorden [R, I, D]
•Inorden [I,R,D]
•Post Orden [I,D,R]
Cada nodo pude contener ( Strings, alfanuméricos y caracteres especiales)
1.Nodo vacio T= Q => T = [ ]
2.Raíz = Se desprende los subarboles
3.Logitud: es el numero de ramas o aristas desde la raíz hasta el nodo en referencia.
4.Profundidad: Se cuentan los nodos desde la raíz hasta el ultimo nodo.
5.Grado: Cantidad de nodos que tiene la raíz.
6.Tamaño. Es el numero de nodos del orden
Nota: Los nodos vacios se llaman externos y los nodos llenos se llaman internos.
Otras características:
Recorridos
•Preorden [R, I, D]
•Inorden [I,R,D]
•Post Orden [I,D,R]
COLAS
Cola (Principio fijo) FIFO
FIFO
First → in → Primero en entrar.
First → out → Primero en salir.
Operaciones con la cola:
1)Enqueve: Añade un elemento final de la cola.
2)Dequeve: elimina el primer elemento de la cola.
3)IsEmpty: La cola esta vacía.
4)IsFull: La cola esta llena.
Consideraciones:
1.La operación de insertar no tiene restricciones.
2.No se puede remover elementos de una lista vacía (Underflow)
3.Se necesita una arreglo y dos variables numéricas (Font – primer elemento se incializa en 0 y Rear Posición del ultimo elemento de la fila -1.
Fila Circular
1.El elemento anterior al primero es el último (en inglés es una dequeue)
2.Implementación con arreglos.
Fila Doble
Los elementos pueden insertarse o eliminarse por cualquiera de los dos extremos.
Variantes:
•Doble fila con entrada restringida
•Doble fila con Salida restringida
Operaciones:
•Insertar elementos Insertar elementos
•Eliminar elementos Eliminar elementos
•Ver si la fila esta vacía
•Ver si la fila esta llena
•Imprimir los elementos Imprimir los elementos
•Obtener el largo de la fila Obtener el largo de la fila
FIFO
First → in → Primero en entrar.
First → out → Primero en salir.
Operaciones con la cola:
1)Enqueve: Añade un elemento final de la cola.
2)Dequeve: elimina el primer elemento de la cola.
3)IsEmpty: La cola esta vacía.
4)IsFull: La cola esta llena.
Consideraciones:
1.La operación de insertar no tiene restricciones.
2.No se puede remover elementos de una lista vacía (Underflow)
3.Se necesita una arreglo y dos variables numéricas (Font – primer elemento se incializa en 0 y Rear Posición del ultimo elemento de la fila -1.
Fila Circular
1.El elemento anterior al primero es el último (en inglés es una dequeue)
2.Implementación con arreglos.
Fila Doble
Los elementos pueden insertarse o eliminarse por cualquiera de los dos extremos.
Variantes:
•Doble fila con entrada restringida
•Doble fila con Salida restringida
Operaciones:
•Insertar elementos Insertar elementos
•Eliminar elementos Eliminar elementos
•Ver si la fila esta vacía
•Ver si la fila esta llena
•Imprimir los elementos Imprimir los elementos
•Obtener el largo de la fila Obtener el largo de la fila
JAVA:
import java.io.*;
import java.io.*;
//Declaramos la clase calculatorTest
public class ejecutar_cola{
//Declaramos el metodo principal
int Espacios = 0;
char Resp,
//---
Imprimir Menu ----
System.out.print("\t Cuantos espacios quiere en la Cola (entre 3 y 30 recomendable)? :"); Espacios = Integer.parseInt(entrada.readLine());
Cola Ejecutar = new Cola(Espacios);
//--- Imprimir Menu ----
//-------- Menu Cola Simple --------\\\\------------ \n ");
aux = entrada.readLine(); op = aux.charAt(0);
//---- Elegir opcion ---
\\ switch (op) { case '1': Ejecutar.Imprimir();
break; case '2':
Ejecutar.Push();
break;
case '3': Ejecutar.Pop();
break;
default:
System.out.println("opcion fuera de rango !!"); }
aux = entrada.readLine(); Resp = aux.charAt(0); } while (Resp == 'S' Resp == 's'); }
// Fin del metodo main }
// Fin de la calse Cola.java(Clase y Metodos de la Cola)
----------------------------------------------------------
Ejemplo: cola de espera
import java.util.*;
public class ColaEspera {
/** Clase interna para almacenar todos los datos de un cliente*/
private static class DatosCliente { Cliente c; long entrada, salida;
// milisegundos
/** Constructor; pone la hora de entrada*/ DatosCliente (Cliente c) {
this.c=c; entrada=Reloj.ahora(); }
void atiende() { salida=Reloj.ahora(); } }
// colas del servicio private Queue colaEspera;
private Queue colaAtendidos;
/**Constructor de ColaEspera *
/ public ColaEspera() {
colaEspera=new LinkedList();
colaAtendidos=new LinkedList(); }
** * Nuevo cliente; se mete en la cola de espera */
public void nuevoCliente(Cliente c)
{ DatosCliente datos=new DatosCliente(c);
colaEspera.add(datos);
} /** * Atender cliente: se saca de la cola de * espera y se mete en la de atendidos;
* retorna el cliente atendido */
public Cliente atenderCliente() throws NoSuchElementException {
DatosCliente datos=colaEspera.remove();
datos.atiende();
colaAtendidos.add(datos);
return datos.c; }
public double tiempoEsperaNoAtendidos() {
long tiempo=0;
int num=0;
long ahora=Reloj.ahora();
for (DatosCliente datos: colaEspera) { tiempo=tiempo + ahora-datos.entrada; num++; }
if (num==0) { return 0.0; }
else { return (((double) tiempo)/num)/1000.0; } }
public double tiempoEsperaNoAtendidos() {
long tiempo=0;
int num=0; long ahora=Reloj.ahora();
for (DatosCliente datos: colaEspera) { tiempo=tiempo + ahora-datos.entrada; num++; }
if (num==0) { return 0.0; }
else { return (((double) tiempo)/num)/1000.0; } }
Ejemplo con cola de prioridad /** *
Clase enumerada que representa la * urgencia de un cliente */
public enum Urgencia { baja, media, alta }
import java.util.*;
/public class ColaEsperaConUrgencia {
/** * Clase interna para almacenar los datos * de un cliente con urgencia */
private static class DatosCliente implements Comparable {
Cliente c; Urgencia urg; /** *
Constructor de DatosCliente */
DatosCliente (Cliente c, Urgencia urg) { this.c=c; this.urg=urg; }
/* * Comparación de clientes por su urgencia */
public int compareTo(DatosCliente otro) { return this.urg.compareTo(otro.urg); } //
cola del servicio private Queue colaEspera;
/** * Constructor de ColaEspera */ public ColaEsperaConUrgencia() { colaEspera=new PriorityQueue(); } /** * Nuevo clie
nte; se mete en la cola de espera *
/ public void nuevoCliente (Cliente c, Urgencia urg) { DatosCliente datos=new DatosCliente(c,urg); colaEspera.add(datos); }
/** * Atender cliente: se saca de la cola de * espera; retorna el cliente atendido */
public Cliente atenderCliente() throws NoSuchElementException { DatosCliente datos=colaEspera.remove(); return datos.c; }
/** *
Mostrar el estado de la cola de espera */
public void muestraEstado()
{ System.out.println();
System.out.println("--Estado de la cola--");
System.out.println("No atendidos "+ colaEspera.size());
if (colaEspera.size()>0) { for (DatosCliente datos:colaEspera) { System.out.println(datos.c+" urgencia: "+datos.urg); }
} }
/** * Num clientes en espera */ public int numClientesEnEspera() { return colaEspera.size();
} }
PILAS
Datos que se introducen (añaden o apilan) o se extraen (extraen o des apilan).
Tope (Se debe analizar cuando esta vacía)
Operaciones con la pila
1. PUSH: Añade un elemento a la pila.
2. POP: Quita un elemento a la pila.
3. PEEK: Tope de la pila.
4. IsEmpty: (Esta vacía) Determina que una pila no tiene elementos.
5. IsFull: (Esta llena) Determina si la pila esta llena.
6. Size: Determina el numero de elementos de la pila.
Ejemplo:
LIFO:
Last → in → ultima en entrar
First → out → primera en salir
Implementación:
1) Mediante un arreglo (Estatico) - Tamaño –Vector
[-1(Tope)][0][1][2][3]
2) Lista Enlazadas ( Dinamicas)
AN ( extraer, des apilar)
Ejemplo (1+2)*4+3
Entrada Operación Pila
1Apila operador 1
2Apila operador 1,2
+Añade 3
4Apila operador 3,4
*Añade 12
3Apila operador 12,3
+Añade 15 (Tope)
Nota: No tiene encuentra los paréntesis y pera de izquierda a derecha
Metodo_Principal.java
(Metodo Principal) JAVA:
import java.io.*;
public class Metodo_Principal{
/Declaramos el metodo principal public static void main (String args[])throws IOException {
BufferedReader entrada = new BufferedReader (new InputStreamReader(System.in));
int Espacios = 0;
char Resp, op;
String aux;
//--- Imprimir Menu ---- \\
System.out.println("\n :: XROM RELOADED :: 19/07/07 \n"); System.out.print("\t Cuantos espacios quiere en la Pila (entre 3 y 30 recomendable)? :");
Espacios = Integer.parseInt(entrada.readLine());
Pila Ejecutar = new Pila(Espacios);
System.out.println("\n\n\t --- //---- Menu Pila------\\\\---- \n");
do { System.out.println("\n\n1.- Imprimir Pila");
// Mostrar System.out.println("2.- Agregar Elemento a la pila");
// Push System.out.println("3.- Quitar Elemento de la pila");
// Pop System.out.print("\n\n Elija una Opcion : ");
aux = entrada.readLine();
op = aux.charAt(0);
//---- Elegir opcion ---\\ switch (op) { case '1': Ejecutar.Imprimir();
break;
case '2': Ejecutar.Push();
break;
case '3': Ejecutar.Pop();
break;
default: System.out.println("opcion fuera de rango !!"); }
// Fin del switch System.out.print("Desea hacer otra operacion ?? S / N ");
aux = entrada.readLine();
Resp = aux.charAt(0);
} while (Resp == 'S' Resp == 's');
System.out.println(" Garcias por utilizar este programa.. "); System.out.println("\t para mas informacion en :: WWW.XROMRELOADED.TK ::");
} // Fin del metodo main }
// Fin de la calse Pila.java
(Clase y Metodos) JAVA:
// Libreria necesaria para introducir datos desde el Teclado import java.io.*;
// Inicio de la Clase Pila public class Pila {
//----- Atributos de la pila ------\\
public int Pila [];
// Estructura de la pila public int Top, Max , Elem;
// variables para la pila
//Top : El Tope de la pila , referencia al ultimo elemento que esta en la pila //Max : Maximo de espacios que tiene la pila //Elem : Elemento que se agrega a la pila (Tecleado por el usuario)
public char Resp;
// Variables para SubMenus. public String aux;
//----- Contructor -------\\
public Pila (int Espacios){
// se recibe como parametro los Espacios de la pila Pila = new int [Espacios];
// Asignamos los espacios en la Pila Max = Pila.length - 1; Top = -1;
// Top se declara como -1 como referencia a que no existen datos en la pila }
// fin del constructor
//----- Metodos de la pila -------\\
// Metodo Imprimir
public void Imprimir ()
{ for (int n = 0 ; n <= Max ;
n++ ) { System.out.println(n + ".- " + Pila [n]);
}
} //----Fin del Metodo Imprimir
// Metodo Push ---
public void Push ( ) throws IOException
{ // Metodo para ingresar datos ...
BufferedReader entrada = new BufferedReader (new InputStreamReader(System.in));
do { // if (1) if(Top != Max)
{ // Si la pila No esta llena ....
// Se puede agregar un nuevo dato a la pila ....
System.out.print("\t Ingrese un numero entero : ");
Elem = Integer.parseInt(entrada.readLine());
Top ++;
// Se incrementa Top como referencia de que se agrego un nuevo dato Pila[Top] = Elem;
// Se agrega el nuevo elemento a la pila // if (1.1) if (Top == Max) {
// Si la pila quedo llena entoces ...
// Imprimir mensaje System.out.print("\n La Pila a quedado llena !! ");
// con esta variable detenemos el bucle do - while Resp = 'N';
} // Fin del if (1.1) } else { System.out.p
rintln("\n Pila llena !! Imposible introducir un valor a la pila"); Resp = 'N';
// detenemos el bucle }
// Fin del if (1)
// if (2) if (Resp != 'N') {
// Si es diferente de No , entoces seguir preguntado si se desea introducir mas datos
System.out.print("Desea introducir un dato mas ??"); aux = entrada.readLine();
Resp = aux.charAt(0);
} // Fin del if (2) }
while (Resp == 'S' Resp == 's');
// Continuar ciclando simpre y cuando sea Resp = 's' } //
Fin del Metodo Push
// Metodo Pop ----
public void Pop () {
if(Top != -1) {
// Si la pila no esta vacia entonces ....
System.out.println("Se borro el Dato : " + Pila[Top]);
// Eliminar dato Pila[Top] = 0;
// remplaza el valor por un cero (Eliminado) Top --;
// Top se reduce para decir que un elemento se borro }
else {
// De lo contrario imprime .."que la pila esta vacia" System.out.println("Pila Vacia... Imposible Eliminar");
} // fin del if }
//-----Fin del Metodo Pop } // Fin de la Clase Pila ----
domingo, 29 de marzo de 2009
COLASQUIZ
// QueueDemo.java
import com.javajeff.cds.*;
class QueueDemo {
public static void main (String [] args) {
System.out.println ("ArrayLinearQueue Demo");
System.out.println ("---------------------");
queueDemo (new ArrayLinearQueue (5));
System.out.println ("ArrayCircularQueue Demo");
System.out.println ("---------------------");
queueDemo (new ArrayCircularQueue (6)); // Need one more slot because
// of empty slot in circular
// implementation
}
static void queueDemo (Queue q) {
System.out.println ("Is empty = " + q.isEmpty ());
System.out.println ("Is full = " + q.isFull ());
System.out.println ("Inserting \"This\"");
q.insert ("This");
System.out.println ("Inserting \"is\"");
q.insert ("is");
System.out.println ("Inserting \"a\"");
q.insert ("a");
System.out.println ("Inserting \"sentence\"");
q.insert ("sentence");
System.out.println ("Inserting \".\"");
q.insert (".");
try {
System.out.println ("Inserting \"One last item\"");
q.insert ("One last item");
}
catch (FullQueueException e) {
System.out.println ("One insert too many");
System.out.println ("Is empty = " + q.isEmpty ());
System.out.println ("Is full = " + q.isFull ());
}
System.out.println ();
while (!q.isEmpty ())
System.out.println (q.remove () + " [Is empty = " + q.isEmpty () +
", Is full = " + q.isFull () + "]");
try {
q.remove ();
}
catch (EmptyQueueException e) {
System.out.println ("One remove too many");
}
System.out.println ();
}
}
************************
// ArrayLinearQueue.java
package com.javajeff.cds;
public class ArrayLinearQueue implements Queue {
private int front = -1, rear = -1;
private Object [] queue;
public ArrayLinearQueue (int maxElements) {
queue = new Object [maxElements];
}
public void insert (Object o) {
if (rear == queue.length - 1)
throw new FullQueueException ();
queue [++rear] = o;
}
public boolean isEmpty () {
return front == rear;
}
public boolean isFull () {
return rear == queue.length - 1;
}
public Object remove () {
if (front == rear)
throw new EmptyQueueException ();
return queue [++front];
}
}
*****************
// ArrayCircularQueue.java
package com.javajeff.cds;
public class ArrayCircularQueue implements Queue {
private int front = 0, rear = 0;
private Object [] queue;
public ArrayCircularQueue (int maxElements) {
queue = new Object [maxElements];
}
public void insert (Object o) {
int temp = rear;
rear = (rear + 1) % queue.length;
if (front == rear) {
rear = temp;
throw new FullQueueException ();
}
queue [rear] = o;
}
public boolean isEmpty () {
return front == rear;
}
public boolean isFull () {
return ((rear + 1) % queue.length) == front;
}
public Object remove () {
if (front == rear)
throw new EmptyQueueException ();
front = (front + 1) % queue.length;
return queue [front];
}
}
**************************
// Queue.java
package com.javajeff.cds;
public interface Queue {
void insert (Object o);
boolean isEmpty ();
boolean isFull ();
Object remove ();
}
****************************
// FullQueueException.java
package com.javajeff.cds;
public class FullQueueException extends RuntimeException {
/**
*
*/
private static final long serialVersionUID = 1L;
}
***********************
// EmptyQueueException.java
package com.javajeff.cds;
public class EmptyQueueException extends RuntimeException {
/**
*
*/
private static final long serialVersionUID = 1L;
}
import com.javajeff.cds.*;
class QueueDemo {
public static void main (String [] args) {
System.out.println ("ArrayLinearQueue Demo");
System.out.println ("---------------------");
queueDemo (new ArrayLinearQueue (5));
System.out.println ("ArrayCircularQueue Demo");
System.out.println ("---------------------");
queueDemo (new ArrayCircularQueue (6)); // Need one more slot because
// of empty slot in circular
// implementation
}
static void queueDemo (Queue q) {
System.out.println ("Is empty = " + q.isEmpty ());
System.out.println ("Is full = " + q.isFull ());
System.out.println ("Inserting \"This\"");
q.insert ("This");
System.out.println ("Inserting \"is\"");
q.insert ("is");
System.out.println ("Inserting \"a\"");
q.insert ("a");
System.out.println ("Inserting \"sentence\"");
q.insert ("sentence");
System.out.println ("Inserting \".\"");
q.insert (".");
try {
System.out.println ("Inserting \"One last item\"");
q.insert ("One last item");
}
catch (FullQueueException e) {
System.out.println ("One insert too many");
System.out.println ("Is empty = " + q.isEmpty ());
System.out.println ("Is full = " + q.isFull ());
}
System.out.println ();
while (!q.isEmpty ())
System.out.println (q.remove () + " [Is empty = " + q.isEmpty () +
", Is full = " + q.isFull () + "]");
try {
q.remove ();
}
catch (EmptyQueueException e) {
System.out.println ("One remove too many");
}
System.out.println ();
}
}
************************
// ArrayLinearQueue.java
package com.javajeff.cds;
public class ArrayLinearQueue implements Queue {
private int front = -1, rear = -1;
private Object [] queue;
public ArrayLinearQueue (int maxElements) {
queue = new Object [maxElements];
}
public void insert (Object o) {
if (rear == queue.length - 1)
throw new FullQueueException ();
queue [++rear] = o;
}
public boolean isEmpty () {
return front == rear;
}
public boolean isFull () {
return rear == queue.length - 1;
}
public Object remove () {
if (front == rear)
throw new EmptyQueueException ();
return queue [++front];
}
}
*****************
// ArrayCircularQueue.java
package com.javajeff.cds;
public class ArrayCircularQueue implements Queue {
private int front = 0, rear = 0;
private Object [] queue;
public ArrayCircularQueue (int maxElements) {
queue = new Object [maxElements];
}
public void insert (Object o) {
int temp = rear;
rear = (rear + 1) % queue.length;
if (front == rear) {
rear = temp;
throw new FullQueueException ();
}
queue [rear] = o;
}
public boolean isEmpty () {
return front == rear;
}
public boolean isFull () {
return ((rear + 1) % queue.length) == front;
}
public Object remove () {
if (front == rear)
throw new EmptyQueueException ();
front = (front + 1) % queue.length;
return queue [front];
}
}
**************************
// Queue.java
package com.javajeff.cds;
public interface Queue {
void insert (Object o);
boolean isEmpty ();
boolean isFull ();
Object remove ();
}
****************************
// FullQueueException.java
package com.javajeff.cds;
public class FullQueueException extends RuntimeException {
/**
*
*/
private static final long serialVersionUID = 1L;
}
***********************
// EmptyQueueException.java
package com.javajeff.cds;
public class EmptyQueueException extends RuntimeException {
/**
*
*/
private static final long serialVersionUID = 1L;
}
SEGUNDO CORTE
COLAS
Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push 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.
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.
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.
En estos casos, el primer elemento de la lista realiza su función (pagar comida, pagar entrada para el partido o para el cine) y deja la cola. Este movimiento está representado en la cola por la función pop o desencolar. Cada vez que otro elemento se añade a la lista de espera se añaden al final de la cola representando la función push o encolar. Hay otras funciones auxiliares para ver el tamaño de la cola (size), para ver si está vacía en el caso de que no haya nadie esperando (empty) o para ver el primer elemento de la cola (front).
Operaciones Básicas
Crear: se crea la cola vacía.
Encolar (añadir, entrar, push): se añade un elemento a la cola. Se añade al final de esta.
Desencolar (sacar, salir, pop): 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 primero elemento que entró.
Colas en 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.
Suscribirse a:
Entradas (Atom)
estructuradedatos301a@gmail.com
Entradas
Comentarios
VISITA NUESTRO PERFIL
- GRUPO DE TRABAJO 6
- GRUPO 6 - ESTRUCTURA DE DATOS UNIVERSIDAD CATOLICA DE COLOMBIA