Concursos públicos

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.

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 8 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.