El árbol También se define como una estructura de datos no lineal. Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos y tablas de contenidos. Entre otros tenemos un tipo especial de árbol que es, llamado árbol binario, que puede ser implementado fácilmente en la computadora.
En ciencias de la computación, un árbol es una estructura de datos ampliamente usada que emula la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b, si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja.
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. También se dice que X es antecesor de Y. En la Figura 1: B es padre de E y F.
Nodo hijo. Cualquiera de los nodos apuntados por uno de los nodos del árbol. Un nodo puede tener varios hijos. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y. En la Figura 1: E es hijo de B.
Hermano. Dos nodos serán hermanos si son descendientes directos de un mismo nodo. En la Figura 1: E y F son hermanos. En cuanto a la posición dentro del árbol:
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 1 A es el nodo raíz.
Nodo hoja. Nodo que no tiene hijos. Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos). En la Figura 1 N es un nodo hoja.
Nodo interior. Es un nodo que no es raíz ni hoja. En la Figura 1 D es un nodo interior.
Existen otros conceptos que definen las características del árbol, en relación a su tamañ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 (Figura 1) es de orden tres.
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.
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 así sucesivamente. En el ejemplo, el nodo D tiene nivel 1, el nodo G tiene nivel 2, y el nodo N nivel 3.
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, también 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 1 tiene altura 3, la rama B tiene altura 2, la rama G tiene altura 1, la N cero...
Peso. Es el número de nodos del árbol sin contar la raíz.
Camino. Es una secuencia 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.
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.
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.
Recorridos en profundidad
El método de este recorrido es tratar de encontrar de la cabecera a la raíz en nodo de unidad binaria. Ahora pasamos a ver la implementación de los distintos recorridos:
Recorrido Pre-orden (N – I – D)
En este recorrido lo primero que se obtiene o evalúa es el nodo, antes de recorrer las ramas; posteriormente se recorre la rama izquierda y finalmente la rama derecha. El orden es Nodo – Izquierda– Derecha (N – I – D). 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 método seria seguir el orden: nodo raíz, 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.
Ejemplo:
void preorden(tArbol *a)
{
if (a != NULL) {
tratar(a); //Realiza una operación en nodo
preorden(a->hIzquierdo);
preorden(a->hDerecho);
}
}
Recorrido Post-orden (I – D – R)
En este recorrido se primero se procesan las ramas para finalmente procesar el nodo. El orden de este recorrido es: Izquierda – Derecha – Nodo (I – D – N). 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 raíz. En el árbol de la figura el recorrido en postorden sería: 2, 5, 11, 6, 7, 4, 9, 5 y 2.
Ejemplo:
void postorden(tArbol *a)
{
if (a != NULL) {
postorden(a->hIzquiedo);
postorden(a->hDerecho);
tratar(a); //Realiza una operación en nodo
}
}
Recorrido In-orden (I – N – D):
En este recorrido se procesa la primera rama (rama izquierda), después el nodo y finalmente la última rama (rama derecha). El orden es: Izquierda – Nodo – Derecha (I – N – D). 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 método seria seguir el orden: nodo izquierda, nodo raíz, nodo derecha. En el árbol de la figura el recorrido en in-orden sería: 2, 7, 5, 6, 11, 2, 5, 4, 9.Esquema de implementación:
Ejemplo:
void inorden(tArbol *a)
{
if (a != NULL) {
inorden(a->hIzquierdo);
tratar(a); //Realiza una operación en nodo
inorden(a->hDerecho);
}
}
No comments:
Post a Comment