Estructuras dinámicas en C++: Inserción de nodos y recorrido

lunes julio 11, 2016

Para administrar un árbol binario ordenado debemos tener especial cuidado en la inserción.

Insertamos el 400

Insertamos el valor 100. Debemos analizar si raíz es distinto a NULL verificamos si 100 es mayor o menor a la información del nodo apuntado por raíz, en este caso es menor y como el subárbol izquierdo es NULL debemos insertarlo allí.

Insertamos el 200. Hay que tener en cuenta que siempre comenzamos las comparaciones a partir de raíz. El 200 es menor que 400, descendemos por el subárbol izquierdo. Luego analizamos y vemos que el 200 es mayor a 100, debemos avanzar por derecha. Como el subárbol derecho es NULL lo insertamos en dicha posición.

Insertamos el 700 y el árbol será:

Como podemos observar si cada vez que insertamos un nodo respetamos este algoritmo siempre estaremos en presencia de un árbol binario ordenado. Posteriormente veremos el algoritmo en C++ para la inserción de información en el árbol.

Búsqueda de información en un árbol binario ordenado.

Este es una de los principales usos de los árboles binarios.

Ej. Si en el árbol anterior necesitamos verificar si está almacenado el 700, primero verificamos si la información del nodo apuntado por raíz es 700, en caso negativo verificamos si la información a buscar (700) es mayor a la información de dicho nodo (400) en caso afirmativo descendemos por el subárbol derecho en caso contrario descendemos por el subárbol izquierdo.

Recorridos de árboles binarios.

Recorrer: Pasar a través del árbol enumerando cada uno de sus nodos una vez.

Los árboles pueden ser recorridos en varios órdenes:

Pre-orden:
           - Visitar la raíz.
           - Recorrer el subárbol izquierdo en pre-orden.
           - Recorrer el subárbol derecho en pre-orden.

Entre-orden
          - Recorrer el subárbol izquierdo en entre-orden.
          - Visitar la raíz.
          - Recorrer el subárbol derecho en entre-orden.

Post-orden
          - Recorrer el subárbol izquierdo en post-orden.
          - Recorrer el subárbol derecho en post-orden.
          - Visitar la raíz.

Ejemplo:

Veamos como se imprimen las informaciones de los nodos según su recorrido:

Recorrido preorden:

Es decir que el orden de impresión de la información es:

400 - 100 - 50 - 75 - 200 - 700

Es importante analizar que el recorrido de árboles es recursivo. Recorrer un subárbol es semejante a recorrer un árbol.

Recorrido entreorden:

Es decir que el orden de impresión de la información es:

50 - 75 - 100 - 200 - 400 - 700

Si observamos podemos ver que la información aparece ordenada.

Recorrido postorden:

Es decir que el orden de impresión de la información es:

75 - 50 - 200 - 100 - 700 - 400

— @INFOUDO.OFICIAL

Categorías: #C++, #

---

[0] Atrás | Directorio

 Inicio

Apps Infoudo ¡Descarga el icono directo en el menú de tu equipo!

[»] Las mejores Apps para tu celular

[»] Imágenes Gratis

---