Árbol Binario De Busqueda En C++ Con Templates (Clases)

// Plantilla de Arbol Binario de Búsqueda en C++
// (C) Abril 2002, Salvador Pozo
// C con Clase: http://c.conclase.net

#include

using namespace std;

template
class ABB {
private:
//// Clase local de Lista para Nodo de ArbolBinario:
template
class Nodo {
public:
// Constructor:
Nodo(const DATON dat, Nodo *izq=NULL, Nodo *der=NULL) :dato(dat), izquierdo(izq), derecho(der) {}
// Miembros:
DATON dato;
Nodo *izquierdo;
Nodo *derecho;
};

// Punteros de la lista, para cabeza y nodo actual:
Nodo *raiz;
Nodo *actual;
int contador;
int altura;

public:
// Constructor y destructor básicos:
ABB() : raiz(NULL), actual(NULL) {}
~ABB() { Podar(raiz); }
// Insertar en árbolordenado:
void Insertar(const DATO dat);
// Borrar un elemento del árbol:
void Borrar(const DATO dat);
// Función de búsqueda:
bool Buscar(const DATO dat);
// Comprobar si el árbol está vacío:
bool Vacio(Nodo *r) { return r==NULL; }
// Comprobar si es un nodo hoja:
bool EsHoja(Nodo *r) { return !r->derecho && !r->izquierdo; }
// Contar número de nodos:const int NumeroNodos();
const int AlturaArbol();
// Calcular altura de un dato:
int Altura(const DATO dat);
// Devolver referencia al dato del nodo actual:
DATO &ValorActual() { return actual->dato; }
// Moverse al nodo raiz:
void Raiz() { actual = raiz; }
// Aplicar una función a cada elemento del árbol:
void InOrden(void (*func)(DATO&) , Nodo *nodo=NULL, boolr=true);
void PreOrden(void (*func)(DATO&) , Nodo *nodo=NULL, bool r=true);
void PostOrden(void (*func)(DATO&) , Nodo *nodo=NULL, bool r=true);
private:
// Funciones auxiliares
void Podar(Nodo* &);
void auxContador(Nodo*);
void auxAltura(Nodo*, int);
};

// Poda: borrar todos los nodos a partir de uno, incluido
template
void ABB::Podar(Nodo* &nodo)
{
//Algoritmo recursivo, recorrido en postorden
if(nodo) {
Podar(nodo->izquierdo); // Podar izquierdo
Podar(nodo->derecho); // Podar derecho
delete nodo; // Eliminar nodo
nodo = NULL;
}
}

// Insertar un dato en el árbol ABB
template
void ABB::Insertar(const DATO dat)
{
Nodo *padre = NULL;

actual = raiz;
// Buscar el dato en el árbol,manteniendo un puntero al nodo padre
while(!Vacio(actual) && dat != actual->dato) {
padre = actual;
if(dat > actual->dato) actual = actual->derecho;
else if(dat < actual->dato) actual = actual->izquierdo;
}

// Si se ha encontrado el elemento, regresar sin insertar
if(!Vacio(actual)) return;
// Si padre es NULL, entonces el árbol estaba vacío, el nuevo nodoserá
// el nodo raiz
if(Vacio(padre)) raiz = new Nodo(dat);
// Si el dato es menor que el que contiene el nodo padre, lo insertamos
// en la rama izquierda
else if(dat < padre->dato) padre->izquierdo = new Nodo(dat);
// Si el dato es mayor que el que contiene el nodo padre, lo insertamos
// en la rama derecha
else if(dat > padre->dato) padre->derecho = new Nodo(dat);}

// Eliminar un elemento de un árbol ABB
template
void ABB::Borrar(const DATO dat)
{
Nodo *padre = NULL;
Nodo *nodo;
DATO aux;

actual = raiz;
// Mientras sea posible que el valor esté en el árbol
while(!Vacio(actual)) {
if(dat == actual->dato) { // Si el valor está en el nodo actual
if(EsHoja(actual)) { // Y si además es un nodo hoja: lo borramosif(padre) // Si tiene padre (no es el nodo raiz)
// Anulamos el puntero que le hace referencia
if(padre->derecho == actual) padre->derecho = NULL;
else if(padre->izquierdo == actual) padre->izquierdo = NULL;
delete actual; // Borrar el nodo
actual = NULL;
return;
}
else { // Si...