Tenho que implementar uma avl que recebe 10 mil números aleatórios de 1 a 1000 000, logo após isso, tenho que remover 1 mil números aleatórios, ambos retirados de arquivos .txt, eu consigo inserir normalmente, mas na hora de remover, ate consigo remover alguns, porem o cmd para de funcionar, gostaria da ajuda e vocês.
Abaixo o código para gerar os números
[Atualização] rastreei e vi que o problema esta quando tenho que remover um número duplicado com 2 filhos. por exemplo. na arvore tem 2 numeros 500, e na função para remover pede para remover o 500, para remover um no com dois filhos tenho que pegar o menor no da arvore, pois é ai que acontece o loop infinito.
#include #include #includetypedef struct no_arvore { int n; struct no_arvore *esq; struct no_arvore *dir; } no_arvore;
//declaração devariaveis globais para contar as rotações duplas, simples e nos visitados na inserção int Rdupla = 0; int rSimples = 0; int nVisitados = 0; //fim da declaração.
int comparacoes = 0;
no_arvore *remover_no_arvore(no_arvore *r, int x); int fator_balanceamento(no_arvore *r); no_arvore *rotacao_simples_direita(no_arvore *r); no_arvore *rotacao_simples_esquerda(no_arvore *r);
//Função que verifica se um nó está balanceado e faz as rotações necessárias. no_arvore *verifica_balanceamento(no_arvore *r) { int fb; fb = fator_balanceamento(r); //Após inserir o nó para esq ou dir, verificar Fator de bal. if (fb < -1) { if (fator_balanceamento(r->esq) > 0) { //Rotação dupla a direita. Rdupla++; //conta rotações duplas. r->esq = rotacao_simples_esquerda(r->esq); } r = rotacao_simples_direita(r); //Rotação simples a esquerda. rSimples++; //conta rotações simples. } else if (fb > 1) { if (fator_balanceamento(r->dir) < 0) { //Rotação dupla a esquerda. Rdupla++; //conta rotações duplas. r->dir = rotacao_simples_direita(r->dir); } r = rotacao_simples_esquerda(r); //Rotação simples a direita. rSimples ++; //conta rotações simples. } return r; }
no_arvore *insere_arvore(no_arvore *r, int num) { if (r == NULL) { //Se a árvore estiver vazia, inserir o nó. r = (no_arvore *)malloc(sizeof(no_arvore)); //Alocar o nó. r->n = num; //Atribuir um valor para o nó. r->dir = NULL; //Iniciar o filho direito. r->esq = NULL; //Iniciar o filho esquerdo. } else { nVisitados ++; //soma o nos visitados. //Se a árvore não estiver vazia, verificar se num é menor que n. if (num < r->n) { //Se for menor, inserir a esquerda. r->esq = insere_arvore(r->esq, num); } else { //Senão, inserir a direita. r->dir = insere_arvore(r->dir, num); } r = verifica_balanceamento(r); //Verificar balanceamento da árvore. } return r; }
void busca_in_order(no_arvore *r, int num) { //Verificar se a árvore não está vazia. if (r != NULL) { if(r -> n != num){ comparacoes++; //Se a árvore não estiver vazia, executar a busca. busca_in_order(r->esq, num); //1 - Buscar na árvore esquerda. //printf("%d ",r->n); //2 - Mostrar a raiz. busca_in_order(r->dir, num); //3 - Buscar na árvore direita.
}else{ //printf("%d ", r -> n); } } //Se a árvore estiver vazia, não executar a busca.
}
void busca_pre_order(no_arvore *r) { //Verificar se a árvore não está vazia. if (r != NULL) { //Se a árvore não estiver vazia, executar a busca. printf("%d ",r->n); //1 - Mostrar a raiz. busca_pre_order(r->esq); //2 - Buscar na árvore esquerda. busca_pre_order(r->dir); //3 - Buscar na árvore direita. } //Se a árvore estiver vazia, não executar a busca. }
void busca_pos_order(no_arvore *r) { //Verificar se a árvore não está vazia. if (r != NULL) { //Se a árvore não estiver vazia, executar a busca. busca_pos_order(r->esq); //1 - Buscar na árvore esquerda. busca_pos_order(r->dir); //2 - Buscar na árvore direita. printf("%d ",r->n); //3 - Mostrar a raiz. } //Se a árvore estiver vazia, não executar a busca. }
int altura_arvore(no_arvore *r) { if (r== NULL) { return -1; } else { int altEsq, altDir; altEsq = altura_arvore(r->esq); altDir = altura_arvore(r->dir); if (altEsq > altDir) { return altEsq + 1; } else { return altDir + 1; } } }
int fator_balanceamento(no_arvore *r) { //Fator de Balanceamento = Altura da sub-arvore direita - Altura da sub-arvore esquerda. return altura_arvore(r->dir) - altura_arvore(r->esq); }
no_arvore *rotacao_simples_direita(no_arvore *r) { no_arvore *q = r->esq; r->esq = q->dir; q->dir = r; return q; }
no_arvore *rotacao_simples_esquerda(no_arvore *r) { no_arvore *q = r->dir; r->dir = q->esq; q->esq = r; return q; }
//Funçães que retorna o endereço do menor nó da árvore. no_arvore *menor_no_arvore(no_arvore *r) { no_arvore *aux = r; while (aux->esq != NULL) { //Procurar o nó mais a esquerda (menor nó da árvore). //printf("aux: %d\n", aux->n); aux = aux->esq; } //printf("aux: %d\n", aux->n); return aux; //Retornar o endereço do menor nó da árvore. }
//Função que remove um nó que é folha (não possui filhos). no_arvore *remover_folha(no_arvore *r) { printf("\nA folha %d foi removida com sucesso!\n", r->n); //getch(); free(r); return NULL; }
no_arvore *remover_1filho_esquerda(no_arvore *r) { no_arvore *aux = r->esq; printf("\n numero %d foi removido com sucesso!\n", r->n); free(r); return aux; }
no_arvore *remover_1filho_direita(no_arvore *r) { no_arvore *aux = r->dir; printf("\n numero %d foi removido com sucesso!\n", r->n); free(r); return aux; }
no_arvore *remover_2filhos(no_arvore *r) { no_arvore *aux; int x; aux = menor_no_arvore(r->dir); //auxiliar recebe o endereço do menor nó da árvore. //printf("aux: %d\n", aux->n); x = aux->n; //guardar o valor do auxiliar em uma variável x. r = remover_no_arvore(r,x); //remover da árvore o nó que substituirá o nó com 2 filhos.
r->n = x; //substituir o valor do nó com 2 filhos. return r;
}
//Função para verificar o tipo de nó que será removido. no_arvore *remover_no(no_arvore *r) { //Verificar se o nó é uma folha (Não possui filhos). if (r->dir == NULL && r->esq == NULL) { //printf("O no %d eh uma folha.\n", r->n); r = remover_folha(r); } else { if (r->dir == NULL) { //printf("O no %d possui 1 filho para esquerda.\n", r->n); r = remover_1filho_esquerda(r); } else { if (r->esq == NULL) { //printf("O no %d possui 1 filho para direita.\n", r->n); r = remover_1filho_direita(r); } else { //printf("O no %d possui 2 filhos.\n", r->n); r = remover_2filhos(r); } } } return r; }
no_arvore *remover_no_arvore(no_arvore *r, int x) { //Verificar se a árvore não está vazia. if (r != NULL) { //Se a árvore não está vazia, buscar o elemento x. if (r->n == x) { //1 - Verificar se o elemento x está na raiz. //printf("ENCONTREI!: %d\n", r->n); r = remover_no(r); //Chamar a função para remover o nó. } else { //Se x não está na raiz, verificar para qual lado x está. if (x < r->n) { //Fazer chamada recursiva para a esquerda. r->esq = remover_no_arvore(r->esq, x); } else { //Fazer chamada recursiva para a direita. r->dir = remover_no_arvore(r->dir, x); } r = verifica_balanceamento(r); //Verificar balanceamento da árvore. } } else { printf("Elemento nao encontrado: %d\n", x); } return r; }
no_arvore *inserir_aleatorio(no_arvore *r){ int num;
char url[]="aleatorios.txt"; FILE *Ale; Ale = fopen(url, "r"); if(Ale == NULL){ printf("Error "); }else{ while(fscanf(Ale, "%d\n", &num)!=EOF){ r = insere_arvore(r, num); } } fclose(Ale); return r;
}
void busca_aleatorio_1000(no_arvore *r){ int num;
char url[]="aleatorios1000.txt"; FILE *Ale; Ale = fopen(url, "r"); if(Ale == NULL){ printf("Error "); }else{ while(fscanf(Ale, "%d\n", &num)!=EOF){ busca_in_order(r, num); } } fclose(Ale);
}
no_arvore *remover_no_arvore_aleatorio(no_arvore *r) {
int num; char url[]="aleatorios1000Remocao.txt"; FILE *Ale; Ale = fopen(url, "r"); if(Ale == NULL){ printf("Error "); }else{ while(fscanf(Ale, "%d\n", &num)!=EOF){ r = remover_no_arvore(r, num); } } fclose(Ale); return r;
}
int main() {
no_arvore *raiz = NULL; raiz = inserir_aleatorio(raiz); printf("\nrotacoes simples: %d",rSimples - Rdupla); printf("\nrotacoes duplas: %d", Rdupla); printf("\nvisitas: %d\n\n",nVisitados); remover_no_arvore_aleatorio(raiz); system("pause");
} inserção
# include < stdio.h> # include < stdlib.h> # include < time.h>int main(){ int i; FILE *fp; fp = fopen("aleatorios.txt", "w"); if(fp == NULL){ printf("erro.\n"); return 1; } srand( (unsigned)time(NULL) ); for(i=1; i<10000; i++){ fprintf(fp, "%d\n", 1 + rand()% 1000000); } fclose(fp); return 0;
}
#include < stdio.h> #include < stdlib.h> #include < time.h> int main(){ int i; FILE *fp; fp = fopen("aleatorios1000Remocao.txt", "w"); if(fp == NULL){ printf("erro.\n"); return 1; } srand( (unsigned)time(NULL) ); for(i=1; i<1000; i++){ fprintf(fp, "%d\n", 1 + rand()% 1000000); } fclose(fp); return 0; } <code>