Se llama recorrido de un árbol al proceso que permite acceder una sola vez a cada uno de los nodos del árbol para examinar el conjunto completo de nodos.

Primeramente se ven los algoritmos para construir el árbol sintáctico, para la expresión dada en sufijo, prefijo o posfijo y también se presentan algoritmos para reconocer si una expresión está sintácticamente correcta cuando esta dada en prefijo o posfijo. Al visitar los nodos de un árbol existen algunas maneras útiles en las que se pueden ordenar sistemáticamente los nodos de un árbol.

Los algoritmos de recorrido de un árbol binario presentan tres tipos de actividades comunes:

• visitar el nodo raíz

• recorrer el subárbol izquierdo

• recorrer el subárbol derecho



Estas tres acciones llevadas a cabo en distinto orden proporcionan los distintos recorridos del árbol.
Un árbol es un grafo simple en el cual existe un único camino entre cada par de vértices.
Sea G =(V,A) un grafo no dirigido. G se denomina ARBOL, si es conexo y no contiene ciclos.
Un árbol con raíz, es un árbol que tiene un vértice particular designado como raíz.
Ejemplo de árbol:

En la figura anterior G1 corresponde a lo que llamamos mediante la definición ARBOL, en el caso de G2, éste no corresponde debido a que contiene un ciclo.
Podemos destacar que cuando un grafo G es un Arbol, se reemplaza G, por R.
En la figura mostrada G1 es un subgrafo de G2, en el que G1 contiene los vértices de G2 y es árbol, además lo llamaremos “árbol abarcador”, por que proporciona conexión minimal para el grafo y un esqueleto minimal que une los vértices.
Ejemplo de árbol raíz:

Para apoyar el entendimiento de las definiciones entregadas agregaremos algunos teoremas.
Teorema:
Si a, b son vértices de un árbol R (V,A), entonces hay un camino único que conecta estos vértices.
Teorema:
En cualquier árbol R= (V,A), |V| = |A| + 1.
Teorema:
Para cualquier árbol R = (V,A), si |A| >= 2, entonces R tiene al menos dos vértices colgantes.
Teorema:
Sea G un grafo simple con v vértices, entonces se puede decir:
G es un árbol.
G es conexo y no contiene circuitos.
G es conexo y tiene (n-1) lados.
G no contiene circuitos y tiene (n-1) lados.

Arboles con Raíz

Sea G un grafo dirigido, se denomina “árbol dirigido” si el grafo no dirigido asociado con G es un árbol. Cuando G es un árbol dirigido, se denomina “árbol con raíz” si hay un único vértice r, la raíz.
Sea G un grafo con raíz V0. Supóngase que x, y, z son vértices en G y que (v0, v1, ..., vn), es un camino en G.
V(n-1) es el padre de v(n).
V0, v1, ..., v(n-1) son los antepasados de v(n).
V(n) es el hijo de v(n-1).
Si x es un antepasado de y, entonces y es un descendiente de x.
Si x e y son hijos de z entonces x e y son hermanos.
Si x no tiene hijos entonces x es un vértice terminal.
Si x no es un vértice terminal, entonces x es un vértice interno.
El subgrafo de G que consiste en x y todos sus descendientes, con x como raíz, es el subarbol de G que tiene a x como raíz.
Sea R= (V,A) un árbol con raíz r. Si R no tiene otros vértices, entonces la raíz misma constituye el recorrido en orden previo, simétrico y posterior de R. Si |V| > 1, sean R1, R2, R3, ...., Rk los subarboles de R según se va de izquierda a derecha.

•  El recorrido de orden previo de R comienza en r y después pasa por los vértices de R1 en orden previo, a continuación por los vértices de R2 en orden previo, y así sucesivamente hasta que se pasa por los vértices de Rk en orden previo.

•  El recorrido en orden simétrico de R primero, se pasa por los vértices de R1 en orden simétrico, después por la raíz r y a continuación por los vértices de los subarboles R2, R3,...., Rk en orden simétrico.

•  El recorrido en orden posterior de R pasa por los vértices de los subarboles R1, R2,...., Rk en orden posterior y a continuación por la raíz.

Un árbol binario es uno con raíz en el cual cada vértice tiene un hijo a la derecha o un hijo a la izquierda, o viceversa, o bien ningún hijo. Un árbol binario completo es uno en el cual cada vértice tiene un hijo a la derecha y uno a la izquierda, o bien ningún hijo.

Teorema:

