package EDNL;
import EDL.*;
/**
* Arbol Binario.
*
* @author MaTU
* @version 2.0
*/
public class ArbolBin<T> implements ArbolInter<T>
{
protected T raiz;
protected ArbolBin<T> izq,der;
public ArbolBin(){
raiz = null;
izq = der = null;
}
public ArbolBin(T r){
colocar(r);
}
/**
* Verifica si esta vacio
*/
public boolean vacio(){
return raiz == null && izq == null && der == null;
}
/**
* Inserta un dato raiz
*/
protected void colocar(T d){
raiz = d;
izq = new ArbolBin<T>();
der = new ArbolBin<T>();
}
/**
* Verifica si es Hoja
*/
public boolean esHoja(){
return !vacio() && izq.vacio() && der.vacio();
}
/**
* Agrega un dato al arbol
*/
public void add(T d){
Cola<ArbolBin<T>> cola = new Cola<ArbolBin<T>>();
cola.encolar(this);
add(d,cola);
}
private void add(T d, Cola<ArbolBin<T>> cola){
ArbolBin<T> arbol = cola.decolar();
if(arbol.vacio()) arbol.colocar(d);
else{
cola.encolar(arbol.izq);
cola.encolar(arbol.der);
add(d,cola);
}
}
/**
* Busca un dato en el arbol en profundidad
*/
public T buscar(T d){
T res;
if(vacio()) res = null;
else if(d.equals(raiz)) res = raiz;
else{
res = izq.buscar(d);
if(res == null)
res = der.buscar(d);
}
return res;
}
/**
* Verifica si existe un nodo en el arbol
*/
public boolean existe(T d){
boolean res;
if(vacio()) res = false;
else if(d.equals(raiz)) res = true;
else res = izq.existe(d)||der.existe(d);
return res;
}
/**
* La busqueda por Amplitud
*/
public T buscarAmp(T d){
Cola<ArbolBin<T>> cola = new Cola<ArbolBin<T>>();
cola.encolar(this);
return buscarAmp(d,cola);
}
private T buscarAmp(T d,Cola<ArbolBin<T>> cola){
T res;
if(cola.vacia()) res = null;
else{
ArbolBin<T> arbol = cola.decolar();
if(arbol.vacio())
res = buscarAmp(d,cola);
else{
T raiz = arbol.raiz;
if(raiz.equals(d)) res = raiz;
else{
cola.encolar(arbol.izq);
cola.encolar(arbol.der);
res = buscarAmp(d,cola);
}
}
}
return res;
}
/**
* Elimina un dato del arbol
*/
public T eliminar(T d){
T res=null;
if(!vacio())
if(d.equals(raiz)){
res = raiz;
int estado = raizEstado();
switch(estado){
case 0: raiz = null;
izq = der = null;
break;
case 1: raiz = izq.raiz;
der = izq.der;
izq = izq.izq;
break;
case 2: raiz = der.raiz;
izq = der.izq;
der = der.der;
break;
case 3: ArbolBin<T> arbol;
arbol = izq.desDer();
raiz = arbol.raiz;
arbol.eliminar(raiz);
}
}else{
res = izq.eliminar(d);
if(res==null)
res = der.eliminar(d);
}
return res;
}
/**
* Estado de la raiz
*/
private int raizEstado(){
int res;
if(izq.vacio()){
if(der.vacio())
res = 0;
else
res = 2;
}else if(der.vacio())
res = 1;
else
res = 3;
return res;
}
/**
* Retorna la raiz mas a la derecha del arbol
*/
public ArbolBin<T> desDer(){
ArbolBin<T> res;
if(der.vacio()) res = this;
else res = der.desDer();
return res;
}
/**
* La profundidad del arbol
*/
public int profundidad(){
int res;
if(vacio()) res = 0;
else res = 1 + Math.max(izq.profundidad(),der.profundidad());
return res;
}
/**
* Añade hojas al arbol usando Lista de simple enlace
*/
public void añadirHojas(ListaSE<T> lista){
if(vacio()) ;
else if(esHoja()) lista.insertar(raiz);
else{
izq.añadirHojas(lista);
der.añadirHojas(lista);
}
}
/**
* Añade Hojas por un indice especifico
*/
public void añadirNodos(ListaSE<T> lista, int k){
if(vacio()) ;
else if(k==0) lista.insertar(raiz);
else{
izq.añadirNodos(lista,k-1);
der.añadirNodos(lista,k-1);
}
}
/**
* Recorrido en preorden
*/
public void preorden(ListaSE<T> lista){
if(!vacio()){
lista.insertar(raiz);
izq.preorden(lista);
der.preorden(lista);
}
}
/**
* Recorrido en inorden
*/
public void inorden(ListaSE<T> lista){
if(!vacio()){
izq.inorden(lista);
lista.insertar(raiz);
der.inorden(lista);
}
}
/**
* Recorrido en posorden
*/
public void posorden(ListaSE<T> lista){
if(!vacio()){
izq.posorden(lista);
der.posorden(lista);
lista.insertar(raiz);
}
}
/**
* Obtiene la raiz del arbol
*/
public T getRaiz(){
return raiz;
}
/**
* Retorna el hijo derecho
*/
public ArbolBin<T> getDer(){
return der;
}
/**
* Retorna el hijo izquierdo
*/
public ArbolBin<T> getIzq(){
return izq;
}
/**
* Modifica la raiz
*/
public void setRaiz(T r){
raiz = r;
}
/**
* Modifica el hijo derecho
*/
public void setDer(ArbolBin<T> d){
der = d;
}
/**
* Modifica el hijo izquierdo
*/
public void setIzq(ArbolBin<T> i){
izq = i;
}
/**
* Retorna los nodos de un nivel especifico
*/
public void nodosNivel(int nivel){
if(!vacio())
if(nivel==0){
System.out.print(raiz+" ");
System.out.println();
}else{
izq.nodosNivel(nivel-1);
der.nodosNivel(nivel-1);
}
}
/**
* Encola todos los nodos de un nivel a la cola
*/
public Cola<T> nodosNivelACola(int nivel,ArbolBin<T> arbol){
Cola<T> cola = new Cola<T>();
return nodosNivelACola(nivel,arbol,cola);
}
private Cola<T> nodosNivelACola(int nivel,ArbolBin<T> arbol,Cola<T> cola){
if(!vacio())
if(nivel==0)
cola.encolar(raiz);
else{
izq.nodosNivelACola(nivel-1,arbol,cola);
der.nodosNivelACola(nivel-1,arbol,cola);
}
return cola;
}
/**
* To String
*/
public String toString(){
String res;
if(vacio()) res ="";
else{
res = "\n"+izq.toString();
res += "\n"+der.toString();
res = res.replaceAll("\n", "\n\t");
res = raiz.toString()+res;
}
return res;
}
/**
* Imprime la ruta de un dato del arbol
*/
public void ruta(ArbolBin<T> arbol,T d){
if(!vacio())
if(existe(d)){
T dato = raiz;
if(d.equals(dato))
System.out.println(dato);
else{
System.out.println(raiz);
der.ruta(arbol,d);
izq.ruta(arbol,d);
}
}
}
/**
* Encola la ruta de un dato
*/
public Cola<T> encolarRuta(ArbolBin<T> arbol,T d){
Cola<T> cola = new Cola<T>();
return encolarRuta(arbol,d,cola);
}
private Cola<T> encolarRuta(ArbolBin<T> arbol,T d,Cola<T> cola){
if(!vacio())
if(existe(d)){
T dato = raiz;
if(d.equals(dato))
cola.encolar(dato);
else{
cola.encolar(raiz);
der.encolarRuta(arbol,d,cola);
izq.encolarRuta(arbol,d,cola);
}
}
return cola;
}
/**
* Retorna el primer nodop Hoja
*/
public T primerNodoHoja(ArbolBin<T> arbol){
Cola<ArbolBin<T>> cola = new Cola<ArbolBin<T>>();
cola.encolar(this);
return primerNodoHoja(arbol,cola);
}
private T primerNodoHoja(ArbolBin<T> arbol,Cola<ArbolBin<T>> cola){
T res=null;
if(!cola.vacia()){
ArbolBin<T> arb = cola.decolar();
if(arb.vacio())
primerNodoHoja(arbol,cola);
else if(arb.esHoja()) res = arb.raiz;
else{
cola.encolar(arb.izq);
cola.encolar(arb.der);
res = primerNodoHoja(arbol,cola);
}
}
return res;
}
/**
* Retorna el nodo hoja de cierto nivel
*/
public T nodoHojaN(ArbolBin<T> arbol,int nivel){
T res=null;
if(!vacio())
if(nivel==0){
if(esHoja()) res = raiz;
else res = null;
}else{
der.nodoHojaN(arbol,nivel-1);
izq.nodoHojaN(arbol,nivel-1);
}
return res;
}
/**
* Retorna la cantidad de nodos hoja de un arbol
*/
private int nodosHoja(ArbolBin<T> arbol){
int res;
if(vacio()) res = 0;
else if(esHoja()) res = 1;
else res = nodosHoja(arbol.getIzq()) + nodosHoja(arbol.getDer());
return res;
}
}