Dev - C++ - Ayuda con implementacion de Arbol AVL solo falta metodo eliminar es para una WEB

   
Vista:

Ayuda con implementacion de Arbol AVL solo falta metodo eliminar es para una WEB

Publicado por Alfredo (1 intervención) el 02/08/2015 19:46:52
Muy buenas a todos amigos, creo este tema ya que pienso hacer una web de arboles en C++ muy completa ya que todas la que he revisado no tienen mucha información de las implementaciones de ello, en este momento estoy casi terminando solo que he tenido un problemilla a la hora de implementar el eliminar de un arbol AVL, me estoy basando en este código que conseguí navegando por la web y he adaptado yo mismo con ello estoy haciendo un programa mas completo quisiera saber si me prodrian echar una mano con este código a ver si se les ocurre algo, para eliminar un nodo de este arbol AVL.

El código esta completamente funcional en C++ solo falta el metodo eliminar

Codigo C++ Arbol AVL sin metodo eliminar nodo.

#include <iostream>
using namespace std;


class Nodo{
public:
int valor,fe;
Nodo *hijoizq, *hijoder;

Nodo(int x){
valor=x;
fe=0;
hijoizq=NULL;
hijoder=NULL;
}
};


class ArbolAVL{

private:
Nodo *Raiz;

public:
ArbolAVL(){
Raiz=NULL;
}

Nodo* get_raiz(){
return Raiz;
}

Nodo * buscar(int x, Nodo *raiz){ // Buscar Dato

if (raiz==NULL){
return NULL;
}
if(raiz->valor==x){
return raiz;

}

if (raiz->valor<x){
buscar(x,raiz->hijoder);
}
else {
buscar(x,raiz->hijoizq);
}

}

int obtenerfe(Nodo *x){// Obtener factor equilibrio

if (x==NULL){

return -1;
}
else {
return x->fe;
}
}

Nodo * rotacionizquierda(Nodo *c){ //Rotacion simple a la izqierda

Nodo *aux=c->hijoizq;
c->hijoizq=aux->hijoder;
aux->hijoder=c;
int maximovalorc;
int maximovaloraux;

if (obtenerfe(c->hijoizq)>obtenerfe(c->hijoder)){
maximovalorc= obtenerfe(c->hijoizq)+1;

}
else {
maximovalorc= obtenerfe(c->hijoder)+1;
}

c->fe=maximovalorc;


if (obtenerfe(aux->hijoizq)>obtenerfe(aux->hijoder)){
maximovaloraux= obtenerfe(aux->hijoizq)+1;

}
else {
maximovaloraux= obtenerfe(aux->hijoder)+1;
}

aux->fe=maximovaloraux;

return aux;

}

Nodo * rotacionderecha(Nodo *c){ //Rotacion simple a la derecha

Nodo *aux=c->hijoder;
c->hijoder=aux->hijoizq;
aux->hijoizq=c;
int maximovalorc;
int maximovaloraux;

if (obtenerfe(c->hijoizq)>obtenerfe(c->hijoder)){
maximovalorc= obtenerfe(c->hijoizq);

}
else {
maximovalorc= obtenerfe(c->hijoder);
}

c->fe=maximovalorc+1;


if (obtenerfe(aux->hijoizq)>obtenerfe(aux->hijoder)){
maximovaloraux= obtenerfe(aux->hijoizq);

}
else {
maximovaloraux= obtenerfe(aux->hijoder);
}

aux->fe=maximovaloraux+1;

return aux;
}


Nodo * rotaciondobleizq(Nodo *c){

Nodo *temp;
c->hijoizq=rotacionderecha(c->hijoizq);
temp=rotacionizquierda(c);
return temp;
}


Nodo * rotaciondobleder(Nodo *c){
Nodo *temp;
c->hijoder=rotacionizquierda(c->hijoder);
temp=rotacionderecha(c);
return temp;
}


Nodo * insertaravl(Nodo *nuevo, Nodo *subarbol){

Nodo *nuevoPadre=subarbol;

if (nuevo->valor<subarbol->valor){
if (subarbol->hijoizq==NULL){
subarbol->hijoizq=nuevo;
}else {
subarbol->hijoizq=insertaravl(nuevo,subarbol->hijoizq);
if ((obtenerfe(subarbol->hijoizq)-obtenerfe(subarbol->hijoder)==2)){
if (nuevo->valor<subarbol->hijoizq->valor){
nuevoPadre=rotacionizquierda(subarbol);
}else {
nuevoPadre=rotaciondobleizq(subarbol);

}

}
}
}else if (nuevo->valor > subarbol->valor){
if (subarbol->hijoder==NULL){
subarbol->hijoder=nuevo;
}
else {
subarbol->hijoder=insertaravl(nuevo, subarbol->hijoder);
if ((obtenerfe(subarbol->hijoder)-obtenerfe(subarbol->hijoizq)==2)){

if (nuevo->valor>subarbol->hijoder->valor){
nuevoPadre=rotacionderecha(subarbol);

} else {

nuevoPadre=rotaciondobleder(subarbol);
}

}

}


}
else {
cout<<"Nodo Duplicado"<<endl;
}

if ((subarbol->hijoizq==NULL) && (subarbol->hijoder!=NULL)) {

subarbol->fe=subarbol->hijoder->fe+1;
}
else{

if ((subarbol->hijoder==NULL) && (subarbol->hijoizq!=NULL)) {

subarbol->fe=subarbol->hijoizq->fe+1;


}
else {
int maximovalor;

if (obtenerfe(subarbol->hijoizq)>obtenerfe(subarbol->hijoder)){
maximovalor= obtenerfe(subarbol->hijoizq);

}
else {
maximovalor= obtenerfe(subarbol->hijoder);
}
subarbol->fe=maximovalor+1;

}

}

return nuevoPadre;
}

void insertar(int d){
Nodo *nuevo= new Nodo(d);
if (Raiz==NULL){
Raiz=nuevo;

}
else {

Raiz=insertaravl(nuevo,Raiz);
}

}

void inorden (Nodo *r){
if (r!=NULL){
inorden(r->hijoizq);
cout<<r->valor<<",";
inorden(r->hijoder);
}

}

void preorden (Nodo *r){
if (r!=NULL){
cout<<r->valor<<",";
preorden(r->hijoizq);
preorden(r->hijoder);

}
}

void postorden(Nodo *r){
if (r!=NULL){
cout<<r->valor<<",";
postorden(r->hijoizq);
postorden(r->hijoder);
}

}

};


int main (){

ArbolAVL *arbol=new ArbolAVL();

arbol->insertar(10);
arbol->insertar(5);
arbol->insertar(13);
arbol->insertar(1);
arbol->insertar(6);
arbol->insertar(17);
arbol->insertar(16);

//arbol->eliminar (10); Metodo que falta


arbol->preorden(arbol->get_raiz());

}
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder
Imágen de perfil de vangodp

Ayuda con implementacion de Arbol AVL solo falta metodo eliminar es para una WEB

Publicado por vangodp (287 intervenciones) el 02/08/2015 20:45:46
No estoy muy a la par de arboles binarios, pero creo que aquí hay una buena ayuda incluyendo ejemplos completos de funcionamiento.
http://www.c.conclase.net/edd/?cap=008#inicio

Y aquí al final de esta lista están implementadas en C++ "puro" con clases y orientación a objetos. También los hay en C y con plantillas genéricas en C++. Particularmente creo que es un chollo.
http://www.c.conclase.net/edd/index.php?cap=ejemplos#inicio

Solo tomar y realizar los cambios para adaptar a tú necesidad. ;)
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar