Recorridos de Árboles Binarios

Recorrido de Árboles Binarios 

Una tarea muy común a realizar con un árbol es ejecutar una determinada operación con cada uno de los elementos del árbol. 

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

Algoritmo-Postorden: GDHIEBKJFCA

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.

Algoritmo-Preorden: ABDGEHICFJK

Inorden: 

1. Recorrer el subárbol izquierdo en inorden.

2. Examinar la raíz. 

3. Recorrer el subárbol derecho en inorden. 

Algoritmo-Inorden: GDBHEIACJKF

Preorden

22,15,3,8,40,45,13,20,30,1,7,34,48,53,9,23,12,51,4,10

Inorden

22,15,3,1,8,2,4,13,9,12,10,20,40,30,23

34,45,48,53,51

Postorden

1,4,7,10,12,9,13,8,3,20,15,23,34,30,51,53,48,45,40,22

Recorrido de un Árboles Binarios

Recorrido de un Árboles Binarios 

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

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.

Árboles de Expresiones

                                                                            a+b

(a-b)-(c-d)

(a+b)-((c-d)+e)

"Árboles de Expresiones"

Los árboles binarios se utilizan para almacenar expresiones aritméticas en memoria, esencialmente en compiladores de lenguajes de programación. Una expresión es una secuencia de tokens (componentes de léxicos que siguen unas reglas establecidas). Un token puede ser un operando o bien un operador.

Los paréntesis no se almacenan en el árbol pero están implicados en la forma del árbol, como puede apreciarse en la Figura 14:

La Figura 15 representa la expresión infija a * (b + c) + d junto a su árbol de expresión. El nombre de infija es debido a que los operadores se sitúan entre los operandos. 

Un árbol de expresión es un árbol binario con las siguientes propiedades:

1. Cada hoja es un operando. 

2. Los nodos raíz y los nodos internos son operadores. 

3. Los subárboles son subexpresiones cuyo nodo raíz es un operador. 

Los árboles binarios se utilizan para representar expresiones en memoria, esencialmente en compiladores de lenguajes de programación.

Se observa que los paréntesis de la expresión no aparecen en el árbol, pero están implicados en su forma, y esto resulta muy interesante para la evaluación de la expresión. Si se supone que todos los operadores tienen dos operandos, se puede representar una expresión mediante un árbol binario cuya raíz contiene un operador y cuyos subárboles izquierdo y derecho son los operandos izquierdo y derecho, respectivamente. Cada operando puede ser una letra (x, y, a, b, etc.) o una subexpresión representada como un subárbol. 

La Figura 16 muestra un árbol cuya raíz es el operador *, su subárbol izquierdo representa la subexpresión (x + y) y su subárbol derecho representa la subexpresión (a - b).

El nodo raíz del subárbol izquierdo contiene el operador (+) de la subexpresión izquierda y el nodo raíz del subárbol derecho contiene el operador (-) de la subexpresión derecha. Todos los operandos letras se almacenan en nodos hojas. 

Utilizando el razonamiento anterior, la expresión (x * (y - z)) + (a - b) con paréntesis alrededor de las subexpresiones, forma el árbol binario de la Figura 16. 

Maquina de Turing