martes, 26 de noviembre de 2013

Metodo de Busqueda Binaria en Java

El programa tiene un metodo de ordenamiento.


public class BusquedaBinaria { 
public static int busquedaBinaria(int[] Arreglo, int elemento) { 
int i = 0, centro = 0, posicion = 0, inferior = 0, superior = Arreglo.length-1; 
while(inferior <= superior) { 
centro = (superior + inferior) / 2; 
if (Arreglo[centro] == elemento){
 return centro;} else{ if (Arreglo[centro] > elemento){
 superior = centro - 1;}else{ inferior = centro + 1;} 
}
} return -1;
}
public static void main (String[] args) { 
java.util.Scanner Leer = new java.util.Scanner(System.in); 
System.out.print("Tamanio del arreglo:"); 
int tamanioArreglo = Leer.nextInt(); int[] Arreglo = new int[tamanioArreglo]; 
for(int i=0; i<Arreglo.length; i++){ 
System.out.println("Introduce elemento:"); 
Arreglo[i] = Leer.nextInt();
}
int A;
for(int i=0;i<Arreglo.length-1;i++){ 
for(int j=0;j<Arreglo.length-i-1;j++){ 
if(Arreglo[j+1]<Arreglo[j]){ 
A=Arreglo[j+1]; 
Arreglo[j+1]=Arreglo[j]; Arreglo[j]=A; 
System.out.print("Elemento a buscar:" ); 
int elemento = Leer.nextInt(); 
System.out.println("dato"); 
for(int i=0;i<Arreglo.length;i++){ 
System.out.println(Arreglo[i]); 
int posicion = busquedaBinaria(Arreglo, elemento); 
if(posicion == -1)
System.out.println("\nElemento no encontrado"); 
else System.out.println("\nElemento " + elemento + " encontrado en la posicion " + posicion); 
}

Metodo de Busqueda Binaria

Es un método que se basa en la división sucesiva del espacio ocupado por el vector en sucesivas mitades, hasta encontrar el elemento buscado. El vector tiene que estar ordenado.

Ventajas:
La búsqueda binaria es un método eficiente siempre que el vector esté ordenado.
La búsqueda binaria proporciona un medio para reducir el tiempo requerido para buscar en una lista.
Este método funciona a un 100%

Desventajas:
Si los datos del arreglo no están ordenados no hará la búsqueda
Este método Necesita un método de ordenamiento como: Burbuja, Quicksort, shell sort, etc. Para que así funcione bien.

Metodo de busqueda secuencial en Java

public class secuencialdesordenado {
public void buscar()
{
Scanner leer=new Scanner(System.in);
int i=0;
boolean bandera=false;
int x;
int v[]= new int[10];
for(int c=0;c<v.length;c++){
System.out.println("introduce los datos del arreglo");
v[c]=leer.nextInt();
}
System.out.println("introduzca elemento a buscar");
x=leer.nextInt();
do{
if(v[i]==x)
{
bandera=true;
}
else {
bandera=false;
}
i++;
}while(i<v.length && bandera==false);
if(bandera==true){
System.out.println("el elemento esta en la posicion "+ i);
}
else if(bandera==false){
System.out.println("el elemento no esta en la lista");
}
}

Metodo Busqueda Secuencial

Este método se usa para buscar un elemento de un vector, es explorar secuencialmente el vector, es decir; recorrer el vector desde el prior elemento hasta el último. Si se encuentra el elemento buscado se debe visualizar un mensaje similar a “Fin de Búsqueda” o “Elemento encontrado” y otro que diga “posición=” en caso contrario, visualizar un mensaje similar a “Elemento no existe en la Lista”.

Este tipo de búsqueda compara cada elemento del vector con el valor a encontrar hasta que este se consiga o se termine de leer el vector completo.

Metodo Shell Sort en Java

public class shell_sort {
public static void shellSort( int b[ ]){
for(int k= b.length/2; k>0; k=k==2?1:(int)( k/2.2)){
for(int i=k;i<b.length; i++ ){
int tmp =b[i];
int j;
for(j=i; j>=k&&tmp<b[j-k]; j-=k){
b[j]=b[j-k]; }
b[j]=tmp;
}
}
}
public static void main(String args[]){
int a[]={321, 6, 1, 234, 213, 4, 5, 123};
System.out.println("Antes del ordenamiento");
for(int i=0;i<a.length;i++)
{
System.out.print(a[i]+" ");
}
shellSort(a);
System.out.println("\n");
System.out.println("Ordenado por el método Shell");
for (int i=0;i < a.length;i++){
System.out.print(a[i]+" ");
}
}
}

Metodo Shell Sort

El método de Shell es una versión mejorada del método de inserción directa. Recibe ese nombre en honor de su autor, Donald L. Shell, quien lo propuso en 1959. Este método tambien se conoce como inserción con incrementos decrecientes.
Shell propone que las comparaciones entre elementos se efectúen con saltos de mayor tamaño, pero con incrementos decrecientes; así, los elementos quedaran ordenados en el arreglo más rápidamente.

En el método de clasificación por inserción, cada elemento se compara con los elementos contiguos de su izquierda, uno tras otro. Si el elemento a insertar es más pequeño - por ejemplo -, hay que ejecutar muchas comparaciones antes de colocarlo en su lugar definitivamente. Shell modifico los saltos contiguos resultantes de las comparaciones por saltos de mayor tamaño y con eso se conseguía la clasificación más rápida. El método se basa en fijar el tamaño de los saltos constantes, pero de mas de una posición.

El análisis de eficiencia del método de Shell es un problema muy complicado y aun no resuelto. Hasta el momento no se ha podido establecer la mejor secuencia de incrementos cuando n es grande. Cabe recordar que cada vez que se propone una secuencia de intervalos, es necesario correr el algoritmo para analizar su tiempo de ejecución.


Ventajas:
-No requiere memoria adicional.
-Mejor rendimiento que el método de inserción rápido.
-Fácil implantación.

Desventajas:
-Su funcionamiento puede resultar confuso
-Suele ser un poco lento.
-Realiza numerosas comparaciones e intercambios.

Método QuickSort en Java

public class quicksort {
public static void main(String a[]){
int i;
int array[] = {12,9,4,99,120,1,3,10,13};
System.out.println(" Quick Sort\n");
System.out.println("Valores antes de QuickSort:\n");
for(i = 0; i < array.length; i++)
System.out.print( array[i]+" ");
System.out.println();
quick_srt(array,0,array.length-1);
System.out.print("\n\n\nValores despues de QuickSort:\n\n");
for(i = 0; i <array.length; i++)
System.out.print(array[i]+" ");
System.out.println();
}

public static void quick_srt(int array[],int low, int n){
int lo = low;
int hi = n;
if (lo >= n) {
return;
}
int mid = array[(lo + hi) / 2];
while (lo < hi) {
while (lo<hi && array[lo] < mid) {
lo++;
}
while (lo<hi && array[hi] > mid) {
hi--;
}
if (lo < hi) {
int T = array[lo];
array[lo] = array[hi];
array[hi] = T;
}
}
if (hi < lo) {
int T = hi;
hi = lo;
lo = T;
}
quick_srt(array, low, lo);
quick_srt(array, lo == low ? lo+1 : lo, n);
}
}

Metodo QuickSort

Este método es una mejora sustancial del método de intercambio directo y recibe el nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo. Su autor C.A. Hoare lo bautizó así.
La idea central de este algoritmo consiste en los siguiente:

  • Se toma un elemento x de una posición cualquiera del arreglo.
  • Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a x y todos los elementos que se encuentren a su derecha sean mayores o iguales a x.
  • Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición correcta de x en el arreglo.
Tiene aparentemente la propiedad de trabajar mejor para elementos de entrada desordenados completamente, que para elementos semiordenados. Esta situación es precisamente la opuesta al ordenamiento de burbuja.

Metodo burbuja en Java

public class Burbuja {
static int [] vec = {312, 614, 88, 22, 54};  
void ordenar (int [] v, int cant) {  
if (cant > 1) {  
for (int f = 0 ; f < cant - 1 ; f++)//  
if (v [f] > v [f + 1]) {  
int aux = v [f];  
v [f] = v [f + 1];  
v [f + 1] = aux;  
}  
ordenar (v, cant - 1);  
}  
}  
void imprimir () {  
for (int f = 0 ; f < vec.length ; f++)  
System.out.print (vec [f] + " ");  
System.out.println("\n");  
}  

public static void main (String [] ar) {  
Recursivdad r = new Burbuja();  
r.imprimir ();  
r.ordenar (vec, vec.length);  
r.imprimir ();  
}
}

Metodo burbuja

Este método consiste en acomodar el vector moviendo el mayor hasta la última casilla comenzando desde la casilla cero del vector hasta haber acomodado el número más grande el la última posición, una vez acomodado el más grande, prosigue a encontrar y acomodar el siguiente más grande comparando de nuevo los números desde el inicio del vector, y así sigue hasta ordenar todo los elementos el arreglo. Este algoritmo es muy deficiente ya que al ir comparando las casillas para buscar el siguiente más grande, éste vuelve a comparar las ya ordenadas. A pesar de ser el algoritmo de ordenamiento más deficiente que hay, éste es el más usado en todos los lenguajes de programación.


El procedimiento de la burbuja es el siguiente:
  • Ir comparando desde la casilla 0 numero tras número hasta encontrar uno mayor, si este es realmente el mayor de todo el vector se llevará hasta la última casilla, si no es así, será reemplazado por uno mayor que él.
  • Este procedimiento seguirá así hasta que halla ordenado todas las casillas del vector.
Una de las deficiencias del algoritmo es que ya cuando a ordenado parte del vector vuelve a compararlo cuando esto ya no es necesario.

Ventajas:
•Bastante sencillo y mas utilizado por su fácil comprensión y programación
•Código reducido
•Eficaz.


Desventajas:
•Consume bastante tiempo calculo computarizado.
•Requiere de muchas lecturas/escrituras en memoria
Una de las deficiencias del algoritmo es que ya cuando a ordenado parte del vector vuelve a compararlo cuando esto ya no es necesario.

domingo, 24 de noviembre de 2013

Numeros de Fibonacci en java


 public class fibonacci {

 public int fibonaci (int n, int fibinf, int fibsup)

{

    Scanner teclado = new Scanner (System.in);
    System.out.println("Ingrese el numero");
    n = teclado.nextInt();
    System.out.println("--------------------");
    if ((n==0)||(n==1))
    {
    System.out.println("La suma es " + n);
    return n;
     }

    fibinf = 0;
    fibsup = 1;
    for (int i = 2; i<n; i++) {
     int x;
     x = fibinf;
     fibinf = fibsup;
     fibsup = x + fibinf;
     System.out.println(" "+fibsup);
    }
     return (fibsup);
   
}
     public static void main(String[] args)

     {

      fibonacci fb = new fibonacci ();

      int n =0, fibinf =0, fibsup = 1;

      fb.fibonaci(n, fibinf, fibsup);

      }
 }

Numero de Fibonacci


Leonardo Fibonacci, también llamado Leonardo Pisano, fue un calculista que nació y murió en la ciudad de Pisa, en Italia, del 1175 a 1240. Dedicó su vida a recopilar todas las enseñanzas que recogió en sus numerosos viajes al mundo árabe, de quienes difundió sus principios de cálculo en el mundo occidental. 

Los conocidos como Números Fibonachi, fueron un intento de describir el crecimiento de una población teniendo en cuenta que cada individuo tendría dos hijos a lo largo de su vida.

Consta de una serie de números naturales que se suman de a 2, a partir de 0 y 1. Básicamente, la sucesión de Fibonacci se realiza sumando siempre los últimos 2 números (Todos los números presentes en la sucesión se llaman números de Fibonacci) de la siguiente manera:
0,1,1,2,3,5,8,13,21,34...

Fácil, ¿no? (0+1=1 / 1+1=2 / 1+2=3 / 2+3=5 / 3+5=8 / 5+8=13 / 8+13=21 / 13+21=34...) Así sucesivamente, hasta el infinito. Por regla, la sucesión de Fibonacci se escribe así:

xn = xn-1 + xn-2.

Recursividad

Recursividad
Propiedad que posee un metodo por la cual puede llamarse a sí mismo. un metodo tiene sentencias entre las que se encuentran al menos una llamada al propio metodo.

Metodos recursivos:

  • Factorial
  • Torres de Hanoi
  • Ajedrez
  • Black Jack
  • Fibonacci.


viernes, 1 de noviembre de 2013

Codigo Arbol


import java.util.Scanner;

public class Arbol {
    class Nodo
    {
        int info;
        Nodo izq, der;
    }
    Nodo raiz;
    int cant;
    int altura;
    public Arbol() {
        raiz=null;
    }
    public void insertar (int info) {
        if (!existe(info)) {
            Nodo nuevo;
            nuevo = new Nodo ();
            nuevo.info = info;
            nuevo.izq = null;
              nuevo.der = null;
            if (raiz == null)
                raiz = nuevo;
            else {
                Nodo anterior = null, reco;
                reco = raiz;
                while (reco != null)  {
                    anterior = reco;
                    if (info < reco.info)
                        reco = reco.izq;
                    else
                        reco = reco.der;
                }
                if (info < anterior.info)
                    anterior.izq = nuevo;
                else
                    anterior.der = nuevo;
            }
        }
    }
    public boolean existe(int info) {
        Nodo reco=raiz;
        while (reco!=null) {
            if (info==reco.info)
                return true;
            else
                if (info>reco.info)
                    reco=reco.der;
                else
                    reco=reco.izq;
        }
        return false;
    }
    private void imprimirEntre (Nodo reco)  {
        if (reco != null)  {
            imprimirEntre (reco.izq);
            System.out.print(reco.info + " ");
            imprimirEntre (reco.der);
        }
    }
    public void imprimirEntre () {
        imprimirEntre (raiz);
        System.out.println();
    }

    private void cantidad(Nodo reco) {
        if (reco!=null) {
            cant++;
            cantidad(reco.izq);
            cantidad(reco.der);
        }
    }
    public int cantidad() {
        cant=0;
        cantidad(raiz);
        return cant;
    }
    private void cantidadNodosHoja(Nodo reco) {
        if (reco!=null) {
            if (reco.izq==null && reco.der==null)
                cant++;
            cantidadNodosHoja(reco.izq);
            cantidadNodosHoja(reco.der);
        }
    }
    public int cantidadNodosHoja() {
        cant=0;
        cantidadNodosHoja(raiz);
        return cant;
    }
    private void imprimirEntreConNivel (Nodo reco,int nivel)  {
        if (reco != null) {
            imprimirEntreConNivel (reco.izq,nivel+1);
            System.out.print(reco.info + " ("+nivel+") - ");
            imprimirEntreConNivel (reco.der,nivel+1);
        }
    }
    public void imprimirEntreConNivel () {
        imprimirEntreConNivel (raiz,1);
        System.out.println();
    }
    private void retornarAltura (Nodo reco,int nivel)    {
        if (reco != null) {
            retornarAltura (reco.izq,nivel+1);
            if (nivel>altura)
                altura=nivel;
            retornarAltura (reco.der,nivel+1);
        }
    }
    public  int retornarAltura () {
        altura=0;
        retornarAltura (raiz,1);
        return altura;
    }
    public void mayorValorl() {
        if (raiz!=null) {
            Nodo reco=raiz;
            while (reco.der!=null)
                reco=reco.der;
            System.out.println("Mayor valor del irbol:"+reco.info);
        }
    }
    public void borrarMenor() {
        if (raiz!=null) {
            if (raiz.izq==null)
                raiz=raiz.der;
            else {
                Nodo atras=raiz;
                Nodo reco=raiz.izq;
                while (reco.izq!=null) {
                    atras=reco;
                    reco=reco.izq;
                }
                atras.izq=reco.der;
            }
        }
    }
    public static void main (String [] ar)
    {
        Scanner leer=new Scanner(System.in);
        int opc1;
        String opc2;
        Arbol abo = new Arbol ();
        do{
            System.out.println("Ingrese dato");
            opc1=leer.nextInt();
            abo.insertar(opc1);
            System.out.println("Desea introducir otro dato?\na)Si b)No");
            opc2=leer.next();
           
        }while(opc2!="a");

        System.out.println ("Impresion entreorden: ");
        abo.imprimirEntre ();
        System.out.println ("Cantidad de nodos del irbol:"+abo.cantidad());
        System.out.println ("Cantidad de nodos hoja:"+abo.cantidadNodosHoja());
        System.out.println ("Impresion en entre orden junto al nivel del nodo.");
        abo.imprimirEntreConNivel();
        System.out.print ("Artura del arbol:");
        System.out.println(abo.retornarAltura());
        abo.mayorValorl();
        abo.borrarMenor();
        System.out.println("Luego de borrar el menor:");
        abo.imprimirEntre ();
    }
}

Ejemplo de la Clase DefaultMutableTreeNode


/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package javaapplication3;

 import java.awt.*;
 import java.awt.event.*;
 import javax.swing.*;
 import javax.swing.tree.*;
 import java.util.*;

/**
 *
 * @author alumno
 */
public class Main {

    /**
     * @param args the command line arguments
     */

   public static void main(String[] args)
    {  JFrame frame = new MainTreeFrame();
       frame.show();
    }
 }
 class MainTreeFrame extends JFrame
 {
    DefaultMutableTreeNode root = new DefaultMutableTreeNode("Mundo");
    DefaultMutableTreeNode arge = new DefaultMutableTreeNode("Argentina");
    DefaultMutableTreeNode sant = new DefaultMutableTreeNode("Santa Fe");
    DefaultMutableTreeNode rafa = new DefaultMutableTreeNode("Rafaela");
    DefaultMutableTreeNode rosa = new DefaultMutableTreeNode("Rosario");
    DefaultMutableTreeNode safe = new DefaultMutableTreeNode("Santa Fe");
    DefaultMutableTreeNode vena = new DefaultMutableTreeNode("Venado Tuerto");
    DefaultMutableTreeNode vill = new DefaultMutableTreeNode("Villa Constitucion");
    DefaultMutableTreeNode cord = new DefaultMutableTreeNode("Cordoba");
    DefaultMutableTreeNode codo = new DefaultMutableTreeNode("Cordoba");
    DefaultMutableTreeNode cbro = new DefaultMutableTreeNode("Cura Brochero");
    DefaultMutableTreeNode rcua = new DefaultMutableTreeNode("Rio Cuarto");
    DefaultMutableTreeNode chac = new DefaultMutableTreeNode("Chaco");
    DefaultMutableTreeNode resi = new DefaultMutableTreeNode("Resistencia");
    DefaultMutableTreeNode vang = new DefaultMutableTreeNode("Villa Angela");
    DefaultMutableTreeNode chil = new DefaultMutableTreeNode("Chile");
    DefaultMutableTreeNode regi = new DefaultMutableTreeNode("Region Metropolitana");
    DefaultMutableTreeNode schi = new DefaultMutableTreeNode("Santiago de Chile");
    public MainTreeFrame()
    {  setTitle("SimpleTree");
       setSize(300, 200);
       addWindowListener(new WindowAdapter()
          {  public void windowClosing(WindowEvent e)
             {  System.exit(0);
             }
          } );
       root.add(arge);                                                   // Enlazado de nodos
       arge.add(sant);                                                   // Enlazado de nodos
       sant.add(rafa);                                                   // Enlazado de nodos
       sant.add(rosa);                                                   // Enlazado de nodos
       sant.add(safe);                                                   // Enlazado de nodos
       sant.add(vena);                                                   // Enlazado de nodos
       sant.add(vill);                                                   // Enlazado de nodos
       arge.add(cord);                                                   // Enlazado de nodos
       cord.add(codo);                                                   // Enlazado de nodos
       cord.add(cbro);                                                   // Enlazado de nodos
       cord.add(rcua);                                                   // Enlazado de nodos
       arge.add(chac);                                                   // Enlazado de nodos
       chac.add(resi);                                                   // Enlazado de nodos
       chac.add(vang);                                                   // Enlazado de nodos
       root.add(chil);                                                   // Enlazado de nodos
       chil.add(regi);                                                   // Enlazado de nodos
       regi.add(schi);                                                   // Enlazado de nodos
       JTree tree = new JTree(root);
       Container contentPane = getContentPane();
       contentPane.add(new JScrollPane(tree));
       Enumeration hijos = sant.children();                              // Enumeracion de hijos
       while ( hijos.hasMoreElements() )                                 // Enumeracion de hijos
       {                                                                 // Enumeracion de hijos
         System.err.println("Hijos de Santa Fe : "+hijos.nextElement()); // Enumeracion de hijos
       }                                                                 // Enumeracion de hijos
       boolean hoja = vena.isLeaf();                                     // Consulta Hoja
       System.err.println("Es Venado Tuerto hoja : "+hoja);              // Consulta Hoja
       Enumeration breadth = root.breadthFirstEnumeration();             // Enumeracion Nodos
       while ( breadth.hasMoreElements() )                               // Enumeracion Nodos
       {                                                                 // Enumeracion Nodos
         System.err.println("Breadth First : "+breadth.nextElement());   // Enumeracion Nodos
       }                                                                 // Enumeracion Nodos
       Enumeration depth = root.depthFirstEnumeration();                 // Enumeracion Nodos
       while ( depth.hasMoreElements() )                                 // Enumeracion Nodos
       {                                                                 // Enumeracion Nodos
         System.err.println("Depth First : "+depth.nextElement());       // Enumeracion Nodos
       }                                                                 // Enumeracion Nodos
       Enumeration preorder = root.preorderEnumeration();                // Enumeracion Nodos
       while ( preorder.hasMoreElements() )                              // Enumeracion Nodos
       {                                                                 // Enumeracion Nodos
         System.err.println("Pre Order : "+preorder.nextElement());      // Enumeracion Nodos
       }                                                                 // Enumeracion Nodos
       Enumeration postorder = root.postorderEnumeration();              // Enumeracion Nodos
       while ( postorder.hasMoreElements() )                             // Enumeracion Nodos
       {                                                                 // Enumeracion Nodos
         System.err.println("Post Order : "+postorder.nextElement());    // Enumeracion Nodos
       }                                                                 // Enumeracion Nodos
    }



    }

Clase DefaultMutableTreeNode

Clase DefaultMutableTreeNode
Esta clase se encuentra en el paquete javax.swing.tree.DefaultMutableTreeNode.

Constructores
  • DefaultMutableTreeNode() Crea un nodo de árbol que no tiene padre y no tiene hijos, pero que permite a los niños.
  • DefaultMutableTreeNode(Object userObject) Crea un nodo del árbol, sin padres, sin hijos, pero que permite a los niños, y lo inicializa con el objeto de usuario especificado.
  • DefaultMutableTreeNode(Object userObject, boolean allowsChildren) Crea un nodo del árbol, sin padres, sin hijos, inicializado con el objeto de usuario especificado, y que permite a los niños sólo si se especifica.



Metodos
  • add(MutableTreeNode newChild) Elimina newChild de su padre y lo convierte en un hijo de este nodo, añadiendo al final de la matriz hijo de este nodo.
  • breadthFirstEnumeration() Crea y devuelve una enumeración que recorre el subárbol con raíz en el nodo de ancho-de primer orden.
  • children() Crea y devuelve una enumeración con miras al fin de los hijos de este nodo.
  • clone() Reemplazado para hacer un clon público.
  • depthFirstEnumeration() Crea y devuelve una enumeración que recorre el subárbol con raíz en este nodo en la profundidad de primer orden.
  • getAllowsChildren() Devuelve true si se permite este nodo para tener hijos.
  • getChildAfter(TreeNode aChild) Devuelve el niño de este nodo hijo que sigue inmediatamente aChild, que debe ser un hijo de este nodo.
  • getChildAt(int index) Devuelve el niño en el índice especificado en serie infantil de este nodo.
  • getChildBefore(TreeNode aChild) Devuelve el niño en serie infantil de este nodo que precede inmediatamente aChild, que debe ser un hijo de este nodo.
  • getChildCount() Devuelve el número de hijos de este nodo.
  • getDepth() Devuelve la profundidad del árbol de raíz en este nodo - la distancia más larga desde este nodo a una hoja.
  • getFirstChild() Devuelve el primer hijo de este nodo.
  • getFirstLeaf() Encuentra y devuelve la primera hoja que es un descendiente de este nodo - ya sea este nodo o primera hoja de su primer hijo.
  • getIndex(TreeNode aChild) Devuelve el índice del elemento secundario especificado en el array hijo de este nodo.
  • getLastChild() Devoluciones último hijo de este nodo.
  • getLastLeaf() Encuentra y devuelve la última hoja que es un descendiente de este nodo - ya sea este nodo o la última hoja de su último hijo.
  • getLeafCount() Devuelve el número total de hojas que son descendientes de este nodo.
  • getLevel() Devuelve el número de niveles por encima de este nodo - la distancia desde la raíz a este nodo.
  • getNextLeaf() Devuelve la hoja después de este nodo o null si este nodo es la última hoja en el árbol.
  • getNextNode() Devuelve el nodo que sigue a este nodo en un recorrido en preorden del árbol de este nodo.
  • getNextSibling() Devuelve el siguiente hermano de este nodo en conjunto los niños de los padres.
  • getParent() Devoluciones padre o nula de este nodo si el nodo no tiene padre.
  • getPath() Devuelve la ruta desde la raíz, para llegar a este nodo.
  • getPathToRoot(TreeNode aNode, int depth) Construye los padres de los nodos hasta e incluyendo el nodo raíz, donde el nodo original es el último elemento de la matriz devuelta.
  • getPreviousLeaf() Devuelve la hoja antes de este nodo o null si este nodo es la primera hoja en el árbol.
  • getPreviousNode() Devuelve el nodo que precede a este nodo en un recorrido en preorden del árbol de este nodo.
  • getPreviousSibling() Devuelve el elemento secundario anterior de este nodo en conjunto los niños de los padres.
  • getRoot() Devuelve la raíz del árbol que contiene este nodo.
  • getSharedAncestor(DefaultMutableTreeNode aNode) Devuelve el ancestro común más cercano a este nodo y el ánodo.
  • getSiblingCount() Devuelve el número de hijos de este nodo.
  • getUserObject() Devoluciones objeto de usuario de este nodo.
  • getUserObjectPath() Devuelve la ruta de objeto de usuario, desde la raíz, para llegar a este nodo.
  • insert(MutableTreeNode newChild, int childIndex) Elimina newChild de su presencia de los padres (si es que tiene uno de los padres), establece los padres del niño a este nodo y, a continuación, añade que el niño array hijo de este nodo en childIndex índice.
  • isLeaf() Devuelve true si el nodo no tiene hijos.
  • isRoot() Devuelve true si este nodo es la raíz del árbol.
  • remove(int childIndex) Elimina el niño en el índice especificado de los niños y los conjuntos de que el padre del nodo a NULL de este nodo.
  • remove(MutableTreeNode aChild) Elimina aChild de la matriz hijo de este nodo, lo que supone una matriz nula.
  • removeAllChildren() Elimina a todos los hijos de este nodo, el establecimiento de sus padres a null.
  • removeFromParent() Elimina el subárbol con raíz en este nodo del árbol, dando a este nodo de un padre nulo.
  • setAllowsChildren(boolean allows) Determina si este nodo se le permite tener hijos.
  • setParent(MutableTreeNode newParent) Sets this node's parent to newParent but does not change the parent's child array.
  • setUserObject(Object userObject) Establece el objeto de usuario para este nodo para UserObject.
  • toString() Devuelve el resultado de enviar toString () a objeto de usuario de este nodo, o null si el nodo no tiene un objeto de usuario.




viernes, 18 de octubre de 2013

Arbol Binario en Java

//arbol en java inorden, posorden, preorden */

//definicion de la clase NodoArbol
class NodoArbol {

 //miembros de acceso
 NodoArbol nodoizquierdo;
 int datos;
 NodoArbol nododerecho;

 //iniciar dato y hacer de este nodo un nodo hoja
 public NodoArbol(int datosNodo)
 {
  datos = datosNodo;
  nodoizquierdo = nododerecho = null; //el nodo no tiene hijos
 }

 //buscar punto de insercion  e insertar nodo nuevo
 public synchronized void insertar(int valorInsertar)
 {
  //insertar en subarbol izquierdo
  if (valorInsertar < datos){

   //inserta nuevo nodoarbol
   if (nodoizquierdo == null)
    nodoizquierdo = new NodoArbol(valorInsertar);
   else //continua recorriendo subarbol izquierdo
    nodoizquierdo.insertar(valorInsertar);
  }

  //insertar nodo derecho
  else if(valorInsertar > datos){

  //insertar nuevo nodoarbol
  if (nododerecho == null)
   nododerecho = new NodoArbol(valorInsertar);
  else //continua recorriendo subarbol derecho
   nododerecho.insertar(valorInsertar);
  }
 } //fin del metodo insertar

} //fin clase nodoarbol

//---------- CLASE ARBOL------------------
 class Arbol{
 private NodoArbol raiz;

 //contruir un arbol vacio
 public Arbol()
 {
  raiz = null;
 }

 //insertar un nuevo nodo en el arbol de busqueda binaria
 public synchronized void insertarNodo(int valorInsertar)
 {
  if(raiz == null)
   raiz = new NodoArbol(valorInsertar); //crea nodo raiz

  else
   raiz.insertar(valorInsertar); // llama al metodo insertar
 }

 //--------------- EMPESAR EL RECORRIDO EN PREORDEN-----------------------
 public synchronized void recorridoPreorden()
 {
  ayudantePreorden(raiz);
 }
 //metodo recursivo para recorrido en preorden

 private void ayudantePreorden(NodoArbol nodo)
 {
  if (nodo == null)
   return;

  System.out.print(nodo.datos + " "); // mostrar datos del nodo
  ayudantePreorden(nodo.nodoizquierdo); //recorre subarbol izquierdo
  ayudantePreorden(nodo.nododerecho); //recorre subarbol derecho
 }

 //--------------EMPEZAR RECORRIDO INORDEN-----------------------------------
 public synchronized void recorridoInorden()
 {
  ayudanteInorden(raiz);
 }

 // metodo recursivo para recorrido inorden

 private void ayudanteInorden(NodoArbol nodo)
 {
  if (nodo == null)
   return;

  ayudanteInorden(nodo.nodoizquierdo);
  System.out.print(nodo.datos + " ");
  ayudanteInorden(nodo.nododerecho);
 }

 //-----------------------------EMPEZAR RECORRIDO POSORDEN---------------------------------
 public synchronized void recorridoPosorden()
 {
  ayudantePosorden(raiz);
 }

 //metodo recursivo para recorrido posorden

 private void ayudantePosorden(NodoArbol nodo)
 {
  if (nodo == null)
   return;

  ayudantePosorden(nodo.nodoizquierdo);
  ayudantePosorden(nodo.nododerecho);
  System.out.print(nodo.datos + " ");
 }

}//fin clase arbol

//programa para probar la clase arbol

public class PruebaArbol {
 public static void main(String args[])
 {
  Arbol arbol = new Arbol();
  int valor;

  System.out.println( "Insertando los siguientes valores: ");

  //insertando 10 numeros aleatorios del 0 al 99 en el arbol
  for (int i = 1; i<=10 ; i++)
  {
   valor = (int) (Math.random() * 100);
   System.out.print(valor + " ");
   arbol.insertarNodo(valor);
  }

  System.out.println("\n\nRecorrido preorden");
  arbol.recorridoPreorden();

  System.out.println("\n\nRecorrido inorden");
  arbol.recorridoInorden();

  System.out.println("\n\nRecorrido posorden");
  arbol.recorridoPosorden();
 }
}

jueves, 17 de octubre de 2013

Bosque

Bosque
Representa un conjunto normalmente ordenado de uno o mas arboles generales.

Conversión a Árbol Binario
Enlazar en forma horizontal las raíces de los distintos arboles generales.
Relacionar los hijos de cada nodo (los hermanos) en forma horizontal.
Enlazar en forma vertical el nodo padre con el hijo que de encuentra mas a la izquierda. Ademas se debe eliminar el vinculo del padre con el resto de sus hijos.
Rotar el diagrama resultante aprox. 45° hacia la izquierda y asi obtendrá el árbol binario correspondiente.

Recorridos
Inorden (Izquierdo, Raiz, Derecho)
Preorden (Raiz, Izquierdo, Derecho)
Postorden (Izquierdo, Derecho, Raiz)

Arboles binarios

Arbol Binario.
Es un árbol ordenado, en el cual cada nodo puede tener como máximo dos subarboles.
Estructura homogenea, resultado de la concatenacion de un elemento de tipo T, llamado raiz, con nodos arboles binarios disjuntos , llamados subarbol izquierdo y subarbol derecho.



Arbol general a Arbol binario

  1. Enlazar los hijos de cada nodo en forma horizontal (los hermanos).
  2. Relacionar en forma vertical el nodo padre con el nodo hijo que se encuentra mas a la izquierda. Ademas, se deben eliminar el vinculo de ese padre con el resto de los hijos.
  3. Rotar el diagrama resultante, aprox 45° hacia la izquierda y asi de obtendra un arbol binario correspondiente.

Arboles

Arboles
Estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos; uno de los cuales es conocido como raíz.

Aplicaciones:
Formulas matemáticas
Circuitos eléctricos
Árbol genealógico

Propiedades
Todo los nodos que son descendientes directos hijos de un mismo nodo padre, son hermanos.
Todos nodo que no tiene ramificaciones (hijos) se conoce con el nombre de terminal u hoja.
Grado: Numero de descendientes directos de un determinado nodo.
Grado de un árbol: Es el máximo grado de todos los nodos del arbol.
Nivel: es el numero de arcos que pueden ser recorridos para llegar a un determinado nodo.

Longitud de camino interno
Es la suma de longitudes de camino de todos los nodos del árbol.
i= nivel del arbol.
h= altura.
ni= Numero de nodos en el nivel i.


Longitud del camino externo
Árbol extendido: es aquel en el que el numero de hijos de cada nodo es igual al grado del arbol, de no cumplir con esta característica se deben incorporar nodos especiales.

Nodos especiales: reemplazan las ramas vacias o nulas.

LCE: es la suma de todos los nodos especiales.

i= nivel del arbol.
h=altura.
nei= numero de nodos especiales.



jueves, 3 de octubre de 2013

Cola estatica

package cola;
import java.util.Scanner;
public class ColaEstatica {
public static int op;
public static int tope;
    int cola[]= new int[10];
    public void insertar(){
        if(tope==10)
            System.out.println("Cola llena");
        else
    {
       for(int i=0;i<cola.length;i++ ){
        System.out.println("Proporciona el dato para la Cola");
        System.out.println("dato " + tope);
        Scanner cap= new Scanner(System.in);
        cola[tope]=cap.nextInt();
        tope++;
    } }
}
    public void imprimir(){
       if(tope>0){
            for(int topeL=0;topeL<10;topeL++){
                System.out.println("\n\n" + cola [topeL]);
                System.out.println(tope);
            }
        }
        else
            System.err.println("cola vacia no hay nada que mostrar");
    }
    public void eliminar(){
        if(tope<0){
            System.out.println("cola vacia");
        }
        else
                for(int topeL=0;topeL<10;topeL++){
                     cola[topeL]=0;
            }
            }
    public static void main(String[] args) {
       ColaEstatica p = new ColaEstatica();
       String r;
       Scanner cap1=new Scanner(System.in);
       Scanner cap=new Scanner(System.in);
       tope=0;
       do{
           System.out.println("Menu principal:\n¿Que desea hacer con la pila?");
           System.out.println("1.-insertar");
           System.out.println("2.- eliminar");
           System.out.println("3.- imprimir");
           System.out.println("4.-salir");
           op=cap.nextInt();
           switch(op){
               case 1: p.insertar();break;
               case 2:p.eliminar();break;
               case 3:p.imprimir();break;
               case 4:break; default:
                   System.out.println("opcion no valida");break;
           }
    }while(op!=4);
}}

Los datos que se introducen al darle a la opción eliminar, son eliminados todos juntos.

Expresiones aritméticas

Un problema en computacion es poder convertir expresiones en notacion infija a su equivalente en notacion posfija (o prefija). Revisense algunos conceptos.


  • Dada la expresión A+B se dice que esta en notacion infija, y su nombre se debe a que el operador(+) esta entre los operandos (A y B).
  • Dada la expresión AB+ se dice que esta en notacion postfija, y su nombre se debe a que el operador (+) esta despues de los operandos (A y B).
  • Dada la expresion +AB se dice que esta en notación prefija, y su nombre se debe a que el operador (+) esta antes que los operadores (A y B).

Para convertir una expresion dad en notacion infija a una notacion posfija (o prefija), deberann establecerse previamente ciertas condiciones:


  • Solamente se manejaran los siguientes operadores (estan dados ordenadamente de mayor a menor segun su prioridad de ejecucion):
^ (potencia)
*/ (multiplicación y division)
+ - (suma y resta)
  • Los operadores de mas alta prioridad se ejecutan primer
  • Sihubiera en una expresion dos o mas operadores de igual prioridad, entonces se procesaran de izquierda a derecha.
  • Las subexpresiones parentizadas tendran mas prioridad que cualquier operador.

Ejemplo:






Pila Dinamica en Java

package javaapplication2;
import java.util.*;

public class PilaDinamica {
    public static void main(String[] args) {
        Scanner leer =new Scanner(System.in);
        int num;
        int op;
        LinkedList lista = new LinkedList();
        do{
            System.out.println("\t Menuº \t");
            System.out.println("Operaciones con pilas");
            System.out.println("1.- Insertar");
            System.out.println("2.- Borrar");
            System.out.println("3.- Mostrar la pila");
            System.out.println("4.- Salir");
            System.out.println("\n");
            System.out.println("Elija la operación que desee");
            op =leer.nextInt();
            switch(op){
            case 1:
                System.out.println("Inserte Numero");
                num =leer.nextInt();
                lista.addLast(num);
                break;
            case 2:
                System.out.println("SE borrará el nodo final");
                lista.removeFirst();
                break;
            case 3:
                System.out.println("La lista es la siguiente");
                 List lista2 = new ArrayList (lista);
                 Iterator it = lista2.iterator();//añade otro nodo ,es un ciclo
                 //sirve para recorrer la lista
                 while (it.hasNext()){
                     System.out.println(it.next() + "");
                 }
                 break;
            case 4:
                System.out.println("Al rato");
                break;
            }
        }
        while(op != 4);
    }
}