¡Hola a todos! Vamos a sumergirnos en el mundo de los árboles binarios en C++. No te preocupes, lo haremos paso a paso.
¿Qué es un Árbol Binario?
Imagina un árbol genealógico. Cada persona tiene (como máximo) dos hijos. Un árbol binario es similar. Es una estructura de datos donde cada elemento, llamado nodo, puede tener como mucho dos "hijos". Estos hijos se llaman hijo izquierdo e hijo derecho.
Piensa en un torneo de tenis. Cada partido tiene dos jugadores. El ganador avanza. Esto se puede representar como un árbol binario. Cada nodo es un partido, y los "hijos" son los dos jugadores.
Must Read
El nodo superior del árbol se llama raíz. Es el punto de partida. Los nodos que no tienen hijos se llaman hojas. Son los finales del árbol.
Terminología Clave
Repasemos algunos términos importantes.
- Nodo: Un elemento en el árbol. Contiene un valor y punteros a sus hijos.
- Raíz: El nodo superior del árbol.
- Hoja: Un nodo que no tiene hijos.
- Hijo Izquierdo: El nodo "debajo" y a la izquierda de un nodo.
- Hijo Derecho: El nodo "debajo" y a la derecha de un nodo.
- Padre: El nodo "encima" de un nodo.
Representación en C++
En C++, podemos representar un nodo de un árbol binario con una estructura o una clase. Veamos un ejemplo usando una estructura:
struct Nodo {
int valor;
Nodo* izquierda;
Nodo* derecha;
};
Aquí, valor guarda la información que queremos almacenar en el nodo. izquierda y derecha son punteros a otros nodos. Es decir, apuntan al hijo izquierdo y al hijo derecho, respectivamente. Si un nodo no tiene un hijo, el puntero correspondiente será nullptr.
Para crear un nuevo nodo, podemos hacer lo siguiente:
Nodo* nuevoNodo = new Nodo;
nuevoNodo->valor = 10;
nuevoNodo->izquierda = nullptr;
nuevoNodo->derecha = nullptr;
Esto crea un nuevo nodo con valor 10 y sin hijos. La palabra clave new reserva memoria para el nuevo nodo.
Recorridos de Árboles Binarios
Una tarea común con los árboles binarios es recorrerlos. Esto significa visitar cada nodo del árbol. Hay varias formas de hacerlo.
Uno de los métodos más comunes es el recorrido in-order. Primero, se recorre el subárbol izquierdo. Luego, se visita el nodo actual. Finalmente, se recorre el subárbol derecho. Esto suele resultar en una visita ordenada de los valores en ciertos tipos de árboles (como los árboles de búsqueda binaria).
Otro método es el recorrido pre-order. Primero, se visita el nodo actual. Luego, se recorre el subárbol izquierdo. Finalmente, se recorre el subárbol derecho.
El último que veremos es el recorrido post-order. Primero, se recorre el subárbol izquierdo. Luego, se recorre el subárbol derecho. Finalmente, se visita el nodo actual.
Ejemplo de Recorrido In-Order
Aquí hay un ejemplo de cómo se vería un recorrido in-order en C++:
void inOrder(Nodo* nodo) {
if (nodo != nullptr) {
inOrder(nodo->izquierda);
std::cout << nodo->valor << " ";
inOrder(nodo->derecha);
}
}
Esta función usa recursión para recorrer el árbol. La recursión es cuando una función se llama a sí misma.
¡Espero que esto te haya ayudado a comprender los conceptos básicos de los árboles binarios en C++! Recuerda practicar y experimentar con código para afianzar tus conocimientos. ¡Mucha suerte!
