Definiciones Básicas

• Grado de un nodo: Cantidad de subárboles que posee. Ejemplo: El nodo A tiene grado 6.
• Grado del árbol: Máximo grado entre todos los nodos. Relación: Nodos totales = Suma de grados + 1.
• Nodo hoja: Nodo con grado 0 (ej: B, C, H).
• Nodo padre: Nodo que continee subárboles (A es padre de B).
• Nodo raíz: Único nodo sin padre (A).
• Altura del árbol: Máximo nivel de nodos (ej: altura 4).

Representación de Árboles

Mediante nodos con referencia al primer hijjo y hermano adyacente:

class Nodo {
    int valor;
    Nodo primerHijo;
    Nodo hermanoSiguiente;
}

Conceptos de Árbol Binario

Estructura con raíz y dos subárboles (izquierdo/derecho). Tipos especiales:

• Árbol lleno: Todos los niveles completos con máximo de nodos.
• Árbol completo: Nodos alineados sin huecos en niveles.

Propiedades clave:

• Nodos hoja = Nodos grado 2 + 1
• Relaciones padre-hijo: Hijo izquierdo: 2i+1, Hijo derecho: 2i+2

Almacenamiento

Implementación mediante estructuras enlazadas o arreglos.

Recorridos

• Preorden: Raíz → Subárbol izq. → Subárbol der.
• Inorden: Subárbol izq. → Raíz → Subárbol der.
• Postorden: Subárbol izq. → Subárbol der. → Raíz
• Por niveles: Visita nodos nivel por nivel

Nota: Se requiere recorrido inorden para reconstruir el árbol

Implementación en Java

class NodoBinario {
    char valor;
    NodoBinario izquierdo;
    NodoBinario derecho;
    
    public NodoBinario(char v) {
        valor = v;
    }
}

class ArbolBinario {
    NodoBinario raiz;

    // Recorrido preorden
    void preorden(NodoBinario nodo) {
        if (nodo == null) return;
        System.out.print(nodo.valor + " ");
        preorden(nodo.izquierdo);
        preorden(nodo.derecho);
    }

    // Contar nodos
    int contarNodos(NodoBinario nodo) {
        return (nodo == null) ? 0 : 
            1 + contarNodos(nodo.izquierdo) + contarNodos(nodo.derecho);
    }

    // Buscar valor
    NodoBinario buscar(NodoBinario nodo, char valorBuscado) {
        if (nodo == null) return null;
        if (nodo.valor == valorBuscado) return nodo;
        NodoBinario izq = buscar(nodo.izquierdo, valorBuscado);
        return (izq != null) ? izq : buscar(nodo.derecho, valorBuscado);
    }

    // Recorrido por niveles
    void recorrerNiveles() {
        if (raiz == null) return;
        Queue<NodoBinario> cola = new LinkedList<>();
        cola.offer(raiz);
        while (!cola.isEmpty()) {
            NodoBinario actual = cola.poll();
            System.out.print(actual.valor + " ");
            if (actual.izquierdo != null) cola.offer(actual.izquierdo);
            if (actual.derecho != null) cola.offer(actual.derecho);
        }
    }

    // Verificar árbol completo
    boolean esCompleto() {
        if (raiz == null) return true;
        Queue<NodoBinario> cola = new LinkedList<>();
        cola.offer(raiz);
        boolean vacioEncontrado = false;
        while (!cola.isEmpty()) {
            NodoBinario actual = cola.poll();
            if (actual == null) {
                vacioEncontrado = true;
            } else {
                if (vacioEncontrado) return false;
                cola.offer(actual.izquierdo);
                cola.offer(actual.derecho);
            }
        }
        return true;
    }
}