Práctica de Binary Search Tree (BST) en Java

Práctica 6: Binary Search Tree

Implementación de diversos métodos recursivos y utilidades para la estructura de datos Binary Search Tree (BST) en Java.

Método findMax()

Busca el elemento de mayor valor en el árbol avanzando recursivamente por la rama derecha:

public T findMax() throws EmptyCollectionException {
    // Inspeccionar con recursividad, bajando por la derecha
    if (!isEmpty()) {
        if (getRightBST().isEmpty()) {
            return getContent();
        } else {
            return getRightBST().findMax();
        }
    } else {
        throw new EmptyCollectionException("No se puede encontrar el máximo de un árbol vacío");
    }
}

Método countEmpty() y Auxiliares

Contabiliza las referencias y subárboles vacíos dentro de la estructura:

public long countEmpty() {
    if (isEmpty()) return 1;
    else return getLeftBST().arbolIzdo() + getRightBST().arbolDcho();
}

private long arbolIzdo() {
    if (leftSubtree == null) return 1;
    else return getLeftBST().arbolIzdo() + getRightBST().arbolDcho();
}

private long arbolDcho() {
    if (rightSubtree == null) return 1;
    else return getLeftBST().arbolIzdo() + getRightBST().arbolDcho();
}

Método countOddLevelElements()

Calcula el número de elementos ubicados en niveles impares del árbol:

public long countOddLevelElements() {
    int nivel = 1;
    if (isEmpty()) return 0;
    return 1 + getLeftBST().countOddL(nivel, 0) + getRightBST().countOddR(nivel, 0);
}

public long countOddR(int nivel, long contador) {
    if (rightSubtree == null) return 0;
    else {
        nivel++;
        if (nivel % 2 != 0) {
            contador++;
            return 1 + getLeftBST().countOddL(nivel, contador) + getRightBST().countOddR(nivel, contador);
        } else {
            return getLeftBST().countOddL(nivel, contador) + getRightBST().countOddR(nivel, contador);
        }
    }
}

public long countOddL(int nivel, long contador) {
    if (leftSubtree == null)
}

Método parentChildPairs()

Almacena en una lista de cadenas las tuplas formadas por cada nodo padre y sus nodos hijos:

public void parentChildPairs(List<String> buffer) {
    String camino = "";
    if (isEmpty()) {
        buffer.add(camino);
        return;
    } else {
        if (!leftSubtree.isEmpty()) {
            buffer.add("(" + content + "," + leftSubtree.content + ")");
            getLeftBST().parentChildPairs(buffer);
        }
        if (!rightSubtree.isEmpty()) {
            buffer.add("(" + content + "," + rightSubtree.content + ")");
            getRightBST().parentChildPairs(buffer);
        }
    }
}

Método getContentWithPath()

Recupera el contenido del nodo indicado por una ruta binaria (donde 0 representa la rama izquierda y 1 la rama derecha):

public T getContentWithPath(String path) {
    if (path.equals("")) return content;
    for (int i = 0; i < path.length(); i++) {
        if (path.charAt(i) != '0' && path.charAt(i) != '1') {
            throw new IllegalArgumentException();
        }
    }
    return getContentWithPathRec(path, 0);
}

private T getContentWithPathRec(String path, int contador) {
    if (contador == path.length()) return content;
    String aux = path.substring(contador, contador + 1);
    if (aux.equals("0")) {
        if (leftSubtree.isEmpty()) {
            throw new NoSuchElementException();
        } else {
            return getLeftBST().getContentWithPathRec(path, ++contador);
        }
    } else {
        if (rightSubtree.isEmpty()) {
            throw new NoSuchElementException();
        } else {
            return getRightBST().getContentWithPathRec(path, ++contador);
        }
    }
}