Arboles Binarios

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 imprimirPost (Nodo reco)

{

if (reco != null)

{

imprimirPost (reco.izq);

imprimirPost (reco.der);

System.out.print(reco.info + " ");

}

}

Problema 2:

Confeccionar una clase que permita insertar un entero en un árbol binario ordenado verificando que no se encuentre previamente dicho número.

Desarrollar los siguientes métodos:

1 - Retornar la cantidad de nodos del árbol.

2 - Retornar la cantidad de nodos hoja del árbol.

3 - Imprimir en entre orden.

4 - Imprimir en entre orden junto al nivel donde se encuentra dicho nodo.

5 - Retornar la altura del árbol.

6 - Imprimir el mayor valor del árbol.

7 - Borrar el nodo menor del árbol.

public class ArbolBinarioOrdenado {

class Nodo

{

int info;

Nodo izq, der;

}

Nodo raiz;

int cant;

int altura;

public ArbolBinarioOrdenado() {

raiz=null;

}

public void insertar (int info) {

if (!existe(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;

}

}

}

public boolean existe(int info) {

Nodo reco=raiz;

while (reco!=null) {

if (info==reco.info)

return true;

else

if (info>reco.info)

...