Buscar

arvoreFinal

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
struct elemento{
 struct elemento * topo;
 int num;
 struct elemento * menor;
 struct elemento * maior;
};
struct ordem{
 int num;
 struct ordem *proximo;
 struct ordem *anterior;
};
int cont;
void inserir(struct elemento **endarvore, struct elemento *arvore,int a){
 if(arvore == NULL){
 arvore = (struct elemento *) malloc(sizeof(struct elemento));
 (*arvore).num = a;
 (*arvore).topo = NULL;
 (*arvore).menor = NULL;
 (*arvore).maior = NULL;
 *endarvore = arvore;
 printf("Numero %d gravado = %d\n",++cont,arvore->num);
 }else{
 while(arvore->topo != NULL){
 arvore = arvore->topo;// faz com que volte para o topo da arvore antes de inserir elementos
 }
 struct elemento *novo, *aux;
 aux = arvore;
 int i = 0;
 while(i == 0){
 if((*aux).num == a){// se já existe então não faz nada
 printf("elemento ja existe\n");
 i++;
 }else if((*aux).num < a){// se o número é maior
 if((*aux).maior != NULL){
 aux = (*aux).maior;
 printf("Numero %d eh maior que o anterior\n",aux->num);
 }else{
 novo = (struct elemento*) malloc ( sizeof(struct elemento));
 (*aux).maior = novo;
 (*novo).num = a;
 (*novo).topo = aux;
 (*novo).menor = NULL;
 (*novo).maior = NULL;
 printf("Numero %d gravado = %d\n",++cont,novo->num);
 i++;
 }
 }else{// se o número é menor
 if((*aux).menor != NULL){
 aux = (*aux).menor;
 printf("Numero %d eh menor que o anterior\n",aux->num);
 }else{
 novo = (struct elemento*) malloc ( sizeof(struct elemento));
 (*aux).menor = novo;
 (*novo).num = a;
 (*novo).topo = aux;
 (*novo).menor = NULL;
 (*novo).maior = NULL;
 i++;
 printf("Numero %d gravado = %d\n",++cont,novo->num);
 }
 }
 }
 }
}
void encontrar(struct elemento *arvore,int a){
 struct elemento *aux;
 while(arvore->topo != NULL){
 arvore = arvore->topo;// faz com que volte para o topo da arvore antes de inserir elementos
 }
 aux = arvore;
 int i = 0;
 while(i == 0){
 if((*aux).num == a){// se já existe então não faz nada
 printf("elemento numero %d encontrado\n",aux->num);
 i++;
 }else if((*aux).num < a){// se o número é maior
 if((*aux).maior != NULL){
 aux = (*aux).maior;
 printf("Numero %d eh maior que o anterior\n",aux->num);
 }else{
 printf("Numero %d nao foi gravado ainda\nDeseja gravar?\nDigite 1 para sim");
 scanf("%d",&i);
 setbuf(stdin,NULL);
 if(i == 1){
 struct elemento *novo;
 novo = (struct elemento*) malloc ( sizeof(struct elemento));
 (*aux).menor = novo;
 (*novo).num = a;
 (*novo).topo = aux;
 (*novo).menor = NULL;
 (*novo).maior = NULL;
 printf("Numero %d gravado = %d\n",++cont,novo->num);
 }
 i++;
 }
 }else{// se o número é menor
 if((*aux).menor != NULL){
 aux = (*aux).menor;
 printf("Numero %d eh menor que o anterior\n",aux->num);
 }else{
 printf("Numero %d nao foi gravado ainda\nDeseja gravar?\nDigite 1 para sim");
 scanf("%d",&i);
 setbuf(stdin,NULL);
 if(i == 1){
 struct elemento *novo;
 novo = (struct elemento*) malloc ( sizeof(struct elemento));
 (*aux).menor = novo;
 (*novo).num = a;
 (*novo).topo = aux;
 (*novo).menor = NULL;
 (*novo).maior = NULL;
 printf("Numero %d gravado = %d\n",++cont,novo->num);
 }
 i++;
 }
 }
 }
}
void inserirOrdem(struct ordem **endLista, int a){
 struct ordem *lista = *endLista;
 if(lista == NULL){
 lista = (struct ordem *) malloc(sizeof(struct ordem));
 lista->num = a;
 lista->anterior = NULL;
 lista->proximo = NULL;
 *endLista = lista;
 }else{
 struct ordem *novo;
 novo = (struct ordem*) malloc(sizeof(struct ordem));
 novo->num = a;
 novo->anterior = lista;
 lista->proximo = novo;
 novo->proximo = NULL;
 *endLista = novo;
 }
}
int verificaOrdem(struct ordem **endLista, int n){
 int flag = 1;
 struct ordem *lista = *endLista;
 if(lista != NULL){
 while(lista->anterior != NULL){
 lista = lista->anterior;
 }
 }
 while(lista != NULL){
 if(lista->num == n){
 flag = 0;
 break;
 }
 lista = lista->proximo;
 }
 return flag; // retorna um se nao encontra o elemento no vetor.
}
void imprimeLista(struct ordem **endLista){
 struct ordem *lista ;
 lista = *endLista;
 if(lista != NULL){
 while(lista->anterior != NULL){
 lista = lista->anterior;
 }
 }
 printf("Os elementos da arvore ordenados sao:\n\n");
 while(lista != NULL){
 printf("-%d",lista->num);
 lista = lista->proximo;
 }
 printf("-\n\n");
}
void preOrdem(struct elemento **endArvore){
 struct elemento *arvore;
 arvore = *endArvore;
 struct ordem *lista = NULL;
 int flag = 1;
 while(flag == 1){
 if(verificaOrdem(&lista,arvore->num)){//primeira pergunta, se não encontrar é verdade
 if(arvore->menor != NULL){//verifica se existe um nó a esquerda, se existir vai para esquerda
 arvore = arvore->menor;
 if(!verificaOrdem(&lista,arvore->num)){//se encontrar é verdade
 arvore = arvore->topo;//sobe de volta para evitar laço infinito
 inserirOrdem(&lista,arvore->num);
 }
 }else{// se não existir inseri no vetor.
 inserirOrdem(&lista,arvore->num);
 }
 }else{
 if(arvore->maior != NULL){
 arvore = arvore->maior;
 while(!verificaOrdem(&lista,arvore->num)){//se encontrar é verdade, é para evitar repetitividade
 if(arvore->topo == NULL){// se estiver no topo e o topo já foi adicionado então termine o processo
 flag = 0;
 break;
 }
 arvore = arvore->topo;// sobe de volta um nível
 }
 }else{
 if(arvore->topo == NULL){// se estiver no topo e o topo já foi adicionado então termine o processo
 flag = 0;
 }else{// se não estiver no topo sobe mais um nível, retornando para o topo.
 arvore = arvore->topo;
 }
 }
 }
 }
 imprimeLista(&lista);
}
char * retornaStr(struct elemento * n){
 char *s;
 s = (char *) malloc(8 * sizeof(char));
 if(n == NULL)
 s = "vazio";
 else{
 sprintf(s,"%d",n->num);
 }
 return s;
}
int remover(struct elemento **endArvore,int menu){
 struct elemento *aux, *pai;
 aux = *endArvore;
pai = aux->topo;
 if(aux->maior == NULL && aux->menor == NULL){
 *endArvore = pai;
 if(pai == NULL){
 printf("elemento unico\n");
 menu = 5;
 }else{
 if(pai->menor == aux)
 pai->menor = NULL;
 else if(pai->maior == aux)
 pai->maior = NULL;
 }
 free(aux);
 aux = NULL;
 }else if(aux->maior != NULL && aux->menor != NULL){
 struct elemento * aux2;// cria um segundo auxiliar
 if(aux->maior->menor != NULL){// verifica se existe algum galho do lado menor do maior do número
 aux2 = aux->maior->menor;// se existe passa ele para o segundo aux
 while(aux2->menor != NULL)// se continuar existe números menores va indo ate não existir mais
 aux2 = aux2->menor;
 pai = aux2->topo;// o galho acima do ultimo define como pai
 aux->num = aux2->num;// iguala o numero do primeiro aux para o segundo aux
 if(aux2->maior != NULL){// se existe um galho do lado maior
 aux2->maior->topo = pai;
 pai->menor = aux2->maior;
 }else{// se não existe nenhum galho do lado maior do aux2
 pai->menor = NULL;
 }
 free(aux2);
 aux2 = NULL;
 }else if(aux->menor->maior != NULL){
 aux2 = aux->menor->maior;
 while(aux2->maior != NULL)
 aux2 = aux2->maior;
 pai = aux2->topo;
 aux->num = aux2->num;
 if(aux2->menor != NULL){
 aux2->menor->topo = pai;
 pai->maior = aux2->menor;
 }else{
 pai->maior = NULL;
 }
 free(aux2);
 aux2 = NULL;
 }else{
 pai = aux->topo;
 aux->menor->topo = pai;
 aux->menor->maior = aux->maior;
 aux->maior->topo = aux->menor;
 *endArvore = aux->menor;
 free(aux);
 aux = NULL;
 }
 }else{
 if(aux->maior == NULL){// se não existir nenhum galho do lado maior
 *endArvore = aux->menor;
 aux->menor->topo = pai;
 if(pai != NULL){
 if(pai->menor == aux){
 pai->menor = aux->menor;
 }else if(pai->maior == aux){
 pai->maior = aux->menor;
 }
 }
 }else{// se não existir nenhum galho do lado menor
 *endArvore = aux->maior;
 aux->maior->topo = pai;
 if(pai != NULL){
 if(pai->menor == aux){
 pai->menor = aux->maior;
 }else if(pai->maior == aux){
 pai->maior = aux->maior;
 }
 }
 }
 free(aux);
 aux = NULL;
 }
 return menu;
}
void navegar(struct elemento **endArvore){
 struct elemento *aux,*pai;
 aux = *endArvore;
 int menu = 0;
 while(menu != 5){
 *endArvore = aux;
 pai = aux->topo;
 printf("--menu navegar--\n");
 if(pai == NULL)
 printf("voce esta no topo da arvore\n");
 printf("elemento atual eh -%d-, acima = %s, menor = %s e maior = %s\n",aux->num,retornaStr(aux->topo),retornaStr(aux->menor),retornaStr(aux->maior));
 printf("Digite 1 para ir acima do numero atual\nDigite 2 para ir para um numero menor que o atual\nDigite 3 para um numero maior que o atual\n");
 printf("Digite 4 para remover este elemento\nDigite 5 para retornar ao menu anterior\n>> ");
 scanf("%d",&menu);
 system("cls");
 setbuf(stdin,NULL);
 switch(menu){
 case 1:
 if(pai == NULL)
 printf("Nao e possivel subir mais, voce ja esta no topo da arvore\n");
 else
 aux = aux->topo;
 break;
 case 2:
 if(aux->menor == NULL)
 printf("Nao possui um numero menor\n");
 else
 aux = aux->menor;
 break;
 case 3:
 if(aux->maior == NULL)
 printf("Nao possui um numero maior\n");
 else
 aux = aux->maior;
 break;
 case 4:
 menu = remover(&aux,menu);
 printf("removeu\n");
 if( menu == 5){
 *endArvore = NULL;
 aux = *endArvore;
 printf("arvore nula\n");
 }
 break;
 case 5:
 break;
 default :
 printf("Numero digitado invalido\n");
 break;
 }
 }
}
int main(){
 struct elemento *arvore;
 arvore = NULL;
 cont = 0;
 int menu = 0;
 int a;
 while(menu != 5){
 printf("--menu--\n");
 if(arvore != NULL)
 printf("elemento atual eh -%d-\n",(*arvore).num);
 else
 printf("--Arvore vazia--\n");
 printf("Digite 1 para inserir um numero\nDigite 2 para encontrar um numero\nDigite 3 para navegar\nDigite 4 para pre-ordem\nDigite 5 para sair\n>> ");
 scanf("%d",&menu);
 system("cls");
 setbuf(stdin,NULL);
 switch(menu){
 case 1:
 printf("digite o numero que voce deseja inserir: ");
 scanf("%d",&a);
 setbuf(stdin,NULL);
 inserir(&arvore,arvore,a);
 break;
 case 2:
 if(arvore != NULL){
 printf("digite o numero que voce deseja encontrar: ");
 scanf("%d",&a);
 setbuf(stdin,NULL);
 encontrar(arvore,a);
 }else
 printf("A arvore esta vazia, adicione elementos primeiro\n");
 break;
 case 3:
 if(arvore != NULL){
 navegar(&arvore);
 printf("Retornou do menu navegar\n");
 }else
 printf("A arvore esta vazia, adicione elementos primeiro\n");
 break;
 case 4:
 if(arvore != NULL){
 preOrdem(&arvore);
 }else
 printf("A arvore esta vazia, adicione elementos primeiro\n");
 break;
 case 5:
 break;
 default :
 printf("Numero digitado invalido\n");
 break;
 }
 }
 //free(s);
 return 0;
}

Teste o Premium para desbloquear

Aproveite todos os benefícios por 3 dias sem pagar! 😉
Já tem cadastro?

Outros materiais