ESTRUCTURA DE DATOS NO LINEALES: ÁRBOLES

ÁRBOLES

 Los árboles son estructuras de datos dinámicas no lineales. Un árbol se define como una colección de nodos donde cada uno además de almacenar información, guarda las direcciones de sus sucesores.  

PARTES DE UN ÁRBOL

Hijo: Es aquel nodo que siempre va a tener un nodo antecesor o padre, son aquellos que se encuentran en el mismo nivel 

Padre: Es aquel que tiene hijos y también puede tener o no antecesores. 

Hermano: Dos nodos son hermanos si son apuntados por el mismo nodo, es decir si tienen el mismo padre. 

Raíz: Es el nodo principal de un árbol y no tiene antecesores. 

Hoja o terminal: Son aquellos nodos que no tienen hijos o también los nodos finales de un árbol.

Interior: Se dice que un nodo es interior si no es raíz ni hoja. 

Nivel de un nodo: Se dice que el nivel de un nodo es el número de arcos que deben ser recorridos, partiendo de la raíz para llegar hasta él.

Altura del árbol: Se dice que la altura de un árbol es el máximo de los niveles considerando todos sus nodos.  

Grado de un nodo: se dice que el grado de un nodo es el número de hijos que tiene dicho nodo.  

TIPOS DE ÁRBOLES

* Binario: Son arboles donde cada nodo solo puede apuntar a dos nodos.

* Arboles B (Multicamino) : Arboles cuyos nodos pueden tener un número múltiple de hijos.

Árbol Binario

RECORRIDOS DEL ÁRBOL BINARIO

Comparado a las estructuras de datos lineales como las listas enlazadas  y arreglos unidimensionales, que tienen un método de acceso, las estructuras arborescentes pueden ser recorridas de muchas maneras diferentes. 

Recorrido en profundidad

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

Recorrido en anchura

Los árboles también pueden ser recorridos en orden por nivel (de nivel en nivel), donde visitamos cada nodo en un nivel antes de ir a un nivel inferior. Esto también es llamado recorrido en anchura.

Ejemplo:

Profundidad

Secuencia de recorrido de preorden: F, B, A, D, C, E, G, I, H (raíz, izquierda, derecha)

Secuencia de recorrido de inorden: A, B, C, D, E, F, G, H, I (izquierda, raíz, derecha); note cómo esto produce una secuencia ordenada

Secuencia de recorrido de postorden: A, C, E, D, B, H, I, G, F (izquierda, derecha, raíz)

Anchura

Secuencia de recorrido de orden por nivel: F, B, G, A, D, I, C, E, H