Tanto altura com a quantidade de elementos são bem mais fáceis fazendo recursivamente utilizando um algoritmo Depth First Search (DFS), assim:
public int nivel(Node no){
if (no == null) return 0;
return (int)Math.max(nivel(no.getNodeEsquerda())+1, nivel(no.getNodeDireita())+1);
}
Utilizando Breadth First Search (BFS), que é o seu exemplo, estes ficam mais complexos e/ou extensos, apesar de terem outras propriedades, como por exemplo, percorrerem nível a nível em vez de em profundidade.
O seu código está a fazer o seguinte:
- Começa do 8 aumenta para nível 1 e empilha o 3 e o 10.
- Depois analisa o 3, aumenta o nível para 2 e empilha o 1 e o 6
- A seguir vai para o 10, e aumenta o nível para 3 empilhando o 13
Neste momento já não está certo pois o 3
e o 10
fazem parte ainda do mesmo nível. Assim o código irá aumentar para cada nó dando a quantidade de nós em vez da altura.
Uma solução que eu vejo é empilhar também o nível do nó para que cada nó considere o nível do nó pai para descobrir o seu, sendo o seu sempre o do pai mais 1. Para facilitar pode-se criar uma classe auxiliar que tenha uma referência para um Node
e o seu nivel
, modificando a Queue
para utilizar esse tipo
Exemplo:
private class NodeNivel { //classe para ter No e Nivel
public Node no;
public int nivel;
public NodeNivel(Node no, int nivel){
this.no = no;
this.nivel = nivel;
}
}
public int nivel(){
Node aux = raiz;
int nivel = 0;
if (aux == null) throw new IllegalArgumentException("Arvore vazia.");
Deque<NodeNivel> fila = new ArrayDeque<>(); //Agora Deque<NodeNivel>
//cada vez que empilha leva nivel tambem,que é 1 para a raiz
fila.add(new NodeNivel(aux, 1));
while (!fila.isEmpty()) {
NodeNivel atual = fila.removeFirst(); //Agora NodeNivel
//estes ifs agora empilham NodeNivel aumentando o nivel em 1
if (atual.no.getNodeEsquerda() != null)
fila.add(new NodeNivel(atual.no.getNodeEsquerda(), atual.nivel+1));
if (atual.no.getNodeDireita() != null)
fila.add(new NodeNivel(atual.no.getNodeDireita(), atual.nivel+1));
//verifica e atualiza o nivel maximo
if (atual.nivel > nivel)
nivel = atual.nivel;
}
return nivel;
}