­čî│ ├ürboles ­čî│

| By Tania Z├║├▒iga

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.


Terminolog├şa

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.


Recorrido de árboles

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:

INodo (Interfaz Nodo)

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


Preorden

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]


Inorden

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]


Postorden

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]


Por nivel

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]

┬┐Por qu├ę usas spanglish?

Para estar familiarizados con los t├ęrminos tanto en ingl├ęs, como en espa├▒ol.

root == ra├şz

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