Arboles

Un árbol es una estructura dinámica no lineal constituida por nodos ordenados jerárquicamente, donde uno de ellos se distingue por ser la raíz del árbol.

La estructura de árbol se utiliza para representar la relación jerárquica entre sus elementos. El orden jerárquico se encuentra dado por un a relación padre-hijo.

Se puede representar un árbol de varias maneras:

Un ejemplo clásico de una estructura tipo árbol es el índice de un libro:

• Libro
  • Unidad I
    • Capitulo I.1
      • Sección I.1.1
      • Sección I.1.2
    • Capítulo I.2
      • Sección I.2.1
  • Unidad II
    • Capítulo II.1
      • Sección II.1.1
      • Sección II.1.2
        • Subsección II.1.2.1
        • Subsección II.1.2.2
      • Sección II.1.3

Otro ejemplo lo constituiría el directorio de un PC:

Terminología

• Nodos: son elementos o vértices del árbol
• Todo árbol no vacío tiene un nodo raíz, que es aquel del cual derivan todos los demás nodos
• Cada nodo tiene un único antecesor o ascendiente denominado padre, excepto el nodo raíz que no tiene padre
• Cualquier nodo incluido el raíz puede tener varios descendientes denominados hijos que salen de él.
• se llama grado de un árbol al número de hijos que salen de él y a los nodos con grado 0 (sin hijos) se les denomina terminales u hojas
• Dos nodos hijos del mismo padre reciben el nombre de hermanos.
• Cada nodo tiene asociado un numero de nivel determinado por el número de antecesores que tiene desde la raíz, teniendo en cuenta que el nivel de la raíz es 1.
• Los nodos que no son ni hojas ni raíz se denominan internos
• Profundidad o altura de un árbol es el máximo de niveles de los nodos de un árbol
• Peso del árbol es el número de terminales u hojas
• Una colección de 2 o más arboles se llama bosque
• Un camino dentro de un árbol es una secuencia de nodos
• Rama es un camino que termina en una hoja

Un árbol binario es aquel en el que cada nodo tiene como máximo grado 2. Un árbol binario es equilibrado si para todos sus nodos la altura de sus subárboles se diferencia como máximo en 1 y es completo si todos sus nodos, excepto las hojas, tienen exactamente dos hijos. Un árbol binario en el que todos los nodos tienen dos hijos excepto las hojas y estas tienen todas el mismo nivel se dice que está lleno. El número de nodos de un árbol binario lleno será 2^altura-1.

Conversión de una árbol general en un árbol binario

Existe un método para convertir un árbol general en binario

• La raíz del árbol binario será la raíz del árbol n-nario
• Se deja enlazado el nodo raíz con el que tenga más a la izquierda y se enlaza este con sus hermanos
• Se repite el segundo proceso con los niveles sucesivos hasta llegar al nivel más alto (últimos niveles)
• Se gira el diagrama 45º a la izquierda

Se denomina recorrido al proceso que permite acceder una sola vez a cada uno de los nodos del árbol

Existen tres formas de efectuar el recorrido, y todas ellas de naturaleza recursiva<(p>

• Preorden: Visitar la raíz, recorrer el subárbol izquierdo, recorrer el subárbol derecho
• Inorden: Recorrer el subárbol izquierdo, visitar la raíz recorrer el subárbol derecho
• Postorden: Recorrer el subárbol izquierdo, recorrer el subárbol derecho visitar la raíz

Por ejemplo:

Otro ejemplo:

Implementación

Un árbol binario se puede implementar con arreglos de la siguiente manera:

Se crean 3 arreglos:

nombre_Nodo[n] tipo String
izquierdo[n] tipo entero
derecho[n] tipo entero

El arreglo tipo cadena se inicia vacío y los arreglos de enteros con el valor -1

• Se ingresa el nodo raíz escribiendo su nombre en algún registro vacío del arreglo tipo cadena.
• Cada vez que se ingresa un nuevo nodo, su nombre se ingresa en un registro vacío del arreglo tipo cadena. Se determina de quien será hijo, y se ubica el registro del padre.
• Si es hijo izquierdo, se coloca el índice del registro del hijo en el registro izquierdo que tenga el mismo índice que el padre.
• Si es hijo derecho, se coloca el índice del registro del hijo en el registro derecho que tenga el mismo índice que el padre.
• Así cada nodo puede tener 2 hijos, uno derecho y uno izquierdo.
• El índice del nodo raíz no debe aparecer en ningún registro del arreglo izquierdo, ni del derecho.

Ejemplo:

Otra manera más elegante de implementar árboles, es usando estructuras con punteros, al igual como se hizo con las listas.

por ejemplo se podría utilizar una estructura como la siguiente:

typedef struct NODO
{
	char nombre[30];
	struct NODO *padre, *hijo_izquierdo, *hijo_derecho;
} arbol;