Desarrollar una clase para la administración de un árbol binario ordenado.
#include <iostream>
using namespace std;
class ArbolBinario {
private:
class Nodo {
public:
int info;
Nodo *izq;
Nodo *der;
};
Nodo *raiz;
void borrar(Nodo *reco);
void imprimirPre(Nodo *reco);
void imprimirEntre(Nodo *reco);
void imprimirPost(Nodo *reco);
public:
ArbolBinario();
~ArbolBinario();
void insertar(int x);
void imprimirPre();
void imprimirEntre();
void imprimirPost();
};
ArbolBinario::ArbolBinario()
{
raiz = NULL;
}
ArbolBinario::~ArbolBinario()
{
borrar(raiz);
}
void ArbolBinario::borrar(Nodo *reco)
{
if (reco != NULL)
{
borrar(reco->izq);
borrar(reco->der);
delete reco;
}
}
void ArbolBinario::insertar(int x)
{
Nodo *nuevo;
nuevo = new Nodo();
nuevo->info = x;
nuevo->izq = NULL;
nuevo->der = NULL;
if (raiz == NULL)
raiz = nuevo;
else
{
Nodo *anterior, *reco;
anterior = NULL;
reco = raiz;
while (reco != NULL)
{
anterior = reco;
if (x < reco->info)
reco = reco->izq;
else
reco = reco->der;
}
if (x < anterior->info)
anterior->izq = nuevo;
else
anterior->der = nuevo;
}
}
void ArbolBinario::imprimirPre()
{
imprimirPre(raiz);
cout << "\n";
}
void ArbolBinario::imprimirPre(Nodo *reco)
{
if (reco != NULL)
{
cout << reco->info << "-";
imprimirPre(reco->izq);
imprimirPre(reco->der);
}
}
void ArbolBinario::imprimirEntre()
{
imprimirEntre(raiz);
cout << "\n";
}
void ArbolBinario::imprimirEntre(Nodo *reco)
{
if (reco != NULL)
{
imprimirEntre(reco->izq);
cout << reco->info << "-";
imprimirEntre(reco->der);
}
}
void ArbolBinario::imprimirPost()
{
imprimirPost(raiz);
cout << "\n";
}
void ArbolBinario::imprimirPost(Nodo *reco)
{
if (reco != NULL)
{
imprimirPost(reco->izq);
imprimirPost(reco->der);
cout << reco->info << "-";
}
}
int main()
{
ArbolBinario *arbol = new ArbolBinario();
arbol->insertar(100);
arbol->insertar(50);
arbol->insertar(25);
arbol->insertar(75);
arbol->insertar(150);
cout<<"Impresion preorden: ";
arbol->imprimirPre();
cout<<"Impresion entreorden: ";
arbol->imprimirEntre();
cout<<"Impresion postorden: ";
arbol->imprimirPost();
delete arbol;
return 0;
}
Este proyecto lo puede descargar en un zip desde este enlace : ArbolBinario1.zip
Creamos un nodo y disponemos los punteros izq y der a NULL, guardamos la información que llega al método en el nodo.
Si el árbol está vacío, apuntamos raíz al nodo creado; en caso de no estar vacío, dentro de una estructura repetitiva vamos comparando x con la información del nodo, si x es mayor a la del nodo descendemos por el subárbol derecho en caso contrario descendemos por el subárbol izquierdo.
Cuando se encuentra un subárbol vacío insertar el nodo en dicho subárbol. Para esto llevamos un puntero anterior dentro del while:
void ArbolBinario::insertar(int x)
{
Nodo *nuevo;
nuevo = new Nodo();
nuevo->info = x;
nuevo->izq = NULL;
nuevo->der = NULL;
if (raiz == NULL)
raiz = nuevo;
else
{
Nodo *anterior, *reco;
anterior = NULL;
reco = raiz;
while (reco != NULL)
{
anterior = reco;
if (x < reco->info)
reco = reco->izq;
else
reco = reco->der;
}
if (x < anterior->info)
anterior->izq = nuevo;
else
anterior->der = nuevo;
}
}
El método imprimirPre() llama al método recursivo imprimirPre(Nodo *reco) y le pasa raiz para comenzar a recorrerlo:
void ArbolBinario::imprimirPre()
{
imprimirPre(raiz);
cout << "\n";
}
void ArbolBinario::imprimirPre(Nodo *reco)
{
if (reco != NULL)
{
cout << reco->info << "-";
imprimirPre(reco->izq);
imprimirPre(reco->der);
}
}
El método recursivo lo primero que verifica con un if si reco está apuntando a un nodo (esto es verdad si reco es distinto a NULL), en caso afirmativo ingresa al bloque del if y realiza:
- Visitar la raiz.
- Recorrer el subárbol izquierdo en pre-orden.
- Recorrer el subárbol derecho en pre-orden.
La visita en este caso es la impresión de la información del nodo y los recorridos son las llamadas recursivas pasando las direcciones de los subárboles izquierdo y derecho.
Los algoritmos de los recorridos en entreorden y postorden son similares. La diferencia es que la visita la realizamos entre las llamadas recursivas en el recorrido en entre orden:
void ArbolBinario::imprimirEntre()
{
imprimirEntre(raiz);
cout << "\n";
}
void ArbolBinario::imprimirEntre(Nodo *reco)
{
if (reco != NULL)
{
imprimirEntre(reco->izq);
cout << reco->info << "-";
imprimirEntre(reco->der);
}
}
y por último en el recorrido en postorden la visita la realizamos luego de las dos llamadas recursivas:
void ArbolBinario::imprimirPost()
{
imprimirPost(raiz);
cout << "\n";
}
void ArbolBinario::imprimirPost(Nodo *reco)
{
if (reco != NULL)
{
imprimirPost(reco->izq);
imprimirPost(reco->der);
cout << reco->info << "-";
}
}
En el destructor debemos borrar todos los nodos que quedan en el árbol, para esto debemos recorrer el árbol en post orden y en la visita eliminar el nodo:
ArbolBinario::~ArbolBinario()
{
borrar(raiz);
}
void ArbolBinario::borrar(Nodo *reco)
{
if (reco != NULL)
{
borrar(reco->izq);
borrar(reco->der);
delete reco;
}
}
Confeccionar una clase que permita insertar un entero en un árbol binario ordenado verificando que no se encuentre previamente dicho número.
Desarrollar los siguientes métodos:
1 - Retornar la cantidad de nodos del árbol.
2 - Retornar la cantidad de nodos hoja del árbol.
3 - Imprimir en entre orden.
4 - Imprimir en entre orden junto al nivel donde se encuentra dicho nodo.
5 - Retornar la altura del árbol.
6 - Imprimir el mayor valor del árbol.
7 - Borrar el nodo menor del árbol.
#include <iostream>
using namespace std;
class ArbolBinario {
private:
class Nodo {
public:
int info;
Nodo *izq;
Nodo *der;
};
Nodo *raiz;
int cant;
int altura;
void borrar(Nodo *reco);
void imprimirEntre(Nodo *reco);
void cantidad(Nodo *reco);
void cantidadNodosHoja(Nodo *reco);
void imprimirEntreConNivel(Nodo *reco, int nivel);
void retornarAltura(Nodo *reco, int nivel);
public:
ArbolBinario();
~ArbolBinario();
void insertar(int x);
bool existe(int x);
void imprimirEntre();
int cantidad();
int cantidadNodosHoja();
void imprimirEntreConNivel();
int retornarAltura();
void mayorValor();
void borrarMenor();
};
ArbolBinario::ArbolBinario()
{
raiz = NULL;
}
ArbolBinario::~ArbolBinario()
{
borrar(raiz);
}
void ArbolBinario::borrar(Nodo *reco)
{
if (reco != NULL)
{
borrar(reco->izq);
borrar(reco->der);
delete reco;
}
}
void ArbolBinario::insertar(int x)
{
if (!existe(x))
{
Nodo *nuevo;
nuevo = new Nodo();
nuevo->info = x;
nuevo->izq = NULL;
nuevo->der = NULL;
if (raiz == NULL)
raiz = nuevo;
else
{
Nodo *anterior, *reco;
anterior = NULL;
reco = raiz;
while (reco != NULL)
{
anterior = reco;
if (x < reco->info)
reco = reco->izq;
else
reco = reco->der;
}
if (x < anterior->info)
anterior->izq = nuevo;
else
anterior->der = nuevo;
}
}
}
bool ArbolBinario::existe(int x)
{
Nodo *reco = raiz;
while (reco != NULL)
{
if (x == reco->info)
return true;
else
if (x>reco->info)
reco = reco->der;
else
reco = reco->izq;
}
return false;
}
int ArbolBinario::cantidad()
{
cant = 0;
cantidad(raiz);
return cant;
}
void ArbolBinario::cantidad(Nodo *reco)
{
if (reco != NULL)
{
cant++;
cantidad(reco->izq);
cantidad(reco->der);
}
}
int ArbolBinario::cantidadNodosHoja()
{
cant = 0;
cantidadNodosHoja(raiz);
return cant;
}
void ArbolBinario::cantidadNodosHoja(Nodo *reco)
{
if (reco != NULL) {
if (reco->izq == NULL && reco->der == NULL)
cant++;
cantidadNodosHoja(reco->izq);
cantidadNodosHoja(reco->der);
}
}
void ArbolBinario::imprimirEntreConNivel()
{
imprimirEntreConNivel(raiz, 1);
cout << "\n";
}
void ArbolBinario::imprimirEntreConNivel(Nodo *reco, int nivel)
{
if (reco != NULL) {
imprimirEntreConNivel(reco->izq, nivel + 1);
cout<<reco->info <<"(" <<nivel <<") - ";
imprimirEntreConNivel(reco->der, nivel + 1);
}
}
int ArbolBinario::retornarAltura()
{
altura = 0;
retornarAltura(raiz, 1);
return altura;
}
void ArbolBinario::retornarAltura(Nodo *reco, int nivel)
{
if (reco != NULL)
{
retornarAltura(reco->izq, nivel + 1);
if (nivel>altura)
altura = nivel;
retornarAltura(reco->der, nivel + 1);
}
}
void ArbolBinario::mayorValor()
{
if (raiz != NULL)
{
Nodo *reco = raiz;
while (reco->der != NULL)
reco = reco->der;
cout<<"Mayor valor del árbol:" <<reco->info;
}
}
void ArbolBinario::borrarMenor()
{
if (raiz != NULL) {
Nodo *bor;
if (raiz->izq == NULL)
{
bor = raiz;
raiz = raiz->der;
delete bor;
}
else {
Nodo *atras = raiz;
Nodo *reco = raiz->izq;
while (reco->izq != NULL)
{
atras = reco;
reco = reco->izq;
}
atras->izq = reco->der;
delete reco;
}
}
}
void ArbolBinario::imprimirEntre()
{
imprimirEntre(raiz);
cout << "\n";
}
void ArbolBinario::imprimirEntre(Nodo *reco)
{
if (reco != NULL)
{
imprimirEntre(reco->izq);
cout << reco->info << "-";
imprimirEntre(reco->der);
}
}
int main()
{
ArbolBinario *arbol1 = new ArbolBinario();
arbol1->insertar(100);
arbol1->insertar(50);
arbol1->insertar(25);
arbol1->insertar(75);
arbol1->insertar(150);
cout<<"Impresion entreorden: ";
arbol1->imprimirEntre();
cout<<"Cantidad de nodos del árbol:" <<arbol1->cantidad() <<"\n";
cout<<"Cantidad de nodos hoja:" <<arbol1->cantidadNodosHoja()<<"\n";
cout<<"Impresion en entre orden junto al nivel del nodo:";
arbol1->imprimirEntreConNivel();
cout<<"Artura del arbol:";
cout << arbol1->retornarAltura();
cout << "\n";
arbol1->mayorValor();
cout << "\n";
arbol1->borrarMenor();
cout<<"Luego de borrar el menor:";
arbol1->imprimirEntre();
delete arbol1;
return 0;
}
Este proyecto lo puede descargar en un zip desde este enlace : ArbolBinario2.zip
Para verificar si existe un elemento de información en el árbol disponemos un puntero reco en el nodo apuntado por raiz. Dentro de un while verificamos si la información del parámetro coincide con la información del nodo apuntado por reco, en caso afirmativo salimos del método retornando true, en caso contrario si la información a buscar es mayor a la del nodo procedemos a avanzar reco con la dirección del subárbol derecho:
bool ArbolBinario::existe(int x)
{
Nodo *reco = raiz;
while (reco != NULL)
{
if (x == reco->info)
return true;
else
if (x>reco->info)
reco = reco->der;
else
reco = reco->izq;
}
return false;
}
Para retornar la cantidad de nodos del árbol procedemos a inicializar un atributo de la clase llamado cant con cero. Llamamos al método recursivo y en cada visita al nodo incrementamos el atributo cant en uno (si definimos cant en el método cantidad() no podemos incrementarlo en el otro método):
int ArbolBinario::cantidad()
{
cant = 0;
cantidad(raiz);
return cant;
}
void ArbolBinario::cantidad(Nodo *reco)
{
if (reco != NULL)
{
cant++;
cantidad(reco->izq);
cantidad(reco->der);
}
}
Para imprimir todos los nodos en entre orden junto al nivel donde se encuentra planteamos un método recursivo que llegue la referencia del nodo a imprimir junto al nivel de dicho nodo. Desde el método no recursivo pasamos la referencia a raiz y un uno (ya que raiz se encuentra en el primer nivel)
Cada vez que descendemos un nivel le pasamos la referencia del subárbol respectivo junto al nivel que se encuentra dicho nodo:
void ArbolBinario::imprimirEntreConNivel()
{
imprimirEntreConNivel(raiz, 1);
cout << "\n";
}
void ArbolBinario::imprimirEntreConNivel(Nodo *reco, int nivel)
{
if (reco != NULL) {
imprimirEntreConNivel(reco->izq, nivel + 1);
cout<<reco->info <<"(" <<nivel <<") - ";
imprimirEntreConNivel(reco->der, nivel + 1);
}
}
Para obtener la altura del árbol procedemos en el método no recursivo a inicializar el atributo altura con el valor cero. Luego llamamos al método recursivo con la referencia a raiz que se encuentra en el nivel uno. Cada vez que visitamos un nodo procedemos a verificar si el parámetro nivel supera al atributo altura, en dicho caso actualizamos el atributo altura con dicho nivel.
int ArbolBinario::retornarAltura()
{
altura = 0;
retornarAltura(raiz, 1);
return altura;
}
void ArbolBinario::retornarAltura(Nodo *reco, int nivel)
{
if (reco != NULL)
{
retornarAltura(reco->izq, nivel + 1);
if (nivel>altura)
altura = nivel;
retornarAltura(reco->der, nivel + 1);
}
}
Para imprimir el mayor valor del árbol debemos recorrer siempre por derecha hasta encontrar un nodo que almacene NULL en el puntero der:
void ArbolBinario::mayorValor()
{
if (raiz != NULL)
{
Nodo *reco = raiz;
while (reco->der != NULL)
reco = reco->der;
cout<<"Mayor valor del árbol:" <<reco->info;
}
}
Para borrar el menor valor del árbol lo primero que comprobamos es si el subárbol izquierdo es nulo luego el menor del árbol es el nodo apuntado por raiz, en este caso disponemos un puntero auxiliar bor que apunte a raiz, luego avanzamos a raiz y finamente borramos el nodo que era raiz hasta este momento. Luego si el subárbol izquierdo no está vacío procedemos a descender siempre por la izquierda llevando un puntero en el nodo anterior. Cuando llegamos al nodo que debemos borrar procedemos a enlazar el puntero izq del nodo que se encuentra en el nivel anterior con la referencia del subárbol derecho del nodo a borrar (reco queda apuntantado al nodo a borrar):
void ArbolBinario::borrarMenor()
{
if (raiz != NULL) {
Nodo *bor;
if (raiz->izq == NULL)
{
bor = raiz;
raiz = raiz->der;
delete bor;
}
else {
Nodo *atras = raiz;
Nodo *reco = raiz->izq;
while (reco->izq != NULL)
{
atras = reco;
reco = reco->izq;
}
atras->izq = reco->der;
delete reco;
}
}
}
Este proyecto lo puede descargar en un zip desde este enlace : ArbolBinario2.zip