Murilo Marchiori

Olá, amigos, bom dia. Gostaria da ajuda dos senhores para encontrar um erro na minha função de rotação, ou na chamada da mesma, não sei... Vou postar o código inteiro caso os senhores precisem de alguma informação extra, embora ache dificil... O erro está na chamada das funções de rotação, dentro da função de inserção, ou dentro das próprias funções de rotação (esq e dir). Essas duas funções estão no final do código, e a chamada para elas está comentada dentro da função de inserção. O problema é que, com o decorrer das inserções, chega uma hora em que entro em um laço infinito... Se alguém puder ajudar, agradeço. Segue o código: #include <iostream> #include <cstdlib> using namespace std; struct tNo { int num; tNo *esq; tNo *dir; }; struct tArvore { tNo *raiz; }; int menu(); int insercao(tArvore &ar,int inf); int busca(tArvore &ar, tNo *&aux, tNo *&aux_ant, int inf); int remove(tArvore &ar, int inf); void preOrdem(tNo *aux); void emOrdem(tNo *aux); void posOrdem(tNo *aux); int altura(tNo *aux); void rot_dir(tNo *aux, tNo *ant, tArvore &ar); void rot_esq(tNo *aux, tNo *ant, tArvore &ar); int main() { int op=0, info=0, recebe=0; tArvore arvore; arvore.raiz = NULL; do { op = menu(); if(op == 1) { cout << "\n\nDigite o valor a ser inserido: "; cin >> info; recebe = insercao(arvore, info); if(recebe == 0) cout << "\n\nImpossÃ*vel realizar a operacao"; preOrdem(arvore.raiz); } else if(op == 2) { cout << "\n\nDigite o numero a ser removido: "; cin >> info; recebe = remove(arvore, info); if(recebe == 0) cout << "\n\nImpossÃ*vel realizar a operacao"; preOrdem(arvore.raiz); } } while(op != 3); } int menu() { int op=0; //system("clear"); // so para poder ver os testes cout << "\n\nMenu: "; cout << "\n\n1- Insercao"; cout << "\n2- Remocao"; cout << "\n3- Sair"; cout << "\n\nDigite sua opcao: "; cin >> op; while(op < 0 || op > 3) { cout << "\n\nOpcao invalida. Digite novamente: "; cin >> op; } return op; } int insercao(tArvore &ar,int inf) { tNo *novo_no = new tNo; if(novo_no == NULL) return 0; novo_no->num = inf; novo_no->esq = NULL; novo_no->dir = NULL; if(ar.raiz == NULL) { ar.raiz = novo_no; return 1; } else { int altura_raiz = 0, altura_ant = 0, flag=0; tNo *aux, *alt, *ant, *back_ant; aux = alt = ar.raiz; ant=NULL; back_ant=NULL; while(flag==0) { if(inf < aux->num) { if(aux->esq != NULL) { back_ant = ant; ant = aux; aux = aux->esq; } else { aux->esq = novo_no; flag=1; } } else { if(aux->dir != NULL) { back_ant = ant; ant = aux; aux = aux->dir; } else { aux->dir = novo_no; flag=1; } } } //calcular alturas e fazer o balanceamento. //NÃO FUNCIONA if(ant != NULL) // coloquei este if... { altura_raiz = altura(alt->dir) - altura(alt->esq); altura_ant = altura(ant->dir) - altura(ant->esq); if(altura_raiz > 0 && altura_ant > 0) rot_esq(alt, ant, ar); else if(altura_raiz < 0 && altura_ant < 0) rot_dir(alt, ant, ar); else if(altura_raiz < 0 && altura_ant > 0) { rot_esq(ant, back_ant, ar); rot_dir(alt, ant, ar); } else if(altura_raiz > 0 && altura_ant < 0) //coloquei este if { rot_dir(ant, back_ant, ar); rot_esq(alt, ant, ar); } } return 1; } } int busca(tArvore &ar, tNo *&aux, tNo *&aux_ant, int inf) { while(aux) { if(aux->num == inf) return 1; else { if(inf < aux->num) { aux_ant = aux; aux = aux->esq; } else { aux_ant = aux; aux = aux->dir; } } } return 0; } int remove(tArvore &ar, int inf) { tNo *aux_ant, *aux; int cont=0; aux_ant = NULL; aux = ar.raiz; if(busca(ar, aux, aux_ant, inf) == 1) { if(aux->dir == NULL && aux->esq == NULL) //caso1 - sem filhos { if(aux_ant != NULL) { if(aux_ant->dir == aux) { aux_ant->dir = NULL; delete aux; } else { aux_ant->esq = NULL; delete aux; } } else { ar.raiz = NULL; delete aux; } } else if(aux->dir != NULL && aux->esq != NULL) //caso3 - dois filhos { tNo *maior, *anterior; anterior = NULL; maior = aux->esq; while(maior->dir != NULL) { anterior = maior; maior = maior->dir; cont=1; } if(aux_ant != NULL) { aux->num = maior->num; if(cont == 0) aux->esq = maior->esq; else anterior->dir = NULL; delete maior; } else { aux->num = maior->num; aux->esq = maior->esq; delete maior; } } else if(aux->dir == NULL) //caso2 - somente o filho da esquerda { if(aux_ant != NULL) { if(aux_ant->dir == aux) { aux_ant->dir = aux->esq; delete aux; } else { aux_ant->esq = aux->esq; delete aux; } } else { ar.raiz = aux->esq; delete aux; } } else //caso2 - somente o filho da direita { if(aux_ant != NULL) { if(aux_ant->dir == aux) { aux_ant->dir = aux->dir; delete aux; } else { aux_ant->esq = aux->dir; delete aux; } } else { ar.raiz = aux->dir; delete aux; } } return 1; } else { cout << "\n\nNo não encontrado."; return 0; } } void preOrdem(tNo *aux) { if(aux != NULL) { cout << aux->num << " "; if(aux->esq != NULL) preOrdem(aux->esq); if(aux->dir != NULL) preOrdem(aux->dir); } else cout << "\n\nA arvore esta vazia"; } void emOrdem(tNo *aux) { if(aux != NULL) { if(aux->esq != NULL) emOrdem(aux->esq); cout << aux->num << " "; if(aux->dir != NULL) emOrdem(aux->dir); } else cout << "\n\nA arvore esta vazia"; } void posOrdem(tNo *aux) { if(aux->esq != NULL) posOrdem(aux->esq); if(aux->dir != NULL) posOrdem(aux->dir); cout << aux->num <<" "; } int altura(tNo *aux) { if (aux == NULL) return -1; else { int he = altura(aux->esq); int hd = altura(aux->dir); if (he < hd) return hd + 1; else return he + 1; } } void rot_dir(tNo *aux, tNo *ant, tArvore &ar) { tNo *q, *temp; q = aux->esq; temp = q->dir; q->dir = aux; aux->esq = temp; if(ant != aux) { if(ant->esq == aux) ant->esq = q; else ant->dir = q; ar.raiz = ant; } else ar.raiz = q; } void rot_esq(tNo *aux, tNo *ant, tArvore &ar) { tNo *q, *temp; q = aux->dir; temp = q->esq; q->esq = aux; aux->dir = temp; if(ant != aux) { if(ant->esq == aux) ant->esq = q; else ant->dir = q; ar.raiz = ant; } else ar.raiz = q; }

