Recorridos y operaciones sobre árboles generales en Java: preorden, inorden, altura y más

Recorridos y operaciones sobre árboles generales

A continuación se presentan implementaciones en Java de distintos algoritmos para trabajar con árboles generales, utilizando la interfaz ArbolGeneral.

Recorridos del árbol

Recorrido en preorden

public static void preorden(ArbolGeneral a){
    if (!a.esVacio()){
        System.out.print(" "+a.raiz());
        ArbolGeneral aux=a.hijoMasIzq();
        while (!aux.esVacio()){
            preorden(aux);
            aux=aux.hermanoDer();
        }
    }
}

Recorrido en inorden

public static void inorden(ArbolGeneral a){
    if (!a.esVacio()){
        ArbolGeneral aux=a.hijoMasIzq();
        inorden(aux);
        System.out.print(" "+a.raiz());
        if (!aux.esVacio()){
            aux=aux.hermanoDer();
            while (!aux.esVacio()){
                inorden(aux);
                aux=aux.hermanoDer();
            }
        }
    }
}

Recorrido en anchura

public static void anchura(ArbolGeneral a){
    Cola<ArbolGeneral> c = new EnlazadaCola<>();
    c.insertar(a);
    do {
        a = c.suprimir();
        if (!a.esVacio()){
            System.out.print(a.raiz() + " ");
            ArbolGeneral hijo=a.hijoMasIzq();
            while (!hijo.esVacio()){
                c.insertar(hijo);
                hijo=hijo.hermanoDer();
            }
        }
    } while (!c.esVacio());
}

Operaciones básicas

Contar nodos

public static int contarNodos(ArbolGeneral a){
    if (a.esVacio()) return 0;
    else {
        int cont=1;
        ArbolGeneral hijo = a.hijoMasIzq();
        while (!hijo.esVacio()){
            cont+=contarNodos(hijo);
            hijo=hijo.hermanoDer();
        }
        return cont;
    }
}

Suma de los nodos

public static int sumaNodos(ArbolGeneral a){
    if (a.esVacio()) return 0;
    else {
        int cont=a.raiz();
        ArbolGeneral hijo = a.hijoMasIzq();
        while (!hijo.esVacio()){
            cont+=sumaNodos(hijo);
            hijo=hijo.hermanoDer();
        }
        return cont;
    }
}

Número de nodos pares

public static int numNodosPares(ArbolGeneral a){
    if (a.esVacio()) return 0;
    else {
        int cont=0;
        if (a.raiz()%2==0) cont++;
        ArbolGeneral hijo = a.hijoMasIzq();
        while (!hijo.esVacio()){
            cont+=numNodosPares(hijo);
            hijo=hijo.hermanoDer();
        }
        return cont;
    }
}

Duplicar el árbol

public static ArbolGeneral duplicar(ArbolGeneral a){
    if (a.esVacio()) return new EnlazadoArbolGeneral<>();
    int numSubArboles = subArboles(a);
    ArbolGeneral[] copias = (ArbolGeneral[])new ArbolGeneral[numSubArboles];
    ArbolGeneral hijo = a.hijoMasIzq();
    int i = 0;
    while (!hijo.esVacio()){
        copias[i++] = duplicar(hijo);
        hijo=hijo.hermanoDer();
    }
    return new EnlazadoArbolGeneral<>(a.raiz()*2, copias);
}

Número de subárboles

public static int subArboles(ArbolGeneral a){
    if (a.esVacio()) return 0;
    else {
        int cont = 0;
        ArbolGeneral hijo = a.hijoMasIzq();
        while (!hijo.esVacio()) {
            cont++;
            hijo = hijo.hermanoDer();
        }
        return cont;
    }
}

Comparación de árboles

Igualdad de estructura

public static boolean igualEstructura(ArbolGeneral a, ArbolGeneral b){
    if (a.esVacio() && b.esVacio()) return true;
    if (a.esVacio() || b.esVacio()) return false;
    ArbolGeneral ha = a.hijoMasIzq();
    ArbolGeneral hb = b.hijoMasIzq();
    while (!ha.esVacio() && !hb.esVacio()){
        if (!igualEstructura(ha,hb)) return false;
        ha = ha.hermanoDer();
        hb = hb.hermanoDer();
    }
    return ha.esVacio() && hb.esVacio();
}

Árboles idénticos

public static boolean identicos(ArbolGeneral a, ArbolGeneral b){
    if (a.esVacio() && b.esVacio()) return true;
    if (!a.esVacio() && !b.esVacio()){
        if (!a.raiz().equals(b.raiz())) return false;
        else {
            ArbolGeneral ha = a.hijoMasIzq();
            ArbolGeneral hb = b.hijoMasIzq();
            while (!ha.esVacio() && !hb.esVacio()) {
                if (!identicos(ha,hb)) return false;
                ha = ha.hermanoDer();
                hb = hb.hermanoDer();
            }
            return ha.esVacio() && hb.esVacio();
        }
    }
    return false;
}

