📅 Lun, 22 Abr 2024 ⏲️ ~ 11 minutos Avanzado

Qué son y cómo usar los Árboles

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.

curso-programacion-arbol

Adivina porqué se le llama á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

arboles-nodos

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.

programacion-arbol-nario

Sin límite de hijos

Á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.

programacion-arbol-binario

Máximo dos hijos

Á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.

programacion-arbol-dfs

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.

programacion-arbol-bfs

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
1. Sacas el primer nodo, y le ejecutas la acción🎇
2. Metes todos los hijos de este nodo en la cola

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

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

C++

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

JavaScript

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();

Python

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()