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

Árboles de Expresiones

Árboles de Expresiones. 

Los árboles binarios se utilizan para almacenar expresiones aritméticas en memoria, esencialmente en compiladores de lenguajes de programación. Una expresión es una secuencia de tokens (componentes de léxicos que siguen unas reglas establecidas). Un token puede ser un operando o bien un operador.

Los paréntesis no se almacenan en el árbol pero están implicados en la forma del árbol, como puede apreciarse en la Figura 14:

La Figura 15 representa la expresión infija a * (b + c) + d junto a su árbol de expresión. El nombre de infija es debido a que los operadores se sitúan entre los operandos.

Un árbol de expresión es un árbol binario con las siguientes propiedades: 
1. Cada hoja es un operando. 
2. Los nodos raíz y los nodos internos son operadores. 
3. Los subárboles son subexpresiones cuyo nodo raíz es un operador.

Los árboles binarios se utilizan para representar expresiones en memoria, esencialmente en compiladores de lenguajes de programación. Se observa que los paréntesis de la expresión no aparecen en el árbol, pero están implicados en su forma, y esto resulta muy interesante para la evaluación de la expresión. 

Si se supone que todos los operadores tienen dos operandos, se puede representar una expresión mediante un árbol binario cuya raíz contiene un operador y cuyos subárboles izquierdo y derecho son los operandos izquierdo y derecho, respectivamente. Cada operando puede ser una letra (x, y, a, b, etc.) o una subexpresión representada como un subárbol. 

La Figura 16 muestra un árbol cuya raíz es el operador *, 
su subárbol izquierdo representa la subexpresión (x + y) 
y su subárbol derecho representa la subexpresión (a - b).

El nodo raíz del subárbol izquierdo contiene el operador (+) de la subexpresión izquierda y el nodo raíz del subárbol derecho contiene el operador (-) de la subexpresión derecha. Todos los operandos letras se almacenan en nodos hojas. 

Utilizando el razonamiento anterior, la expresión (x * (y - z)) + (a - b) con paréntesis alrededor de las subexpresiones, forma el árbol binario de la Figura 16.

Ejemplos:

                                                           Bibliografia:

http://artemisa.unicauca.edu.co/~cardila/ED2__Arboles_Binarios_02.pdf

Maquina de Turing