Estructura de Árbol Binario en Java: Implementación con Nodos, Recorridos y Búsqueda
Estructura base
++++++++++++++++++++++++++++++++++++
Árbol binario
Nombre del package: cl.duoc.ded.tree;
Clase Nodo
----------------------------
package cl.duoc.ded.tree;
public class Nodo {
private int valor;
private Nodo padre;
private Nodo hojaIzquierda;
private Nodo hojaDerecha;
public Nodo (int valor) {
this.valor = valor;
}
public int getValor() {
return valor;
}
public void setValor(int valor) {
this.valor = valor;
}
public Nodo getPadre() {
return padre;
}
public void setPadre(Nodo padre) {
this.padre = padre;
}
public Nodo getHojaIzquierda() {
return hojaIzquierda;
}
public void setHojaIzquierda(Nodo hojaIzquierda) {
this.hojaIzquierda = hojaIzquierda;
}
public Nodo getHojaDerecha() {
return hojaDerecha;
}
public void setHojaDerecha(Nodo hojaDerecha) {
this.hojaDerecha = hojaDerecha;
}
}
Clase Arbol
------------------------------
package cl.duoc.ded.tree;
import cl.duoc.ded.stackqueue.*;
public class Arbol {
private Nodo raiz;
public Arbol (int valor) {
this.raiz = new Nodo (valor);
}
public Arbol (Nodo raiz) {
this.raiz = raiz;
}
public Nodo getRaiz() {
return raiz;
}
public void setRaiz(Nodo raiz) {
this.raiz = raiz;
}
private void addNodo (Nodo nodo, Nodo raiz) {
if (raiz == null) {
this.setRaiz(nodo);
}
else {
if (nodo.getValor() <= raiz.getValor()) {
if (raiz.getHojaIzquierda() == null) {
raiz.setHojaIzquierda(nodo);
nodo.setPadre(raiz);
}
else {
addNodo (nodo, raiz.getHojaIzquierda());
}
}
else {
if (raiz.getHojaDerecha() == null) {
raiz.setHojaDerecha(nodo);
nodo.setPadre(raiz);
}
else {
addNodo (nodo, raiz.getHojaDerecha());
}
}
}
}
public void addNodo (Nodo nodo) {
this.addNodo(nodo, this.raiz);
}
public void recorridoPorNivelesIter (Nodo raiz) {
if (raiz != null) {
Cola p = new Cola ();
p.enqueue(new cl.duoc.ded.stackqueue.Nodo (raiz));
Nodo nodoTmp = null;
while (p.getCantidad() > 0) {
nodoTmp = (Nodo)p.dequeue().getValor();
System.out.print (nodoTmp.getValor() + " ");
if (nodoTmp.getHojaIzquierda() != null)
p.enqueue(new cl.duoc.ded.stackqueue.Nodo (nodoTmp.getHojaIzquierda()));
if (nodoTmp.getHojaDerecha() != null)
p.enqueue(new cl.duoc.ded.stackqueue.Nodo (nodoTmp.getHojaDerecha()));
}
}
}
public void recorridoPreordenIter (Nodo raiz) {
if (raiz != null) {
Pila p = new Pila ();
p.push(new cl.duoc.ded.stackqueue.Nodo (raiz));
Nodo nodoTmp = null;
while (p.getCantidad() > 0) {
nodoTmp = (Nodo)p.pop().getValor();
System.out.print (nodoTmp.getValor() + " ");
if (nodoTmp.getHojaDerecha() != null)
p.push(new cl.duoc.ded.stackqueue.Nodo (nodoTmp.getHojaDerecha()));
if (nodoTmp.getHojaIzquierda() != null)
p.push(new cl.duoc.ded.stackqueue.Nodo (nodoTmp.getHojaIzquierda()));
}
}
}
//(raiz, izquierdo, derecho)
private void recorridoPreorden (Nodo nodo) {
if (nodo == null) {
return;
}
System.out.print (nodo.getValor() + " ");
recorridoPreorden (nodo.getHojaIzquierda());
recorridoPreorden (nodo.getHojaDerecha());
}
//(izquierdo, raiz, derecho)
private void recorridoInorden (Nodo nodo) {
if (nodo == null) {
return;
}
recorridoInorden (nodo.getHojaIzquierda());
System.out.print (nodo.getValor() + " ");
recorridoInorden (nodo.getHojaDerecha());
}
//(izquierdo, derecho, raiz)
private void recorridoPostorden (Nodo nodo) {
if (nodo == null) {
return;
}
recorridoPostorden (nodo.getHojaIzquierda());
recorridoPostorden (nodo.getHojaDerecha());
System.out.print (nodo.getValor() + " ");
}
public void recorridoPreorden () {
this.recorridoPreorden(this.raiz);
}
public void recorridoInorden () {
this.recorridoInorden(this.raiz);
}
public void recorridoPostorden () {
this.recorridoPostorden(this.raiz);
}
public Nodo buscarNodo (int valor, Nodo nodo) {
if (nodo == null) {
return null;
}
if (nodo.getValor() == valor) {
return nodo;
}
else if (valor <= nodo.getValor()) {
return buscarNodo (valor, nodo.getHojaIzquierda());
}
else if (valor > nodo.getValor()) {
return buscarNodo (valor, nodo.getHojaDerecha());
}
else {
return null;
}
}
public Nodo buscarNodoIter (int valor, Nodo raiz) {
Nodo nodoTmp = null;
if (raiz != null) {
nodoTmp = raiz;
while (nodoTmp != null && valor != nodoTmp.getValor()) {
if (valor <= nodoTmp.getValor()) {
nodoTmp = nodoTmp.getHojaIzquierda();
}
else {
nodoTmp = nodoTmp.getHojaDerecha();
}
}
}
return nodoTmp;
}
}
Clase Main
------------------------------
public class Main {
public static void main (String[] args) {
Arbol tree1 = new Arbol(10);
tree1.addNodo (new Nodo (1));
tree1.addNodo(new Nodo (20));
tree1.addNodo(new Nodo (8));
tree1.addNodo(new Nodo (11));
tree1.addNodo(new Nodo (25));
tree1.addNodo(new Nodo (-1));
tree1.addNodo(new Nodo (9));
//tree1.obtenerCodigoHuf(tree1, valor)
System.out.println ("Preorden Recursivo");
tree1.recorridoPreorden();
System.out.println();
System.out.println ("\nPreorden Iter");
tree1.recorridoPreordenIter(tree1.getRaiz());
System.out.println("\n");
System.out.println ("Por niveles Iterativo");
tree1.recorridoPorNivelesIter(tree1.getRaiz());
System.out.println("\n");
Nodo n = tree1.buscarNodo(20, tree1.getRaiz());
if (n != null) {
System.out.println ("Valor encontrado: " + n.getValor());
System.out.println ("Eliminar el nodo con valor 20");
tree1.removerNodo(n);
tree1.recorridoPreorden();
System.out.println();
}
else
System.out.println ("Nodo NO encontrado");
System.out.println ("\nBuscando Iter 25");
Nodo n2 = tree1.buscarNodoIter(25, tree1.getRaiz());
if (n2 != null)
System.out.println ("Valor encontrado: " + n2.getValor());
else
System.out.println ("Nodo NO encontrado");
/*
System.out.println ("Eliminar el nodo con valor 8");
tree1.removerNodo(new Nodo (8));
System.out.println ("nodo eliminado list");
tree1.recorridoPreorden();
*/
System.out.println ();
System.out.println ("Inorden Recursivo");
tree1.recorridoInorden();
System.out.println ();
System.out.println ("Postorden Recursivo");
tree1.recorridoPostorden();
System.out.println ();
}
}
Pila y cola
Nombre del package: cl.duoc.ded.stackqueue;
Clase Nodo
-------------------------
public class Nodo {
private Object valor;
private Nodo siguiente;
public Nodo (Object valor, Nodo siguiente) {
this.valor = valor;
this.siguiente = siguiente;
}
public Nodo (Object valor) {
this.valor = valor;
this.siguiente = null;
}
public Object getValor() {
return valor;
}
public void setValor(Object valor) {
this.valor = valor;
}
public Nodo getSiguiente() {
return siguiente;
}
public void setSiguiente(Nodo siguiente) {
this.siguiente = siguiente;
}
}
Clase Cola
-----------------------
public class Cola {
private Nodo nodoInicio;
private int cantidad;
public Cola () {
this.nodoInicio = null;
this.cantidad = 0;
}
public void enqueue (Nodo nodo) {
if (this.cantidad == 0) {
this.nodoInicio = nodo;
nodo.setSiguiente (null);
}
else {
nodo.setSiguiente (this.nodoInicio);
this.nodoInicio = nodo;
}
this.cantidad++;
}
public Nodo dequeue () {
Nodo nodoResultado = null;
if (this.cantidad > 0) {
if (this.cantidad == 1) {
nodoResultado = this.nodoInicio;
this.nodoInicio = null;
}
else {
Nodo tmpActual = this.nodoInicio;
Nodo tmpSiguiente = tmpActual.getSiguiente ();
while (tmpSiguiente.getSiguiente() != null) {
tmpActual = tmpSiguiente;
tmpSiguiente = tmpActual.getSiguiente ();
}
nodoResultado = tmpSiguiente;
tmpActual.setSiguiente (null);
}
this.cantidad--;
}
return nodoResultado ;
}
public Nodo getNodoInicio() {
return nodoInicio;
}
public void setNodoInicio(Nodo nodoInicio) {
this.nodoInicio = nodoInicio;
}
public int getCantidad() {
return cantidad;
}
public void setCantidad(int cantidad) {
this.cantidad = cantidad;
}
}
Clase Pila
---------------------------
public class Pila {
private Nodo nodoInicio;
private int cantidad;
public Pila () {
this.nodoInicio = null;
this.cantidad = 0;
}
public void push (int valor) {
Nodo nodo = new Nodo (valor, null);
if (this.cantidad == 0) {
this.nodoInicio = nodo;
nodo.setSiguiente (null);
}
else {
nodo.setSiguiente (this.nodoInicio);
this.nodoInicio = nodo;
}
this.cantidad++;
}
public void push (Nodo nodo) {
if (this.cantidad == 0) {
this.nodoInicio = nodo;
nodo.setSiguiente (null);
}
else {
nodo.setSiguiente (this.nodoInicio);
this.nodoInicio = nodo;
}
this.cantidad++;
}
public Nodo pop () {
Nodo nodoResultado = null;
if (this.cantidad > 0) {
nodoResultado = this.nodoInicio;
this.nodoInicio = this.nodoInicio.getSiguiente ();
this.cantidad--;
}
return nodoResultado ;
}
public Nodo getNodoInicio() {
return nodoInicio;
}
public void setNodoInicio(Nodo nodoInicio) {
this.nodoInicio = nodoInicio;
}
public int getCantidad() {
return cantidad;
}
public void setCantidad(int cantidad) {
this.cantidad = cantidad;
}
}