Arboles Java

Apartado 13.3, clase ÁrbolBinario package arbolBinario; public class ArbolBinario { protected Nodo raiz; public ArbolBinario() { raiz = null; } public ArbolBinario(Nodo raiz) { this.raiz = raiz; } public Nodo raizArbol() { return raiz; } public boolean esVacio() { return raiz == null; } public static Nodo nuevoArbol( Nodo ramaIzqda, Object dato, Nodo ramaDrcha) { return new Nodo(ramaIzqda, dato, ramaDrcha); } public static void preorden(Nodo r) { if (r != null) { r.visitar(); preorden (r.subarbolIzdo()); preorden (r.subarbolDcho()); } } // Recorrido de un árbol binario en inorden public static void inorden(Nodo r) { if (r != null) { inorden (r.subarbolIzdo()); r.visitar(); inorden (r.subarbolDcho()); } } // Recorrido de un árbol binario en postorden public static void postorden(Nodo r) { if (r != null) { postorden (r.subarbolIzdo()); postorden (r.subarbolDcho()); r.visitar(); } } public static int altura(Nodo raiz) { if (raiz == null) return 0 ;

else { int alturaIz = altura (raiz.subarbolIzdo()); int alturaDr = altura (raiz.subarbolDcho()); if (alturaIz > alturaDr) return alturaIz + 1; else return alturaDr + 1; } } public static boolean arbolLleno(Nodo raiz) { if (raiz == null) return true; else if (altura(raiz.subarbolIzdo())!= altura(raiz.subarbolDcho())) return false; return arbolLleno(raiz.subarbolIzdo()) && arbolLleno(raiz.subarbolDcho()); } public static int numNodos(Nodo raiz) { if (raiz == null) return 0; else return 1 + numNodos(raiz.subarbolIzdo()) + numNodos(raiz.subarbolDcho()); } public static ArbolBinario copiaArbol(Nodo raiz) { Nodo raizCopia; if (raiz == null) raizCopia = null; else { ArbolBinario izdoCopia, dchoCopia; izdoCopia = copiaArbol(raiz.subarbolIzdo()); dchoCopia = copiaArbol(raiz.subarbolDcho()); raizCopia = new Nodo(izdoCopia.raizArbol(), raiz.valorNodo(), dchoCopia.raizArbol()); } return new ArbolBinario(raizCopia); } public static double evaluar(Nodo raiz, double[] operandos) throws Exception { double x, y, valor; char ch ; Character nr; valor = 0.0; if (raiz != null) // no está vacío { nr = (Character) raiz.valorNodo(); ch = nr.charValue(); if (ch >= 'A' && ch <= 'Z') return operandos[ch - 'A']; else { x = evaluar(raiz.subarbolIzdo(), operandos); y = evaluar(raiz.subarbolDcho(), operandos);

switch (ch) { case '+': valor = x + y; break; case '-': valor = x - y; break; case '*': valor = x * y; break; case '/': if (y != 0) valor = x/y; else throw new Exception("Error: división por 0"); break; case '^': valor = Math.pow(x, y); } }

}

return valor; } }

EJEMPLO 13.7 public static int numNodos(Nodo raiz) { if (raiz == null) return 0; else return 1 + numNodos(raiz.subarbolIzdo()) + numNodos(raiz.subarbolDcho()); }

EJEMPLO 13.11 public Nodo buscarIterativo (Object buscado) { Comparador dato; boolean encontrado = false; Nodo raizSub = raiz; dato = (Comparador) buscado; while (!encontrado && raizSub != null) { if (dato.igualQue(raizSub.valorNodo())) encontrado = true; else if (dato.menorQue(raizSub.valorNodo())) raizSub = raizSub.subarbolIzdo(); else raizSub = raizSub.subarbolDcho(); } return raizSub; }

EJERCICIO 13.2 import java.io.*; import arbolBinarioOrdenado.*; import arbolBinario.*; class Estudiante implements Comparador { int numMat; String nombre; public Estudiante(String n, int mat) { nombre = n; numMat = mat; } public Estudiante() { this(null, 0); } public String toString() { if (nombre != null) return nombre + numMat; else return "No asignado"; } public boolean menorQue(Object op2) { Estudiante p2 = (Estudiante) op2; return numMat < p2.numMat; } public boolean menorIgualQue(Object op2) { Estudiante p2 = (Estudiante) op2; return numMat <= p2.numMat; } public boolean mayorQue(Object op2) { Estudiante p2 = (Estudiante) op2; return numMat > p2.numMat; } public boolean mayorIgualQue(Object op2) { Estudiante p2 = (Estudiante) op2; return numMat >= p2.numMat; } public boolean igualQue(Object op2) { Estudiante p2 = (Estudiante) op2; return numMat == p2.numMat; } }

public class ArbolEstudiante { public static void main(String [] a) { ArbolBinarioBusqueda ab = new ArbolBinarioBusqueda(); BufferedReader entrada = new BufferedReader( new InputStreamReader(System.in)); Estudiante el; int nm; String nom; try { // Se crea el árbol de búsqueda do{ System.out.print("Numero de matricula(0 -> Fin): "); nm = Integer.parseInt(entrada.readLine()); if (nm > 0) { System.out.print("Nombre: "); nom = entrada.readLine(); el = new Estudiante(nom, nm); ab.insertar(el); } }while (nm != 0); // Operaciones con el arbol do { System.out.print(" 1. Mostrar el árbol\n"); System.out.print(" 2. Eliminar un estudiante\n"); System.out.print(" 3. Salir\n "); do nm = Integer.parseInt(entrada.readLine()); while(nm < 1 || nm > 3); if (nm == 1) { System.out.print("\n\tEstudiantes \n"); visualizar(ab.raizArbol()); } else if (nm == 2) { int nmt; System.out.print ("Matricula: "); nmt = Integer.parseInt(entrada.readLine()); try { ab.eliminar(new Estudiante(null,nmt)); } catch (Exception e) { System.out.println(e); } } }while (nm != 3); } catch (Exception er) { System.out.println("Error en el proceso del arbol: " + er); } } static void visualizar (Nodo r) { if (r != null) {

visualizar(r.subarbolIzdo()); System.out.println(r.valorNodo()); visualizar(r.subarbolDcho()); }

}

}

EJERCICIO 13.7 public static int numNodos(Nodo raiz) { if (raiz == null) return 0; else return 1 + numNodos(raiz.subarbolIzdo()) + numNodos(raiz.subarbolDcho()); }

EJERCICIO 13.11 public Nodo buscarIterativo (Object buscado) { Comparador dato; boolean encontrado = false; Nodo raizSub = raiz; dato = (Comparador) buscado; while (!encontrado && raizSub != null) { if (dato.igualQue(raizSub.valorNodo())) encontrado = true; else if (dato.menorQue(raizSub.valorNodo())) raizSub = raizSub.subarbolIzdo(); else raizSub = raizSub.subarbolDcho(); } return raizSub; }