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();
 }
}

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.

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);
    }
}

Pila Estática en Java

package javaapplication10;

import java.util.Scanner;

public class PilaEstatatica {

public static int op;
public static int tope;
    int pila[]= new int[10];
    public void insertar(){
        if(tope==10)
            System.out.println("Pila llena");
        else
    {
       for(int i=0;i<pila.length;i++ ){
        System.out.println("Proporciona el dato para la pila");
        System.out.println("dato " + tope);
        Scanner cap= new Scanner(System.in);
        pila[tope]=cap.nextInt();
        tope++;
    } }
}
    public void imprimir(){
        if(tope!=0){
            for(int topeL=tope-1;topeL>=0;topeL--){
                System.out.println("\n\n" + pila [topeL]);
            }
        }
        else
            System.err.println("pila vacia no hay nada que mostrar");
    }
    public void eliminar(){
        if(tope<0){
            System.out.println("pila vacia");
        }
        else
            if(tope==10){//Esto se usa cuando la pila esta totalmente llena,
                //ya que se incremento en insertar y quedo en 10, de lo contrario
                //noz arrojara un error de array
                tope--;
                pila[tope]=0;
                tope--;//se vuelve a decrementar para que este en la pocision correcta, porque
                //tenia un numero de mas
            }
            else{
            pila[tope]=0;
            tope--;
            }     
    }
    public static void main(String[] args) {
       PilaEstatatica p = new PilaEstatatica();
       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:if(tope==10)
                   p.eliminar();
               else
                       System.out.println("no hay nada que eliminar :) ");
                   break;
               case 3:p.imprimir();break;
               case 4:break;
               default:
                   System.out.println("opcion no valida");break;
           }
    }while(op!=4);

}
}