martes, 3 de agosto de 2010

Recorrido en Árboles Binarios [Java - PreOrden - InOrden - PostOrden]

5 comentarios
Recorrido en Árboles Binarios [Java - PreOrden - InOrden - PostOrden]
Una de las operaciones mas importantes a realizar en un árbol binario es el recorrido de los mismos. Recorrer significa visitar los nodos del árbol en forma sistemática, de tal manera que todos los nodos del mismo sean visitados una sola vez. Existen tres formas diferentes de efectuar el recorrido y todas ellas de naturaleza recursiva, éstas son:


a)Recorrido en Preorden
•Visitar la Raiz.
•Recorrer el subárbol izquierdo.
•Recorrer el subárbol derecho.

b)Recorrido en Inorden
•Recorrer el subárbol izquierdo
•Visitar la raíz
•Recorrer el subárbol derecho

c)Recorrido en Postorden
•Recorrer el subárbol izquierdo
•Recorrer el subárbol derecho
•Visitar la raíz

El recorrido preorden produce la notación polaca prefija, el recorrido inorden la
notación convencional y el recorrido postorden produce la notación polaca postfija.
ejemplo:
Recorrido en Árboles Binarios [Java - PreOrden - InOrden - PostOrden]









PREORDEN: A B D E C F G
INORDEN: D B E A F C G
POSTORDEN: D E B F G C A

Aquí te muestro el código Implementado en Java para que te sirva de referencia sobre el tema incluso también e colocado como realizar la búsqueda en un árbol binario. ¡¡¡Saludos¡¡¡¡

package Arbol;

import javax.swing.JOptionPane;

/**
 *
 * @author ZAVALETA CHAVEZ, ENRIQUE
 */
public class nodo {
public String info;
public int infor;
nodo izq;
nodo der;

public void cargarNodo(nodo n)
{
String numero,resp;
nodo otro;

numero=JOptionPane.showInputDialog(null,"Ingrese Valor:");
n.info=numero;

resp=JOptionPane.showInputDialog(null,"Existe Nodo por la izquierda: s/n");

if(resp.charAt(0) =='s')
{
otro=new nodo();
n.izq=otro;
cargarNodo(n.izq);
}
else
{
n.izq=null;
}



resp=JOptionPane.showInputDialog(null,"Existe Nodo por la derecha: s/n");

if(resp.charAt(0) =='s')
{
otro=new nodo();
n.der=otro;
cargarNodo(n.der);
}
else
{
n.der=null;
}
}
public void recorridoEnPreorden(nodo n)
{
String cad="";
if(n!=null)
{
JOptionPane.showMessageDialog(null,"Elementos:"+n.info,"Resultados",JOptionPane.INFORMATION_MESSAGE);
recorridoEnPreorden(n.izq);
recorridoEnPreorden(n.der);
}
}
public void recorridoInOrden(nodo n)
{
if(n!=null)
{
recorridoInOrden(n.izq);
JOptionPane.showMessageDialog(null,"Elementos:"+n.info,"Resultados",JOptionPane.INFORMATION_MESSAGE);
recorridoInOrden(n.der);
}
}
public void recorridoPostOrden(nodo n)
{
if(n!=null)
{
recorridoPostOrden(n.izq);
recorridoPostOrden(n.izq);
JOptionPane.showMessageDialog(null,"Elementos:"+n.info,"Resultados",JOptionPane.INFORMATION_MESSAGE);
}
}
public void busqueda(nodo n,int info)
{
if(info<n.infor)
{
if(n.izq==null)
{
JOptionPane.showMessageDialog(null,"El nodo no se encuentar en el arbol");
}
else
busqueda(n.izq,infor);
}
else
{
if(infor>n.infor)
{
if(n.der==null)
{
JOptionPane.showMessageDialog(null,"El nodo no se encuentar en el arbol");
}
else
busqueda(n.der,infor);
}
else
JOptionPane.showMessageDialog(null,"El nodo se encuentar en el arbol");
}
}
public static void main(String arg[])
{
nodo n =new nodo();
nodo a =new nodo();
n.cargarNodo(a);
n.recorridoEnPreorden(a);
}

}