Tarea 3: Algoritmos de Búsqueda en Java - Rodrigo Cofré.-

Arboles Binarios

Se define un árbol binario como un conjunto finito de elementos (nodos) que bien esta vacío o esta formado por una raíz con dos arboles binarios disjuntos, es decir, dos descendientes directos llamados subarbol izquierdo y subarbol derecho.

Los árboles binarios (también llamados de grado 2 )tienen una especial importancia.

Las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.

Arbol binario de búsqueda.

Los árboles binarios se utilizan frecuentemente para representar conjuntos de datos cuyos elementos se identifican por una clave única. Si el árbol está organizado de tal manera que la clave de cada nodo es mayor que todas las claves su subarbol izquierdo, y menor que todas las claves del subarbol derecho se dice que este árbol es un árbol binario de búsqueda.


Ejemplo:

Operaciones básicas

Una tarea muy común a realizar con un árbol es ejecutar una determinada operación con cada uno de los elementos del árbol. Esta operación se considera entonces como un parámetro de una tarea más general que es la visita de todos los nodos o, como se denomina usualmente, del recorrido del árbol.

Si se considera la tarea como un proceso secuencial, entonces los nodos individuales se visitan en un orden específico, y pueden considerarse como organizados según una estructura lineal. De hecho, se simplifica considerablemente la descripción de muchos algoritmos si puede hablarse del proceso del siguiente elemento en el árbol, según un cierto orden subyacente.

Hay dos formas básicas de recorrer un árbol: El recorrido en amplitud y el recorrido en profundidad.

Recorrido de un Arbol Binario

Recorrido en amplitud

Es aquel recorrido que recorre el árbol por niveles, en el último ejemplo sería:

12 - 8,17 - 5,9,15

Recorrido en profundidad

Recorre el árbol por subárboles.

Hay tres Preorden, orden central y postorden.

Hay tres formas: en inorden, preorden y postorden. Cada una de ellas tiene una secuencia distinta para analizar el árbol como se puede ver a continuación:

1. Inorden

Recorrer el subarbol izquierdo en inorden.

Examinar la raíz.

Recorrer el subarbol derecho en inorden.

Preorden

Examinar la raíz.

Recorrer el subarbol izquierdo en preorden.

recorrer el subarbol derecho en preorden.

Postorden

Recorrer el subarbol izquierdo en postorden.

Recorrer el subarbol derecho en postorden.

Examinar la raíz.

A continuación se muestra un ejemplo de los diferentes recorridos en un árbol binario.

Inorden: GDBHEIACJKF

Preorden: ABDGEHICFJK

Postorden: GDHIEBKJFCA

Clasificación de Arboles Binarios

Existen cuatro tipos de árbol binario:.

Arbol Binario Distinto.

Arbol Binario Similares.

Arbol Binario Equivalentes.

Arbol Binario Completos.

A continuación se hará una breve descripción de los diferentes tipos de árbol binario así como un ejemplo de cada uno de ellos.

Arbol Binario Distinto

Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes.

Ejemplo:

Arbol Binario Similar

Dos arboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente.

Ejemplo:

Arbol Binario Equivalente

Son aquellos arboles que son similares y que además los nodos contienen la misma información. Ejemplo:

Arbol Binario Completo

Son aquellos arboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subarbol izquierdo y el subarbol derecho.

Terminología

La terminología que por lo regular se utiliza para el manejo de arboles es la siguiente:

Hijo: X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y.

Padre: X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y.

Hermano: Dos nodos serán hermanos si son descendientes directos de un mismo nodo.

Hoja: Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos).

Nodo anterior: Es un nodo que no es raíz ni terminal.

Grado: Es el número de descendientes directos de un determinado nodo.

Grado de un árbol: Es el máximo grado de todos los nodos del árbol.

Nivel: Es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1.

Altura: Es el máximo número de niveles de todos los nodos del árbol.

Peso: Es el número de nodos del árbol sin contar la raíz.

Longitud de camino: Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente.

/*
*
*  Autor Rodrigo Cofré F.
*
*
*/
//********************
// ArbolBinario.java
//********************

import arbolbinario.Leer;

public class ArbolBinario
{

    void borrarnodo() {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }
    class Nodo
    {
        int info;
        Nodo izq, der;
    }
    Nodo raiz;

    public ArbolBinario(){
        raiz = null;
    }
   
