4

Amigos estou tendo problema para resolver este exercício, e não sei mais como fazer. Cheguei implementar a árvore com recursividade, mas nao consegui deixar o NÓ vazio e algumas folhas com número, conforme o exercício. Em seguida preciso somar os itens que estão nas folhas.

No.java

public class No {

    public int valor;
    public No direito;
    public No esquerdo;

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

ArvoreBinaria.java

public class ArvoreBinaria {

    private No raiz;

    public void inserir(int valor) {
        if (raiz == null) {
            raiz = new No(valor);
        } else {
            No novo = new No(valor);
            inserir(raiz, novo);

        }

    }

    private void inserir(No arvore, No novo) {
        if (novo.valor > arvore.valor) {
            if (arvore.direito == null) {
                arvore.direito = novo;
            } else {
                inserir(arvore.direito, novo);
            }
        } else {
            if (arvore.esquerdo == null) {
                arvore.esquerdo = novo;
            } else {
                inserir(arvore.esquerdo, novo);
            }
        }
    }

EXERCÍCIO

- Uma árvore tem nós;
- Um nó pode ou não ter outros nós;
- Um nó, não folha, tem sempre um nó do lado direito e outro do lado esquerdo
- As folhas não tem nós abaixo;
- As folhas têm associado um número inteiro

A figura seguinte representa 3 instâncias de árvores binárias

árvores binárias

Pretende-se implementar um algoritmo em Java que permita a contrução de instância deste tipo. Deverá ter um método que devolva a soma da árvore, ou seja a soma das folhas.

Dicas:

  • Um nó, não folha, tem sempre um nó à esquerda e um nó a direita
  • Após a contrução de um nó, será possivel adicionar outros nós
  • Recursividade
  • Não usar tipo complexos de Java (HashMaps, Lists e etc)

1 Resposta 1

4

Aqui vai a sua classe de árvore binária. Acrescentei na classe No e na classe ArvoreBinaria os métodos soma(). Também coloquei o toString() para poder mostrar a estrutira da árvore.

class ArvoreBinaria {

    private No raiz;

    public void inserir(int valor) {
        if (raiz == null) {
            raiz = new No(valor);
        } else {
            No novo = new No(valor);
            inserir(raiz, novo);
        }
    }

    private void inserir(No arvore, No novo) {
        if (novo.valor > arvore.valor) {
            if (arvore.direito == null) {
                arvore.direito = novo;
            } else {
                inserir(arvore.direito, novo);
            }
        } else {
            if (arvore.esquerdo == null) {
                arvore.esquerdo = novo;
            } else {
                inserir(arvore.esquerdo, novo);
            }
        }
    }

    public int soma() {
        return raiz == null ? 0 : raiz.soma();
    }

    @Override
    public String toString() {
        return raiz == null ? "*" : raiz.toString();
    }

    private static class No {

        private int valor;
        private No direito;
        private No esquerdo;

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

        public int soma() {
            return valor
                    + (direito == null ? 0 : direito.soma())
                    + (esquerdo == null ? 0 : esquerdo.soma());
        }

        @Override
        public String toString() {
            return (esquerdo == null ? "*" : "(" + esquerdo + ")")
                    + valor
                    + (direito == null ? "*" : "(" + direito + ")");
        }
    }
}

Aqui vai uma classe de teste:

class Teste {
    public static void main(String[] args) {
        ArvoreBinaria ab = new ArvoreBinaria();
        System.out.println(ab);
        ab.inserir(5);
        System.out.println(ab);
        ab.inserir(10);
        System.out.println(ab);
        ab.inserir(15);
        System.out.println(ab);
        ab.inserir(2);
        System.out.println(ab);
        ab.inserir(4);
        System.out.println(ab);
        ab.inserir(6);
        System.out.println(ab);
        ab.inserir(8);
        System.out.println(ab);
        ab.inserir(20);
        System.out.println(ab);
        System.out.println(ab.soma());
    }
}

Eis a saída:

*
*5*
*5(*10*)
*5(*10(*15*))
(*2*)5(*10(*15*))
(*2(*4*))5(*10(*15*))
(*2(*4*))5((*6*)10(*15*))
(*2(*4*))5((*6(*8*))10(*15*))
(*2(*4*))5((*6(*8*))10(*15(*20*)))
70

Observe pela saída que a árvore está sendo montada conforme o esperado e que a soma também está correta.

Veja aqui funcionando no ideone.

5
  • @Slinkey99 Se esta resposta resolveu o seu problema e não te restar mais nenhuma dúvida, marque-a como aceita/correta ao clicar no "✅" aqui do lado, o que também marca a sua pergunta como respondida/solucionada. Se por outro lado, ainda não estiver satisfeito, deixe um comentário e vamos esclarecer. Commented 29/10/2017 às 22:47
  • Olá Victor, agradeço pela ajuda. Fiquei com uma duvida quando você usou os sinais ? e tambem os dois ponto : Poderia traduzir por favor. Isso é o que? O que posso estudar para aprender isso? Obrigado. public int soma() { return valor + (direito == null ? 0 : direito.soma()) + (esquerdo == null ? 0 : esquerdo.soma()); }
    – Slinkey99
    Commented 29/10/2017 às 22:49
  • @Slinkey99 É o operador ternário. Se o que está antes do ? for verdadeiro, então o resultado é o que está entre o ? e o :. Se for falso, o resultado é o que está depois do :. Commented 29/10/2017 às 22:50
  • Vou dar uma olhada sobre isso, nao havia usado antes. Obrigado.
    – Slinkey99
    Commented 29/10/2017 às 22:52
  • @VictorStafusa , pelo que entendi, você está levando em consideração todos os nós na soma, quando o pedido foi apenas soma das folhas. Eu diria que a soma final deveria ter sido 32. A correção seria o método public int somaFolhas() { return (esquerdo == null && direito == null)? valor: ((esquerdo != null? esquerdo.somaFolha():0) + (direito != null? direito.somaFolha(): 0); } Commented 30/10/2017 às 5:05

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .