Lista Árvores Genéricas

Prévia do material em texto

LISTA Árvores Genéricas
Estruturas de Dados II
Prof. Murilo Ybanez
Qual o resultado da impressão dos elementos da árvore abaixo a partir de caminhamentos em pré-ordem, in-ordem e pós-ordem?
Qual das seguintes expressões posfixas é equivalente à expressão infixa A+(B/C)*((D-E)/F)?
ABC/-DE*F+/
ABC/DE-/F+*
ABC/DE-F/*+
ABC/D-EF*/+
ABD/CE+/F-*
O número máximo de nos no nível i de uma árvore de grau máximo 2 é (considere o nível da raiz igual a 1):
2i+1, i ≥ 0
2i-1, i ≥ 1
2i, i ≥ 1
2i + 1, i ≥ 1
2i - 1, i ≥ 1
Faça um algoritmo que percorre e imprime os elementos de uma árvore em pré-ordem, in-ordem e pós-ordem, adotando as seguintes representações:
Com um número máximo de filhos, usando array.
Sem um número máximo de filhos, usando ponteiros.
Elabore um algoritmo que imprima a lista com os elementos de um determinado nível k de uma árvore, assumindo uma estrutura baseada em ponteiros.
Forneça um algoritmo para percorrer uma árvore em nível (sugestão: use uma fila como estrutura auxiliar).
Elabore um algoritmo que conta o número de folhas de uma árvore, assumindo uma estrutura baseada em ponteiros.
Elabore um algoritmo que obtém a altura de uma árvore, assumindo uma estrutura baseada em ponteiros.
As informações relativas a uma determinada aplicação estão armazenadas em uma estrutura de árvore genérica dentro de um array. Cada elemento deste array representa um nodo da árvore, que é definido pela estrutura abaixo com dois campos: info e grau:
struct No {
 char info;
 int grau;
};
No arv[100];
A estrutura da árvore é representada armazenando, após cada nodo, seu grau e seus descendentes diretos, como no exemplo a seguir: 
Com base nesta estrutura, escreva um algoritmo que recebe este array e um caractere c, e imprime os caracteres e os graus dos descendentes do nodo que contém c. Caso o caractere c não seja encontrado em nenhum nodo da árvore, o algoritmo deverá escrever uma mensagem.