Arboles Binarios
Enviado por scooter • 31 de Enero de 2014 • 5.169 Palabras (21 Páginas) • 259 Visitas
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();
}
public static void main (String [] ar)
{
ArbolBinarioOrdenado abo = new ArbolBinarioOrdenado ();
abo.insertar (100);
abo.insertar (50);
abo.insertar (25);
abo.insertar (75);
abo.insertar (150);
System.out.println ("Impresion preorden: ");
abo.imprimirPre ();
System.out.println ("Impresion entreorden: ");
abo.imprimirEntre ();
System.out.println ("Impresion postorden: ");
abo.imprimirPost ();
}
}
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;
}
}
Creamos un nodo y disponemos los punteros izq y der a null, guardamos la información que llega al método en el nodo.
Si el árbol está vacío, apuntamos raíz al nodo creado; en caso de no estar vacío, dentro de una estructura repetitiva vamos comparando info con la información del nodo, si info es mayor a la del nodo descendemos por el subárbol derecho en caso contrario descendemos por el subárbol izquierdo.
Cuando se encuentra un subárbol vacío insertar el nodo en dicho subárbol. Para esto llevamos un puntero anterior dentro del while.
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();
}
El método imprimirPre(), es decir el no recursivo se encarga de llamar al método recursivo pasando la dirección del nodo raiz.
El método recursivo void imprimirPre (Nodo reco) lo primero que verifica con un if si reco está apuntando a un nodo (esto es verdad si reco es distinto a null), en caso afirmativo ingresa al bloque del if y realiza:
- Visitar la raiz.
- Recorrer el subárbol izquierdo en pre-orden.
- Recorrer el subárbol derecho en pre-orden.
La visita en este caso es la impresión de la información del nodo y los recorridos son las llamadas recursivas pasando las direcciones de los subárboles izquierdo y derecho.
Los algoritmos de los recorridos en entreorden y postorden son similares. La diferencia es que la visita la realizamos entre las llamadas recursivas en el recorrido en entre orden:
private void imprimirEntre (Nodo reco)
{
if (reco != null)
{
imprimirEntre (reco.izq);
System.out.print(reco.info + " ");
imprimirEntre (reco.der);
}
}
y por último en el recorrido en postorden la visita la realizamos luego de las dos llamadas recursivas:
private void
...