Ir al contenido principal

Árboles Binarios de Búsqueda en C++ | Recorrido por niveles (Amplitud)

Hola a todos en esta ocasión compartiré sobre este tema de Arboles Binarios de Búsqueda, como un poco de teoría para su mejor entendimiento seguidamente mostraré la implementación en lenguaje de programación C++. Primero una breve introducción a árboles.


¿Qué es un árbol?


Un árbol es una estructura de datos no lineal puesto que cada elemento apunta a uno o varios elementos del mismo tipo; esto es dado un elemento, no hay un único camino a seguir. El elemento que apunta a otro es llamado padre, mientras que el elemento apuntado se conoce como hijo. Todos los elementos tienen un padre a excepción de la raíz. Puede decirse que un árbol esta formado por subárboles resaltando así su naturaleza recursiva.

¿Qué es un árbol binario?

Un árbol binario es aquel es el que cada elemento apunta como máximo a otros 2 elementos, comúnmente llamados hijo izquierdo y hijo derecho.


¿Qué es un árbol binario de búsqueda?

Un árbol binario de buque da o ABB, es un árbol binario en el cual para todo elemento, los elementos mayores a él, se ubican en su rama derecha, mientras que los elementos menores van en su rama izquierda. Cada elemento se almacena una sola vez por lo que no existen elementos repetidos.


Ya con estas definiciones claras sobre arboles;ahora estos son conceptos generales de lo que es un árbol, para poder implementarlos en lenguaje C++ tenemos que tener conocimientos previos sobre listas enlazadas y su implementación.

Cada elemento(nodo) de un árbol ABB cuenta con tres campos:
  • Dato(numero, letra, palabra, etc), en este caso usaremos un numero(entero).
  • Puntero al nodo derecho
  • Puntero al nodo izquierdo

Los punteros tienen que ser del tipo árbol, ya que apuntaran a un nodo del mismo tipo, este seria un ejemplo de como se seria el tipo arbol ABB.

Primero creamos el nodo:

struct nodo{
   int dato;
   struct nodo *der;
   struct nodo *izq;
};

Los punteros son variables que guardaran en la memoria la dirección de otra variable en este caso la de una estructura llamado nodo.

Recorridos de una árbol

Es la manera recursiva como pasaremos por cada nodo del árbol, existes tres formas:
  • Enorden: Si visitamos primero hijo izquierdo, luego el padre y finalmente el hijo derecho
  • Preorden: Primero el padre, luego el hijo izquierdo y finalmente el hijo derecho.
  • Postorden: Primero hijo izquierdo, luego el hijo derecho y finalmente el padre

Existe muchos mas conceptos sobre arboles ABB por ejemplo, recorridos por nivel, profundidad de una árbol, etc; por ahora solo dejare esos conceptos. Ahora pasaremos a la implementaciónen lenguaje C++ como le había comentado al inicio del post.

Implementación:


Como verán el árbol se muestra girado 90° a la izquierda, ya que es un poco difícil implementarlo verticalmente, tratare de poder hacerlo y los estaré compartiendo con ustedes.

