Tda de un arbol de busqueda binario

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

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

public:
// Constructor y destructor básicos:
ArbolABB() : raiz(NULL), actual(NULL) {}
~ArbolABB() { Podar(raiz); }
// Insertar en árbol ordenado:
void Insertar(const int dat);
// Borrar un elemento del árbol:
void Borrar(const int dat);
// Función de búsqueda:
bool Buscar(const int 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 int:
int Altura(const int dat);
// Devolver referencia al int del nodo actual:
int&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)(int&) , Nodo *nodo=NULL, bool r=true);
void PreOrden(void (*func)(int&) , Nodo *nodo=NULL, bool r=true);
void PostOrden(void (*func)(int&) , Nodo *nodo=NULL, bool r=true);
private:
// Funcionesauxiliares
void Podar(Nodo* &);
void auxContador(Nodo*);
void auxAltura(Nodo*, int);
};

// Poda: borrar todos los nodos a partir de uno, incluido
void ArbolABB::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 int en el árbol ABB
void ArbolABB::Insertar(const int dat)
{
Nodo *padre = NULL;

actual = raiz;
// Buscar el int 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 nodo será
// el nodo raiz
if(Vacio(padre)) raiz = new Nodo(dat);
// Si el int es menor que el que contiene el nodo padre, lo insertamos
// en la rama izquierda
else if(dat dato) padre->izquierdo = new Nodo(dat);
// Si el int 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
void ArbolABB::Borrar(const int dat)
{
Nodo *padre = NULL;
Nodo *nodo;
int aux;

actual = raiz;
// Mientras sea posible que elvalor 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 borramos
if(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 el valor está en el nodo actual, pero no es hoja
// Buscar nodo
padre = actual;
// Buscar nodo más izquierdo de rama derecha
if(actual->derecho) {...

Leer documento completo

Regístrate para leer el documento completo.