🌳 Árboles 🌳

Un árbol es una estructura de datos no lineal que colecciona elementos llamados nodos. Este se caracteriza por imponer una estructura jerárquica en un conjunto de datos.

Uno de los nodos del árbol es llamado raíz (root), se caracteriza por no tener ascendencia (no tiene padre). El descendiente de un nodo es llamado hijo (child). La conexión entre dos nodos es llamada “relación de paternidad” o edge.

Ojo 👀

Un nodo puede tener n hijos, n es un número entero positivo. No nos estamos limitando a Arboles Binarios, por ahora.

Los nodos que pertenecen al mismo padre son hermanos (siblings). Por ejemplo, en la Imagen 1 de abajo vemos como los nodos G, H I son hermanos. Por otro lado, el nodo F no tiene hermanos.

Una hoja (leaf) es un nodo que no tiene hijos. En nuestro ejemplo, los nodos F, K, D y J son hojas.

La altura (height) de un nodo es el numero total de edges desde un nodo en particular hasta la hoja más lejana. La altura de un árbol, es la altura de su raíz. Por ejemplo, la altura del Árbol azul es tres.

Por otro lado, la profundidad (depth) de un nodo es el número total de edges desde la raíz hasta un nodo particular. Por ejemplo, la profundidad del nodo J es dos.

En un árbol, la raíz siempre está en el Nivel 0 y los hijos de la raíz están en el Nivel 1 y los hijos de los nodos que están en el Nivel 1 estarán en el Nivel 2 y así sucesivamente. Del lado derecho del Árbol azul se denota el nivel correspondiente.

Hay diversas formas de recorrer todos los nodos de un árbol. Explicaré en pseudocódigo los cuatro recorridos más comunes. Para ello vamos a tomar en cuenta que los nodos de nuestro árbol tienen los siguientes métodos:

• Padre(): Devuelve el nodo que es padre. Si el iNodo es la raíz, la cual no tiene padre, se devuelve un valor indeterminado.

• hijoIzquierdo(): Devuelve el nodo hijo que está más a la izquierda. Si el INodo es una hoja, devuelve un valor indeterminado por no tener hijos.

• hermanoDerecho(): Devuelve el nodo hermano que está inmediatamente a la derecha. Por ejemplo, en el Árbol azul, el hermano derecho de G es H. Si el INodo no tiene hermano derecho, es decir, es el hijo más a la derecha de su padre, devuelve un valor indeterminado.

• obtenerValor(): Devuelve la información almacenada en el INodo.

function Preorden(INodo n):
    if n es valido:
        console.log(n.obtenerValor())
        Preorden(n.hijoIzquierdo())
        Preorden(n.hermanoDerecho())
    end if
end function

Si recorremos el Árbol azul en Preorden obtendremos:

[A, B, F, C, G, K, H, I, D, E, J]

function Inorden(INodo n):
    if n.hijoIzquierdo() no es valido:
        Listar(n.obtenerValor())
    else:
        Inorden(n.hijoIzquierdo())
        Listar(n.obtenerValor())
        h = n.hermanoDerecho()
        while h sea valido:
            Inorden(h)
            h = n.hermanoDerecho()
        end while
    end if
end function

Si recorremos el Árbol azul en Inorden obtendremos: [F, B, A, K, G, C, H, I, D, J, E]

function Postorden(INodo n):
    if n es valido then:
        Postorden(n.hujoIzquierdo())
        Listar(n.obtenerValor())
        Postorden(n.hermanoDerecho())
    end if
end function

Si recorremos el Árbol azul en Postorden obtendremos: [F, B, K, G, H, I, C, D, J, E, A]

function Nivel(INodo n):
    Queue q
    q.enqueue(n)
    while q tenga elementos do:
        root = q.dequeue()
        Listar(root.obtenerValor())
        hijo = root.hijoIzquierdo()
        while hijo sea valido do:
            q.enqueue(hijo)
            hijo = hijo.hijoIzquierdo()
        end while
    end while
end function

Si recorremos el Árbol azul por Nivel obtendremos:

[A, B, C, D, E, F, G, H, I, J, K]

Para estar familiarizados con los términos tanto en inglés, como en español.

root == raíz

si... entonces == if... then