Hello, friends. I am having a little problem with a c++ tree... When i try to delete a node, and there is just one node in the tree (so I must delete the root), the program does not work ("Segmentation Fault" message, compiling on Linux). Here is my code, and below is the logic that I tried to follow.. can you help, me please? Thank you very much! *aux is the node that I must delete, and aux_prev is the previous node if(aux->right == NULL && aux->left == NULL) { if(aux_prev != NULL) { if(aux_prev->right == aux) { aux_prev->right = NULL; delete aux; } else { aux_prev->left = NULL; delete aux; } } else { tree.root = NULL; delete aux; } } if (the node don't have sons) { if (is not the root) { if (the node is in the right of the previous node) { aux_ant->right = NULL; delete aux; } else //the node is in the left of the previous node { aux_ant->left = NULL; delete aux; } } else //if is the root { tree.root = NULL; //the root ponts to NULL delete aux; //delete the node } }

Olá, amigos, bom dia. Gostaria de saber se seria possivel uma pequena ajuda dos senhores com relação a um rebalanceamento de arvores avl. Na verdade, meu programa já está quase pronto, minha dificuldade é numa chamada de função. Segue meu codigo abaixo: #include <iostream> #include <cstdlib> using namespace std; struct tNo { int num; tNo *esq; tNo *dir; }; struct tArvore { tNo *raiz; }; int menu(); int insercao(tArvore &ar,int inf); int busca(tArvore &ar, tNo *&aux, tNo *&aux_ant, int inf); int remove(tArvore &ar, int inf); void preOrdem(tNo *aux); void emOrdem(tNo *aux); void posOrdem(tNo *aux); int altura(tNo *aux); int main() { int op=0, info=0, recebe=0; tArvore arvore; tNo *aux; arvore.raiz = NULL; do { op = menu(); if(op == 1) { cout << "\n\nDigite o valor a ser inserido: "; cin >> info; recebe = insercao(arvore, info); if(recebe == 0) cout << "\n\nImpossível realizar a operacao"; preOrdem(arvore.raiz); } else if(op == 2) { cout << "\n\nDigite o numero a ser removido: "; cin >> info; recebe = remove(arvore, info); if(recebe == 0) cout << "\n\nImpossível realizar a operacao"; preOrdem(arvore.raiz); } } while(op != 3); } int menu() { int op=0; system("clear"); cout << "\n\nMenu: "; cout << "\n\n1- Insercao"; cout << "\n2- Remocao"; cout << "\n3- Sair"; cout << "\n\nDigite sua opcao: "; cin >> op; while(op < 0 || op > 3) { cout << "\n\nOpcao invalida. Digite novamente: "; cin >> op; } return op; } int insercao(tArvore &ar,int inf) { //lembrar de verificar se o numero já existe tNo *novo_no = new tNo; if(novo_no == NULL) return 0; novo_no->num = inf; novo_no->esq = NULL; novo_no->dir = NULL; if(ar.raiz == NULL) { ar.raiz = novo_no; return 1; } else { int altura_raiz = 0, altura_ant = 0, flag=0; tNo *aux, *alt, *ant, *back_ant; aux = alt = ar.raiz; ant=NULL; back_ant=NULL; while(flag==0) { if(inf < aux->num) { if(aux->esq != NULL) { back_ant = ant; ant = aux; aux = aux->esq; } else { aux->esq = novo_no; flag=1; } } else { if(aux->dir != NULL) { back_ant = ant; ant = aux; aux = aux->dir; } else { aux->dir = novo_no; flag=1; } } } //calcular alturas altura_raiz = altura(alt->dir) - altura(alt->esq); altura_ant = altura(ant->dir) - altura(ant->esq); /* if(altura_raiz > 0 && altura_ant > 0) //rotacao simples à esq da raiz else if(altura_raiz < 0 && altura_ant < 0) //rotacao simples à dir da raiz else if(altura_raiz < 0 && altura_ant > 0) { //rotacao dupla //primeiro ant a esq //depois raiz a direita } else { //rotacao dupla //primeiro ant a dir //depois raiz a esq } */ } } int busca(tArvore &ar, tNo *&aux, tNo *&aux_ant, int inf) { while(aux) { if(aux->num == inf) return 1; else { if(inf < aux->num) { aux_ant = aux; aux = aux->esq; } else { aux_ant = aux; aux = aux->dir; } } } return 0; } int remove(tArvore &ar, int inf) { tNo *aux_ant, *aux; aux_ant = NULL; aux = ar.raiz; if(busca(ar, aux, aux_ant, inf) == 1) { if(aux->dir == NULL && aux->esq == NULL) //caso1 - sem filhos { if(aux_ant->dir == aux) { aux_ant->dir = NULL; delete aux; } else { aux_ant->dir = NULL; delete aux; } } else if(aux->dir != NULL && aux->esq != NULL) //caso3 - dois filhos { tNo *menor, *anterior; anterior = NULL; menor = aux->esq; while(menor->dir != NULL) { anterior = menor; menor = menor->dir; } aux->num = menor->num; anterior->dir = menor->esq; delete menor; } else if(aux->dir == NULL) //caso2 - somente o filho da esquerda { if(aux_ant->dir == aux) { aux_ant->dir = aux->esq; delete aux; } else { aux_ant->esq = aux->esq; delete aux; } } else //caso2 - somente o filho da direita { if(aux_ant->dir == aux) { aux_ant->dir = aux->dir; delete aux; } else { aux_ant->esq = aux->dir; delete aux; } } return 1; } else { cout << "\n\nNo não encontrado."; return 0; } } void preOrdem(tNo *aux) { cout << aux->num << " "; if(aux->esq != NULL) preOrdem(aux->esq); if(aux->dir != NULL) preOrdem(aux->dir); } void emOrdem(tNo *aux) { if(aux->esq != NULL) emOrdem(aux->esq); cout << aux->num << " "; if(aux->dir != NULL) emOrdem(aux->dir); } void posOrdem(tNo *aux) { if(aux->esq != NULL) posOrdem(aux->esq); if(aux->dir != NULL) posOrdem(aux->dir); cout << aux->num <<" "; } int altura(tNo *aux) { if (aux == NULL) return -1; // altura de árvore vazia é -1 else { int he = altura(aux->esq); int hd = altura(aux->dir); if (he < hd) return hd + 1; else return he + 1; } } /* rot_dir(tNo *aux, tNo *ant, tArvore &ar) { tNo q, temp; q = aux->esq; temp = q->dir; q->dir = aux; aux->esq = temp; if(ant != aux) { if(ant->esq == aux) ant->esq = q; else ant->dir = q; ar.raiz = ant; } else ar.raiz = q; } rot_esq(tNo *aux, tNo *ant, tArvore &ar) { tNo q, temp; q = aux->dir; temp = q->esq; q->esq = aux; aux->dir = temp; if(ant != aux) { if(ant->esq == aux) ant->esq = q; else ant->dir = q; ar.raiz = ant; } else ar.raiz = q; } */ Minhas duas funções de rebalanceamento já estão feitas, elas estão comentadas no final do código, se os senhores quiserem dar uma olhada. Mas eu gostaria de uma ajuda na função de inserção... Logo depois de inserir um numero, calculo as alturas dos nós, e tal... essa parte ta beleza... depois, tenho q rotacionar (isso esta comentado no final da função inserção)... mas eu não sei como chamar a função, não sei qual parametro passar... vocês podem ver pelo meu codigo de balanceamento que eu passo pra essa função o nó que quero rotacionar, o nó anterior a ele, e a raiz... mas e quando eu rotaciono a raiz? qual é o nó anterior a ela? enfim, seria possivel uma ajuda somente na hora de chamar as funções de balanceamento?