Estructura de Datos: ARBOLES EN C

Explicaremos lo árboles binarios; árboles cuyos nodos contienen dos ligas (ninguna, una, o ambas de las cuáles pueden ser NULL). El nodo raíz es el primer nodo del árbol. Cada liga del nodo raíz hace referencia a un hijo. El hijo izquierdo es el primer nodo del subárbol izquierdo, y el hijo derecho es el primer nodo del subárbol derecho.

Las definiciones a tener en cuenta son:

Raíz del árbol: Todos los árboles que no están vacíos tienen un único nodo raíz. Todos los demás elementos o nodos se derivan de él. El nodo raíz no tiene padre es decir, no es el hijo de ningún elemento.
Nodo, son los vértices o elementos del árbol.
Nodo terminal u hoja (leaf node) es aquel nodo que no contiene ningún subárbol.
A cada nodo que no es hoja se asocia uno o varios subárboles llamados hijos. De igual forma tiene asociado un antecesor llamado padre.
Los nodos de un mismo padre se llaman hermanos.
Todos los nodos tienen un solo padre – excepto la raíz – que no tiene padre.
Se denomina camino el enlace entre dos nodos consecutivos, y rama es un camino que termina en una hoja.
Cada nodo tiene asociado un número de nivel que se determina por la longitud del camino desde la raíz al nodo específico.
La altura o profundidad de un árbol es el número máximo de nodos de una rama. Equivale al nivel más alto de los nodos más uno. El peso de un árbol es el número de nodos terminales.

ejemplo.

Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'.
Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.

Recorrido en Inorden

Recorrer un árbol en Inorden consiste en primer lugar en recorrer el subárbol izquierdo en Inorden, luego se examina el dato del nodo raíz, y finalmente se recorre el subárbol derecho en Inorden. Esto significa que para cada subárbol se debe conservar el recorrido en Inorden, es decir, primero se visita la parte izquierda, luego la raíz y posteriormente la parte derecha.

Recorrido en Preorden:

Recorrer un árbol en preorden consiste en primer lugar, examinar el dato del nodo raíz, posteriormente se recorrer el subárbol izquierdo en preorden y finalmente se recorre el subárbol derecho en preorden. Esto significa que para cada subárbol se debe conservar el recorrido en preorden, primero la raíz, luego la parte izquierda y posteriormente la parte derecha.

Recorrido en Postorden:

Recorrer un árbol en Postorden consiste en primer lugar en recorrer el subárbol izquierdo en Postorden, luego serecorre el subárbol derecho en Postorden y finalmente se visita el nodo raíz. Esto significa que para cada subárbol se debe conservar el recorrido en Postorden, es decir, primero se visita la parte izquierda, luego la parte derecha y por último la raíz.