    public void insertar(int info)
    {

        Nodo 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;
        }      
    }  
   
    private void preorden (Nodo n)
    {
        if (n != null)
        {
            System.out.print(n.info + " ");
            preorden (n.izq);
            preorden (n.der);
           
        }
    }      
   
    public void preorden ()
    {
        preorden (raiz);
        System.out.println();
    }
   
    private void inorden (Nodo n)
    {
        if (n != null)
        {
            inorden (n.izq);
            System.out.print(n.info + " ");
            inorden (n.der);
        }
    }
   
    public void inorden ()
    {
        inorden (raiz);
        System.out.println();
    }
   
    private void postorden (Nodo n)
    {
        if (n != null)
        {
            postorden (n.izq);
            postorden (n.der);
            System.out.print(n.info + " ");          
        }
    }
   
    public void postorden ()
    {
        postorden (raiz);
        System.out.println();
    }
    //metodo para insertar nodos
    public void insertarteclado ()
    {
        int can;
        int num;
        System.out.print("Ingresar la Cantidad de Nodos para crear el árbol: ");
        can = Leer.datoInt();
        for (int i=0; i<can; i++)
        {
            System.out.print("Ingrese Nodo "+(i+1)+" :");
            num = Leer.datoInt();
            insertar(num);
        }
    }
    // metodo para buscar nodo en el arbol
   
    public String buscar(int num)
    {
        if (buscar(this.raiz,num)==true) return "Se ecnontro el número "+ num + " en el arbol";
        else return "No se encontro el número "+num +"en el arbol";//aqui retorna falso
    }
    private boolean buscar(Nodo n,int num)
    {
        if (n != null)
        {
            if (n.info == num) return true;
            boolean bus1 = buscar(n.izq,num);
            boolean bus2 = buscar(n.der,num);
            if((bus1 == true)||(bus2 == true)) return true;
        }
        return false;
    }
    //metodo para sumer los números del arbol
    public String sumar()
    {
        int suma = sumar(this.raiz);
        return "Suma de nodos: "+suma;
    }
   
    private int sumar(Nodo n)
    {
        if (n == null)return 0;
        int c1 = sumar(n.izq);// relaliza la suma de las posisiones izquierdas
        int c2 = sumar(n.der);// relaliza la suma de las posisiones derecha
        int c3 = c1 + c2 + n.info;
       
        return c3;//retorna la suma
    }
    //metodo para contar los nodos
    public int contar()
    {
        int cant = contar(this.raiz);
        return cant;
    }
   
    private int contar(Nodo n)
    {
        if (n==null) return 0;
        int c1 = contar (n.izq);
        int c2 = contar (n.der);
        int c3 = c1 + c2 + 1;
       
        return c3;
    }
    //metodo para sacar el promerdio de los numeros
    public String promedio()
    {
        Double prom = promedio(this.raiz);
        return "Promedio de los números: "+ prom/contar();
    }
   
    private Double promedio(Nodo n)
    {
        if (n == null) return 0.0;
        Double c1 = promedio(n.izq);
        Double c2 = promedio(n.der);
        Double c3 = c1 + c2 + n.info;
        return c3;
    }
    //metodo para retornar cantidad de números pares
    public String pares()
    {
        int cant = pares(this.raiz);
        return "Cantidad de números pares: "+cant;
    }
    int con=0;  //metodo global para que no se convierta en 0
    private int pares (Nodo n)
    {
        if (n != null)
        {
            if (n.info % 2 == 0)con++; //hace la comparacion si es par o no.
            pares (n.izq);
            pares (n.der);
        }
        return con;
    }
    // metodo para eliminar
    public void borrar (int elemento)//aqui se recibe el elemento a eliminar
    {
        raiz = borrar(this.raiz, elemento);
    }
   
    private Nodo borrar(Nodo r, int elemento)
    {
        if (r.info == elemento)//este es un caso en que el nodo r se requiere borrar del arbol
        {
            if(r.der == null && r.izq == null)
            {
                r = null;
                return r;
            }
            if(r.der == null)// caso en el que r solo tiene hijo izquierdo
            {
                r = r.izq;
                return r;    //aqui el hijo ocupa el lugar del padre
            }
            if(r.izq ==null)
            {
                r = r.der;
                return r;
            }
            //este es el caso en el que el nodo tiene dos hijos
            r.info = encontrarMaximo(r.izq); //sera igual que el nodo de mayor valor
            r = ajuste(r, r.izq, r);
            return r;//el nodo igualado de mayor valor se debe eliminar
        }
   
        if(elemento > r.info)//si el elemento buscado es mayor al del nodo actual
        {
            r.der = borrar(r.der, elemento);
            return r;
        }
   
        r.izq = borrar(r.izq, elemento);
        return r;
    }
    //este metodo sirve para econtrar al nodo maximo
    //nos ayudara para la eliminacion del nodo dado en el metodo borrar
    private int encontrarMaximo(Nodo r)
    {
        if(r.der == null)//si no hay un nodo mayor retorna el valor del nodo
            return r.info;
        return encontrarMaximo(r.der);
    }
    //metodo que elimina el nodo repetido y ajusta el arbol
    private Nodo ajuste(Nodo padre, Nodo hijo, Nodo ances)
    {
        if(hijo.der == null)
        {
            if(padre.equals(ances))
            {
                padre.izq = hijo.izq;
                return padre;
            }
            padre.der = hijo.izq;
            return padre;
        }
        return padre;
    }
   
}  
//************************************
// Principal.java
//************************************