Propiedades estructurales

Nivel de un elemento

public static <E> int nivel(ArbolGeneral a, E elemento){
    if (a.esVacio()) return -1;
    else {
        if (a.raiz().equals(elemento)){
            return 0;
        } else {
            ArbolGeneral hijo = a.hijoMasIzq();
            while (!hijo.esVacio()){
                int n = nivel(hijo, elemento);
                if (n == -1) hijo = hijo.hermanoDer();
                else return 1 + n;
            }
            return -1;
        }
    }
}

Grado del árbol

public static int grado(ArbolGeneral a){
    if (a.esVacio()) return 0;
    else {
        int num=0;
        ArbolGeneral hijo=a.hijoMasIzq();
        while (!hijo.esVacio()){
            num++;
            hijo=hijo.hermanoDer();
        }
        int maxGrado=num;
        hijo=a.hijoMasIzq();
        while (!hijo.esVacio()){
            int gradoAct=grado(hijo);
            if (gradoAct>maxGrado) maxGrado=gradoAct;
            hijo=hijo.hermanoDer();
        }
        return maxGrado;
    }
}

Altura del árbol

public static int altura(ArbolGeneral a) {
    if (a.esVacio()) return 0;
    if (a.hijoMasIzq().esVacio()) return 0;
    int maxGrado=0;
    ArbolGeneral hijo = a.hijoMasIzq();
    while (!hijo.esVacio()) {
        int cont = altura(hijo);
        if (cont > maxGrado) maxGrado = cont;
        hijo = hijo.hermanoDer();
    }
    return maxGrado+1;
}

Hojas del árbol

//guarda en una lista las hojas del árbol general
public static <E> void hojas(ArbolGeneral a, List<E> l){
    if (!a.esVacio()){
        if (a.hijoMasIzq().esVacio()) l.add(a.raiz());
        else {
            ArbolGeneral hijo = a.hijoMasIzq();
            while (!hijo.esVacio()) {
                hojas(hijo, l);
                hijo = hijo.hermanoDer();
            }
        }
    }
}

Número de hijos pares

public static <E> int numHijosPares(ArbolGeneral a){
    if (a.esVacio()) return 0;
    int contNodos=0, contHijos = 0;
    ArbolGeneral hijo = a.hijoMasIzq();
    while (!hijo.esVacio()){
        contHijos++;
        hijo = hijo.hermanoDer();
    }
    if (contHijos%2==0) contNodos =1;
    hijo = a.hijoMasIzq();
    while (!hijo.esVacio()){
        contNodos+=numHijosPares(hijo);
        hijo = hijo.hermanoDer();
    }
    return contNodos;
}

Verificación de propiedades

Árbol equilibrado

public static <E> boolean equilibrado(ArbolGeneral a){
    if (a.esVacio()) return true;
    else if (a.hijoMasIzq().esVacio()) return true;
    else {
        int numSub = subArboles(a);
        ArbolGeneral hijo = a.hijoMasIzq();
        while (!hijo.esVacio()) {
            int numSubHijo = subArboles(hijo);
            if (numSubHijo!=0 && numSub!=numSubHijo) return false;
            if (!equilibrado(hijo)) return false;
            hijo = hijo.hermanoDer();
        }
        return true;
    }
}

Árbol de dos o tres hijos

public static <E> boolean arbolDosTres(ArbolGeneral a){
    if (a.esVacio()) return true;
    ArbolGeneral hijo = a.hijoMasIzq();
    if (hijo.esVacio()) return true;
    int cont = 0;
    while (!hijo.esVacio() && arbolDosTres(hijo)){
        cont++;
        hijo = hijo.hermanoDer();
    }
    if (cont==2 || cont==3) return true;
    return false;
}

Árbol cuadrado (cuatro hijos por nodo)

public static <E> boolean cuadArbol(ArbolGeneral arbol){
    if (arbol.esVacio()) return true;
    else {
        ArbolGeneral hijo = arbol.hijoMasIzq();
        if (hijo.esVacio()) return true;
        else {
            int cont = 0;
            while (!hijo.esVacio() && cuadArbol(hijo)){
                cont++;
                hijo = hijo.hermanoDer();
            }
            if (hijo.esVacio()) return cont==4;
            else return false;
        }
    }
}

Árbol de selección

public static <E extends Comparable<E>> boolean esSeleccion(ArbolGeneral a){
    if (a.esVacio()) return true;
    else {
        ArbolGeneral hijo = a.hijoMasIzq();
        if (hijo.esVacio()) return true;
        else {
            E menor = hijo.raiz();
            while (!hijo.esVacio() && esSeleccion(hijo)){
                if (hijo.raiz().compareTo(menor)<0) menor = hijo.raiz();
                hijo = hijo.hermanoDer();
            }
            if (hijo.esVacio() && a.raiz().equals(menor)) return true;
            else return false;
        }
    }
}