Recorrido de Arboles Binarios

Concepto de Arboles Binarios:

Un árbol binario es un tipo de árbol en que cada vértice máximo puede tener dos hijos; su nodo raíz está enlazado a dos subárboles binarios disjuntos denominados subárbol izquierdo y subárbol derecho. Los árboles binarios no son vacíos ya que como mínimo tienen el nodo raíz.

 

Recorrido de Arboles Binarios:

se refiere al proceso de visitar de una manera sistemática, exactamente una vez, cada nodo en una estructura de datos de árbol (examinando y/o actualizando los datos en los nodos). Tales recorridos están clasificados por el orden en el cual son visitados los nodos. 

·         Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:

1.      Visite la raíz.

2.      Atraviese el sub-árbol izquierdo.

3.      Atraviese el sub-árbol derecho.

·         Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:

1.      Atraviese el sub-árbol izquierdo.

2.      Visite la raíz.

3.      Atraviese el sub-árbol derecho.

·         Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:

1.      Atraviese el sub-árbol izquierdo.

2.      Atraviese el sub-árbol derecho.

3.      Visite la raíz.

En general, la diferencia entre preorden, inorden y postorden es cuándo se recorre la raíz. En los tres, se recorre primero el sub-árbol izquierdo y luego el derecho.

·         En preorden, la raíz se recorre antes que los recorridos de los subárboles izquierdo y derecho

·         En inorden, la raíz se recorre entre los recorridos de los árboles izquierdo y derecho, y

·         En postorden, la raíz se recorre después de los recorridos por el subárbol izquierdo y el derecho

Preorden (antes), inorden (en medio), postorden (después).

Ejemplo:

Ordenar de Menor a Mayor.

Menor ----> Izquierda.

Mayor ----> Derecha.

Ejemplo:

Recorrido del Árbol en Preorden.

Algoritmo Del Preorden.

Para recorrer un árbol no vacío en orden de profundidad-primero, hay que realizar las siguientes operaciones recursivamente en cada nodo:

1. Realice la operación pre-orden
2. Para i=1 a n-1 haga
   1. Visite al hijo[i], si existe
   2. Realice la operación in-orden
3. Visite al hijo[n], si existe
4. Realice la operación post-orden

donde n es el número de nodos hijos.

preorden(nodo)
  si nodo == nulo entonces retorna
  imprime nodo.valor
  preorden(nodo.izquierda)
  preorden(nodo.derecha)

Ejemplo:

Recorrido del Árbol en Inorden.

Algoritmo Del Inorden.

inorden(nodo)
  si nodo == nulo entonces retorna
  inorden(nodo.izquierda)
  imprime nodo.valor
  inorden(nodo.derecha)

Ejemplo:

Recorrido del Árbol en Postorden.

Algoritmo Del Postorden.

postorden(nodo)
  si nodo == nulo entonces retorna
  postorden(nodo.izquierda)
  postorden(nodo.derecha)
  imprime nodo.valor

Código de Ordenamiento Preorden, Inorden, Postorden:

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Derli Alexander
 */

public class ArbolBinario {
    class Nodo
    {
      int info;
      Nodo izq, der;
    }
    Nodo raiz;

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

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

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

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


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


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

    String getString(int llave) {
      return buscar(llave, raiz);
    }

    String buscar(int llave, Nodo nodo) {
      if (nodo==null)
       return("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
    }
}

import javax.swing.JOptionPane;

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Derli Alexander
 */
public class Arbol {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        ArbolBinario abo = new ArbolBinario (); 

      int valor;
        String Dato;
       
        System.out.println("Insertando los siguientes valores: ");
       
        Dato = JOptionPane.showInputDialog("Inserta el numero de nodos que desea ingresar");
        int n = Integer.parseInt(Dato);
       
        for(int i = 1; i <= n; i++ )
        {
            Dato = JOptionPane.showInputDialog("Dame el " + i + " valor para colocar en el Arbol");
            valor = Integer.parseInt(Dato);
            System.out.print(valor + " ");
            abo.insertar(valor);
        }
 
        System.out.println ("");
        System.out.println ("Impresion Preorden: ");
        abo.imprimirPreorden ();
        System.out.println ("Impresion Inorden: ");
        abo.imprimirInorden ();
        System.out.println ("Impresion Postorden: ");
        abo.imprimirPostorden ();
   
    }
   
}