A manipulação de árvores binárias é um conceito fundamental na ciência da computação. Abaixo, apresentamos a implementação em Java de uma árvore binária, incluindo a definição do nó, os algoritmos de percurso (pré-ordem, em-ordem e pós-ordem) e a lógica para verificar se uma árvore é subárvore de outra.

1. Definição do Nó da Árvore

A classe base representa a estrutura de cada nó, armazenando um valor inteiro e as referências para os filhos à esquerda e à direita.

public class NoArvore {
    private int valor;
    private NoArvore esquerda;
    private NoArvore direita;

    public NoArvore(int valor) {
        this.valor = valor;
    }

    public NoArvore(int valor, NoArvore esquerda, NoArvore direita) {
        this.valor = valor;
        this.esquerda = esquerda;
        this.direita = direita;
    }

    public int getValor() { return valor; }
    public void setValor(int valor) { this.valor = valor; }
    public NoArvore getEsquerda() { return esquerda; }
    public void setEsquerda(NoArvore esquerda) { this.esquerda = esquerda; }
    public NoArvore getDireita() { return direita; }
    public void setDireita(NoArvore direita) { this.direita = direita; }
}

2. Algoritmos de Percurso

A classe de percursos utiliza recursão para navegar pela estrutura. As implementações foram otimizadas para verificar a nulidade do nó no início de cada chamada, tornando o código mais limpo e direto.

public class PercursosArvore {
    private void exibirNo(NoArvore no) {
        System.out.print(no.getValor() + " ");
    }

    public void percursoPreOrdem(NoArvore raiz) {
        if (raiz == null) return;
        exibirNo(raiz);
        percursoPreOrdem(raiz.getEsquerda());
        percursoPreOrdem(raiz.getDireita());
    }

    public void percursoEmOrdem(NoArvore raiz) {
        if (raiz == null) return;
        percursoEmOrdem(raiz.getEsquerda());
        exibirNo(raiz);
        percursoEmOrdem(raiz.getDireita());
    }

    public void percursoPosOrdem(NoArvore raiz) {
        if (raiz == null) return;
        percursoPosOrdem(raiz.getEsquerda());
        percursoPosOrdem(raiz.getDireita());
        exibirNo(raiz);
    }
}

3. Verificação de Subárvore

Para determinar se uma árvore B está contida em uma árvore A, primeiro buscamos um nó em A com o mesmo valor da raiz de B. Ao encontrar, verificamos se a estrutura subsequente também é idêntica.

public class VerificadorSubarvore {
    public boolean contemSubarvore(NoArvore raizPrincipal, NoArvore raizSubarvore) {
        boolean resultado = false;

        if (raizPrincipal != null && raizSubarvore != null) {
            if (raizPrincipal.getValor() == raizSubarvore.getValor()) {
                resultado = comparaEstruturas(raizPrincipal, raizSubarvore);
            }
            if (!resultado) {
                resultado = contemSubarvore(raizPrincipal.getEsquerda(), raizSubarvore);
            }
            if (!resultado) {
                resultado = contemSubarvore(raizPrincipal.getDireita(), raizSubarvore);
            }
        }
        return resultado;
    }

    private static boolean comparaEstruturas(NoArvore noPrincipal, NoArvore noSubarvore) {
        if (noSubarvore == null) return true;
        if (noPrincipal == null) return false;
        if (noPrincipal.getValor() != noSubarvore.getValor()) return false;

        return comparaEstruturas(noPrincipal.getEsquerda(), noSubarvore.getEsquerda()) &&
               comparaEstruturas(noPrincipal.getDireita(), noSubarvore.getDireita());
    }
}

4. Execução e Testes

O programa pricnipal monta duas estruturas de exemplo e utiliza as classes anteriores para exibir os percursos e validar a relação de subárvore.

public class ExecucaoArvore {
    public static void main(String[] args) {
        NoArvore raizA = new NoArvore(10);
        NoArvore noA1 = new NoArvore(20);
        NoArvore noA2 = new NoArvore(30);
        NoArvore noA3 = new NoArvore(40);
        NoArvore noA4 = new NoArvore(50);
        NoArvore noA5 = new NoArvore(60);
        NoArvore noA6 = new NoArvore(70);

        raizA.setEsquerda(noA1);
        raizA.setDireita(noA2);
        noA1.setEsquerda(noA3);
        noA1.setDireita(noA4);
        noA2.setEsquerda(noA5);
        noA2.setDireita(noA6);

        PercursosArvore traverser = new PercursosArvore();
        System.out.print("Pre-ordem Arvore A: ");
        traverser.percursoPreOrdem(raizA);
        System.out.println();

        NoArvore raizB = new NoArvore(20);
        NoArvore noB1 = new NoArvore(40);
        NoArvore noB2 = new NoArvore(50);

        raizB.setEsquerda(noB1);
        raizB.setDireita(noB2);

        System.out.print("Pre-ordem Arvore B: ");
        traverser.percursoPreOrdem(raizB);
        System.out.println();

        VerificadorSubarvore verificador = new VerificadorSubarvore();
        boolean ehSubarvore = verificador.contemSubarvore(raizA, raizB);
        System.out.println("A Arvore B e subarvore da Arvore A? " + ehSubarvore);
    }
}