Estructura de Datos : Arboledas Binarias

Definiciones

• Una arboleda es un conjunto de árboles. Si T1, T2, T3, ..., Tn son los árboles comunes de una arboleda, denotaremos a la arboleda como A( T1, T2, T3, ..., Tn ) y al árbol binario que la representa por B( T1, T2, T3, ...; Tn ).
• Todo árbol común representado con un árbol binario tiene en el nodo raíz, el enlace derecho vacio, ya que a ese nivel, el árbol común, no tiene hermanos. Si a cada árbol común de una arboleda lo representamos como un árbol binario, todos sus nodos raíz tendrán el enlace vacio. La arboleda se conforma enlazando todos los nodos raices con el enlace derecho vacio de su nodo raíz. Esta interpretación significa considerar a todos los nodos raices de los árboles comunes de la arboleda como hermanos. Una arboleda binaria es una arboleda común representada a través de un árbol binario.
• La transformación de una arboleda a un árbol binario se enuncia diciendo :
  • Si existe A( T1, T2, ....., Tn ), luego el árbol binario correspondiente a la arboleda B(T1, T2, ....., Tn), es :
    • Un árbol binario, vacio, si n es igual a 0
    • Un árbol binario, con las siguientes características, si n es distinto de 0
      • La raíz es T1
      • El subárbol isquierdo es igual a B(T11, T12, ....., T1m) donde T11, T12, ....., T1m son los subárboles de root(T1)
      • El subárbol derecho es B(T2, ....., Tn)

Ejemplos

                       *---*                        *---*                        *---*
                       | A |                        | E |                        | G |
                       *---*                        *---*                        *---*
                        |||                           |                           | |
             +----------+|+----------+                |                +----------+ +----------+
             |           |           |                |                |                       |
           *---*       *---*       *---*            *---*            *---*                   *---*
           | B |       | C |       | D |            | F |            | H |                   | I |
           *---*       *---*       *---*            *---*            *---*                   *---*

                                                 Arboleda  1



                                                    *---*
                                                    | A |
                                                    *---*
                                                     | |
                                        +------------+ +------------+
                                        |                           |
                                      *---*                       *---*
                                      | B |                       | E |
                                      *---*                       *---*
                                         |                         | |
                                         +---+                 +---+ +---+
                                             |                 |         |
                                           *---*             *---*     *---*
                                           | C |             | F |     | G |
                                           *---*             *---*     *---*
                                              |                         |
                                              +---+                 +---+
                                                  |                 |
                                                *---*             *---*
                                                | D |             | H |
                                                *---*             *---*
                                                                     |
                                                                     +---+
                                                                         |
                                                                       *---*
                                                                       | I |
                                                                       *---*

                                                   Arbol 1

Terminología

1. Arboleda ( Forest of Trees )

Travesías de Arboledas

Las travesías preorder e inorder del árbol binario que representa la arboleda tiene un correspondencia natural con las travesías de la arboleda. Siendo T el árbol binario que representa la arboleda F :

1. Travesía Preorder de la Arboleda
   1. Si F está vacia, entonces retornar
   2. Visitar el nodo raíz del primer árbol de F
   3. Ejecutar la travesía preorder del primer árbol de F
   4. Ejecutar la travesía preorder de los siguientes árboles de F
2. Travesía Inorder de la Arboleda
   1. Si F está vacia, entonces retornar
   2. Ejecutar la travesía inorder del primer árbol de F
   3. Visitar el nodo raíz del primer árbol de F
   4. Ejecutar la travesía inorder de los siguientes árboles de F
3. Travesía Postorder de la Arboleda
   1. Si F está vacia, entonces retornar
   2. Ejecutar la travesía postorder del primer árbol de F
   3. Ejecutar la travesía postorder de los siguientes árboles de F
   4. Visitar el nodo raíz del primer árbol de F