import arbolbinario.Leer;

class principal
{
    public static void Menu()
    {
        //creo mi menu
        System.out.println("");
        System.out.println("         MENU      \n");
        System.out.println("---------------------");
        System.out.println(" [1]  Crea Arbol: se ingresan los nodos.");
        System.out.println(" [2]  Recorrido preorden");
        System.out.println(" [3]  Recorrido inorden");
        System.out.println(" [4]  Recorrido postorden ");
        System.out.println(" [5]  Realizar los tres recorridos");
        System.out.println(" [6]  Realizar la busqueda de un número");
        System.out.println(" [7]  Sumar los números");
        System.out.println(" [8]  Hallar el promedio de los nodos");
        System.out.println(" [9]  Mostrar cantidad de número pares");
        System.out.println(" [10] Eliminar nodo");
       
        System.out.println(" (0) Salir \n");
        System.out.println("Ingresar Opción \n");
    }

    public static void main(String args[])
    {
            ArbolBinario abo = new ArbolBinario ();
       
            int opc;
            Menu();
        System.out.println("Elegir opción: ");
        opc = Leer.datoInt();
        System.out.println("");
                //en cada opcion se llama a cada metodo segun corresponda
        while (opc != 0)
        {
            switch(opc)
            {
                case 0:
                {
                    System.out.println("Salir");
                    break;
                }
               
                case 1:
                {
                    abo.insertarteclado();
                    break;
                }
               
                case 2:
                {
                    System.out.println("PRE_ORDEN: ");
                    abo.preorden();
                    break;
                }
               
                case 3:
                {
                    System.out.println("IN-ORDEN: ");
                    abo.inorden();
                    break;
                }
               
                case 4:
                {
                    System.out.println("POST-ORDEN: ");
                    abo.postorden();
                    break;
                }
               
                case 5:
                {
                    System.out.println("PRE-ORDEN: ");
                    abo.preorden();
                    System.out.println("IN-ORDEN: ");
                    abo.inorden();
                    System.out.println("POST-ORDEN: ");
                    abo.postorden();
                    break;
                }
               
                case 6:
                {
                    int bus;
                    System.out.println("Ingresar el número a buscar: ");
                    bus = Leer.datoInt();
                    System.out.println("" + abo.buscar(bus));
                    break;
                }
               
                case 7:
                {
                    System.out.println("" + abo.sumar());
                    break;
                }
               
                case 8:
                {
                    Double prom = 0.0;
                    System.out.println("" + abo.promedio());
                    break;
                }
                   
                case 9:
                {
                    System.out.println("" + abo.pares());
                    break;
                }
                   
                case 10:
                {
                    abo.borrarnodo();
                    break;
                }
            }
            Menu();
                    opc = Leer.datoInt();
        }
    }


}


//***************************
//Leer.java
//***************************

package arbolbinario;

//***********************************************************************

//esta es mi clase leer que me ayuda a ingresar datos de todo tipo por teclado
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; //devolver dato tecleando
    }

    public static short datoShort()
    {
        try
        {
            return Short.parseShort(dato());
        }
        catch(NumberFormatException e)
        {
            return Short.MIN_VALUE;//valor más pequeño
        }
    }
    public static int datoInt()
    {
        try
        {
            return Integer.parseInt(dato());
        }
        catch(NumberFormatException e)
        {
            return Integer.MIN_VALUE;//valor mas pequeño
        }
    }

    public static long datoLong()
    {
        try
        {
            return Long.parseLong(dato());    
        }
            catch(NumberFormatException e)
        {
            return Long.MIN_VALUE; //valor mas pequeño
        }
    }

    public static float datoFloat()
    {
        try
        {
            Float f = new Float(dato());
            return f.floatValue();
        }
        catch(NumberFormatException e)
        {
            return Float.NaN;//No es un numero Valor float.
        }
    }

    public static double datoDouble()
    {
        try  
        {
            Double d = new Double(dato());
            return d.doubleValue();
        }
        catch(NumberFormatException e)
        {
            return Double.NaN;//no es un numero; valor double.
        }              
    }
}