Informatica

#include
#include

using namespace std;

class MiArobolito {
private:
// Clase
class Nodo {
public:
// Mi Constructor:
Nodo(const int dat, Nodo *izq=NULL, Nodo *der=NULL) :
valor(dat), izquierdo(izq), derecho(der) {}
int valor;
Nodo *izquierdo;
Nodo *derecho; };
// Punteros de la lista, para arriba y nodo actual:Nodo *raiz;
Nodo *actual;
int contador;
int altura;
public:
// Constructor y destructor
MiArobolito() : raiz(NULL), actual(NULL) {}
~MiArobolito() { quitar(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 entero
int Altura(const int dat);
// Devolver referencia al int del nodo actual:
int&ValorActual() { return actual->valor; }
// 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:
// Funciones auxiliaresvoid quitar(Nodo* &);
void AuxCont(Nodo*);
void auxAltura(Nodo*, int); };
// quitar: borrar todos los nodos a partir de uno, incluido
void MiArobolito::quitar(Nodo* &nodo)
{
// Algoritmo recursivo, recorrido en postorden
if(nodo) {
quitar(nodo->izquierdo); // quitar izquierdo
quitar(nodo->derecho); // quitar derecho
delete nodo; // Eliminarnodo
nodo = NULL;
}
}
// Insertar un entero en el árbol ABB
void MiArobolito::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->valor) {
padre = actual;
if(dat > actual->valor) actual = actual->derecho;
else if(dat valor) 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 valor) 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->valor) padre->derecho = new Nodo(dat);
}
// Eliminar un elemento de un árbol ABB
void MiArobolito::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->valor) { // 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.