AVA1_-_ESTRUTURA_DE_DADOS_I[2] - marcelo

Prévia do material em texto

UNIVERSIDADE VEIGA DE ALMEIDA – UVA 
GRADUAÇÃO EM ANÁLISE E DESENVOLVIMENTO DE SISTEMAS 
 
 
 
ENTREGA DA AVALIAÇÃO - AVA 2 
 
 
 
 
ESTRUTURA DE DADOS I 
MARCELO RICHTER CASSAR 
 
https://uva.instructure.com/courses/38447/grades/140182
SUMÁRIO 
INTRODUÇÃO ................................................................................................................................ 3 
RESOLUÇÃO ................................................................................................................................... 4 
APRESENTAÇÃO ............................................................................................................................. 4 
ALGORÍTIMO ................................................................................................................................. 5 
REFERÊNCIAS ................................................................................................................................. 7 
 
 
 
INTRODUÇÃO 
Busca em árvores binárias 
As árvores binárias de busca são estruturas de dados de árvore binária 
baseada em nós em que todos os nós da subárvore esquerda possuem um 
valor numérico inferior ao nó raiz e todos os nós da subárvore direita possuem 
um valor superior ao nó raiz (FORBELLONE; EBERSPACHER, 2005). 
A Empresa Renalf S/A solicita a você, membro da equipe de 
programadores de computador em linguagem C, que desenvolva um programa 
que seja capaz de manipular uma árvore binária (inclusão e remoção de nós), 
admitindo a escolha dos três processos de busca em profundidade. 
Procedimentos para elaboração do TD 
Nesse contexto, escreva um programa em linguagem C que apresente 
um menu de opções que possibilite executar as seguintes opções: 
* * * MENU DE OPÇÕES * * * 
Incluir nó. 
Remover nó. 
Buscar pré-ordem. 
Buscar em ordem. 
Buscar pós-ordem. 
Opção [0 para encerrar] 
RESOLUÇÃO 
APRESENTAÇÃO 
Este código em linguagem C apresenta a implementação de um programa para 
manipulação de árvores binárias de busca. A estrutura da árvore é baseada em nós, em que cada 
nó possui um valor numérico, e a subárvore esquerda contém valores inferiores ao nó raiz, 
enquanto a subárvore direita contém valores superiores ao nó raiz. 
 
O programa oferece um menu de opções que permite ao usuário realizar operações 
como inclusão e remoção de nós na árvore, além de executar três tipos de busca: pré-ordem, 
em ordem e pós-ordem. O usuário interage com o programa através da escolha numérica das 
opções no menu, com a opção "0" para encerrar a execução. 
 
A estrutura do código compreende a definição da estrutura do nó, funções para 
criação e inserção de nós na árvore, bem como funções para realizar buscas nos diferentes 
modos mencionados. O programa é modular e oferece espaço para expansão, possibilitando a 
implementação de funcionalidades adicionais conforme necessário. 
ALGORITMO 
 
#include <stdio.h> 
#include <stdlib.h> 
 
struct No { 
 int dado; 
 struct No *esquerda, *direita; 
}; 
 
struct No* criarNo(int valor) { 
 struct No* novoNo = (struct 
No*)malloc(sizeof(struct No)); 
 novoNo->dado = valor; 
 novoNo->esquerda = novoNo->direita = 
NULL; 
 return novoNo; 
} 
 
struct No* inserirNo(struct No* raiz, int 
valor) { 
 if (raiz == NULL) { 
 return criarNo(valor); 
 } 
 
 if (valor < raiz->dado) { 
 raiz->esquerda = inserirNo(raiz-
>esquerda, valor); 
 } else if (valor > raiz->dado) { 
 raiz->direita = inserirNo(raiz->direita, 
valor); 
 } 
 
 return raiz; 
} 
 
void percorrer(struct No* raiz, int escolha) 
{ 
 if (raiz != NULL) { 
 if (escolha == 1) { 
 printf("%d ", raiz->dado); 
 } 
 percorrer(raiz->esquerda, escolha); 
 if (escolha == 2) { 
 printf("%d ", raiz->dado); 
 } 
 percorrer(raiz->direita, escolha); 
 if (escolha == 3) { 
 printf("%d ", raiz->dado); 
 } 
 } 
} 
 
int main() { 
 struct No* raiz = NULL; 
 int escolha, valor; 
 
 do { 
 printf("\n1. Incluir no\n"); 
 printf("2. Buscar pre-ordem\n"); 
 printf("3. Buscar em ordem\n"); 
 printf("4. Buscar pos-ordem\n"); 
 printf("0. Encerrar\n"); 
 
 printf("Opcao: "); 
 scanf("%d", &escolha); 
 
 switch (escolha) { 
 case 1: 
 printf("Digite o valor a ser 
incluido: "); 
 scanf("%d", &valor); 
 raiz = inserirNo(raiz, valor); 
 break; 
 
 case 0: 
 printf("Programa encerrado.\n"); 
 break; 
 
 default: 
 printf("Opcao invalida. Tente 
novamente.\n"); 
 } 
 
 if (escolha >= 1 && escolha <= 3) { 
 percorrer(raiz, escolha); 
 printf("\n"); 
 } 
 
 } while (escolha != 0); 
 
 return 0; 
} 
 
TELAS 
 
 
 
 
REFERÊNCIAS 
ASCENCIO, A. F. G.; ARAÚJO, G. S. Estruturas de dados: algoritmos, análise 
de complexidade e implementações em Java e C/C++. São Paulo: Pearson 
Prentice Hall,2010. ISBN: 9788576058816. (Disponível na Biblioteca Virtual) 
PUGA, S.; RISSETTI, G. Lógica de Programação e Estrutura de Dados, com 
aplicações em Java – 3 ed. São Paulo: Pearson Prentice Hall, 2009. ISBN: 
9788543019147. (Disponível na Biblioteca Virtual) 
SIMÕES-PEREIRA, J. M. S. Grafos e redes: teoria e algoritmos básicos – 1 ed. 
Rio deJaneiro: Interciência, 2003. ISBN: 9788571933316. (Disponível na 
Biblioteca Virtual)