Rodrigo Ferreira
31/12/1969 • 21:00
Gabarito: b)
Primeiro, precisamos entender que a árvore binária de busca (ABB) organiza as chaves de forma que, para cada nó, as chaves menores ficam na subárvore esquerda e as maiores na subárvore direita.
Ao inserir as chaves {Lina, Ana, Lia, Ada, Lua, Sol, Cris, Bia, Rita, Mel, Rosa, Val} na ABB, a estrutura resultante terá uma ordem específica que determina os percursos.
O percurso em pré-ordem visita o nó raiz, depois a subárvore esquerda e depois a direita. A sequência apresentada em I não corresponde a essa ordem para a ABB formada, pois a ordem dos elementos não respeita a estrutura da árvore.
O percurso em ordem simétrica (in-order) visita a subárvore esquerda, depois o nó raiz e depois a subárvore direita. Para uma ABB, esse percurso deve retornar as chaves em ordem crescente. A sequência em II está em ordem decrescente, o que indica que está invertida, mas ainda assim é um percurso válido, apenas invertido.
O percurso em nível (level-order) visita os nós por níveis, da esquerda para a direita. A sequência em III está coerente com a estrutura da ABB formada, pois respeita a ordem de inserção e a organização da árvore.
O percurso em pós-ordem visita a subárvore esquerda, depois a direita e por último o nó raiz. A sequência em IV não corresponde ao pós-ordem da ABB formada, pois a raiz deveria ser o último elemento visitado, o que não ocorre.
Fazendo uma segunda análise, o percurso em ordem simétrica (II) está invertido, o que não é o padrão esperado para uma ABB, que deve apresentar as chaves em ordem crescente. Portanto, II não está correto.
Assim, a única alternativa que apresenta percursos corretos é a que indica II e III, que é a letra b.
Portanto, a resposta correta é b, conforme o gabarito oficial e a resposta mais comentada.
Primeiro, precisamos entender que a árvore binária de busca (ABB) organiza as chaves de forma que, para cada nó, as chaves menores ficam na subárvore esquerda e as maiores na subárvore direita.
Ao inserir as chaves {Lina, Ana, Lia, Ada, Lua, Sol, Cris, Bia, Rita, Mel, Rosa, Val} na ABB, a estrutura resultante terá uma ordem específica que determina os percursos.
O percurso em pré-ordem visita o nó raiz, depois a subárvore esquerda e depois a direita. A sequência apresentada em I não corresponde a essa ordem para a ABB formada, pois a ordem dos elementos não respeita a estrutura da árvore.
O percurso em ordem simétrica (in-order) visita a subárvore esquerda, depois o nó raiz e depois a subárvore direita. Para uma ABB, esse percurso deve retornar as chaves em ordem crescente. A sequência em II está em ordem decrescente, o que indica que está invertida, mas ainda assim é um percurso válido, apenas invertido.
O percurso em nível (level-order) visita os nós por níveis, da esquerda para a direita. A sequência em III está coerente com a estrutura da ABB formada, pois respeita a ordem de inserção e a organização da árvore.
O percurso em pós-ordem visita a subárvore esquerda, depois a direita e por último o nó raiz. A sequência em IV não corresponde ao pós-ordem da ABB formada, pois a raiz deveria ser o último elemento visitado, o que não ocorre.
Fazendo uma segunda análise, o percurso em ordem simétrica (II) está invertido, o que não é o padrão esperado para uma ABB, que deve apresentar as chaves em ordem crescente. Portanto, II não está correto.
Assim, a única alternativa que apresenta percursos corretos é a que indica II e III, que é a letra b.
Portanto, a resposta correta é b, conforme o gabarito oficial e a resposta mais comentada.