Baixe o app para aproveitar ainda mais
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; }
Compartilhar