Conceitos Fundamentais

Existem duas abordagens principais para percorrer uma árvore binária:

1. Busca em Profundidade (DFS): Explora o caminho mais profundo primeiro, retrocedendo ao encontrar folhas.
2. Busca em Largura (BFS): Visita todos os nós de um nível antes de avançar para o próximo.

Esses dois métodos são a base para os algoritmos de travessia em grafos. A partir deles, derivamos as seguintes variações:

• DFS:
  • Pré-ordem (recursivo, iterativo)
  • Em-ordem (recursivo, iterativo)
  • Pós-ordem (recursivo, iterativo)
• BFS:
  • Travessia por Nível (iterativo)

Um nó em uma árvore binária representada em JavaScript pode ser definido assim:

function NoArvore(valor, esquerda, direita) {
    this.valor = (valor === undefined ? 0 : valor);
    this.esquerda = (esquerda === undefined ? null : esquerda);
    this.direita = (direita === undefined ? null : direita);
}

Algoritmos de Travessia

1. Travessia Recursiva

Para percorrer uma árvore recursivamente, visitamos o nó atual e chamamos a função recursivamente para suas subárvores.

Pré-ordem (Raiz → Esquerda → Direita)

var percorrePreOrdem = function(no) {
    if (!no) return [];
    const coletor = [];
    function visitar(n) {
        if (!n) return;
        coletor.push(n.valor); // Visita a raiz primeiro
        visitar(n.esquerda);   // Percorre subárvore esquerda
        visitar(n.direita);    // Percorre subárvore direita
    }
    visitar(no);
    return coletor;
};

Em-ordem (Esquerda → Raiz → Direita)

var percorreEmOrdem = function(no) {
    const resultado = [];
    function explorar(noAtual) {
        if (!noAtual) return;
        explorar(noAtual.esquerda);
        resultado.push(noAtual.valor);
        explorar(noAtual.direita);
    }
    explorar(no);
    return resultado;
};

Pós-ordem (Esquerda → Direita → Raiz)

var percorrePosOrdem = function(no) {
    const elementos = [];
    function processar(noAtual) {
        if (!noAtual) return;
        processar(noAtual.esquerda);
        processar(noAtual.direita);
        elementos.push(noAtual.valor);
    }
    processar(no);
    return elementos;
};

2. Travessia Iterativa

Usando uma pilha, podemos simular a travessia rceursiva de forma iterativa.

Pré-ordem Iterativa

var percorrePreOrdemIterativo = function(noRaiz) {
    if (!noRaiz) return [];
    const pilha = [noRaiz];
    const saida = [];
    while (pilha.length > 0) {
        const no = pilha.pop();
        saida.push(no.valor);
        // Empilhamos a direita primeiro para que a esquerda seja processada primeiro
        if (no.direita) pilha.push(no.direita);
        if (no.esquerda) pilha.push(no.esquerda);
    }
    return saida;
};

Em-ordem Iterativa

var percorreEmOrdemIterativo = function(noRaiz) {
    const resultado = [];
    const suporte = [];
    let corrente = noRaiz;
    while (corrente || suporte.length) {
        // Vai até o nó mais à esquerda
        while (corrente) {
            suporte.push(corrente);
            corrente = corrente.esquerda;
        }
        corrente = suporte.pop();
        resultado.push(corrente.valor);
        corrente = corrente.direita;
    }
    return resultado;
};

Pós-ordem Iterativa

var percorrePosOrdemIterativo = function(noRaiz) {
    if (!noRaiz) return [];
    const pilha = [noRaiz];
    const caminho = [];
    while (pilha.length) {
        const no = pilha.pop();
        caminho.unshift(no.valor); // Insere no início para inversão
        if (no.esquerda) pilha.push(no.esquerda);
        if (no.direita) pilha.push(no.direita);
    }
    return caminho;
};

3. Travessia por Nível (BFS)

Utilizamos uma fila (queue) para visitar os nós nível a nível.

Modelo Base

var percorrePorNivel = function(noRaiz) {
    let niveis = [];
    let fila = [];
    if (noRaiz === null) return niveis;
    fila.push(noRaiz);
    while (fila.length !== 0) {
        let nosDoNivel = [];
        let tamanhoNivel = fila.length;
        for (let i = 0; i < tamanhoNivel; i++) {
            let noAtual = fila.shift();
            nosDoNivel.push(noAtual.valor);
            if (noAtual.esquerda) fila.push(noAtual.esquerda);
            if (noAtual.direita) fila.push(noAtual.direita);
        }
        niveis.push(nosDoNivel);
    }
    return niveis;
};

Travessia de Baixo para Cima

Podemos inverter o array de resultados da travessia por nível normal.

var percorrePorNivelInvertido = function(noRaiz) {
    const niveis = percorrePorNivel(noRaiz);
    return niveis.reverse();
};

Vista Lateral Direita

Coletamos apenas o último elemento de cada nível.

