// Ejercicio 1
public static int numNodos(ArbolBinario arbol) {
if (arbol.esVacio())
return 0;
else
return 1 + numNodos(arbol.hijoIzq()) + numNodos(arbol.hijoDer());
}
// Ejercicio 2
public static int numHojas(ArbolBinario arbol) {
if (arbol.esVacio())
return 0;
else
if (arbol.hijoIzq().esVacio() && arbol.hijoDer().esVacio())
return 1;
else
return numHojas(arbol.hijoIzq()) + numHojas(arbol.hijoDer());
}
// Ejercicio 3
public static boolean esDegenerado(ArbolBinario arbol) {
if (arbol.esVacio())
return false;
else if (arbol.hijoIzq().esVacio() && !arbol.hijoDer().esVacio())
return esDegenerado(arbol.hijoDer());
else if (!arbol.hijoIzq().esVacio() && arbol.hijoDer().esVacio())
return esDegenerado(arbol.hijoIzq());
else if (arbol.hijoIzq().esVacio() && arbol.hijoDer().esVacio())
return true;
else
return false;
}
// Ejercicio 4
public static boolean identicos(ArbolBinario a, ArbolBinario b) {
if (a.esVacio() && b.esVacio())
return true;
else if (a.esVacio() || b.esVacio())
return false;
else if (!a.raiz().equals(b.raiz()))
return false;
else
return identicos(a.hijoIzq(), b.hijoIzq()) && identicos(a.hijoDer(), b.hijoDer());
}
// Ejercicio 5
public static ArbolBinario copia(ArbolBinario arbol) {
if (arbol.esVacio())
return new EnlazadoArbolBinario<>();
else
return new EnlazadoArbolBinario(arbol.raiz(),
copia(arbol.hijoIzq()),
copia(arbol.hijoDer()));
}
// Ejercicio 6
public static int contarNivel(ArbolBinario a, int nivel) {
if (a.esVacio()) return 0;
else {
if (nivel == 0) return 1;
else return (contarNivel(a.hijoDer(), nivel – 1) + contarNivel(a.hijoIzq(), nivel – 1));
}
}
// Ejercicio 7
public static ArbolBinario copiaNivel(ArbolBinario a, int nivel) {
if (a.esVacio())
return new EnlazadoArbolBinario<>();
else
if (nivel == 0)
return new EnlazadoArbolBinario(a.raiz(),
new EnlazadoArbolBinario<>(),
new EnlazadoArbolBinario<>());
else
return new EnlazadoArbolBinario(a.raiz(),
copiaNivel(a.hijoIzq(), nivel – 1),
copiaNivel(a.hijoDer(), nivel – 1));
}
// Ejercicio 8
public static ArbolBinario copiaSinHojas(ArbolBinario arbol) {
if (arbol.esVacio())
return new EnlazadoArbolBinario();
else if (arbol.hijoIzq().esVacio() && arbol.hijoDer().esVacio())
return new EnlazadoArbolBinario();
else {
return new EnlazadoArbolBinario(arbol.raiz(),
copiaSinHojas(arbol.hijoIzq()),
copiaSinHojas(arbol.hijoDer()));
}
}
// Ejercicio 9
public static boolean esSeleccion2(ArbolBinario arbol) {
if (arbol.esVacio()) return true;
else if (arbol.hijoIzq().esVacio() && arbol.hijoDer().esVacio()) return true;
else if (arbol.hijoIzq().esVacio() && !arbol.hijoDer().esVacio())
return arbol.raiz().equals(arbol.hijoDer().raiz()) && esSeleccion2(arbol.hijoDer());
else if (!arbol.hijoIzq().esVacio() && arbol.hijoDer().esVacio())
return arbol.raiz().equals(arbol.hijoIzq().raiz()) && esSeleccion2(arbol.hijoIzq());
else {
E menor = arbol.hijoIzq().raiz().compareTo(arbol.hijoDer().raiz()) < 0 ?
arbol.hijoIzq().raiz() :
arbol.hijoDer().raiz();
return arbol.raiz().equals(menor) &&
esSeleccion2(arbol.hijoIzq()) &&
esSeleccion2(arbol.hijoDer());
}
}
public static boolean hayCamino(ArbolBinario arbol, String camino) {
if (camino.length() == 0)
return true;
if (arbol.esVacio())
return false;
else {
if (arbol.raiz().equals(camino.charAt(0))) {
String sub = camino.substring(1);
return hayCamino(arbol.hijoIzq(), sub) || hayCamino(arbol.hijoDer(), sub);
}
else return false;
}
// Ejercicio 11
public static void visualizarPalabras(ArbolBinario a, String palabras) {
if (!a.esVacio()) {
if (a.hijoIzq().esVacio() && a.hijoDer().esVacio()) {
System.out.print(palabras + a.raiz());
}
else {
ArbolBinario hi = a.hijoIzq();
ArbolBinario hd = a.hijoDer();
visualizarPalabras(hi, palabras + a.raiz());
visualizarPalabras(hd, palabras + a.raiz());
}
}
}
// Ejercicio 12
public static E padre(ArbolBinario a, E elemento) {
if (a.esVacio()) return null;
else if (a.raiz().equals(elemento)) return null;
else if ((!a.hijoIzq().esVacio() && a.hijoIzq().raiz().equals(elemento)) ||
(!a.hijoDer().esVacio() && a.hijoDer().raiz().equals(elemento)))
return a.raiz();
else {
E aux = padre(a.hijoIzq(), elemento);
if (aux == null)
return padre(a.hijoDer(), elemento);
else return aux;
}
}
// Ejercicio Parecidos
public static boolean parecidos(ArbolBinario a, ArbolBinario b) {
if (a.esVacio())
return b.esVacio();
if (b.esVacio())
return a.esVacio();
if (parecidos(a.hijoIzq(), b.hijoDer()))
if (parecidos(a.hijoDer(), b.hijoIzq()))
return (a.raiz().equals(b.raiz()));
return false;
}
// Ejercicio 7
public static ArbolBinario podar(ArbolBinario a) {
if (a.esVacio())
return new EnlazadoArbolBinario();
else {
if (a.hijoIzq().esVacio() || a.hijoDer().esVacio())
return new EnlazadoArbolBinario(a.raiz(), new EnlazadoArbolBinario(), new EnlazadoArbolBinario());
else {
ArbolBinario nuevo1 = podar(a.hijoIzq());
ArbolBinario nuevo2 = podar(a.hijoDer());
return new EnlazadoArbolBinario(a.raiz(), nuevo1, nuevo2);
}
}
// EJR 33
public static boolean zurdo(ArbolBinario a) {
if (a.esVacio()) return true;
else if (a.hijoIzq().esVacio() && a.hijoDer().esVacio())
return true;
else if (zurdo(a.hijoDer()) && zurdo(a.hijoIzq())) {
int hi = numNodos(a.hijoIzq());
int hd = numNodos(a.hijoDer());
if (hi > hd)
return true;
else
return false;
}
else
return false;
}
private int recorrerArbol(ArbolBusqueda arbol) {
if (arbol.esVacio()) {
return 0;
}
else {
return 1 + (recorrerArbol(arbol.hijoIzq()) + (recorrerArbol(arbol.hijoDer())));
}
}
public int cardinal() {
if (elementos.esVacio()) {
return 0;
}
else {
return recorrerArbol(elementos);
}
}
public boolean pertenece(E x) {
return elementos.buscar(x);
}
public boolean inserta(E x) {
if (elementos.buscar(x))
return false;
else elementos.insertar(x);
return true;
}
public boolean elimina(E x) {
if (elementos.buscar(x)) {
elementos.eliminar(x);
return true;
}
else
return false;
}
public E elige() throws IllegalArgumentException {
if (elementos.esVacio())
throw new IllegalArgumentException(«El conjunto elementos está vacío»);
else {
return elementos.raiz();
}
}
public Conjunto union(Conjunto conj) {
Conjunto nuevoConjunto = new ConjuntoABB();
Conjunto aux = new ConjuntoABB();
while (this.cardinal() != 0) {
E elemento = this.elige();
nuevoConjunto.inserta(elemento);
aux.inserta(elemento);
this.elimina(elemento);
}
while (aux.cardinal() != 0) {
E elemento = aux.elige();
this.inserta(elemento);
aux.elimina(elemento);
}
while (conj.cardinal() != 0) {
E elemento = conj.elige();
nuevoConjunto.inserta(elemento);
aux.inserta(elemento);
conj.elimina(elemento);
}
while (aux.cardinal() != 0) {
E elemento = aux.elige();
conj.inserta(elemento);
aux.elimina(elemento);
}
return nuevoConjunto;
}
public Conjunto interseccion(Conjunto conj) {
Conjunto nuevoConjunto = new ConjuntoABB();
Conjunto aux = new ConjuntoABB();
while (this.cardinal() != 0) {
if (conj.pertenece(this.elige())) {
nuevoConjunto.inserta(this.elige());
}
aux.inserta(this.elige());
this.elimina(this.elige());
}
while (aux.cardinal() != 0) {
this.inserta(aux.elige());
aux.elimina(aux.elige());
}
return nuevoConjunto;
}
public Conjunto diferencia(Conjunto conj) {
Conjunto nuevoConjunto = new ConjuntoABB();
Conjunto aux = new ConjuntoABB();
while (this.cardinal() != 0) {
if (!conj.pertenece(this.elige())) {
nuevoConjunto.inserta(this.elige());
}
aux.inserta(this.elige());
this.elimina(this.elige());
}
while (aux.cardinal() != 0) {
this.inserta(aux.elige());
aux.elimina(aux.elige());
}
return nuevoConjunto;
}
// Con operaciones de árboles
private void recorrer(ArbolBusqueda arbol, Conjunto c) {
if (!arbol.esVacio()) {
c.inserta(arbol.raiz());
recorrer(arbol.hijoIzq(), c);
recorrer(arbol.hijoDer(), c);
}
}
public Conjunto union2(Conjunto conj) {
Conjunto union = new ConjuntoABB();
recorrer(elementos, union);
recorrer(((ConjuntoABB) conj).elementos, union);
return union;
}
private void recorrer(ArbolBusqueda a1, ArbolBusqueda a2, Conjunto inter) {
if (!a1.esVacio()) {
if (a2.buscar(a1.raiz())) inter.inserta(a1.raiz());
recorrer(a1.hijoIzq(), a2, inter);
recorrer(a1.hijoDer(), a2, inter);
}
}
public Conjunto interseccion2(Conjunto conj) {
Conjunto inter = new ConjuntoABB();
recorrer(elementos, ((ConjuntoABB) conj).elementos, inter);
return inter;
}
}