Explicación de arboles binarios
Operaciones básicas
Una tarea muy común a realizar con un árbol es ejecutar una determinada operación con cada uno de los elementos del árbol. Esta operación se considera entonces como un parámetro de una tarea más general que es la visita de todos los nodos o, como se denomina usualmente, del recorrido del árbol.
Si se considera la tarea como un proceso secuencial, entonces los nodos individuales se visitan en un orden específico, y pueden considerarse como organizados según una estructura lineal. De hecho, se simplifica considerablemente la descripción de muchos algoritmos si puede hablarse del proceso del siguiente elemento en el árbol, según un cierto orden subyacente.
Hay dos formas básicas de recorrer un árbol: El recorrido en amplitud y el recorrido en profundidad.
Recorrido de un Arbol Binario
Recorrido en amplitud
Es aquel recorrido que recorre el árbol por niveles, en el último ejemplo sería:
12 - 8,17 - 5,9,15
Recorrido en profundidad
Recorre el árbol por subárboles.
Hay tres Preorden, orden central y postorden.
Hay tres formas: en inorden, preorden y postorden. Cada una de ellas tiene una secuencia distinta para analizar el árbol como se puede ver a continuación:
1. Inorden
- Recorrer el subarbol izquierdo en inorden.
- Examinar la raíz.
- Recorrer el subarbol derecho en inorden.
- Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:
- 1. Atraviese el sub-árbol izquierdo
- 2. Visite la raíz
- 3. Atraviese el sub-árbol derecho
Preorden
- Examinar la raíz.
- Recorrer el subarbol izquierdo en preorden.
- recorrer el subarbol derecho en preorden.
- Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:
- 1. Visite la raíz
- 2. Atraviese el sub-árbol izquierdo
- 3. Atraviese el sub-árbol derecho
Postorden
- Recorrer el subarbol izquierdo en postorden.
- Recorrer el subarbol derecho en postorden.
- Examinar la raíz
- Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:
- 1. Atraviese el sub-árbol izquierdo
- 2. Atraviese el sub-árbol derecho
- 3. Visite la raíz
Por:Patricia E. Olivares Rocha
Germán Gerrero Romero
