Embedded Files
Árboles Binarios de Búsqueda en C++ | Recorrido por niveles (Amplitud)
Á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.
/*
* C++ - Arboles Binaros de busqueda -Recorridos por amplitud
*
* Copyright 2014 Martin Cruz Otiniano
*
* Description: Recorrdos por Orden, Pre-Orden y Post-Orden
*
* Site: martincruz.me
*/
#include <iostream>
#include <cstdlib>
using namespace std;
struct nodo{
int nro;
struct nodo *izq, *der;
};
typedef struct nodo *ABB;
/* es un puntero de tipo nodo que hemos llamado ABB, que ulitizaremos
para mayor facilidad de creacion de variables */
ABB crearNodo(int x)
{
ABB nuevoNodo = new(struct nodo);
nuevoNodo->nro = x;
nuevoNodo->izq = NULL;
nuevoNodo->der = NULL;
return nuevoNodo;
}
void insertar(ABB &arbol, int x)
{
if(arbol==NULL)
{
arbol = crearNodo(x);
}
else if(x < arbol->nro)
insertar(arbol->izq, x);
else if(x > arbol->nro)
insertar(arbol->der, x);
}
void preOrden(ABB arbol)
{
if(arbol!=NULL)
{
cout << arbol->nro <<" ";
preOrden(arbol->izq);
preOrden(arbol->der);
}
}
void enOrden(ABB arbol)
{
if(arbol!=NULL)
{
enOrden(arbol->izq);
cout << arbol->nro << " ";
enOrden(arbol->der);
}
}
void postOrden(ABB arbol)
{
if(arbol!=NULL)
{
postOrden(arbol->izq);
postOrden(arbol->der);
cout << arbol->nro << " ";
}
}
void verArbol(ABB arbol, int n)
{
if(arbol==NULL)
return;
verArbol(arbol->der, n+1);
for(int i=0; i<n; i++)
cout<<" ";
cout<< arbol->nro <<endl;
verArbol(arbol->izq, n+1);
}
int main()
{
ABB arbol = NULL; // creado Arbol
int n; // numero de nodos del arbol
int x; // elemento a insertar en cada nodo
cout << "\n\t\t ..[ ARBOL BINARIO DE BUSQUEDA ].. \n\n";
cout << " Numero de nodos del arbol: ";
cin >> n;
cout << endl;
for(int i=0; i<n; i++)
{
cout << " Numero del nodo " << i+1 << ": ";
cin >> x;
insertar( arbol, x);
}
cout << "\n Mostrando ABB \n\n";
verArbol( arbol, 0);
cout << "\n Recorridos del ABB";
cout << "\n\n En orden : "; enOrden(arbol);
cout << "\n\n Pre Orden : "; preOrden(arbol);
cout << "\n\n Post Orden : "; postOrden(arbol);
cout << endl << endl;
system("pause");
return 0;
}
Page updated
Report abuse