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
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 (
HashMap
s,List
s e etc)