Si T es un árbol binario completo con i vértices internos, entonces T tiene i + 1 vértices terminales y 2i + 1 vértices en total.
Un árbol binario de búsqueda es un árbol binario T donde se han asociado datos a los vértices. Los datos se disponen de manera que para cualquier vértice v en T, cada dato en el subarbol a la izquierda de v es menor que el dato correspondiente a v.

Arboles generadores:

Un árbol T es un árbol generador de un grafo G si T es un subgrafo de G que contiene todos los vértices de G.
A esta característica general es posible agregar ciertos teoremas de modo de detallar aún más el alcance de la definición. Es así como el Grafo que contiene a T debe ser conexo, pues de lo contrario no existiría un subgrafo que contuviera todos sus vértices.
En general un grafo G tendrá varios árboles generadores ,como el del ejemplo 1 el cual tiene a lo menos dos arboles generadores T1 yT2.

Algoritmos de ordenación y búsqueda

• Ordenación • Ordenación por burbuja • Ordenación por selección • Ordenación por inserción • Ordenación Shell • Ordenación rápida (quicksort) • Búsqueda en listas: búsqueda secuencial y binaria • Resumen • Ejercicios • Problemas

Ordenación
La ordenación o clasificación de datos (sort en inglés) es una operación que consiste en disponer un conjunto (estructura) de datos en algún determinado orden con respecto a uno de los campos de los elementos del conjunto. Por ejemplo, cada elemento del conjunto de datos de una guía telefónica tiene un campo nombre, un campo dirección y un campo número de teléfono; la guía telefónica está dispuesta en orden alfabético de nombres. Los elementos numéricos se pueden ordenar en forma creciente o decreciente de acuerdo con el valor numérico del elemento. En terminología de ordenación, el elemento por el cual está ordenado un conjunto de datos (o se está buscando) se denomina clave. Una colección de datos (estructura) puede ser almacenada en un archivo, un arreglo (vector o tabla), un arreglo de registros, una lista enlazada o un árbol. Cuando los datos están almacenados en un arreglo, una lista enlazada o un árbol, se denomina ordenación interna. Si los datos están almacenados en un archivo, el proceso.

 

6.4.1 Componentes de los  árboles.

Un árbol es una estructura de datos dinámica ( las estructuras del árbol pueden cambiar durante la ejecución del programa ) no lineal ( puesto que a cada elemento del árbol puede seguirle varios elementos ) y homogénea en el que cada elemento puede tener varios elementos posteriores y solamente un elemento anterior. Es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos, de los cuales uno es conocido como raíz , además se crea una relación de parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc.
Un árbol es una estructura que está compuesta por un dato y varios árboles. Dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente, es decir un nodo cualquiera puede ser considerado como la raíz de una árbol completo.



En relación con otros nodos:



o Nodo Padre: Nodo que contiene un puntero al nodo actual. En un árbol un nodo solo puede tener un nodo padre.. X es padre de Y sí y solo sí el nodo X apunta a Y, tambien se dice que X es antecesor de Y. En la figura B es padre de E y F.
o Nodo Hijo: Cualquiera de los nodos apuntados por uno de los nodos del aŕbol. Un nodo puede tener varios hijos.. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. Tambien se dice que X es descenciente directo de Y. En la figura : E es hijo de B.
o Hermano: Dos nodos serán hermanos si son descencientes directos de un mismo nodo. En la figura Ey F son hermanos.

En cuanto a la posición dentro del árbol:
o Nodo Raíz: Es el único nodo del árbol que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En la figura A es el nodo raíz.
o Nodo Hoja: Nodo que no tiene hijos. Se llama hoja o terminal a aquellos nodos que no tienen ramificaciones ( hijos ). En la figura .. N es un nodo hoja.
o Nodo Interior: Es un nodo que no es raíz ni hoja. En la figura .. D es un nodo interior.
o Orden: Es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc. Podríamos decir que nuestro árbol de ejemplo es de orden tres.

o Grado: El número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto A como D tienen tres hijos, y no existen elementos con más de tres hijos.
o Nivel: Se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero, el de sus hijos uno y asi sucesivamente. En el ejemplo, el nodo D tiene nivel 1, el nodo G tiene nivel 2 y el nodo N nivel 3.
o Rama: Es el camino desde el nodo raíz a una hoja. En el ejemplo A-B-E-K y A-B-F son ramas.
o Altura: La altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, tambien podemos  hablar de altura de ramas, el máximo número de nodos que hay que recorrer para llegar de la raíz a una de las hojas. El árbol de la Figura tiene altura 3, la rama B tiene altura 2, la rama G tiene altura 1 y la N cero.

