Arbol Binario con Iterador en JAVA
package estructuradatos.arbol.ab;
import estructuradatos.excepciones.*;
public interface InterArbolIter {
boolean esValido(); //--> True si estamos en una posicion valida
Object obtener() throws ElementoNoEncontrado; //--> Devuelve el elemento en la posicion actual
void primero(); //--> Coloca la posicion actual en el primero
void avanzar() throws ElementoNoEncontrado; //--> Avanza
}
package estructuradatos.arbol.ab;
import estructuradatos.excepciones.*;
abstract public class ArbolIter implements InterArbolIter {
public ArbolIter(ArbolBinario ab){
this.ab = ab;
this.actual = null;
}
abstract public void primero();
final public boolean esValido(){
return this.actual != null;
}
final public Object obtener() throws ElementoNoEncontrado {
if(this.actual == null)
throw new ElementoNoEncontrado("Error al Obtener");
return this.actual.elemento;
}
abstract public void avanzar() throws ElementoNoEncontrado;
protected ArbolBinario ab;
protected Nodo actual;
}
Calcular la altura en un Arbol Binario
private int altura(Nodo ab) {
if (ab == null)
return -1;
else
return (1 + Math.max(altura(ab.izq), altura(ab.der)));
}
public int altura() {
return altura(this.raiz);
}
Duplicar un Arbol Binario
public Nodo duplicar() {
Nodo raiz = new Nodo(elemento);
if (izq != null) //Si hay un arbol izquierdo
raiz.izq = izq.duplicar(); //Duplicarlo
if (der != null) //Si hay un arbol derecho
raiz.der = der.duplicar(); //Duplicarlo
return raiz; //Devolver el arbol resultante
}
Arbol ABB + Metodos
Clase Nodo
package arboles;
public class Nodo {
public Nodo izq, der;
public int elemento;
public Nodo(int elemento) {
this.elemento = elemento;
this.izq = this.der = null;
}
public Nodo insertarNodo(Nodo n, int elemento) {
if (n == null) {
return new Nodo(elemento);
} else if (elemento < n.elemento) {
n.izq = insertarNodo(n.izq, elemento);
} else if (elemento > n.elemento) {
n.der = insertarNodo(n.der, elemento);
}
return n;
}
}
Clase ABB
package arboles;
public class ABB {
Nodo raiz;
ABB() {
this.raiz = null;
}
public void insertar(int elemento) {
if (this.raiz == null) {
this.raiz = new Nodo(elemento);
} else {
raiz = raiz.insertarNodo(raiz, elemento);
}
}
private boolean miembro(Nodo abb, int elemento) {
if (abb == null) {
return false;
} else if (elemento < abb.elemento) {
return miembro(abb.izq, elemento);
} else if (elemento > abb.elemento) {
return miembro(abb.der, elemento);
} else {
return true;
}
}
private void preorden(Nodo abb) {
if (abb != null) {
System.out.print(" " + abb.elemento);
preorden(abb.izq);
preorden(abb.der);
}
}
private void inorden(Nodo abb) {
if (abb != null) {
inorden(abb.izq);
System.out.print(" " + abb.elemento);
inorden(abb.der);
}
}
private void postorden(Nodo abb) {
if (abb != null) {
postorden(abb.izq);
postorden(abb.der);
System.out.print(" " + abb.elemento);
}
}
private void mostrarArbolSangrado(Nodo abb, int nivel) {
if (abb != null) {
mostrarArbolSangrado(abb.der, nivel + 1);
System.out.println(" " + nivel + " " + abb.elemento);
mostrarArbolSangrado(abb.izq, nivel + 1);
}
}
private int nNiveles(Nodo abb) {
if(abb == null)
return -1;
else
return(1+Math.max(nNiveles(abb.izq), nNiveles(abb.der)));
}
private int nNodos(Nodo abb) {
if (abb == null) {
return 0;
} else {
return 1 + nNodos(abb.izq) + nNodos(abb.der);
}
}
private int sumaTotal(Nodo abb) {
if (abb == null) {
return 0;
} else {
return sumaTotal(abb.izq) + sumaTotal(abb.der) + abb.elemento;
}
}
public boolean miembro(int elemento) {
return miembro(this.raiz, elemento);
}
public void preorden() {
preorden(this.raiz);
}
public void inorden() {
inorden(this.raiz);
}
public void postorden() {
postorden(this.raiz);
}
public void mostrarArbolSangrado() {
mostrarArbolSangrado(this.raiz, 0);
}
public int nNiveles() {
return nNiveles(this.raiz);
}
public int nNodos() {
return nNodos(this.raiz);
}
public int sumaTotal() {
return sumaTotal(this.raiz);
}
}
Clase Main
package arboles;
public class Main {
public static void main(String[] args) {
ABB a = new ABB();
a.insertar(10);
a.insertar(5);
a.insertar(50);
a.insertar(3);
a.insertar(7);
a.insertar(40);
a.insertar(100);
a.insertar(-1);
a.insertar(6);
a.insertar(30);
a.insertar(45);
a.preorden();
System.out.println();
a.inorden();
System.out.println();
a.postorden();
System.out.println();
System.out.println("Nodos: "+a.nNodos());
System.out.println("Miembro:8: "+a.miembro(8));
System.out.println("Suma Total: "+a.sumaTotal());
System.out.println("nNiveles: "+a.nNiveles());
a.mostrarArbolSangrado();
}
}
Salida
10 5 3 -1 7 6 50 40 30 45 100
-1 3 5 6 7 10 30 40 45 50 100
-1 3 6 7 5 30 45 40 100 50 10
Nodos: 11
Miembro:8: false
Suma Total: 295
nNiveles: 3
2 100
1 50
3 45
2 40
3 30
0 10
2 7
3 6
1 5
2 3
3 -1
Arbol ABB o ABO
Clase Nodo
package arboles;
public class Nodo {
public Nodo izq, der;
public int elemento;
public Nodo(int elemento) {
this.elemento = elemento;
this.izq = this.der = null;
}
public Nodo insertarNodo(Nodo n, int elemento) {
if (n == null) {
return new Nodo(elemento);
} else if (elemento < n.elemento) {
n.izq = insertarNodo(n.izq, elemento);
} else if (elemento > n.elemento) {
n.der = insertarNodo(n.der, elemento);
}
return n;
}
}
Clase ABB
package arboles;
public class ABB {
private Nodo raiz;
ABB() {
this.raiz = null;
}
void insertar(int elemento) {
if (this.raiz == null) {
this.raiz = new Nodo(elemento);
} else {
raiz = raiz.insertarNodo(raiz, elemento);
}
}
private void preorden(Nodo abb) {
if (abb != null) {
System.out.print(" " + abb.elemento);
preorden(abb.izq);
preorden(abb.der);
}
}
private void inorden(Nodo abb) {
if (abb != null) {
inorden(abb.izq);
System.out.print(" " + abb.elemento);
inorden(abb.der);
}
}
private void postorden(Nodo abb) {
if (abb != null) {
postorden(abb.izq);
postorden(abb.der);
System.out.print(" " + abb.elemento);
}
}
public void preorden() {
preorden(this.raiz);
}
public void inorden() {
inorden(this.raiz);
}
public void postorden() {
postorden(this.raiz);
}
}
Clase Main
package arboles;
public class Main {
public static void main(String[] args) {
ABB a = new ABB();
a.insertar(10);
a.insertar(5);
a.insertar(50);
a.insertar(3);
a.insertar(7);
a.insertar(40);
a.insertar(100);
a.insertar(-1);
a.insertar(6);
a.insertar(30);
a.insertar(45);
a.preorden();
System.out.print("\n");
a.inorden();
System.out.print("\n");
a.postorden();
}
}
Salida
10 5 3 -1 7 6 50 40 30 45 100
-1 3 5 6 7 10 30 40 45 50 100
-1 3 6 7 5 30 45 40 100 50 10