Published on
May 21, 2020

­čî│ ├ürboles ­čî│

Authors
  • tanx
    Name
    Tania Z├║├▒iga
    tanx
    @tanx

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.

arbol azul
Imagen 1: Árbol azul, indicando partes del árbol.

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