SLE_Practica60_Busqueda

/* Practica 60

    Mediante un árbol binario de búsqueda, almacenar N números aleatorios
   y mostrar el árbol con recorrido en anchura. N es dado por el usuario.
*/


tipos
   Nodo: registro {
    valor: numerico
    izquierdo: numerico
    derecho: numerico
    }

var
    arbol: vector [*] Nodo
    raiz, libre, temp, actual, padre, N, numero, i, frente, final: numerico
    opcion, valor: numerico
    cola: vector [*] numerico
    encontrado: logico

inicio
    cls()
    raiz = 0
    libre = 1

    imprimir("\nIntroduce el número de elementos (N): ")
    leer(N)

   dim (arbol, N)
   dim (cola, N)

    // Inicializar la lista para el manejo de nodos libres
    desde i=1 hasta N {
        arbol[i].izquierdo = i + 1
    }
    arbol[N].izquierdo = 0


    // Insertar N números aleatorios en el árbol
    desde i=1 hasta N {
        numero = random(100)  // Generar un número aleatorio entre 1 y 100

        // Insertar el número en el árbol
        si (libre == 0) {
            imprimir("\nEl árbol está lleno.")
        sino
            temp = libre
            libre = arbol[libre].izquierdo

            arbol[temp].valor = numero
            arbol[temp].izquierdo = 0
            arbol[temp].derecho = 0

            si (raiz == 0) {
                raiz = temp
            sino
                actual = raiz
                encontrado = FALSE  // Variable booleana para controlar el bucle
                repetir
                    padre = actual
                    si (numero < arbol[actual].valor) {
                        actual = arbol[actual].izquierdo
                        si (actual == 0) {
                            arbol[padre].izquierdo = temp
                            encontrado = TRUE  // Se ha encontrado el lugar de inserción
                        }
                    sino
                        actual = arbol[actual].derecho
                        si (actual == 0) {
                            arbol[padre].derecho = temp
                            encontrado = TRUE  // Se ha encontrado el lugar de inserción
                        }
                     }
                hasta (encontrado)  // El bucle se repetirá hasta que se encuentre un lugar de inserción
            }
        }
    }

     // Llamar al procedimiento para mostrar el árbol en anchura
    recorrido_en_anchura()
fin



   // Mostrar el árbol con recorrido en anchura
subrutina recorrido_en_anchura()

inicio
        si (raiz == 0) {
            imprimir("\nEl árbol está vacío.")
        sino
            // Inicializar cola
            frente = 1
            final = 1
            cola[frente] = raiz

            mientras (frente <= final) {
                actual = cola[frente]
                frente = frente + 1

                // Imprimir el valor del nodo actual
                imprimir("\nValor: ", arbol[actual].valor)

                // Agregar los hijos del nodo actual a la cola
                si (arbol[actual].izquierdo <> 0) {
                    final = final + 1
                    cola[final] = arbol[actual].izquierdo
                }
                si (arbol[actual].derecho <> 0) {
                    final = final + 1
                    cola[final] = arbol[actual].derecho
                }
            }
        }
fin