Arboles

Un árbol consta de un conjunto finito de elementos, llamados nodos y un conjunto limitado de líneas dirigidas, o ramas, que conectan a los nodos. La cantidad de ramas asociada con un nodo es el grado del nodo.
Si un árbol no está vacío, entonces el primer nodo se llama raíz.

  • El nivel de un nodo es la distancia a la raíz.
  • La raíz tiene una distancia cero de si misma, por lo que se dice que la raíz esta en el nivel 0.
  • Los hijos de la raíz están en el nivel 1, sus hijos están en el nivel 2 y así sucesivamente.

Árboles binarios    
Un árbol binario es en el que ningún nodo puede tener mas de dos ramas (subárboles).
Cada nodo debe contener el campo dato y dos campos que señalen los subárboles (nodos) derecho e izquierdo.

La trayectoria de un árbol binario requiere que cada nodo del árbol sea procesado una vez y solo una en secuencia predeterminada.

Los recorridos se conocen como enorden, preorden y postorden.

 

Preorden (NID nodo-izquierdo-derecho): 

Los pasos para el recorrido preorden es:

  1. Recorrer la raíz
  2. Recorrer el subárbol izquierdo en preorden
  3. Recorrer el subárbol derecho en preorden

Se visita primero la raíz, a continuación se  visita el subárbol izquierdo, si el subárbol es también un árbol, se pasa por los nodos utilizando el orden NID

 

Enorden (izquierdo-nodo-derecho) IND:

El recorrido enorden procesa primero el subárbol izquierdo, después la raíz y a continuación el subárbol derecho. El método implica los siguientes pasos:

  1. Recorrer el subárbol izquierdo en inorden
  2. Visitar el nodo raíz
  3. Recorrer el subárbol derecho en inorden

 

Postorden (izquierdo-derecho-nodo) IDN:

El recorrido postorden procesa el nodo raíz después de que los subárboles izquierdo y derecho han sido procesados. Empieza situándose en la hoja mas a la izquierda y se procesa. A continuación se procesa su árbol derecho. Por último se procesa el nodo raíz. Etapas del algoritmo:

  1. Recorrer el árbol izquierdo en postorden
  2. Recorrer el árbol derecho en postorden
  3. Visitar el nodo raíz

Código