En la entrega anterior de nuestro curso de Java, os dimos la solución al ejercicio que os propusimos sobre mapas enumerados. También comenzamos con una breve introducción sobre los árboles de datos en Java.
En la entrega de esta semana os vamos a hablar sobre la ordenación y el recorrido de los árboles de datos. Os explicaremos de que tres modos pueden realizarse estas acciones y trataremos de explicároslo de forma gráfica para tratar de que veáis como se realiza.
Sin perder más tiempo, vamos con el temario de esta entrega.
Los hermanos se ordenan generalmente de izquierda a derecha
La ordenación o recorrido de los nudos se suele hacer de 3 modos:
- preorden, postorden, e inorden
Estos tipos de ordenación se definen recursivamente de la forma siguiente:
- Si el árbol T es nulo, entonces la lista vacía es la lista de T en preorden, postorden e inorden.
- Si T tiene un solo nudo, entonces el nudo es la lista de T en preorden, postorden e inorden.
- Si T consiste en un árbol con una raíz n y subárboles T1, T2, …, Tk , como en la figura a de arriba:
- La lista de T en preorden es la raíz n seguida de los nudos de T1 en preorden, luego los nudos de T2 en preorden, hasta finalizar con la lista de Tk en preorden.
- La lista de T en inorden es la lista de los nudos de T1 en inorden, seguida de la raíz n, luego los nudos de T2, …, Tk con cada grupo de nudos en inorden.
- La lista de T en postorden es la lista de los nudos de T1 en postorden, luego los nudos de T2 en postorden, y así hasta la lista de Tk en postorden, finalizando con el nudo raíz n.
Un método para producir estas tres ordenaciones de nudos a mano consiste en recorrer los nudos en la forma que se indica en la figura b de arriba:
- Para ordenar en preorden se lista cada nudo la primera vez que se pasa por él. Para postorden la última vez. Para inorden se listan las hojas la primera vez que se pasa por ellas, pero los nudos interiores la segunda.
Métodos recursivos con los que recorrer los árboles(Pesudocódigo)
[java]
método Preorden (N : Nudo; A : Arbol)
listar N;
para cada hijo H de N, y empezando por la izquierda
hacer
Preorden(H,A);
fpara;
fmétodo
[/java]
[java]
método Postorden (N : Nudo; A : Arbol)
para cada hijo H de N, y empezando por la izquierda
hacer
Postorden(H,A);
fpara;
listar N;
fmétodo;
[/java]
[java]
método Inorden (N : Nudo; A : Arbol)
si n es una hoja entonces
listar n;
si no
Inorden(hijo más a la izquierda de n,A);
listar n;
para cada hijo h de n, excepto el más a la
izquierda, y empezando por la izquierda
hacer
Inorden(H,A);
fpara;
fsi;
fmétodo;
[/java]
Que mejor para ver a que nos estamos refiriendo que utilizar un ejemplo sencillo.
Teniendo en cuenta los pesudocódigos anteriores, ¿cómo quedaría la expresión aritmética para cada recorrido?
Expresión normal: 5+8*(3+4)-3*5
- preorden: +5-*8+3,4*3,5
- inorden: 5+(8*(3+4)-(3*5)) es la expresión en notación matemática normal
- postorden: 5,8,3,4+*3,5*-+ es la expresión en Notación Inversa
El tipo de datos árbol
Antes de acabar, os vamos a dar una introducción a los iteradores de los árboles de datos
La mayoría de las operaciones se encuentran en el iterador de árboles, que
- contiene una referencia a uno de los nudos del árbol
- inicialmente es la raíz
- si la referencia es nula, se dice que el iterador no es válido
- puede usarse para recorrer y/o modificar el árbol
- si el iterador no es válido, casi todas las operaciones lanzan NoValido
En la siguiente entrega, además de ver todas las operaciones que poseen los iteradores, implementaremos los métodos de recorrido de los árboles de los que hemos hablado en esta entrega y veremos algunos ejemplos de utilización de los mismos
