MAPA SUB - ESTRUTURA DE DADOS II - 52/2021 1ª QUESTÃOExistem várias formas de se implementar uma árvore
MAPA SUB - ESTRUTURA DE DADOS II - 52/2021 1ª QUESTÃOExistem várias formas de se implementar uma árvore binária. A mais simples delas é usar um vetor de nós. Dessa forma, cada nó possui pelo menos três valores: uma referência para o pai do nó, uma referência para o filho à esquerda do nó e mais uma outra referência para o filho à direita do respectivo nó. O atributo "pai" vai apontar para a posição na qual o pai do nó se encontra, no vetor. O atributo "esquerda" vai armazenar aposição da raiz da sub-árvore à esquerda do nó, e o atributo "direita" guarda a posição da raiz da sub-árvore direita do nó, no vetor. Além disso, é relevante estabelecer um atributo "dado" que irá armazenar o conteúdo do nó.
É possível adicionar algumas regras à inserção de dados em uma árvore para que ela se torne ordenada. Assim, sempre que um novo dado estiver para ser adicionado junto à árvore, ele será comparado com o nóraiz. Se ele é menor do que a raiz, deverá ser adicionado na sub-árvore esquerda, caso contrário na sub-árvore direita.
Considere que, no seu primeiro estágio, ao realizar um teste no seu programa que implementa árvores binárias, você inseriu os números de seu RA (da esquerda para a direita) como se cada algarismo fosse um nó na árvore. Dessa forma, altere o código-fonte dado para que seu programa, durante a execução, monte uma árvore binária a partir dos dígitos de seu RA. O seu programa não deve realizar a inserção automaticamente ordenada, ou seja, não é preciso desenvolver um método que realize a inserção ordenadamente. Você mesmo pode construir a árvore (via inserções simples, porém seguindo as regras de inserção ordenada), de maneira a compor a árvore ordenada com os números de seu RA. Além disso, você precisará criar uma função que seja capaz de realizar o percurso pós-ordem na árvore recém-criada, partindo da raiz e imprimindo na tela os nós visitados de acordo com esse método.
Por exemplo, considere que seu RA é igual a 61207895. Abaixo temos um exemplo de como sua árvore ordenada deveria ser, bem como o resultado do caminhamento pós-ordem quando executado a partir da raiz da respectiva árvore.
Visitação pós-ordem: 0 2 1 5 9 8 7 6
O QUE ENVIAR:
1.
Enviar seu código-fonte completo, com extensão “.c”.
Observação
: A correção será feita em ambiente Bloodshed Dev C++, no padrão C ANSI. Assim, caso o aluno tenha desenvolvido seu código em outra IDE/Compilador, é importante que o aluno garanta que seu código também é compilável/executável em ambiente Dev C++. Essa é uma responsabilidade do aluno, e não da equipe de correção.
1 Resposta
Clique aqui para adicionar a sua resposta.
Mais perguntas de Informática
Informática
A informática é uma área em constante evolução e desenvolvimento. Para aproveitar ao máximo os benefícios desta área, é importante manter-se...
vitoriaheleen - há 2 anos
Informática
A informática é uma área importante que está cada vez mais presente em nossas vidas. Se você deseja aprender mais sobre ela, aqui estão algumas...
Jsydhsjsksndbdhydehehehdhhdh - há 2 anos
Informática
A informática é uma área em constante evolução, com novas tecnologias surgindo a todo momento. Para se manter informado e atualizado, é...
Gabrielpereira Caio - há 2 anos
Informática
A informática é a ciência que estuda o armazenamento, a recuperação, a transmissão e a manipulação de informações. Ela se baseia na...
Jjjjkkkkk - há 2 anos
Informática
A Informática é uma área de conhecimento que se dedica ao estudo, aplicação e desenvolvimento de tecnologias de computação. Ela abrange diversas...
RafaelLima Tainaraie - há 2 anos
Informática
A informática é uma área de estudo que abrange a tecnologia da computação e seus usos na vida cotidiana. Ela está envolvida em quase todos os...
Gui Alisont Alison - há 2 anos
Informática
aryadnesanttos15
As árvores binárias são interessantes considerando a forma que as mesmas são percorridas. Distintos algoritmos possibilitam esse processo, entre eles estão os de busca em largura e busca em profundidade.
A questão exemplifica um outro tipo de busca e percurso, visto que o caminhamento pré-ordem na árvore binária deve partir da raiz a 5 e em seguida ir até 7, 2, 3, 1, 8, 6, após ir até G e por sim, se encerrar em 9.
Bons estudos!