var vistaDireita = function(noRaiz) {
    const visao = [];
    let fila = [];
    if (noRaiz === null) return visao;
    fila.push(noRaiz);
    while (fila.length) {
        let tamanhoNivel = fila.length;
        let ultimoNoValor;
        for (let i = 0; i < tamanhoNivel; i++) {
            let no = fila.shift();
            ultimoNoValor = no.valor; // Atualiza constantemente
            if (no.esquerda) fila.push(no.esquerda);
            if (no.direita) fila.push(no.direita);
        }
        visao.push(ultimoNoValor); // Adiciona o último da iteração
    }
    return visao;
};

Média dos Valores por Nível

var mediaPorNivel = function(noRaiz) {
    const medias = [];
    let fila = [];
    if (!noRaiz) return medias;
    fila.push(noRaiz);
    while (fila.length) {
        let soma = 0;
        let quantidade = fila.length;
        for (let i = 0; i < quantidade; i++) {
            let no = fila.shift();
            soma += no.valor;
            if (no.esquerda) fila.push(no.esquerda);
            if (no.direita) fila.push(no.direita);
        }
        medias.push(soma / quantidade);
    }
    return medias;
};

Maior Valor por Nível

var maiorValorPorNivel = function(noRaiz) {
    const maiores = [];
    let fila = [];
    if (!noRaiz) return maiores;
    fila.push(noRaiz);
    while (fila.length) {
        let nivelAtual = [];
        let tamanho = fila.length;
        for (let i = 0; i < tamanho; i++) {
            let no = fila.shift();
            nivelAtual.push(no.valor);
            if (no.esquerda) fila.push(no.esquerda);
            if (no.direita) fila.push(no.direita);
        }
        maiores.push(Math.max(...nivelAtual));
    }
    return maiores;
};

Conexão de Nós à Direita (Problema 116/117)

var conectaIrmaos = function(noRaiz) {
    if (!noRaiz) return noRaiz;
    let fila = [noRaiz];
    while (fila.length) {
        let tamanhoNivel = fila.length;
        for (let i = 0; i < tamanhoNivel; i++) {
            let no = fila.shift();
            if (i < tamanhoNivel - 1) {
                no.proximo = fila[0]; // Aponta para o próximo na fila do mesmo nível
            }
            if (no.esquerda) fila.push(no.esquerda);
            if (no.direita) fila.push(no.direita);
        }
    }
    return noRaiz;
};

Profundidade Máxima e Mínima

// Profundidade Máxima (podemos usar o tamanho do array de níveis)
var profundidadeMaxima = function(noRaiz) {
    return percorrePorNivel(noRaiz).length;
};

// Profundidade Mínima
var profundidadeMinima = function(noRaiz) {
    let fila = [];
    if (!noRaiz) return 0;
    fila.push(noRaiz);
    let profundidade = 1;
    while (fila.length) {
        let tamanho = fila.length;
        for (let i = 0; i < tamanho; i++) {
            let no = fila.shift();
            if (!no.esquerda && !no.direita) {
                return profundidade; // Encontrou uma folha
            }
            if (no.esquerda) fila.push(no.esquerda);
            if (no.direita) fila.push(no.direita);
        }
        profundidade++;
    }
    return profundidade;
};

Operações em Árvores Binárias

Inverter uma Árvore (Espelhamento)

var inverteArvore = function(noRaiz) {
    function trocaFilhos(no) {
        if (!no) return;
        // Troca os filhos
        let temporario = no.esquerda;
        no.esquerda = no.direita;
        no.direita = temporario;
        trocaFilhos(no.esquerda);
        trocaFilhos(no.direita);
    }
    trocaFilhos(noRaiz);
    return noRaiz;
};

Verificar Árvore Simétrica

var ehSimetrica = function(noRaiz) {
    if (!noRaiz) return true;
    function saoEspelhos(a, b) {
        if (!a && !b) return true;
        if (!a || !b) return false;
        if (a.valor !== b.valor) return false;
        return saoEspelhos(a.esquerda, b.direita) && saoEspelhos(a.direita, b.esquerda);
    }
    return saoEspelhos(noRaiz.esquerda, noRaiz.direita);
};

Contagem de Nós em Árvore Completa

var contaNos = function(noRaiz) {
    let contador = 0;
    function contar(no) {
        if (!no) return;
        contador++;
        contar(no.esquerda);
        contar(no.direita);
    }
    contar(noRaiz);
    return contador;
};

Verificar Árvore Balanceada

var ehBalanceada = function(noRaiz) {
    function obterAltura(no) {
        if (!no) return 0;
        return Math.max(obterAltura(no.esquerda), obterAltura(no.direita)) + 1;
    }
    if (!noRaiz) return true;
    let alturaEsq = obterAltura(noRaiz.esquerda);
    let alturaDir = obterAltura(noRaiz.direita);
    if (Math.abs(alturaEsq - alturaDir) > 1) return false;
    return ehBalanceada(noRaiz.esquerda) && ehBalanceada(noRaiz.direita);
};

Comparra duas Árvores

var saoIguais = function(arvore1, arvore2) {
    if (!arvore1 && !arvore2) return true;
    if (!arvore1 || !arvore2) return false;
    if (arvore1.valor !== arvore2.valor) return false;
    return saoIguais(arvore1.esquerda, arvore2.esquerda) && saoIguais(arvore1.direita, arvore2.direita);
};