Tarea 3 - Arboles Binarios

Fundamentos de Sistemas Inteligentes – Tarea 3

Árbol Binario

Un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario").

Si algún hijo tiene como referencia a NULL, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno.

Usos comunes de los árboles binarios son los árboles binarios de búsqueda (ABB), los montículos binarios y Codificación de Huffman.

Árbol Binario de Búsqueda (BST Binary Search Tree)

Un árbol binario de búsqueda es un tipo particular de árbol binario que presenta una estructura de datos en forma de árbol.

Árbol binario

La mayoría de los arboles binarios son de búsqueda:

Un árbol binario no vacío, de raíz R, es un árbol binario de búsqueda si:

·         En caso de tener subárbol izquierdo, la raíz R debe ser mayor que el valor máximo almacenado en el subárbol izquierdo, y que el subárbol izquierdo sea un árbol binario de búsqueda.

·         En caso de tener subárbol derecho, la raíz R debe ser menor que el valor mínimo almacenado en el subárbol derecho, y que el subárbol derecho sea un árbol binario de búsqueda.

Recorridos sobre árboles binarios

Ejemplo de árbol binario

Recorrido en preorden

En este tipo de recorrido se realiza cierta acción (quizás simplemente imprimir por pantalla el valor de la clave de ese nodo) sobre el nodo actual y posteriormente se trata el subárbol izquierdo y cuando se haya concluido, el subárbol derecho. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo raiz, nodo izquierdo, nodo derecho.

En el árbol de la figura el recorrido en preorden sería: 2, 7, 2, 6, 5, 11, 5, 9 y 4.

Recorrido en postorden

En este caso se trata primero el subárbol izquierdo, después el derecho y por último el nodo actual. Otra forma para entender el recorrido con este método seria seguir el orden: nodo izquierdo, nodo derecho, nodo raiz.

En el árbol de la figura el recorrido en postorden sería: 2, 5, 11, 6, 7, 4, 9, 5 y 2.

Recorrido en inorden

En este caso se trata primero el subárbol izquierdo, después el nodo actual y por último el subárbol derecho. En un ABB este recorrido daría los valores de clave ordenados de menor a mayor. Otra forma para entender el recorrido con este método seria seguir el orden: nodo izquierdo, nodo raíz, nodo derecho.

En el árbol de la figura el recorrido en inorden sería: 2, 7, 5, 6, 11, 2, 5, 4, 9.

El código del programa:

package tarea_3;

/**
 *
 * @author PABLO
 */
public class ArbolBinarioOrdenado {
    class Nodo
    {
      int info;
      Nodo izq, der;
    }
    Nodo raiz;

    public ArbolBinarioOrdenado() {
        raiz=null;
    }

    public void insertar (int 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;
      }
  }


    private void imprimirPre (Nodo reco)
    {
      if (reco != null)
      {
          System.out.print(reco.info + " ");
          imprimirPre (reco.izq);
          imprimirPre (reco.der);
      }
  }

    public void imprimirPre ()
    {
      imprimirPre (raiz);
      System.out.println();
  }

    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 imprimirPost (Nodo reco)
    {
        if (reco != null)
        {
            imprimirPost (reco.izq);
            imprimirPost (reco.der);
            System.out.print(reco.info + " ");
        }
    }


    public void imprimirPost ()
    {
        imprimirPost (raiz);
        System.out.println();
    }
   
    String getString(int llave) {
      return buscar(llave, raiz);
    }

    String buscar(int llave, Nodo nodo) {
      if (nodo==null)
          System.out.println("El dato: " + llave + " no existe en el arreglo");
      else if (llave == nodo.info)
          return "Esta en el arbol";
          //return nodo.info;
      else if (llave < nodo.info)
          return buscar(llave, nodo.izq);
      else
          return buscar(llave, nodo.der);
      return null; // Solo para evitar el error en compilacion
    }
   
    public static void main (String [] ar)
    {
        ArbolBinarioOrdenado abo = new ArbolBinarioOrdenado ();
        System.out.println( "Insertando los siguientes valores: ");

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

        System.out.println ("Impresion preorden: ");
        abo.imprimirPre ();
        System.out.println ("Impresion entreorden: ");
        abo.imprimirEntre ();
        System.out.println ("Impresion postorden: ");
        abo.imprimirPost ();
       
        int z;
        java.util.Scanner leer=new java.util.Scanner(System.in);
        System.out.println ("Buscar: " );
       
        z=leer.nextInt();
        System.out.println ("Dato buscado: " + z);
        String k;
        k = abo.getString(z);
        System.out.println ("info: " + k);
       
  }
}