Arvore Binaria em Java

Prévia do material em texto

Arvores binarias em JAVA
1. Árvores binárias são estruturas de dados nas quais cada nodo possui no máximo dois filhos. Observe a árvore a
seguir:
C.  O nodo 6 é neto da raiz da árvore.
O nodo 49 é filho do nodo 71 e pai do nodo 50.
O nodo 44 está no quarto nível da árvore, a raiz está no primeiro nível, o nodo 71 está no segundo nível, o
nodo 49 está no terceiro nível e, por fim, o nodo 44 está no quarto nível.
O nodo 6 é neto da raiz da árvore, pois o pai do nodo 6 é o nodo 2, que é filho da raiz. Logo, este nodo é avô
do nodo 6.
Os nodos 28 e 44 não são irmãos. Para isso, eles teriam de possuir o mesmo pai, o que não ocorre.
Há três nodos de grau 2 nessa árvore: 35, 71 e 49.
2. O método de inserção em uma árvore binária é sensível à ordem em que os dados são inseridos na árvore. Portanto, a
ordem em que os dados são inseridos influencia a aparência final da árvore. Observe a árvore a seguir:
E. 500 — 900 — 300 — 800 — 600 — 400 — 150.
De forma genérica, em uma sequência de inserção válida, a raiz é o primeiro nodo a ser inserido, e um nodo
pai sempre é inserido antes de seus filhos.
A única sequência que segue essa regra é: 500 — 900 — 300 — 800 — 600 — 400 — 150.
Nas demais alternativas, a ordem dos dados produziria uma distorção na árvore. O nodo 400, se inserido antes
do nodo 300, alteraria suas posições na árvore. O nodo 600, se inserido antes dos nodos 900 e 800, também
alteraria a árvore. A primeira inserção do nodo 900 se tornaria a raiz da árvore e afetaria a posição de todos os
demais nodos. Também é errada a inserção do nodo 800 antes do nodo 900.
3 . A remoção de nodos de uma árvore binária requer que se preste atenção ao grau do nodo que será removido.
Afinal, dependendo dessa informação, diferentes medidas deverão ser adotadas para que a remoção ocorra com sucesso,
mantendo a ordenação dos nodos da árvore. Suponha que se deseja remover o nodo 36 da árvore a seguir:
B. 33.
Existem duas regras para a escolha do nodo substituto: ou se escolhe o maior nodo da subárvore esquerda, ou
o menor nodo da subárvore direita do nodo que será removido. Nesse caso, a segunda alternativa contém o
maior nodo da subárvore esquerda, que é o nodo 33. Os nodos 20, 29 e 32 estão na subárvore esquerda, mas
não são os maiores nodos. O nodo 40, que está na subárvore direita, não é o maior nodo dessa subárvore. 
4. Árvores são estruturas de dados naturalmente recursivas, pois cada subárvore de um nodo pode ser vista como uma
árvore com raiz no filho daquele nodo. Logo, é comum que os métodos que manipulam essa estrutura de dados sejam
recursivos. Considere o método a seguir, que foi implementado na classe ArvoreBinaria:
C. 78 : 3.
O método apresentado busca o nodo informado como parâmetro na árvore e imprime o seu valor, juntamente
ao nível da árvore em que ele se encontra. Na situação proposta no exercício, seria impresso o valor 78 : 3. As
alternativas 78 : 2 e 78 : 4 possuem uma informação incorreta relativa ao nível que seria impresso. Já as
demais alternativas imprimem também as informações do nodo filho, que não são impressas pela função dada.
5. Para determinadas aplicações, é interessante percorrer todos os nodos de uma árvore. Para isso, pode-se utilizar um
dos três algoritmos de caminhamento: prefixado, pós-fixado e em ordem. Observe a árvore binária a seguir:
A. 22 — 20 — 27 — 25 — 45 — 40 — 30.
A primeira sequência contém o caminhamento pós-fixado pela árvore. A segunda sequência contém o
caminhamento prefixado. Já a quinta sequência contém o caminhamento em ordem pela árvore. As demais
sequências contêm caminhamentos aleatórios pela árvore.