
Ir al contenido Ir a la navegación Ir al buscador

English Directorio WAP para móvil, Tablet, iPhone o Smartphone Centro de Noticias de la Universidad de Oriente Categorías

Inicio | Contacto | Posts |

TIENDA PUBLISHOP | Sobre nosotros | Registro y Planes | Pagos | Donaciones

Ver Código QR de esta página

Campaña #AyudemosaYuli | Campaña #AyudemosaStephany. | ¿Interesado(a) en cursos y resolución de ejercicios de materias prácticas? Para más información, contáctenos por: Teléfono: +58 (412) - 8226575. WhatsApp y Telegram: +58 (426) - 6836955 o escriba al correo: [email protected]. Únete al grupo: SISTEMAS (UDOMO).

[»]

Musica para tu celular

Buscar en InfoUDO

Estructuras dinámicas en C++: Implementación de un árbol binario

lunes julio 11, 2016

Problema 1:

Desarrollar una clase para la administración de un árbol binario ordenado.

Programa:

#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 << "";
}

void ArbolBinario::imprimirPre(Nodo *reco)
{
    if (reco != NULL)
    {
        cout << reco->info << "-";
        imprimirPre(reco->izq);
        imprimirPre(reco->der);
    }
}

void ArbolBinario::imprimirEntre()
{
    imprimirEntre(raiz);
    cout << "";
}

void ArbolBinario::imprimirEntre(Nodo *reco)
{
    if (reco != NULL)
    {
        imprimirEntre(reco->izq);
        cout << reco->info << "-";
        imprimirEntre(reco->der);
    }
}

void ArbolBinario::imprimirPost()
{
    imprimirPost(raiz);
    cout << "";
}

void ArbolBinario::imprimirPost(Nodo *reco)
{
    if (reco != NULL)
    {
        imprimirPost(reco->izq);
        imprimirPost(reco->der);
        cout << reco->info << "-";
    }
}


void 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;
    cin.get();
}

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 << "";
}

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 << "";
}

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 << "";
}

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;
    }
}

Problema 2:

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 << "";
}

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 << "";
}

void ArbolBinario::imprimirEntre(Nodo *reco)
{
    if (reco != NULL)
    {
        imprimirEntre(reco->izq);
        cout << reco->info << "-";
        imprimirEntre(reco->der);
    }
}

void 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() <<"";
    cout<<"Cantidad de nodos hoja:" <<arbol1->cantidadNodosHoja()<<"";
    cout<<"Impresion en entre orden junto al nivel del nodo:";
    arbol1->imprimirEntreConNivel();
    cout<<"Artura del arbol:";
    cout << arbol1->retornarAltura();
    cout << "";
    arbol1->mayorValor();
    cout << "";
    arbol1->borrarMenor();
    cout<<"Luego de borrar el menor:";
    arbol1->imprimirEntre();
    delete arbol1;
    cin.get();
}

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 << "";
}

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

— @INFOUDO.OFICIAL

Categorías: #C++, #

[0] Atrás | Directorio

Inicio

Apps Infoudo ¡Descarga el icono directo en el menú de tu equipo!

[»] Las mejores Apps para tu celular

[»] Imágenes Gratis

Comenta o lee lo que otros opinan

COMPÁRTELO:

Indica que te gusta y comparte

Facebook

Twitter

También te puede interesar:

NOCIONES BÁSICAS DE LA PROGRAMACIÓN ORIENTADA A OBJETOS.
Material de Apoyo del Curso de Programación - Lenguaje C++ - Periodo (Feb - May) del año en curso
Parámetros por valor y por referencia de objetos
Parámetros por valor y por referencia de datos simples
Métodos constantes (const)
Parámetros de un método constante (const)
Definición de constantes (const)
Directiva #define
Puntero this
Métodos estáticos de una clase

« Estructuras dinámicas en C++: Inserción de nodos y recorrido | Métodos inline »

Buscador:

Síguenos por RSS

Puedes leerlos mediante el navegador Firefox, lectores de noticias en la computadora o el móvil o usando el servicio de Feedburner de Google para recibir las notificaciones por correo electrónico.