Un ÁRBOL es una estructura de datos que se utiliza para representar relaciones jerárquicas entre elementos.
Los ÁRBOLES son una versión reducida de un GRAFO orientado. Por tanto, está compuesto por nodos interconectados, donde cada nodo puede tener cero o más nodos hijos.
Sin embargo, el ÁRBOL añade las restricciones de que:
- Cada nodo nodo únicamente puede tener un padre
- Es acíclico
En consecuencia, un ÁRBOL da como resultado una estructura que se origina en un único nodo, y a partir de ahí se ramifica… pues eso, como un árbol.
El nodo en la parte superior se conoce como el nodo raíz. Cada relación padre-hijo se denomina rama. Los nodos sin hijos se llaman hojas. Y creo que ya se quedaron sin símiles botánicos 🌱
Los ÁRBOLES son una estructura muy empleada, porque permiten representar datos con jerarquía. Con eso nos referimos a que cada dato puede tener otros datos dentro.
Pongamos algún ejemplo. La organización de archivos en un sistema de archivos sigue una estructura de árbol. Cada directorio puede contener archivos y subdirectorios, y estos a su vez a otros. Así sucesivamente.
Otro ejemplo, el organigrama de una empresa se podría representar mediante un árbol. Cada nodo representa un empleado o un departamento, y las relaciones jerárquicas entre ellos se representan mediante las conexiones entre los nodos.
Más ejemplos, la lista de productos disponibles en una tienda online. Cada nodo representa una categoría de productos (por ejemplo, alimentos, productos de limpieza, etc.) y los elementos de cada categoría son los productos individuales.
Finalmente, en el desarrollo web, el Document Object Model (DOM) representa la estructura de una página web como un árbol. Donde cada elemento HTML es un nodo en el árbol, y contiene otros elementos en su interior.
Es decir, que los árboles son una de las estructuras que más frecuentemente vais a emplear. Así que conviene aprender a usarla.
Componentes de un Árbol
- Nodo: Un nodo es una entidad básica de un árbol que puede contener información y referencias a sus nodos hijos
Nodo raíz: Es el nodo principal del árbol, desde el cual se ramifican todos los demás nodos. Un árbol solo puede tener un nodo raíz.
Nodo hoja: Un nodo hoja es aquel que no tiene nodos hijos. Es decir, es el extremo de una rama en el árbol.
Rama: Es cada una de las relaciones entre un nodo padre y sus hijos.
Nivel del nodo: El nivel de un nodo es su distancia desde el nodo raíz. El nivel del nodo raíz es 0, y el nivel de los nodos hijos directos del nodo raíz es 1, y así sucesivamente.
Altura de árbol: La altura de un árbol es la longitud del camino más largo desde la raíz hasta una hoja.
Subárbol: Un subárbol es un conjunto de nodos y aristas que forman un árbol dentro de un árbol más grande. Cada nodo en un árbol puede considerarse como la raíz de un subárbol.
Tipos de Árboles
Los árboles pueden clasificarse en varios tipos según su estructura y las restricciones que imponen. Algunos tipos comunes de árboles incluyen:
- Árboles N-arios: En un árbol N-ario, cada nodo puede tener un número variable de hijos. Esto lo hace más general que un árbol binario.
- Árboles Binarios: Un árbol binario es aquel en el que cada nodo puede tener como máximo dos nodos hijos, generalmente denominados hijo izquierdo y hijo derecho.
- Árboles de Búsqueda Binaria: Un árbol de búsqueda binaria es un tipo especial de árbol binario en el que para cada nodo, los nodos en el subárbol izquierdo tienen valores menores que el nodo actual, y los del subárbol derecho valores mayores que el nodo actual. Esto lo hace muy apropiado para búsquedas.
Búsqueda DFS y BFS
Al trabajar con ÁRBOLES, lo primero que vais a necesitar es una forma de recorrerlos. Para acceder a sus nodos, para buscar elementos, para todo.
Los dos algoritmos comunes para recorrer árboles son:
- DFS (Depth-First Search, Búsqueda en Profundidad)
- BFS (Breadth-First Search, Búsqueda en Anchura)
Aunque a estos algoritmos se les llama de “búsqueda”, pero no únicamente sirven para buscar un nodo. Sirven para recorrer el árbol, y hacer cualquier operación en los nodos que queramos.
No hay uno mejor que otro, en algunos problemas será mejor DFS, en otro BFS, y en muchos nos dará igual uno que otro. Vamos a echarles un ojo.
Búsqueda en Profundidad (DFS)
Este método DFS recorre el árbol en profundidad, visitando todos los descendientes de un nodo antes de pasar al siguiente hermano.
Es decir, supongamos que queremos hacer una acción en un nodo. Le voy a llamar la acción 🎇. Por ejemplo, queremos inicializar el valor de cada nodo, o buscar, o lo que sea.
El DFS se llama “en profundidad”, porque prioriza bajar en vertical. Así coge el root del árbol y baja hasta el final todo lo que puede. A continuación, retrocede, se desplaza en horizontal, y vuelve a bajar todo lo que puede.
Normalmente el DFS se implementa como una función recursiva, bastante sencilla:
- Comenzar desde el nodo raíz
- Llamar a la función recursiva 🔁 para cada uno de sus hijos
- Después ejecutar
la acción🎇 en nodo
recursiva_DFS(node, action)
{
// Recorre todos los hijos del nodo actual
node.childs.foreach(child => recursiva_DFS(child, action));
// Después de visitar todos los hijos, se aplica la acción al nodo actual
action(node);
}Búsqueda en Anchura (BFS)
La método BFS recorre todos los nodos de un nivel, antes de pasar al siguiente nivel, visitando todos los vecinos de un nodo antes de continuar con el siguiente nivel.
El BFS se llama “en anchura”, porque prioriza expandirse en horizontal. Así coge la raíz del árbol y pasa por todos sus hijos. Luego pasa al siguiente nivel, y procesa todos los nodos. Va bajando de nivel hasta que acaba.
Para implementar un BFS, generalmente usaremos una colección auxiliar, como una lista o una cola. El algoritmo es:
- Comenzar desde el nodo raíz, lo metes en la cola
- Mientras la cola no esté vacía
- Sacas el primer nodo, y le ejecutas
la acción🎇 - Metes todos los hijos de este nodo en la cola
- Sacas el primer nodo, y le ejecutas
recursiva_BFS(node, action)
{
queue = new Queue(); // Creamos una cola para almacenar los nodos a visitar
queue.enqueue(node); // Agregamos el nodo raíz a la cola
while (!queue.isEmpty()) { // Mientras haya nodos en la cola
current = queue.dequeue(); // Sacamos el primer nodo de la cola
action(current); // Aplicamos la acción al nodo actual
// Agregamos los hijos del nodo actual a la cola
current.childs.foreach(child => queue.enqueue(child));
}
}Ejemplo de Árboles en diferentes lenguajes
Vamos a ver como implementar un árbol no binario en distintos lenguajes de programación:
using System;
using System.Collections.Generic;
class Node
{
public int Value { get; set; }
public List<Node> Children { get; set; }
public Node(int value)
{
Value = value;
Children = new List<Node>();
}
public void AddChild(Node child)
{
Children.Add(child);
}
public override string ToString()
{
return $"Node Value: {Value}";
}
}
class Tree
{
public Node Root { get; set; }
public Tree()
{
Root = null;
}
public void PrintTree(Node node, string indent = "")
{
if (node == null) return;
Console.WriteLine(indent + node.ToString());
if (node.Children != null)
{
foreach (var child in node.Children)
{
PrintTree(child, indent + " ");
}
}
}
public Node Search(int value, Node node)
{
if (node == null) return null;
if (node.Value == value) return node;
foreach (var child in node.Children)
{
var foundNode = Search(value, child);
if (foundNode != null) return foundNode;
}
return null;
}
public void DFS(Node node)
{
if (node == null) return;
Console.WriteLine(node.Value);
if (node.Children != null)
{
foreach (var child in node.Children)
{
DFS(child);
}
}
}
public void BFS()
{
if (Root == null) return;
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(Root);
while (queue.Count > 0)
{
Node current = queue.Dequeue();
Console.WriteLine(current.Value);
foreach (var child in current.Children)
{
queue.Enqueue(child);
}
}
}
}
class Program
{
static void Main(string[] args)
{
Tree tree = new Tree();
tree.Root = new Node(1);
tree.Root.AddChild(new Node(2));
tree.Root.AddChild(new Node(3));
tree.Root.Children[0].AddChild(new Node(4));
// Imprimir el árbol
Console.WriteLine("Árbol:");
tree.PrintTree(tree.Root);
// Buscar un valor en el árbol
int valueToFind = 4;
Node foundNode = tree.Search(valueToFind, tree.Root);
if (foundNode != null)
{
Console.WriteLine($"\nSe encontró el nodo con valor {valueToFind}: {foundNode}");
}
else
{
Console.WriteLine($"\nNo se encontró el nodo con valor {valueToFind}.");
}
// DFS
Console.WriteLine("\nRecorrido en Profundidad (DFS):");
tree.DFS(tree.Root);
// BFS
Console.WriteLine("\nRecorrido en Amplitud (BFS):");
tree.BFS();
}
}
#include <iostream>
#include <queue>
#include <vector>
class Node {
public:
int value;
std::vector<Node*> children;
Node(int val) : value(val) {}
void addChild(Node* child) {
children.push_back(child);
}
};
class Tree {
public:
Node* root;
Tree() : root(nullptr) {}
void printTree(Node* node, std::string indent = "") {
if (node == nullptr) return;
std::cout << indent << "Node Value: " << node->value << std::endl;
for (auto child : node->children) {
printTree(child, indent + " ");
}
}
Node* search(int value, Node* node) {
if (node == nullptr) return nullptr;
if (node->value == value) return node;
for (auto child : node->children) {
Node* foundNode = search(value, child);
if (foundNode != nullptr) return foundNode;
}
return nullptr;
}
void DFS(Node* node) {
if (node == nullptr) return;
std::cout << node->value << std::endl;
for (auto child : node->children) {
DFS(child);
}
}
void BFS() {
if (root == nullptr) return;
std::queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* current = q.front();
q.pop();
std::cout << current->value << std::endl;
for (auto child : current->children) {
q.push(child);
}
}
}
};
int main() {
Tree tree;
tree.root = new Node(1);
tree.root->addChild(new Node(2));
tree.root->addChild(new Node(3));
tree.root->children[0]->addChild(new Node(4));
// Imprimir el árbol
std::cout << "Árbol:" << std::endl;
tree.printTree(tree.root);
// Buscar un valor en el árbol
int valueToFind = 4;
Node* foundNode = tree.search(valueToFind, tree.root);
if (foundNode != nullptr) {
std::cout << "\nSe encontró el nodo con valor " << valueToFind << ": Node Value: " << foundNode->value << std::endl;
} else {
std::cout << "\nNo se encontró el nodo con valor " << valueToFind << "." << std::endl;
}
// DFS
std::cout << "\nRecorrido en Profundidad (DFS):" << std::endl;
tree.DFS(tree.root);
// BFS
std::cout << "\nRecorrido en Amplitud (BFS):" << std::endl;
tree.BFS();
// Liberar memoria
delete tree.root->children[0]->children[0];
delete tree.root->children[0];
delete tree.root->children[1];
delete tree.root;
return 0;
}
class Node {
constructor(value) {
this.value = value;
this.children = [];
}
addChild(child) {
this.children.push(child);
}
}
class Tree {
constructor() {
this.root = null;
}
printTree(node, indent = "") {
if (node === null) return;
console.log(indent + "Node Value: " + node.value);
for (let child of node.children) {
this.printTree(child, indent + " ");
}
}
search(value, node) {
if (node === null) return null;
if (node.value === value) return node;
for (let child of node.children) {
let foundNode = this.search(value, child);
if (foundNode !== null) return foundNode;
}
return null;
}
DFS(node) {
if (node === null) return;
console.log(node.value);
for (let child of node.children) {
this.DFS(child);
}
}
BFS() {
if (this.root === null) return;
let queue = [this.root];
while (queue.length > 0) {
let current = queue.shift();
console.log(current.value);
for (let child of current.children) {
queue.push(child);
}
}
}
}
// Crear el árbol
let tree = new Tree();
tree.root = new Node(1);
tree.root.addChild(new Node(2));
tree.root.addChild(new Node(3));
tree.root.children[0].addChild(new Node(4));
// Imprimir el árbol
console.log("Árbol:");
tree.printTree(tree.root);
// Buscar un valor en el árbol
let valueToFind = 4;
let foundNode = tree.search(valueToFind, tree.root);
if (foundNode !== null) {
console.log(`\nSe encontró el nodo con valor ${valueToFind}: Node Value: ${foundNode.value}`);
} else {
console.log(`\nNo se encontró el nodo con valor ${valueToFind}.`);
}
// DFS
console.log("\nRecorrido en Profundidad (DFS):");
tree.DFS(tree.root);
// BFS
console.log("\nRecorrido en Amplitud (BFS):");
tree.BFS();
class Node:
def __init__(self, value):
self.value = value
self.children = []
def add_child(self, child):
self.children.append(child)
class Tree:
def __init__(self):
self.root = None
def print_tree(self, node, indent=""):
if node is None:
return
print(indent + "Node Value: " + str(node.value))
for child in node.children:
self.print_tree(child, indent + " ")
def search(self, value, node):
if node is None:
return None
if node.value == value:
return node
for child in node.children:
found_node = self.search(value, child)
if found_node is not None:
return found_node
return None
def dfs(self, node):
if node is None:
return
print(node.value)
for child in node.children:
self.dfs(child)
def bfs(self):
if self.root is None:
return
queue = [self.root]
while queue:
current = queue.pop(0)
print(current.value)
for child in current.children:
queue.append(child)
# Crear el árbol
tree = Tree()
tree.root = Node(1)
tree.root.add_child(Node(2))
tree.root.add_child(Node(3))
tree.root.children[0].add_child(Node(4))
# Imprimir el árbol
print("Árbol:")
tree.print_tree(tree.root)
# Buscar un valor en el árbol
value_to_find = 4
found_node = tree.search(value_to_find, tree.root)
if found_node is not None:
print(f"\nSe encontró el nodo con valor {value_to_find}: Node Value: {found_node.value}")
else:
print(f"\nNo se encontró el nodo con valor {value_to_find}.")
# DFS
print("\nRecorrido en Profundidad (DFS):")
tree.dfs(tree.root)
# BFS
print("\nRecorrido en Amplitud (BFS):")
tree.bfs()