El siguiente ejemplo presenta una estructura de datos conocida como árboles, específicamente este ejemplo trata de emular las instancias finales de un campeonato de fútbol.
Como descripción tendremos tres niveles, en el primer nivel se encontrará el equipo campeón que representa la raiz del árbol, luego en el siguiente nivel, se encontrará 2 equipos de fútbol que representan los finalistas, finalmente en esta estructura de datos por cada nodo del nivel 2(finalistas) tendrán 2 equipos que representan los equipos que participaron en las semifinales.
Se presentan las siguientes clases para resolver este ejercicio de estructura de datos utilizando árboles.
1. Clase Equipo(Nombre, goles)
2. Clase NodoArbol
3. Clase Arbol
4. Clase NodoCola
5. Clase Cola.
6. Clase Principal.
Vamos a crear la clase Equipo la cual va contener 2 atributos: Nombre y Goles.
package pryarbolequipo;
import java.util.Random;
public class Equipo {
private String nombre;
private int goles;
public Equipo(String nombre,boolean caso) {
this.nombre = nombre;
if(caso)
goles=generarGoles();
else
goles=-1;
}
public int generarGoles() {
Random aleatorio=new Random();
int gol=aleatorio.nextInt();
if(gol<0)
gol=gol*(-1);
gol=gol%8;
goles=gol;
return goles;
}
public String getNombre() {
return nombre;
}
public int getGoles() {
return goles;
}
@Override
public String toString() {
if(goles==-1)
return "Equipo Campeon: "+nombre;
else
return "Equipo "+nombre+" goles=" + goles;
}
}
La clase NodoArbol va contener 3 atributos: un Objeto Equipo y dos objetos de la clase NodoArbol, pues es un árbol binario que tiene una referencia hacia el nodo izquierdo y otro para el lado derecho.
package pryarbolequipo;
/**
*
* @author Paulo Guerra
*/
public class NodoArbol {
private Equipo datos;
private NodoArbol iz;
private NodoArbol der;
public NodoArbol(Equipo datos) {
this.datos = datos;
iz = der = null;
}
public NodoArbol(Equipo datos, NodoArbol iz, NodoArbol der) {
this.datos = datos;
this.iz = iz;
this.der = der;
}
public Equipo getDatos() {
return datos;
}
public void setDatos(Equipo datos) {
this.datos = datos;
}
public NodoArbol getIz() {
return iz;
}
public void setIz(NodoArbol iz) {
this.iz = iz;
}
public NodoArbol getDer() {
return der;
}
public void setDer(NodoArbol der) {
this.der = der;
}
}
La clase Arbol que es la estructura de datos principal de nuestro ejercicio, contiene como atributo a la raiz, la cual es un objeto de tipo NodoArbol creado anteriormente. Además posee los métodos necesarios para unir con otros 2 nodos para ir formando el árbol de abajo hacia arriba.
package pryarbolequipo;
/**
*
* @author Paulo Guerra
*/
public class Arbol {
private NodoArbol raiz;
public Arbol() {
raiz = null;
}
public Arbol(Equipo datos) {
raiz = new NodoArbol(datos);
}
public NodoArbol getRaiz() {
return raiz;
}
public void unir(Equipo datos, NodoArbol iz, NodoArbol der) {
if (iz == der) {
System.out.println("No se puede unir");
return;
}
raiz = new NodoArbol(datos, iz, der);
}
public void recorridoAnchura() {
if (raiz != null) {
Cola cola = new Cola();
cola.encolar(raiz);
Cola colaAux = new Cola();
while (!cola.esVacio()) {
NodoArbol aux = cola.desencolar().getNodoDatos();
if (aux.getIz() != null) {
cola.encolar(aux.getIz());
}
if (aux.getDer() != null) {
cola.encolar(aux.getDer());
}
colaAux.encolar(aux);
}
colaAux.imprimir();
}
}
}
Al implementar el recorrido por Anchura de un árbol necesitamos implementar la estructura de datos Cola por lo que vamos a necesitar crear los Nodos de la Cola los mismos que van a contener como datos, nodos de la clase Árbol(NodoArbol).
package pryarbolequipo;
/**
*
* @author Paulo Guerra
*/
public class NodoCola {
private NodoArbol nodoDatos;
private NodoCola siguiente;
public NodoCola(NodoArbol nodoDatos, NodoCola siguiente) {
this.nodoDatos = nodoDatos;
this.siguiente = siguiente;
}
public NodoArbol getNodoDatos() {
return nodoDatos;
}
public void setNodoDatos(NodoArbol nodoDatos) {
this.nodoDatos = nodoDatos;
}
public NodoCola getSiguiente() {
return siguiente;
}
public void setSiguiente(NodoCola siguiente) {
this.siguiente = siguiente;
}
}
La Clase Cola implementa cuatro métodos importantes.
1. encolar
2. desencolar
3. verificar si está Vacía la Cola
4. imprimir toda la Cola.
package pryarbolequipo;
/**
*
* @author cisco
*/
public class Cola {
private NodoCola inicio;
private NodoCola fin;
public Cola() {
inicio = fin = null;
}
public void encolar(NodoArbol datos) {
NodoCola nuevo = new NodoCola(datos, null);
if (inicio == fin && inicio == null) {
inicio = fin = nuevo;
} else {
fin.setSiguiente(nuevo);
fin = nuevo;
}
}
public NodoCola desencolar() {
NodoCola aux = inicio;
inicio = inicio.getSiguiente();
if (inicio == null) {
fin = null;
}
return aux;
}
public boolean esVacio() {
return inicio == null;
}
public void imprimir() {
NodoCola aux = inicio;
while (aux != null) {
System.out.println(aux.getNodoDatos().getDatos().toString());
aux = aux.getSiguiente();
}
}
}
Finalmente la invocación de la clase principal será como se muestra a continuación:
package pryarbolequipo;
/**
*
* @author Paulo Guerra
*/
public class Principal {
/**
* @param args the command line arguments
*/
public static Equipo ganador(Equipo eA, Equipo eB){
while(eA.getGoles()==eB.getGoles()){
eA.generarGoles();
eB.generarGoles();
}
if(eA.getGoles()>eB.getGoles())
return new Equipo(eA.getNombre(),false);
else
return new Equipo(eB.getNombre(), false);
}
public static void main(String[] args) {
// TODO code application logic here
Arbol eq1=new Arbol(new Equipo("Ecuador", true));
Arbol eq2=new Arbol(new Equipo("Colombia", true));
Arbol sf1=new Arbol();
sf1.unir(ganador(eq1.getRaiz().getDatos(),eq2.getRaiz().getDatos()),
eq1.getRaiz(),eq2.getRaiz());
Arbol eq3=new Arbol(new Equipo("Argentina", true));
Arbol eq4=new Arbol(new Equipo("Brasil", true));
Arbol sf2=new Arbol();
sf2.unir(ganador(eq3.getRaiz().getDatos(),eq4.getRaiz().getDatos()),
eq3.getRaiz(),eq4.getRaiz());
Arbol campeon=new Arbol();
campeon.unir(ganador(sf1.getRaiz().getDatos(), sf2.getRaiz().getDatos()),
sf1.getRaiz(),sf2.getRaiz());
campeon.recorridoAnchura();
}
}
Ejecución
run:
Equipo Campeon: Argentina
Equipo Ecuador goles=0
Equipo Argentina goles=7
Equipo Ecuador goles=5
Equipo Colombia goles=0
Equipo Argentina goles=2
Equipo Brasil goles=0
BUILD SUCCESSFUL (total time: 0 seconds)
Para interpretar el resultado de la estructura de datos árbol, se explica a continuación:
El Equipo que está en la raíz es el campeón (Argentina). La final la jugó frente a Ecuador.
Ecuador clasificó ganando el encuentro frente a Colombia y Argentina clasificó ganando el encuentro frente a Brasil.
