Questão 16849

• Banca: CESPE / CEBRASPE
• Órgão: TRE-AL
• Ano: 2004
• Provas: CESPE - 2004 - TRE-AL - Analista Judiciário - Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Busca

A atividade de programação requer conhecimento técnico de
diversas formas de algoritmos e estruturas de controle e de dados.
Acerca dos elementos técnicos da atividade de programação,
julgue os itens a seguir.

Um procedimento correto para determinar o sucessor de um
nodo N em uma árvore de busca binária é o seguinte:
primeiro, localiza-se o nodo N; em seguida, com o ponteiro
direito de N, obtém-se o nodo ND e, a partir de ND, faz-se
o percurso de todos os possíveis ponteiros esquerdos até que
seja alcançado o fim da ramificação, cujo nodo final é o
sucessor de N.

• C. Certo
• E. Errado

Gabarito: C

Comentários

• Aqui temos um comentário acerca disso: http://equipe.nce.ufrj.br/adriano/c/apostila/arvore.htmEsse caso envolve tentar remover um nó com dois filhos em uma árvore binária.Este nó (sucessor) é um descendente que está na subárvore da direita do nó e corresponde ao nó mais à esquerda desta árvore. Ele não tem filhos à esquerda e a sua árvore à direita pode ser movida para o lugar de s.
•          m
      /           \
     i               q
   /   \          /       \
  h    k        o        s
       /  \     /  \      /
      j    l   n   p    r
  
  Nesta árvore temos um exemplo em que este algoritmo não funciona. Se buscarmos "n" e utilizarmos seu ponteiro direito para obter seu sucessor nada encontraremos, pois o mesmo é nulo, seria preciso retornar um nível para encontramos "o".
  
  Para que o algoritmo esteja completo é preciso, caso o ponteiro direito seja nulo, retornar ao nó pai e esté será seu sucessor. Caso não haja pai (se "n" for o nó raiz da árvore) não há sucessor.
  
  Desta forma a questão deveria estar "Errada"
• A questão está correta. 
  
  Em uma árvore de busca binária podemos ter uma regra de inserção que seguem duas regras:
  
  - os elementos da subárvore a direita do nó N possuem valor maior que N
  - os elementos da subárevore à equerda do nó N possuem valor menor ou igual que N. 
  
  desse modo, para acharmos o valor sucessor de N, devemos caminhar para a subárvore a direita de N e a partir dela percorrermos a subárvore esquerde sucessivamente até encontrarmos o fim dela. Esse elemento será chamado de elemento sucessor. 
  
  por exemplo. 
  
                                                10
                          5                                  20                           
                   3            8                  16              30
                                                12        17
                                                  
  Nessa árvore, o elemento sucesso de 10 é 12. E o elemento sucesso de 20 é 30. 
• Erick,
  
  Usando o algoritmo descrito pela banca e o seu exemplo, por favor, qual o sucessor de 17? =)
  
  Concordo com o João Guedes Júnior, esta questão está ERRADA.