jueves, 28 de mayo de 2009
martes, 26 de mayo de 2009
IMPLEMENTACION DE UNA MATRIZ EN UN ARBOL
Introducción
La matriz binaria, en la que el valor ‘1’ representará al color NEGRO y el valor ‘0’ al color BLANCO.
Otra posible representación de la misma imagen consiste en emplear árboles binarios.
Para realizar la conversión entre una representación de la imagen a su equivalente en árbol binario
debemos suponer que la matriz binaria es cuadrada y el rango de la misma es potencia de 2.
En esta representación obtendremos un árbol por cada fila de la matriz binaria, que almacenaremos en una estructura para poder trabajar posteriormente sobre esta representación en futuras operaciones.
El proceso principal de obtención de un árbol binario consiste en ir dividiendo la fila en dos mitades cuando ésta no tenga un valor constante, hasta que lleguemos al caso de encontrar un trozo de tal fila cuyos elementos tengan el mismo valor o bien tengamos únicamente una fila con un único elemento, guandándose en ese caso información pictórica.
La matriz binaria, en la que el valor ‘1’ representará al color NEGRO y el valor ‘0’ al color BLANCO.
Otra posible representación de la misma imagen consiste en emplear árboles binarios.
Para realizar la conversión entre una representación de la imagen a su equivalente en árbol binario
debemos suponer que la matriz binaria es cuadrada y el rango de la misma es potencia de 2.
En esta representación obtendremos un árbol por cada fila de la matriz binaria, que almacenaremos en una estructura para poder trabajar posteriormente sobre esta representación en futuras operaciones.
El proceso principal de obtención de un árbol binario consiste en ir dividiendo la fila en dos mitades cuando ésta no tenga un valor constante, hasta que lleguemos al caso de encontrar un trozo de tal fila cuyos elementos tengan el mismo valor o bien tengamos únicamente una fila con un único elemento, guandándose en ese caso información pictórica.
Ordenación por el método de Shell (ShellSort)
El método se denomina Shell en honor de su inventor Donald Shell.
Es un algoritmo de ordenación interna muy sencillo pero muy ingenioso, basado en comparaciones e intercambios, y con unos resultados radicalmente mejores que los que se pueden obtener con el método de la burbuja, el de selección directa o el de inserción directa.
Por ejemplo, considere una lista de números como [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. Si comenzamos con un tamaño de paso de 5, podríamos visualizar esto dividiendo la lista de números en una tabla con 5 columnas.
Esto quedaría así:
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
Entonces ordenamos cada columna, lo que nos da
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
Cuando lo leemos de nuevo como una única lista de números, obtenemos
[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].
SECUENCIA DE ESPACIOS
La secuencia de espacios es una parte integral del algoritmo Shell sort. Cualquier secuencia incremental funcionaría siempre que el último elemento sea 1. El algoritmo comienza realizando un ordenamiento por inserción con espacio, siendo el espacio el primer número en la secuencia de espacios. Continua para realizar un ordenamiento por inserción con espacio para cada número en la secuencia, hasta que termina con un espacio de 1. Cuando el espacio es 1, el ordenamiento por inserción con espacio es simplemente un ordenamiento por inserción ordinario, garantizando que la lista final estará ordenada.
La secuencia de espacios que fue originalmente sugerida por Donald Shell debía comenzar con N / 2 y dividir por la mitad el número hasta alcanzar 1. Aunque esta secuencia proporciona mejoras de rendimiento significativas sobre los algoritmos cuadráticos como el ordenamiento por inserción. se puede cambiar ligeramente para disminuir más el tiempo necesario medio y el del peor caso. El libro de texto de Weiss demuestra que esta secuencia permite un ordenamiento O(n2) del peor caso, si los datos están inicialmente en el vector como (pequeño_1, grande_1, pequeño_2, grande_2, ...) - es decir, la mitad alta de los números están situados, de forma ordenada, en las posiciones con índice par y la mitad baja de los números están situados de la misma manera en las posiciones con índice impar.
Es un algoritmo de ordenación interna muy sencillo pero muy ingenioso, basado en comparaciones e intercambios, y con unos resultados radicalmente mejores que los que se pueden obtener con el método de la burbuja, el de selección directa o el de inserción directa.
Por ejemplo, considere una lista de números como [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. Si comenzamos con un tamaño de paso de 5, podríamos visualizar esto dividiendo la lista de números en una tabla con 5 columnas.
Esto quedaría así:
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
Entonces ordenamos cada columna, lo que nos da
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
Cuando lo leemos de nuevo como una única lista de números, obtenemos
[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].
SECUENCIA DE ESPACIOS
La secuencia de espacios es una parte integral del algoritmo Shell sort. Cualquier secuencia incremental funcionaría siempre que el último elemento sea 1. El algoritmo comienza realizando un ordenamiento por inserción con espacio, siendo el espacio el primer número en la secuencia de espacios. Continua para realizar un ordenamiento por inserción con espacio para cada número en la secuencia, hasta que termina con un espacio de 1. Cuando el espacio es 1, el ordenamiento por inserción con espacio es simplemente un ordenamiento por inserción ordinario, garantizando que la lista final estará ordenada.
La secuencia de espacios que fue originalmente sugerida por Donald Shell debía comenzar con N / 2 y dividir por la mitad el número hasta alcanzar 1. Aunque esta secuencia proporciona mejoras de rendimiento significativas sobre los algoritmos cuadráticos como el ordenamiento por inserción. se puede cambiar ligeramente para disminuir más el tiempo necesario medio y el del peor caso. El libro de texto de Weiss demuestra que esta secuencia permite un ordenamiento O(n2) del peor caso, si los datos están inicialmente en el vector como (pequeño_1, grande_1, pequeño_2, grande_2, ...) - es decir, la mitad alta de los números están situados, de forma ordenada, en las posiciones con índice par y la mitad baja de los números están situados de la misma manera en las posiciones con índice impar.
Ordenamiento por Método de inserción binaria
Carácteristicas fundamentales:
1.- La secuencia destino donde debe insertarse el nuevo elemento ya esta ordenada.
2.-Búsqueda Binaria para localizar el lugar de inserción.
3.-Desplazar elementos.
4.-Insertar.
Análisis:
Al realizar la búsqueda binaria se divide una longitud L por la mitad un número determinado de veces.
1.- La secuencia destino donde debe insertarse el nuevo elemento ya esta ordenada.
2.-Búsqueda Binaria para localizar el lugar de inserción.
3.-Desplazar elementos.
4.-Insertar.
Análisis:
Al realizar la búsqueda binaria se divide una longitud L por la mitad un número determinado de veces.
METODOS DE BUSQUEDA
BUSQUEDA
La BUSQUEDA , es una operación que permite recuperar datos previamente almacenados. El resultado puede ser exitoso si se encuentra el elemento solicitado, o fracaso, en otro caso.
METODOS DE BUSQUEDA
Los métodos de búsqueda pueden clasificarse según la ubicación de los datos sobre los que se realizara la búsqueda. Existen dos clases:
Métodos de Búsqueda Interna
Métodos de Búsqueda Externa.
METODOS DE BUSQUEDA INTERNA
Se denomina búsqueda interna cuando todos los elementos se encuentran en la memoria principal. Por ejemplo, almacenados en estructuras estáticas (arreglos) o en estructuras dinámicas (listas ligadas y arboles).
Los métodos de búsqueda mas importantes son:
Secuencial o lineal
Binaria
Por transformación de claves
Arboles de búsqueda
METODOS DE BUSQUEDA EXTERNA
Se denomina búsqueda externa cuando todos los elementos se encuentran en memoria secundaria (archivos almacenados en dispositivos tales como cintas y discos magnéticos).
BUSQUEDA SECUENCIAL
Búsqueda secuencial consiste en revisar elemento por elemento hasta encontrar el dato buscado, o hasta llegar al final de la lista de datos disponible.
CARACTERISTICAS
La búsqueda se puede realizar en arreglos desordenados.
El método es totalmente confiable.
El numero de comparaciones es significativa si el arreglo es muy grande.
En arreglos desordenados de N componentes puede suceder que el elemento no se encuentre, por lo tanto se harán N comparaciones al recorrer todo el arreglo
Cantidad mínima de comparaciones es 1.
Cantidad media de comparaciones es (1+N)/2.
Cantidad máxima de comparaciones es N.
DIAGRAMA DE FLUJO (BUSQUEDA SECUENCIAL)
BUSQUEDA BINARIA
La búsqueda binaria utiliza un método de `divide y vencerás' para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si éste es el elemento buscado, entonces la búsqueda ha terminado.
En caso contrario, se determinar si el elemento buscado será en la primera o la segunda mitad de la lista y a continuación se repite este proceso, utilizando el elemento central de esa sub-lista.
CARACTERISTICAS
Sirve únicamente para arreglos ordenados.
Es mas eficiente que el método de búsqueda secuencial, debido a que el numero de comparaciones se reduce a la mitad por cada iteración del método.
Cantidad mínima de comparaciones es 1.
Cantidad media de comparaciones es (1+log₂(N))/2.
Cantidad máxima de comparaciones es log₂(N).
ALGORITMO
Se compara la llave buscada con la llave localizada al centro del arreglo.
Si la llave analizada corresponde a la buscada fin de búsqueda si no.
Si la llave buscada es menor que la analizada repetir proceso en mitad superior, sino en la mitad inferior.
El proceso de partir por la mitad el arreglo se repite hasta encontrar el registro o hasta que el tamaño de la lista restante sea cero, lo cual implica que el valor de la llave buscada no está en la lista.
BUSQUEDA POR TRANSFORMACION DE CLAVES (HASH)
Aumenta la velocidad de búsqueda sin necesidad de tener los objetos ordenados.
El tiempo de búsqueda es totalmente independiente del numero de componentes del arreglo.
La búsqueda se realiza por medio de direcciones, creadas por una función hash(H).
FUNCIONES HASH
Las Funciones HASH (H) mas aplicadas son:
Función Modulo (Por división).
Función Cuadrado.
Función Plegamiento.
Función Truncamiento.
La BUSQUEDA , es una operación que permite recuperar datos previamente almacenados. El resultado puede ser exitoso si se encuentra el elemento solicitado, o fracaso, en otro caso.
METODOS DE BUSQUEDA
Los métodos de búsqueda pueden clasificarse según la ubicación de los datos sobre los que se realizara la búsqueda. Existen dos clases:
Métodos de Búsqueda Interna
Métodos de Búsqueda Externa.
METODOS DE BUSQUEDA INTERNA
Se denomina búsqueda interna cuando todos los elementos se encuentran en la memoria principal. Por ejemplo, almacenados en estructuras estáticas (arreglos) o en estructuras dinámicas (listas ligadas y arboles).
Los métodos de búsqueda mas importantes son:
Secuencial o lineal
Binaria
Por transformación de claves
Arboles de búsqueda
METODOS DE BUSQUEDA EXTERNA
Se denomina búsqueda externa cuando todos los elementos se encuentran en memoria secundaria (archivos almacenados en dispositivos tales como cintas y discos magnéticos).
BUSQUEDA SECUENCIAL
Búsqueda secuencial consiste en revisar elemento por elemento hasta encontrar el dato buscado, o hasta llegar al final de la lista de datos disponible.
CARACTERISTICAS
La búsqueda se puede realizar en arreglos desordenados.
El método es totalmente confiable.
El numero de comparaciones es significativa si el arreglo es muy grande.
En arreglos desordenados de N componentes puede suceder que el elemento no se encuentre, por lo tanto se harán N comparaciones al recorrer todo el arreglo
Cantidad mínima de comparaciones es 1.
Cantidad media de comparaciones es (1+N)/2.
Cantidad máxima de comparaciones es N.
DIAGRAMA DE FLUJO (BUSQUEDA SECUENCIAL)
BUSQUEDA BINARIA
La búsqueda binaria utiliza un método de `divide y vencerás' para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si éste es el elemento buscado, entonces la búsqueda ha terminado.
En caso contrario, se determinar si el elemento buscado será en la primera o la segunda mitad de la lista y a continuación se repite este proceso, utilizando el elemento central de esa sub-lista.
CARACTERISTICAS
Sirve únicamente para arreglos ordenados.
Es mas eficiente que el método de búsqueda secuencial, debido a que el numero de comparaciones se reduce a la mitad por cada iteración del método.
Cantidad mínima de comparaciones es 1.
Cantidad media de comparaciones es (1+log₂(N))/2.
Cantidad máxima de comparaciones es log₂(N).
ALGORITMO
Se compara la llave buscada con la llave localizada al centro del arreglo.
Si la llave analizada corresponde a la buscada fin de búsqueda si no.
Si la llave buscada es menor que la analizada repetir proceso en mitad superior, sino en la mitad inferior.
El proceso de partir por la mitad el arreglo se repite hasta encontrar el registro o hasta que el tamaño de la lista restante sea cero, lo cual implica que el valor de la llave buscada no está en la lista.
BUSQUEDA POR TRANSFORMACION DE CLAVES (HASH)
Aumenta la velocidad de búsqueda sin necesidad de tener los objetos ordenados.
El tiempo de búsqueda es totalmente independiente del numero de componentes del arreglo.
La búsqueda se realiza por medio de direcciones, creadas por una función hash(H).
FUNCIONES HASH
Las Funciones HASH (H) mas aplicadas son:
Función Modulo (Por división).
Función Cuadrado.
Función Plegamiento.
Función Truncamiento.
Heapsort
El ordenamiento por heapsort es un algoritmo de ordenación no recursivo, no estable, con complejidad computacional
El Heapsort está basado en el uso de un tipo especial de árbol binario (llamado apilamiento) para estructurar el proceso de ordenamiento. La estructura de ramificación del árbol conserva el número de comparaciones necesarias en O(n log n).
Caracteristicas
Las llaves están acomodadas en los nodos de tal manera que, para cada nodo i, Ki <= Kj donde el nodo j es el padre del nodo i. Es decir, al recorrer el camino desde la raíz hacia abajo, las claves se encuentran en orden descendente.
El árbol se llena de izquierda a derecha, lo que implica que si algún(os) nodo(s) no está(n) en el mismo nivel que el resto, éste(os) estará(n) entonces lo más a la izquierda posible del árbol.
Pasos del Heap
1º. Saca el valor máximo del Heap. (El de la posición 1).
2º. Pone el valor sacado en el arreglo ordenado.
3º. Reconstruir el Heap con un elemento menos.
Ejemplo
El Heapsort está basado en el uso de un tipo especial de árbol binario (llamado apilamiento) para estructurar el proceso de ordenamiento. La estructura de ramificación del árbol conserva el número de comparaciones necesarias en O(n log n).
Caracteristicas
Las llaves están acomodadas en los nodos de tal manera que, para cada nodo i, Ki <= Kj donde el nodo j es el padre del nodo i. Es decir, al recorrer el camino desde la raíz hacia abajo, las claves se encuentran en orden descendente.
El árbol se llena de izquierda a derecha, lo que implica que si algún(os) nodo(s) no está(n) en el mismo nivel que el resto, éste(os) estará(n) entonces lo más a la izquierda posible del árbol.
Pasos del Heap
1º. Saca el valor máximo del Heap. (El de la posición 1).
2º. Pone el valor sacado en el arreglo ordenado.
3º. Reconstruir el Heap con un elemento menos.
Ejemplo
BUSQUDA POR HASH
Procedimiento
Método consistente en aplicar una función que traduce un conjunto de posibles valores llave en un rango de direcciones relativas
Casos de Colision
soluciones para reducir el número de colisiones
-Propagar los registros: Buscar funciones que distribuyan muy aleatoriamente los registros podemos evitar "agrupaciones" de llaves que produzcan las mismas direcciones.
-Usar memoria extra: En el ejemplo anterior planteamos tener una dirección de entre 1000 posibles, el uso de memoria extra se basa en proponer un espacio de direcciones posibles mucho más grande que el número de registros a usar, de modo que si vamos a insertar 100 registros un espacio de 500 direcciones nos una mejor opción de esparcir mejor.
-Colocar más de un registro en una dirección: A diferencia de los casos anteriores donde cada dirección almacena únicamente un registro, este concepto se basa en "buckets" o cubetas de datos en cada dirección, ahí se colocan algunos (casi todos) los registros que colisionan de manera que al hacer una búsqueda debemos recuperar la cubeta entera y ahi buscar por el registro deseado.
Un Algoritmo de Hash
No existe una fórmula "única" para hash, pero el producirla es un algoritmo que básicamente se presenta en 3 pasos:
1) Representar la llave de manera numérica (siempre que no sea de por sí un número)
Una buena opción es usar los valores ASCII o bien los Unicode de las letras
LOWELL= L O W E L L
76 79 87 69 76 76 32 32 32 32 32 32
2) Plegar y Agregar
-Combinar algunos de estos números para generar pequeños trozos con los que podamos trabajar
76 79 | 87 69 | 76 76 | 32 32 | 32 32 | 32 32
De manera que podemos hacer algunas operaciones matemáticas con dichos números para finalmente obtener un número del cual obtendremos la dirección
7679 + 8769 + 7676 + 3232 + 3232 = 30 588
Nota: Respecto a la implementación se puede dar el caso de formar números demasiado grandes, tanto que llegue al overflow del tipo de datos que estemos usando. Para solucionar esto podemos usar funciones como el "mod" intermedias para no tener ese problema.
3) Dividir por un número primo y usar el resultado como dirección Los archivos de hash por lo general suelen limitarse a un cierto rango de direcciones posibles para aprovechar mejor el concepto de memoria. de manera que podemos concluir nuestro algoritmo con la fórmula:
a= s mod n
Donde a es la dirección resultante, s es la suma o resultado de los pasos anteriores y n el número de direcciones posibles en el archivo Existen innumerables operaciones adicionales que pueden aplicarse en las fórmulas, así como las técnicas para limitar el valor final. Entre ellas se encuentran: elevar a alguna potencia, raíz cuadrada, convertir los números de base (hexadecimal, octal), etc...
Ventajas
Se pueden usar los valores naturales de la llave, puesto que se traducen internamente a direcciones fáciles de localizar
Se logra independencia lógica y física, debido a que los valores de las llaves son independientes del espacio de direcciones
No se requiere almacenamiento adicional para los índices.
Desventajas
No pueden usarse registros de longitud variable
El archivo no esta clasificado
No permite llaves repetidas
Solo permite acceso por una sola llave
Costos
Tiempo de procesamiento requerido para la aplicación de la función hash
Tiempo de procesamiento y los accesos E/S requeridos para solucionar las colisiones.
Factores de Eficiencia
La distribución de los valores de llave que realmente se usan
El numero de valores de llave que realmente están en uso con respecto al tamaño del espacio de direcciones
El numero de registros que pueden almacenarse en una dirección dad sin causar una colisión.
La técnica usada para resolver el problema de las colisiones
Tipos de Funcion Hash
Residuo de la división
Medio del cuadrado
Pliegue
Hashing por residuo de división
La idea de este método es la de dividir el valor de la llave entre un numero apropiado, y después utilizar el residuo de la división como dirección relativa para el registro (dirección = llave módulo divisor).
Consideraciones
Independientemente de que tan bueno sea el divisor, cuando el espacio de direcciones de un archivo esta completamente lleno, la probabilidad de colisión crece dramáticamente. La saturación de archivo de mide mediante su factor de carga, el cual se define como la relación del numero de registros en el archivo contra el numero de registros que el archivo podría contener si estuviese completamente lleno.
Factor de Carga
Hashing por Elevacion al cuadrado
En esta técnica, la llave es elevada al cuadrado, después algunos dígitos específicos se extraen de la mitad del resultado para constituir la dirección relativa. Si se desea una dirección de n dígitos, entonces los dígitos se truncan en ambos extremos de la llave elevada al cuadrado, tomando n dígitos intermedios. Las mismas posiciones de n dígitos deben extraerse para cada llave.
Utilizando esta función hashing el tamaño del archivo resultante es de 10n donde n es el numero de dígitos extraídos de los valores de la llave elevada al cuadrado.
Hashing por Pliegue
En esta técnica el valor de la llave es particionada en varias partes, cada una de las cuales
(excepto la ultima) tiene el mismo numero de dígitos que tiene la dirección relativa objetivo. Estas particiones son después plegadas una sobre otra y sumadas. El resultado, es la dirección relativa. Igual que para el método del medio del cuadrado, el tamaño del espacio de direcciones relativas es una potencia de 10.
Método consistente en aplicar una función que traduce un conjunto de posibles valores llave en un rango de direcciones relativas
Casos de Colision
soluciones para reducir el número de colisiones
-Propagar los registros: Buscar funciones que distribuyan muy aleatoriamente los registros podemos evitar "agrupaciones" de llaves que produzcan las mismas direcciones.
-Usar memoria extra: En el ejemplo anterior planteamos tener una dirección de entre 1000 posibles, el uso de memoria extra se basa en proponer un espacio de direcciones posibles mucho más grande que el número de registros a usar, de modo que si vamos a insertar 100 registros un espacio de 500 direcciones nos una mejor opción de esparcir mejor.
-Colocar más de un registro en una dirección: A diferencia de los casos anteriores donde cada dirección almacena únicamente un registro, este concepto se basa en "buckets" o cubetas de datos en cada dirección, ahí se colocan algunos (casi todos) los registros que colisionan de manera que al hacer una búsqueda debemos recuperar la cubeta entera y ahi buscar por el registro deseado.
Un Algoritmo de Hash
No existe una fórmula "única" para hash, pero el producirla es un algoritmo que básicamente se presenta en 3 pasos:
1) Representar la llave de manera numérica (siempre que no sea de por sí un número)
Una buena opción es usar los valores ASCII o bien los Unicode de las letras
LOWELL= L O W E L L
76 79 87 69 76 76 32 32 32 32 32 32
2) Plegar y Agregar
-Combinar algunos de estos números para generar pequeños trozos con los que podamos trabajar
76 79 | 87 69 | 76 76 | 32 32 | 32 32 | 32 32
De manera que podemos hacer algunas operaciones matemáticas con dichos números para finalmente obtener un número del cual obtendremos la dirección
7679 + 8769 + 7676 + 3232 + 3232 = 30 588
Nota: Respecto a la implementación se puede dar el caso de formar números demasiado grandes, tanto que llegue al overflow del tipo de datos que estemos usando. Para solucionar esto podemos usar funciones como el "mod" intermedias para no tener ese problema.
3) Dividir por un número primo y usar el resultado como dirección Los archivos de hash por lo general suelen limitarse a un cierto rango de direcciones posibles para aprovechar mejor el concepto de memoria. de manera que podemos concluir nuestro algoritmo con la fórmula:
a= s mod n
Donde a es la dirección resultante, s es la suma o resultado de los pasos anteriores y n el número de direcciones posibles en el archivo Existen innumerables operaciones adicionales que pueden aplicarse en las fórmulas, así como las técnicas para limitar el valor final. Entre ellas se encuentran: elevar a alguna potencia, raíz cuadrada, convertir los números de base (hexadecimal, octal), etc...
Ventajas
Se pueden usar los valores naturales de la llave, puesto que se traducen internamente a direcciones fáciles de localizar
Se logra independencia lógica y física, debido a que los valores de las llaves son independientes del espacio de direcciones
No se requiere almacenamiento adicional para los índices.
Desventajas
No pueden usarse registros de longitud variable
El archivo no esta clasificado
No permite llaves repetidas
Solo permite acceso por una sola llave
Costos
Tiempo de procesamiento requerido para la aplicación de la función hash
Tiempo de procesamiento y los accesos E/S requeridos para solucionar las colisiones.
Factores de Eficiencia
La distribución de los valores de llave que realmente se usan
El numero de valores de llave que realmente están en uso con respecto al tamaño del espacio de direcciones
El numero de registros que pueden almacenarse en una dirección dad sin causar una colisión.
La técnica usada para resolver el problema de las colisiones
Tipos de Funcion Hash
Residuo de la división
Medio del cuadrado
Pliegue
Hashing por residuo de división
La idea de este método es la de dividir el valor de la llave entre un numero apropiado, y después utilizar el residuo de la división como dirección relativa para el registro (dirección = llave módulo divisor).
Consideraciones
Independientemente de que tan bueno sea el divisor, cuando el espacio de direcciones de un archivo esta completamente lleno, la probabilidad de colisión crece dramáticamente. La saturación de archivo de mide mediante su factor de carga, el cual se define como la relación del numero de registros en el archivo contra el numero de registros que el archivo podría contener si estuviese completamente lleno.
Factor de Carga
Hashing por Elevacion al cuadrado
En esta técnica, la llave es elevada al cuadrado, después algunos dígitos específicos se extraen de la mitad del resultado para constituir la dirección relativa. Si se desea una dirección de n dígitos, entonces los dígitos se truncan en ambos extremos de la llave elevada al cuadrado, tomando n dígitos intermedios. Las mismas posiciones de n dígitos deben extraerse para cada llave.
Utilizando esta función hashing el tamaño del archivo resultante es de 10n donde n es el numero de dígitos extraídos de los valores de la llave elevada al cuadrado.
Hashing por Pliegue
En esta técnica el valor de la llave es particionada en varias partes, cada una de las cuales
(excepto la ultima) tiene el mismo numero de dígitos que tiene la dirección relativa objetivo. Estas particiones son después plegadas una sobre otra y sumadas. El resultado, es la dirección relativa. Igual que para el método del medio del cuadrado, el tamaño del espacio de direcciones relativas es una potencia de 10.
sábado, 2 de mayo de 2009
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 ----
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