Java arboles

Solo disponible en BuenasTareas
  • Páginas : 4 (903 palabras )
  • Descarga(s) : 0
  • Publicado : 28 de marzo de 2011
Leer documento completo
Vista previa del texto
Recorridos sobre árboles binarios
Se consideran dos tipos de recorrido: recorrido en profundidad y recorrido en anchura o a nivel. Puesto que los árboles no son secuenciales como las listas, hay quebuscar estrategias alternativas para visitar todos los nodos. Dada la siguiente figura:

Figura 1
- Recorridos en profundidad:
* Recorrido en preorden: consiste en visitar el nodo actual(visitar puede ser simplemente mostrar la clave del nodo por pantalla), y después visitar el subárbol izquierdo y una vez visitado, visitar el subárbol derecho. Es un proceso recursivo por naturaleza. Sise hace el recorrido en preorden del árbol de la figura 1 las visitas serían en el orden siguiente: a,b,d,c,e,f.
* Recorrido en inorden u orden central: se visita el subárbol izquierdo, el nodoactual, y después se visita el subárbol derecho. En el ejemplo de la figura 1 las visitas serían en este orden: b,d,a,e,c,f.
* Recorrido en postorden: se visitan primero el subárbol izquierdo, después elsubárbol derecho, y por último el nodo actual. En el ejemplo de la figura 1 el recorrido quedaría así: d,b,e,f,c,a.
La ventaja del recorrido en postorden es que permite borrar el árbol de formaconsistente. Es decir, si visitar se traduce por borrar el nodo actual, al ejecutar este recorrido se borrará el árbol o subárbol que se pasa como parámetro. La razón para hacer esto es que no se debeborrar un nodo y después sus subárboles, porque al borrarlo se pueden perder los enlaces, y aunque no se perdieran se rompe con la regla de manipular una estructura de datos inexistente. Una alternativa esutilizar una variable auxiliar, pero es innecesario aplicando este recorrido.
- Recorrido en amplitud:
Consiste en ir visitando el árbol por niveles. Primero se visitan los nodos de nivel 1 (comomucho hay uno, la raíz), después los nodos de nivel 2, así hasta que ya no queden más. Si se hace el recorrido en amplitud del árbol de la figura una visitaría los nodos en este orden: a,b,c,d,e,f....
tracking img