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

\begin{algorithm}
\caption{Preorden}
\begin{algorithmic}
\FUNCTION{Preorden}{INodo $n$}
    \IF{ $n$ es valido } 
        \STATE \CALL{Listar}{ $n.obtenerValor( )$ }
        \STATE \CALL{Preorden}{ $n.hijoIzquierdo( )$ }
        \STATE \CALL{Preorden}{ $n.hermanoDerecho( )$ }
    \ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}


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


Inorden

\begin{algorithm}
\caption{Inorden}
    \begin{algorithmic}
    \FUNCTION{Inorden}{INodo $n$}
        \IF{ $n.hijoIzquierdo( )$ no es valido } 
            \STATE \CALL{Listar}{$n.obtenerValor( )$ }
        \ELSE
            \STATE \CALL{Inorden}{$n.hijoIzquierdo( )$}
            \STATE \CALL{Listar}{$n.obtenerValor( )$ }
            \STATE $h = n.hermanoDerecho( ) $
            \WHILE{ $h$ sea valido }
                \STATE \CALL{Inorden}{$h$}
                \STATE $h = n.hermanoDerecho( ) $
            \ENDWHILE
        \ENDIF
    \ENDFUNCTION
    \end{algorithmic}
    \end{algorithm}


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


Postorden

\begin{algorithm}
\caption{Inorden}
    \begin{algorithmic}
    \FUNCTION{Postorden}{INodo $n$}
        \IF{ $n$ es valido } 
            \STATE \CALL{Postorden}{$n.hijoIzquierdo( )$}
            \STATE \CALL{Listar}{$n.obtenerValor( )$ }
            \STATE \CALL{Postorden}{$n.hermanoDerecho( )$}
        \ENDIF
    \ENDFUNCTION
    \end{algorithmic}
    \end{algorithm}


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


Por nivel

\begin{algorithm}
\caption{Level Order}
    \begin{algorithmic}
    \FUNCTION{Nivel}{INodo $n$}
        \STATE Queue $q$
        \STATE $q.enqueue(n)$
        \WHILE{ $q$ tenga elementos }
            \STATE $root = q.dequeue( ) $
            \STATE \CALL{Listar}{$root.obtenerValor( )$ }
            \STATE $hijo = root.hijoIzquierdo( ) $
            \WHILE{ $hijo$ sea valido }
                \STATE $q.enqueue(hijo)$
                \STATE  $hijo = hijo.hijoIzquierdo( ) $
            \ENDWHILE
        \ENDWHILE
    \ENDFUNCTION
    \end{algorithmic}
    \end{algorithm}


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