teste

Árvores – atividade de laboratório

1

Árvores – atividade de laboratório
1. Especificação do programa
O objetivo desta atividade é criar um programa em C que permita a construção manual de árvores ordenadas através de um “prompt” de comando, para teste de algoritmos relacionados a esta estrutura – percursos, cálculo da profundidade e do grau etc. A informação contida em cada nó será uma string e o programa se limitará a árvores de grau no máximo 10.
O programa deve começar definindo a raiz da árvore. Suponhamos que a raiz seja definida como a string “A”. Inicialmente a raiz será o nó ativo, sobre o qual atuarão os comandos. O nó ativo será identificado com uma seta.
O prompt de comando será identificado por “comando>”: comando> Um filho do nó ativo é criado com o comando “novo”: comando> novo B

O filho de cada nó será numerado, iniciando com 0. Neste caso, o nó B é o filho 0 de A. Cada nó pode ter até 10 filhos, portanto até o filho número 9. comando> novo C
Podemos mudar o nó ativo com o comando “filho”: comando> filho 0
Este comando muda o nó ativo para o filho 0 de A.
Agora podemos criar filhos de B, que é o nó ativo atual: comando> novo C comando> novo D
Note que deve ser possível que dois nós diferentes contenham a mesma informação (neste caso, a informação C está repetida).

Podemos novamente mudar o nó ativo e criar mais um nó: comando> filho 1 comando> novo F

Árvores – atividade de laboratório

2

Podemos retroceder o nó ativo com o comando pai: comando> pai

Em seguida, criar mais um filho de B: comando> novo G

Retrocedendo mais uma vez, podemos criar um novo nó da raiz: comando> pai comando> novo H

comando> filho 2 comando> novo I

Fica claro, assim, que é possível criar qualquer árvore com os comandos “novo”, “filho” e
“pai”. Queremos também implementar vários outros comandos, por exemplo “pre_ordem” para a listagem em pré-ordem, “pos_ordem” para a listagem em “pos_ordem”, “profundidade” para o