domingo, 4 de enero de 2015

Clases en Java (Árbol Binario)


A   continuación   se   muestra   la   implementación   de   un arbol binario que hace uso de un  Nodo   Binario doble enlace genérico, esto para poder parametrizar el tipo de dato.

package NegocioArbol; import java.util.StringTokenizer; /** * @author Angel Céspedes Quiroz <acq1305@gmail.com> * @web www.nubeando.com * 04-01-2015 */ public class ArbolB { private NodoB Raiz; //Constructor public ArbolB() { Raiz = null; } private boolean Hoja(NodoB T) { return T.getHD() == null && T.getHI() == null; } //Revisar private NodoB SucInOrden(NodoB T) { NodoB Ant = null; T = T.getHD(); while (T != null) { Ant = T; T = T.getHI(); } return Ant; } //Insercion de un elemento en el arbol public void Insertar(int Elem) { if (Raiz == null) { Raiz = new NodoB(Elem); } else { Raiz.Insertar(Elem); } } public void Recargar(String Arbol) { StringTokenizer st = new StringTokenizer(Arbol, ","); while (st.hasMoreTokens()) { int data = Integer.valueOf(st.nextToken()); Insertar(data); } } //Inorden Recursivo del arbol public void InOrden1(NodoB T) { if (T == null) { return; } else { InOrden1(T.getHI()); System.out.print(T.getDato() + " "); InOrden1(T.getHD()); } } public void InOrden() { InOrden1(Raiz); } public void InOrdenNR() { NodoB Ant = null, P = Raiz; while (P != null) { Ant = P; P = P.getHI(); } while (Ant != null) { int ele = Ant.getDato(); System.out.print(ele + ","); Ant = SucInOrden(Ant); } } //Preorden Recursivo del arbol public void PreOrden1(NodoB T) { if (T == null) { return; } else { System.out.print(T.getDato() + " "); PreOrden1(T.getHI()); PreOrden1(T.getHD()); } } public void PreOrden() { PreOrden1(Raiz); } //PostOrden recursivo del arbol public void postOrden1(NodoB T) { if (T == null) { return; } else { postOrden1(T.getHI()); postOrden1(T.getHD()); System.out.print(T.getDato() + " "); } } public void PostOrden() { postOrden1(Raiz); } /***************************************************************************/ /*METODOS SOBRE ARBOLES*/ /***************************************************************************/ // Existe public boolean Existe(int ele) { NodoB P = Raiz; while (P != null) { if (ele < P.getDato()) { P = P.getHI(); } else { if (ele > P.getDato()) { P = P.getHD(); } else { return true; } } } return false; } // Cantidad de Hojas public int CantHojas1(NodoB T) { if (T == null) { return 0; } else { if (Hoja(T)) { return 1; } else {//5 int HI = CantHojas1(T.getHI()); int HD = CantHojas1(T.getHD()); return HI + HD; } } } public int CantHojas() { return CantHojas1(Raiz); } // Altura public int altura1(NodoB T) { if (T == null) { return 0; } else { if (Hoja(T)) { return 1; } else { int HI = altura1(T.getHI()); int HD = altura1(T.getHD()); return Math.max(HI, HD) + 1; } } } public int Altura() { return altura1(Raiz); } // Cantidad Total public int Cantidad1(NodoB T) { if (T == null) { return 0; } else { if (Hoja(T)) { return 1; } else { int HI = Cantidad1(T.getHI()); int HD = Cantidad1(T.getHD()); return HI + HD + 1; } } } public int Cantidad() { return Cantidad1(Raiz); } // Cantidad de Padres con un Solo hijo (INCOMPLETOS) public int Incompletos1(NodoB T) { if (T == null) { return 0; } else { if (Hoja(T)) { return 0; } else { int HI = Incompletos1(T.getHI()); int HD = Incompletos1(T.getHD()); if ((T.getHI() != null && T.getHD() == null) || (T.getHI() == null && T.getHD() != null)) { return HI + HD + 1; } else { return HI + HD; } } } } public int Incompletos() { return Incompletos1(Raiz); } // Cantidad de Padres con 2 hijos (COMPLETOS) public int Completos1(NodoB T) { if (T == null) { return 0; } else { if (Hoja(T)) { return 0; } else { int HI = Completos1(T.getHI()); int HD = Completos1(T.getHD()); if (T.getHI() != null && T.getHD() != null) { return HI + HD + 1; } else { return HI + HD; } } } } public int Completos() { return Completos1(Raiz); } // Cantidad de hijos Izquierdos public int HijosIzq1(NodoB T) { if (T == null) { return 0; } else { if (Hoja(T)) { return 0; } else { int HI = HijosIzq1(T.getHI()); int HD = HijosIzq1(T.getHD()); if (T.getHI() != null) { return HI + HD + 1; } else { return HI + HD; } } } } public int HijosIzq() { return HijosIzq1(Raiz); } // Cantidad Hijos Derechos public int HijosDer1(NodoB T) { if (T == null) { return 0; } else { if (Hoja(T)) { return 0; } else { int HI = HijosDer1(T.getHI()); int HD = HijosDer1(T.getHD()); if (T.getHD() != null) { return HI + HD + 1; } else { return HI + HD; } } } } public int HijosDer() { return HijosDer1(Raiz); } // es HEAP: si todo los hijos de T son iguales o menores a el (ARBOL DESORDENADO) public boolean EsHeap(NodoB T) { if (T == null) { return true; } else { if (Hoja(T)) { return true; } else { boolean HI = EsHeap(T.getHI()); boolean HD = EsHeap(T.getHD()); if (T.getHI() != null) { if (T.getDato() < T.getHI().getDato()) { return false; } } if (T.getHD() != null) { if (T.getDato() < T.getHD().getDato()) { return false; } } return HI && HD; } } } // Gemelo (ARBOL DESORDENADO) public boolean gemelos() { return gemelos1(Raiz); } private boolean gemelos1(NodoB T) { if (T == null) { return false; } else { if (Hoja(T)) { return false; } else { boolean HI = gemelos1(T.getHI()); boolean HD = gemelos1(T.getHD()); if (T.getHD().getDato() != T.getHI().getDato()) { return false; } else { return HI && HD; } } } } // El arbol es equilibrada, o sea si es Delta public boolean equilibrada() { return equilibrada1(Raiz); } public boolean equilibrada1(NodoB T) { if (T == null) { return true; } else { if (Hoja(T)) { return true; } else { boolean HI = equilibrada1(T.getHI()); boolean HD = equilibrada1(T.getHD()); if (T.getHI() == null || T.getHD() == null) { return false; } if (altura1(T.getHD()) != altura1(T.getHI())) { return false; } return HI && HD; } } } // devuelve true si d1 es hermano de d2 public boolean SonHermanos1(NodoB T, int d1, int d2) { if (T == null) { return false; } else { if (Hoja(T)) { return false; } else { boolean HI = SonHermanos1(T.getHI(), d1, d2); boolean HD = SonHermanos1(T.getHD(), d1, d2); if (T.getHI() == null || T.getHD() == null) { return false; } else { if (T.getHI().getDato() == d1 && T.getHD().getDato() == d2) { return true; } else { return HI || HD; } } } } } public boolean SonHermanos(int d1, int d2) { return SonHermanos1(Raiz, d1, d2); } // Ancestros : Devuelve los Ancestros del data private String ancestros1(NodoB T, int data) { if (T == null) { return ""; } else { if (Hoja(T)) { if (T.getDato() == data) { return String.valueOf(T.getDato()); } else { return ""; } } else { String HI = ancestros1(T.getHI(), data); String HD = ancestros1(T.getHD(), data); if (data < T.getDato()) { return T.getDato() + " " + HI; } else { return T.getDato() + " " + HD; } } } } public String ancestros(int data) { return ancestros1(Raiz, data); } // Nivel del Dato public int Nivel1(NodoB T, int x) { if (T == null) { return 0; } else { if (Hoja(T)) { if (T.getDato() == x) { return 1; } else { return 0; } } else { int HI = Nivel1(T.getHI(), x); int HD = Nivel1(T.getHD(), x); if (T.getDato() == x) { return 1; } if (x < T.getDato()) { return HI + 1; } else { return HD + 1; } } } } public int Nivel(int x) { return Nivel1(Raiz, x); } // Devolver los elementos de un Nivel public void Generacion1(NodoB T, int n) { if (T == null) { return; } else { Generacion1(T.getHI(), n); if (Nivel(T.getDato()) == n) { System.out.print(T.getDato() + " "); } Generacion1(T.getHD(), n); } } public void Generacion(int n) { Generacion1(Raiz, n); } // Siguiente Generacion de un Nodo public void SiguienteGeneracion1(NodoB T, int n) { if (T == null) { return; } else { SiguienteGeneracion1(T.getHI(), n); if (Nivel(T.getDato()) == n + 1) { System.out.print(T.getDato() + " "); } SiguienteGeneracion1(T.getHD(), n); } } public void SiguienteGeneracion(int n) { SiguienteGeneracion1(Raiz, n); } // Anterior Generacion de un Nodo public void AnteriorGeneracion1(NodoB T, int n) { if (T == null) { return; } else { AnteriorGeneracion1(T.getHI(), n); if (Nivel(T.getDato()) == n - 1) { System.out.print(T.getDato() + " "); } AnteriorGeneracion1(T.getHD(), n); } } public void AnteriorGeneracion(int n) { AnteriorGeneracion1(Raiz, n); } // Cantidad de Gajos: es un gajo si es un puntero hijo no nulo public int CantGajos1(NodoB T) { if (T == null) { return 0; } else { if (Hoja(T)) { return 0; } else { int HI = CantGajos1(T.getHI()); int HD = CantGajos1(T.getHD()); if (T.getHI() != null && T.getHD() != null) { return HI + HD + 2; } else { if (T.getHI() != null) { return HI + HD + 1; } if (T.getHD() != null) { return HI + HD + 1; } } return HI + HD; } } } public int CantGajos() { return CantGajos1(Raiz); } // Cantidad de gajos Completos public int CantGajoCompletos1(NodoB T) { if (T == null) { return 0; } else { if (Hoja(T)) { return 0; } else { int HI = CantGajoCompletos1(T.getHI()); int HD = CantGajoCompletos1(T.getHD()); if (T.getHI() != null && T.getHD() != null) { return HI + HD + 1; } else { return HI + HD; } } } } public int CantGajosCompletos() { return CantGajoCompletos1(Raiz); } // Cantidad de Nodos cuyos datas sean Pares public int CantPares1(NodoB T) { if (T == null) { return 0; } else { if (Hoja(T)) { if (T.getDato() % 2 == 0) { return 1; } else { return 0; } } else { int HI = CantPares1(T.getHI()); int HD = CantPares1(T.getHD()); if (T.getDato() % 2 == 0) { return HI + HD + 1; } else { return HI + HD; } } } } public int CantPares() { return CantPares1(Raiz); } // InOrden no recursivo // Mostrar en Preorden usando SucInorden // Mostra en Inorden usando sucinorden // Multiplicar por X al Arbol /***************************************************************************/ /*REPRESENTACION*/ /***************************************************************************/ public static void main(String[] Args) { ArbolB A = new ArbolB(); //FORMA DE CARGAR EL ARBOL A.Recargar("40,30,60,20,35,70,18,33,37,65,10,19,31,36"); //MUESTRA DEL ARBOL /* 40 * 30 60 * 20 35 70 * 18 33 37 65 * 10 19 31 36 */ //METODOS SOBRE ARBOLES: System.out.print("El recorrido en Inorden es: "); A.InOrden(); System.out.println(); System.out.print("El recorrido en Preorden es: "); A.PreOrden(); System.out.println(); System.out.print("El recorrido en Postorden es: "); A.PostOrden(); System.out.println(); //System.out.print("El recorrido en InordenNR es: "); //A.InOrdenNR(); //System.out.println(); System.out.println("La altura del arbol es: " + A.Altura()); System.out.println("La cantidad de \"nodos\" que posee el arbol es: " + A.Cantidad()); System.out.println("La cantidad de hojas es: " + A.CantHojas()); System.out.println("La cantidad de hijos izquierdos es: " + A.HijosIzq()); System.out.println("La cantidad de hijos derechos es: " + A.HijosDer()); System.out.println("Los Ancestros de 35 son : " + A.ancestros(35)); System.out.println("Son Hermanos 33 y 37 : " + A.SonHermanos(33, 37)); System.out.println("el nivel del dato es : " + A.Nivel(35)); System.out.println("LA cantidad de gajos es : " + A.CantGajos()); System.out.println("LA cantidad de gajos completos es : " + A.CantGajosCompletos()); System.out.println("LA cantidad de datas pares es : " + A.CantPares()); System.out.println(); System.out.print("La generacion 4 es: "); A.Generacion(3); System.out.println(); } }

0 comentarios:

Publicar un comentario