Guest tiagooot Postado Maio 21, 2008 Denunciar Share Postado Maio 21, 2008 não consigo implementar em C++ a funcao de remocao em ARVORE AVL !!Poderia alguém me ajudar nesta funcao !!!SEGUE abaixo o programa sem a Opcao de remover !!**********************************************************************/*Este programa insere elementos em uma arvore AVL,fazendo as rotacoes necessarias para manter o balanceamento correto*/#include <iostream.h>#include <conio.h>struct AVL{ int num, alte, altd; AVL *esq, *dir;};AVL *rotacao_esq(AVL *no){ AVL *aux1, *aux2; aux1 = no->dir; aux2 = aux1->esq; no->dir = aux2; aux1->esq = no; if (no->dir == NULL) no->altd = 0; else { if (no->dir->alte > no->dir->altd) no->altd = no->dir->alte + 1; else no->altd = no->dir->altd + 1; } if (aux1->esq->alte > aux1->esq->altd) aux1->alte = aux1->esq->alte + 1; else aux1->alte = aux1->esq->altd + 1; return aux1;}AVL *rotacao_dir(AVL *no){ AVL *aux1, *aux2; aux1 = no->esq; aux2 = aux1->dir; no->esq = aux2; aux1->dir = no; if (no->esq == NULL) no->alte = 0; else { if (no->esq->alte > no->esq->altd) no->alte = no->esq->alte + 1; else no->alte = no->esq->altd + 1; } if (aux1->dir->alte > aux1->dir->altd) aux1->altd = aux1->dir->alte + 1; else aux1->altd = aux1->dir->altd + 1; return aux1;}AVL *inserir(AVL *r, int n){ AVL *novo; int d; if (r == NULL) { novo = new(AVL); novo->num = n; novo->alte=0; novo->altd=0; novo->esq = NULL; novo->dir = NULL; r=novo; } else { if (n < r->num) { r->esq = inserir(r->esq, n); if (r->esq->alte > r->esq->altd) r->alte = r->esq->alte + 1; else r->alte = r->esq->altd + 1; d = r->altd - r->alte; if (d == 2) { if (r->dir->altd - r->dir->alte == 1) { cout << "\nRotação simples para esquerda"; r = rotacao_esq®; } else { cout << "\nRotação Dupla: "; cout << "o filho rotaciona para a direita e o nó desbalanceado rotaciona para esquerda"; getch(); r->dir=rotacao_dir(r->dir); r=rotacao_esq®; } } if (d == -2) { if (r->esq->altd - r->esq->alte == -1) { cout << "\nRotação simples para direita"; r = rotacao_dir®; } else { cout << "\nRotação Dupla: "; cout << "o filho rotaciona para a esquerda e o nó desbalanceado rotaciona para direita"; getch(); r->esq=rotacao_esq(r->esq); r=rotacao_dir®; } } } else { r->dir = inserir(r->dir, n); if (r->dir->alte > r->dir->altd) r->altd = r->dir->alte + 1; else r->altd = r->dir->altd + 1; d = r->altd - r->alte; if (d == 2) { if (r->dir->altd - r->dir->alte == 1) { cout << "\nRotação simples para esquerda"; r=rotacao_esq®; } else { cout << "\nRotação Dupla: "; cout << "o filho rotaciona para a direita e o nó desbalanceado rotaciona para esquerda"; getch(); r->dir=rotacao_dir(r->dir); r=rotacao_esq®; } } if (d == -2) { if (r->esq->altd - r->esq->alte == -1) { cout << "\nRotação simples para direita"; r=rotacao_dir®; } else { cout << "\nRotação Dupla: "; cout << "o filho rotaciona para a esquerda e o nó desbalanceado rotaciona para direita"; getch(); r->esq=rotacao_esq(r->esq); r=rotacao_dir®; } } } }return r;} //fim inserirvoid mostrar(AVL *r, int nivel){ if(r !=NULL) { mostrar(r->esq, nivel+1); cout << "\n " << r->num << "\t Nivel" << nivel; mostrar(r->dir, nivel+1); }} //fim mostrarvoid main(){ int op, aux; AVL *raiz; raiz = NULL; do { clrscr(); cout << "\n1- Inserir"; cout << "\n2- Mostrar"; cout << "\n3- Sair"; cout << "\nDigite a opção desejada: "; cin >> op; if(op==1) { cout << "\nDigite um número: "; cin >> aux; raiz = inserir(raiz, aux); cout << "\nElemento inserido com sucesso. "; } else if (op==2) { mostrar(raiz,0); } getch(); } while (op != 3);} //fim void main() Citar Link para o comentário Compartilhar em outros sites More sharing options...
Pergunta
Guest tiagooot
não consigo implementar em C++ a funcao de remocao em ARVORE AVL !!
Poderia alguém me ajudar nesta funcao !!!
SEGUE abaixo o programa sem a Opcao de remover !!
**********************************************************************
/*
Este programa insere elementos em uma arvore AVL,
fazendo as rotacoes necessarias para manter o balanceamento correto
*/
#include <iostream.h>
#include <conio.h>
struct AVL
{ int num, alte, altd;
AVL *esq, *dir;
};
AVL *rotacao_esq(AVL *no)
{ AVL *aux1, *aux2;
aux1 = no->dir;
aux2 = aux1->esq;
no->dir = aux2;
aux1->esq = no;
if (no->dir == NULL)
no->altd = 0;
else
{ if (no->dir->alte > no->dir->altd)
no->altd = no->dir->alte + 1;
else no->altd = no->dir->altd + 1;
}
if (aux1->esq->alte > aux1->esq->altd)
aux1->alte = aux1->esq->alte + 1;
else aux1->alte = aux1->esq->altd + 1;
return aux1;
}
AVL *rotacao_dir(AVL *no)
{ AVL *aux1, *aux2;
aux1 = no->esq;
aux2 = aux1->dir;
no->esq = aux2;
aux1->dir = no;
if (no->esq == NULL)
no->alte = 0;
else
{ if (no->esq->alte > no->esq->altd)
no->alte = no->esq->alte + 1;
else no->alte = no->esq->altd + 1;
}
if (aux1->dir->alte > aux1->dir->altd)
aux1->altd = aux1->dir->alte + 1;
else aux1->altd = aux1->dir->altd + 1;
return aux1;
}
AVL *inserir(AVL *r, int n)
{ AVL *novo;
int d;
if (r == NULL)
{ novo = new(AVL);
novo->num = n;
novo->alte=0;
novo->altd=0;
novo->esq = NULL;
novo->dir = NULL;
r=novo;
}
else
{
if (n < r->num)
{ r->esq = inserir(r->esq, n);
if (r->esq->alte > r->esq->altd)
r->alte = r->esq->alte + 1;
else r->alte = r->esq->altd + 1;
d = r->altd - r->alte;
if (d == 2)
{
if (r->dir->altd - r->dir->alte == 1)
{ cout << "\nRotação simples para esquerda";
r = rotacao_esq®;
}
else {
cout << "\nRotação Dupla: ";
cout << "o filho rotaciona para a direita e o nó desbalanceado rotaciona para esquerda";
getch();
r->dir=rotacao_dir(r->dir);
r=rotacao_esq®;
}
}
if (d == -2)
{ if (r->esq->altd - r->esq->alte == -1)
{ cout << "\nRotação simples para direita";
r = rotacao_dir®;
}
else {
cout << "\nRotação Dupla: ";
cout << "o filho rotaciona para a esquerda e o nó desbalanceado rotaciona para direita";
getch();
r->esq=rotacao_esq(r->esq);
r=rotacao_dir®;
}
}
}
else
{ r->dir = inserir(r->dir, n);
if (r->dir->alte > r->dir->altd)
r->altd = r->dir->alte + 1;
else r->altd = r->dir->altd + 1;
d = r->altd - r->alte;
if (d == 2)
{ if (r->dir->altd - r->dir->alte == 1)
{ cout << "\nRotação simples para esquerda";
r=rotacao_esq®;
}
else { cout << "\nRotação Dupla: ";
cout << "o filho rotaciona para a direita e o nó desbalanceado rotaciona para esquerda";
getch();
r->dir=rotacao_dir(r->dir);
r=rotacao_esq®;
}
}
if (d == -2)
{ if (r->esq->altd - r->esq->alte == -1)
{ cout << "\nRotação simples para direita";
r=rotacao_dir®;
}
else { cout << "\nRotação Dupla: ";
cout << "o filho rotaciona para a esquerda e o nó desbalanceado rotaciona para direita";
getch();
r->esq=rotacao_esq(r->esq);
r=rotacao_dir®;
}
}
}
}
return r;
} //fim inserir
void mostrar(AVL *r, int nivel)
{
if(r !=NULL)
{
mostrar(r->esq, nivel+1);
cout << "\n " << r->num << "\t Nivel" << nivel;
mostrar(r->dir, nivel+1);
}
} //fim mostrar
void main()
{ int op, aux;
AVL *raiz;
raiz = NULL;
do {
clrscr();
cout << "\n1- Inserir";
cout << "\n2- Mostrar";
cout << "\n3- Sair";
cout << "\nDigite a opção desejada: ";
cin >> op;
if(op==1)
{ cout << "\nDigite um número: ";
cin >> aux;
raiz = inserir(raiz, aux);
cout << "\nElemento inserido com sucesso. ";
}
else if (op==2)
{ mostrar(raiz,0);
}
getch();
} while (op != 3);
} //fim void main()
Link para o comentário
Compartilhar em outros sites
0 respostass a esta questão
Posts Recomendados
Participe da discussão
Você pode postar agora e se registrar depois. Se você já tem uma conta, acesse agora para postar com sua conta.