(ENADE 2008) Um programador propôs um algoritmo não-recursivo para o percurso em preordem de uma árvore binária com as seguintes características: - Cada nó da árvore binária é representado por um registro com três campos: chave, que armazena seu identificador; esq e dir, ponteiros para os filhos esquerdo e direito, respectivamente. - O algoritmo deve ser invocado inicialmente tomando o ponteiro para o nó raiz da árvore binária como argumento. - O algoritmo utiliza push() e pop() como funções auxiliares de empilhamento e desempilhamento de ponteiros para nós de árvore binária, respectivamente. A seguir, está apresentado o algoritmo proposto, em que λ representa o ponteiro nulo. Procedimento preordem (ptraiz : PtrNoArvBin) Var ptr : PtrNoArvBin; ptr := ptraiz; Enquanto (ptr ≠ λ) Faça escreva (ptr↑.chave); Se (ptr↑.dir ≠ λ) Então push(ptr↑.dir); Se (ptr↑.esq ≠ λ) Então push(ptr↑.esq); ptr := pop(); Fim_Enquanto Fim_Procedimento Com base nessas informações e supondo que a raiz de uma árvore binária com n nós seja passada ao procedimento preordem(), julgue os itens seguintes. I O algoritmo visita cada nó da árvore binária exatamente uma vez ao longo do percurso. II O algoritmo só funcionará corretamente se o procedimento pop() for projetado de forma a retornar λ caso a pilha esteja vazia. III Empilhar e desempilhar ponteiros para nós da árvore são operações que podem ser implementadas com custo constante. IV A complexidade do pior caso para o procedimento preordem() é O(n). Assinale a opção correta.
Respostas
Boa noite!
Para resolver essa questão iremos avaliar as alternativas e ver as que estão corretas e erradas, trabalhando com comentários ok? Vamos lá!
I O algoritmo visita cada nó da árvore binária exatamente uma vez ao longo do percurso.
CORRETA! Pelo processo da árvore binária, temos um pré processo estabelecido, logo se tem uma ordem onde a árvore é percorrida, tendo todos os seus nós visitados apenas 1 vez.
II O algoritmo só funcionará corretamente se o procedimento pop() for projetado de forma a retornar λ caso a pilha esteja vazia.
CORRETA! Ocorre sim a utilização da pilha, isso porque o algoritimo organiza os nós não visitados em forma de coleção. Sendo o Pop a operação que retorna ao valor nulo.
III Empilhar e desempilhar ponteiros para nós da árvore são operações que podem ser implementadas com custo constante.
CORRETA! Ambas operações podem ser geradas usando estruturas encadeadas ou estáticas.
IV A complexidade do pior caso para o procedimento preordem() é O(n)
CORRETA! É necessária a visitação de todos os nós, a cada visita um número de operações é gerado. No caso representamos pela função O(n) onde o é número de operações constantes e n os passos.