Version:0.9
StartHTML:0000000105
EndHTML:0000013006
StartFragment:0000000152
EndFragment:0000012972
/******************************************************/
/*************** Isidro Pastor Jorda ******************/
/******************************************************/
/****************** Telematica ************************/
/******************** FPII ****************************/
/****************** Practica 7 ************************/
/******************************************************/
#include <iostream.h>
#include <stdlib.h>
#include <string>
#include "ABB.h"
/*****************************************************************************
* Funcion: ABB
* Descripcion: Constructor de la clase arbol binario de busqueda
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
*
*
*
*
* Valor devuelto:
* Inicializa un objeto de la clase arbol binario de busqueda
*****************************************************************************/
ABB::ABB()
{
esvacio = true;
izdo = NULL;
dcho = NULL;
ocur = 0;
};
/*****************************************************************************
* Funcion: Arbol
* Descripcion: Constructor de copia de la clase arbol
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
*
*
*
*
* Valor devuelto:
* Hace una copia del objeto de la clase arbol que hace la llamada
*****************************************************************************/
ABB::ABB (ABB &ori)
{
if (!ori.ArbolVacio())
{
izdo = new ABB(ori.HijoIzdo());
dcho = new ABB (ori.HijoDcho());
ori.Informacion(dato, ocur);
esvacio = false;
}
else
{
esvacio = true;
izdo = NULL;
dcho = NULL;
ocur = 0;
}
};
/*****************************************************************************
* Funcion: CopiarABB
* Descripcion: Funcion para realizar una copia de un arbol
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* ori E/S Arbol origen de la copia
*
*
*
* Valor devuelto:
*
*****************************************************************************/
void ABB::CopiarABB(ABB &ori)
{
if (!ori.ArbolVacio())
{
izdo = new ABB(ori.HijoIzdo());
dcho = new ABB(ori.HijoDcho());
ori.Informacion(dato, ocur);
esvacio = false;
}
else
{
esvacio = true;
izdo = NULL;
dcho = NULL;
ocur = 0;
}
};
/*****************************************************************************
* Funcion: ~Arbol
* Descripcion: Destructor de la clase arbol
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
*
*
*
*
* Valor devuelto:
* Destruye el objeto de la clase arbol que hace la llamada
*****************************************************************************/
ABB::~ABB()
{
if (!esvacio)
{
delete izdo;
delete dcho;
}
};
/*****************************************************************************
* Funcion: ArbolVacio
* Descripcion: Nos indica si el objeto arbol que hace la llamada esta vacio.
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
*
*
*
*
* Valor devuelto:
* True si el objeto arbol esta vacio, false en caso contrario.
*****************************************************************************/
bool ABB::ArbolVacio()
{
return (esvacio);
};
/*****************************************************************************
* Funcion: HijoIzdo
* Descripcion: Devuelve el hijo izquierdo del objeto que hace la llamada.
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
*
*
*
*
* Valor devuelto:
* Objeto de clase arbol.
*****************************************************************************/
ABB & ABB::HijoIzdo()
{
return (*izdo);
};
/*****************************************************************************
* Funcion: HijoDcho
* Descripcion: Devuelve el hijo derecho del objeto que hace la llamada.
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
*
*
*
*
* Valor devuelto:
* Objeto de clase arbol.
*****************************************************************************/
ABB & ABB::HijoDcho()
{
return (*dcho);
};
/*****************************************************************************
* Funcion: Informacion
* Descripcion: Obtiene el dato almacenado en el nodo raiz del objeto
* que hace la llamada.
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* x E/S Variable donde almacenaremos el Dato del nodo raiz
*
*
*
* Valor devuelto:
* True si existe elemento en el objeto, false en caso contrario.
*****************************************************************************/
bool ABB::Informacion(Valor & x, int &ocurrencias)
{
bool ok;
if(ArbolVacio())
ok = false;
else
{
ok = true;
x = dato;
ocurrencias = ocur;
}
return ok;
};
/*****************************************************************************
* Funcion: Buscar
* Descripcion: Busca un elemento valor en el arbol que hace la llamada.
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* x E/S Valor que queremos buscar
*
*
*
* Valor devuelto:
* Devuelve el arbol donde esta el elemento buscado en la raiz
*****************************************************************************/
ABB &ABB::Buscar(Valor x)
{
PunteroABB aux;
Valor info;
aux = this;
int trash;
aux -> Informacion(info, trash);
while((!aux -> ArbolVacio()) && (info != x))
{
if(x < info)
aux = & aux -> HijoIzdo();
else
aux = & aux -> HijoDcho();
aux -> Informacion(info,trash);
}
return(*aux);
};
/*****************************************************************************
* Funcion: Insertar
* Descripcion: Inserta un valor en el arbol binario de busqueda que hace la llamada
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* x E/S Valor que queremos insertar
*
*
*
* Valor devuelto:
* True si hemos conseguido insertar el valor en el arbol
*****************************************************************************/
bool ABB::Insertar(Valor x)
{
PunteroABB aux;
bool ok;
aux = this;
while((!aux -> esvacio) && (x != aux -> dato))
{
if(x < aux -> dato)
aux = aux -> izdo;
else
aux = aux -> dcho;
}
if (x == aux->dato)
{
aux->ocur++;
}
if(aux -> esvacio)
{
aux -> dato = x;
aux -> ocur = 1;
aux -> esvacio = false;
aux -> izdo = new ABB();
aux -> dcho = new ABB();
ok = true;
}
else
ok = false;
return(ok);
};
/*****************************************************************************
* Funcion: Eliminar
* Descripcion: Alimina el elemento del arbol
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* x E/S Valor que queremos eliminar
*
*
*
* Valor devuelto:
* True si hemos conseguido eliminar el valor en el arbol
*****************************************************************************/
bool ABB::Eliminar(Valor x)
{
PunteroABB aux;
bool ok;
aux = this;
while((!aux -> esvacio) && (x != aux -> dato))
{
if(x < aux -> dato)
aux = aux -> izdo;
else
aux = aux -> dcho;
}
if(aux -> esvacio)
ok = false;
else
{
if((aux -> izdo -> esvacio) && (aux -> dcho -> esvacio))
Borrar0(aux);
else
{
if(aux -> izdo -> esvacio)
Borrar1(aux, aux -> dcho);
else
{
if(aux -> dcho -> esvacio)
Borrar1(aux, aux -> izdo);
else
Borrar2(aux);
}//else
}//else
ok = true;
}//else
return(ok);
};
/*****************************************************************************
* Funcion: Borrar0
* Descripcion: Funcion auxiliar para borrar un caso de arbol
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* aux E Puntero a arbol que queremos borrar
*
*
*
* Valor devuelto:
* no devuelve nada
*****************************************************************************/
void ABB::Borrar0(PunteroABB aux)
{
aux -> esvacio = true;
delete aux -> izdo;
delete aux -> dcho;
};
/*****************************************************************************
* Funcion: Borrar1
* Descripcion: Funcion auxiliar para borrar un caso de arbol
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* aux E Puntero a arbol que queremos borrar
* hijo E Puntero a arbol que queremos borrar
*
*
* Valor devuelto:
* no devuelve nada
*****************************************************************************/
void ABB::Borrar1(PunteroABB aux, PunteroABB hijo)
{
*aux = *hijo;
hijo -> esvacio = true;
delete hijo;
};
/*****************************************************************************
* Funcion: Borrar2
* Descripcion: Funcion auxiliar para borrar un caso de arbol
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* aux E Puntero a arbol que queremos borrar
*
*
*
* Valor devuelto:
* no devuelve nada
*****************************************************************************/
void ABB::Borrar2(PunteroABB aux)
{
PunteroABB sust;
sust = aux -> dcho;
while(!sust -> izdo -> esvacio)
sust = aux -> izdo;
aux -> dato = sust -> dato;
sust -> Eliminar(sust -> dato);
};