Comentarios

  1. muy buen aporte amigo! Funciona perfecto y bastante fácil de entender. Muchas gracias!!

    ResponderEliminar
  2. Muchas gracias te he escrito en facebook espero me ayudes !

    ResponderEliminar
  3. Muy buen aporte... Gracias me ayudo bastante...

    ResponderEliminar
  4. Pues simplemnente luego de tener tu cadena almacenada; en un bucle for en lugar de ingresar entero como dato, le asignas cada posicion de la cadena. Quedaria algo asi:

    cin >> cad;
    for(int i=0; i<strlen(cad); i++)
    {
    x = cad[i]; // el 'x' tiene que se tipo char
    insertar( arbol, x);
    }

    Tendrias que cambiar tambien el tipo de dato a 'char nro;' creado en struct nodo{..}; y tambien el tipo de dato a 'char' en lugar de 'int' de los parametros de las funciones donde se manda a 'x' como parametro. Saludos y suerte con la codificacion :)

    PD: El los 'if' del algoritmo de compararia los codigos ASCII

    ResponderEliminar
  5. Pidrias tambien declarar en lugar de char con string, y utilizar operadores < y >, te los compararia por orden alfabetico sin meterse en tantos problemas como con char y codigo ascii

    ResponderEliminar
  6. Solo una duda en la función insertar. void insertar(ABB &arbol, int x).
    ¿Qué rayos significa el '&' para que se usa?

    ResponderEliminar
  7. El '&' se usa para pasar un parametro por referencia, en otras palabras en esa funcion la variable arbol su moficacion(inserciones) sera permanente que es lo que queremos. Si no se usara '&' (parametro por valor) la variable 'arbol' solo se moficaria en esa funcion y al volver al main() seria la misma con la que se llamo a la funcion. Espero haberme dejado enteder. Saludos y gracias por comentar :D!

    ResponderEliminar
  8. Muy buen aporte, solo una duda... ¿en que parte del codigo reservas la memoria en el heap?
    porque veo que incluyes stdlib.h pero en ninguna parte del codigo veo que usas la instruccion malloc, gracias y saludos! :D

    ResponderEliminar
  9. "stdlib" es para la funciones system("pause"). Este programa esta hecho en C++, para reservar memoria se ha usado "new". Espero haberte ayudado :)

    ResponderEliminar
  10. Que tal amigo tengo una duda estoy usando una estructura similar pero quiero eliminar un o bueno liberar la memoria de ese nodo tengo que liberar primero cada subnodo o solo libero la del nodo y sus subnodos se libera?

    ResponderEliminar
  11. Hola amigo, gracias por la explicación aunque tengo una duda, como se haría una función para buscar un elemento? Estoy quebrandome la cabeza con eso pero ningun avance hasta ahora... :(

    ResponderEliminar
  12. Amigo Dicuslpa y si deseo palabras completas y no solo caracteres? Gracias ;)

    ResponderEliminar
  13. Puedes usar std::string en lugar de int, solo modifica la estructura nodo el campo 'nro' :)

    ResponderEliminar
  14. Muy buen ejemplo, excelente trabajo.

    ResponderEliminar
  15. Excelente tu aporte, felicitaciones. Mis dudas son: a) cómo imprimir el árbol verticalmente; y b) cómo imprimir por niveles en forma horizontal, comenzando desde la raíz. Y muchas gracias por tu aporte :D.

    ResponderEliminar

Publicar un comentario

Entradas populares de este blog

Obtener numeros aleatorios en C++ (rand, srand)

Es algo muy frecuente, cuando ya dominas todo eso de pedir y almacenar datos, ahora tu profesor te pedirá que tus programas generen números aleatorios para automatizar el proceso de llenar arreglos y todo eso.
Así que lo primero que tenemos que hacer es incluir la librería:
#include<stdlib.h>

Necesitamos esta libreria para usar la función time()
#include<time.h>

Luego inicializar los números aleatorios incluyendo esto:
srand(time(NULL));

Luego guardar el número aleatorio en alguna parte:
num = rand();

Para ajustar el rango de número aleatorios podemos hacer varias cosas.

- Número aleatorios entre 0 y 50:
  num=rand()%51;

- Número aleatorios entre 1 y 100:
  num=1+rand()%(101-1);

- Número aleatorios entre 250 y 420:
  num=250+rand()%(421-250);

De forma general es:
variable = limite_inferior + rand() % (limite_superior +1 - limite_inferior) ;

Así que un programa que muestre 10 números aleatorios entre 1 y 10 quedaría así:

Serie de Fibonacci en C++

Una sucesión de Fibonacci es aquella cuya ley de recurrencia es: an = an-1 + an-2. Es decir, cada término de la sucesión se obtiene sumando los dos anteriores. Para empezar a construirla necesitamos, por tanto, dos números de partida, a1 y a2. De esta forma, a3 sería a2 + a1 ; a4 sería a3 + a2 y así sucesivamente.


La más conocida es la que tiene a1 = 1 y a2 = 1, cuyos términos son: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377 ... números que son conocidos como Números de Fibonacci.

Los términos de cualquier sucesión de Fibonacci tienen la particularidad de que el cociente entre dos términos consecutivos se aproxima al Número de Oro (1.6180339887499...), es decir, el límite de los cocientes an+1/an tiende al Número de Oro cuando n tiende a infinito.

Además, las series de Fibonacci cumplen otras curiosas propiedades, como por ejemplo, que la suma de n términos es igual al término n+2 menos uno:

a1 + a2 + a3 + a4 + ..... + an-1 + an = an+2 - 1

Implementación