Estructuras de Datos: Árboles Binarios y Métodos de Recorrido

Estructuras de Datos: Árboles

Árboles: Es una estructura no lineal cuyos nodos cumplen con las siguientes características:

• a) Jerarquía: Existe una relación entre nodos del tipo padre-hijo.
• b) Raíz: Todo nodo posee un padre, excepto la raíz.
• c) Trayectoria: Todo nodo está unido a la raíz por una trayectoria única.
• d) Recursividad: Todo nodo es, a su vez, un árbol.

Árbol Binario

Un árbol binario es aquel cuyos nodos tienen, a lo más, dos hijos.

Criterio de ingreso de datos a un árbol binario

Para organizar la información, se establece el siguiente criterio:

• Un nodo o dato menor o igual a la raíz se destina hacia la rama izquierda.
• Un nodo o dato mayor que la raíz se destina a la rama derecha.

Recorrido de un Árbol

Recorrer un árbol significa examinar cada uno de sus nodos sin repetición.

Métodos de recorrido

• a) Pre-orden: Examinar raíz, examinar rama izquierda en Pre-orden, examinar rama derecha en Pre-orden.
• b) In-orden: Examinar rama izquierda en In-orden, examinar raíz, examinar rama derecha en In-orden.
• c) Post-orden: Examinar rama izquierda en Post-orden, examinar rama derecha en Post-orden, examinar raíz.

Ejemplo práctico:

          80
        /    \
      60      100
     /  \    /   \
    40  70  90   180

• Pre-orden: 80, 60, 40, 70, 100, 90, 180.
• In-orden: 40, 60, 70, 80, 90, 100, 180.
• Post-orden: 40, 70, 60, 90, 180, 100, 80.

Módulo insertar_nodo_arbol(dir_ar, nodos)

• Función: Devuelve la dirección del árbol con la incorporación del nuevo nodo.
• Lógica de incorporación:
  • Nodo menor o igual que la raíz se determina a la rama izquierda.
  • Si es mayor, se destina a la rama derecha.
• Implementación: La función utiliza recursividad.

Implementación en Lenguaje C

El siguiente programa crea un árbol binario:

#include <arbol.h>

void main() {
    arbol *par; // Puntero al árbol.
    par = NULL; // Inicialización de puntero vacío.
    par = insertar_nodo_arbol(par, 70);
    par = insertar_nodo_arbol(par, 100);
    par = insertar_nodo_arbol(par, 40);
    par = insertar_nodo_arbol(par, 10);
    printf("Árbol binario creado\n\n");
}

Ejercicio de Aplicación

Escribir las instrucciones necesarias para crear el siguiente árbol:

                  100
                /     \
              70       180
             /           \
           -5             300

Código de inserción dinámica:

void main() {
    arbol *par;
    int nodo, i;
    for(i = 0; i <= 10; i++) {
        printf("Ingrese número:\n\n");
        scanf("%d", &nodo);
        par = ingresar_nodo_arbol(par, nodo);
    }
}