o Peso: Es el número de nodos del árbol sin contar la raíz.
o Camino: Es una consecuencia de nodos, en el que dos nodos consecutivos cualesquiera son padre e hijo. En el ejemplo A-D-H y A-C-G-M son caminos.
o Longitud de camino: Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente. En nuestro árbol de ejemplo G tiene longitud de camino 3 y N tiene longitud de camino 4.

6.4.2 Propiedades de los árboles

1. Dados dos nodos cualesquiera de un árbol, existe exactamente un camino que los conecta.
2. Un árbol con N nodos tiene N-1 aristas.
3. Un árbol binario con N nodos internos tiene N+1 nodos externos.
4. La altura de un árbol binario lleno1 con   nodos internos es aproximadamente  .
5. En general, la altura promedio de un árbol binario es  , pero puede llegar a ser  .
6.4.3 Clasificación de árboles

 Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos. Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.

 

 Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.

 Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura).

 A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.
Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.



6.4.4 Arboles con peso. (Recubridor mínimo)

Dado un grafo conexo, un árbol recubridor mínimo de ese grafo es un subgrafo que tiene que ser un árbol y contener todos los vértices del grafo inicial. Cada arista tiene asignado un peso proporcional entre ellos, que es un número representativo de algún objeto, distancia, etc.. , y se usa para asignar un peso total al árbol recubridor mínimo computando la suma de todos los pesos de las aristas del árbol en cuestión. Un árbol recubridor mínimo o un árbol expandido mínimo es un árbol recubridor que pesa menos o igual que otros árboles recubridores. Todo grafo tiene un bosque recubridor mínimo.En el caso de un empate, porque podría haber más de un árbol recubridor mínimo; en particular, si todos los pesos son iguales, todo árbol recubridor será mínimo. De todas formas, si cada arista tiene un peso distinto existirá sólo un árbol recubridor mínimo. La demostración de esto es trivial y se puede hacer por inducción. Esto ocurre en muchas situaciones de la realidad, como con la compañía de cable en el ejemplo anterior, donde es extraño que dos caminos tengan exactamente el mismo coste. Esto también se generaliza para los bosques recubridores.Si los pesos son positivos, el árbol recubridor mínimo es el subgrafo de menor costo posible conectando todos los vértices, ya que los subgrafos que contienen ciclos necesariamente tienen más peso total.

 

​

6.4.5 Recorrido de un árbol: Preorden, Inorden, Postorden,​

En ciencias de la computación, el recorrido de árboles refiere al proceso de visitar de una manera sistemática, exactamente una vez, cada nodo en una estructura de datos de árbol (examinando y/o actualizando los datos en los nodos). Tales recorridos están clasificados por el orden en el cual son visitados los nodos. Los siguientes algoritmos son descritos para un árbol binario, pero también pueden ser generalizados a otros árboles.
Comparado a las estructuras de datos lineales como las listas enlazadas y arreglos unidimensionales, que tienen un método canónico de recorrido, las estructuras arborescentes pueden ser recorridas de muchas maneras diferentes. Comenzando en la raíz de un árbol binario, hay tres tres pasos principales que pueden ser realizados y el orden en la cual son realizados define el tipo de recorrido.
Recorrido en preorden
En este tipo de recorrido se realiza cierta acción (quizás simplemente imprimir por pantalla el valor de la clave de ese nodo) sobre el nodo actual y posteriormente se trata el subárbol izquierdo y cuando se haya concluido, el subárbol derecho. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo raiz, nodo izquierda, nodo derecha.
En el árbol de la figura el recorrido en preorden sería: 2, 7, 2, 6, 5, 11, 5, 9 y 4.

 

Recorrido en postorden
En este caso se trata primero el subárbol izquierdo, después el derecho y por último el nodo actual. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo izquierda, nodo derecha, nodo raiz. En el árbol de la figura el recorrido en postorden sería: 2, 5, 11, 6, 7, 4, 9, 5 y 2.

 

Recorrido en inorden
En este caso se trata primero el subárbol izquierdo, después el nodo actual y por último el subárbol derecho. En un ABB este recorrido daría los valores de clave ordenados de menor a mayor. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo izquierda,nodo raiz,nodo derecha. En el árbol de la figura el recorrido en inorden sería: 2, 7, 5, 6, 11, 2, 5, 4, 9.