SLE_Practica64_NodosTerminales

/* Practica 64
    Mostrar todos los nodos terminales de un árbol binario de búsqueda en el
   que se almacenaron números introducidos por el usuario y son controlados
   mediante el siguiente menú:

    1.  Insertar
    2.  Eliminar
    3.  Mostrar nodos terminales
    4.  Salir
*/

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

var
    arbol: vector [100] Nodo
    raiz, libre, temp, actual, padre, i, opcion, valor, reemplazo, hijo, padre_reemplazo: numerico
    encontrado: logico

inicio
   cls()
    raiz = 0
    libre = 1

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

    repetir
        imprimir("\nMenú:")
        imprimir("\n1. Insertar")
        imprimir("\n2. Eliminar")
        imprimir("\n3. Mostrar nodos terminales")
        imprimir("\n4. Salir")
        imprimir("\nElija una opción: ")
        leer(opcion)

        eval {
            caso (opcion ==1)
                // Insertar
                si (libre == 0) {
                    imprimir("\nEl árbol está lleno.")
                sino
                    temp = libre
                    libre = arbol[libre].izquierdo

                    imprimir("\nIntroduce el número a insertar: ")
                    leer(valor)

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

                    si (raiz == 0) {
                        raiz = temp
                    sino
                        actual = raiz
                        encontrado = FALSE
                        repetir
                            padre = actual
                            si (valor < arbol[actual].valor) {
                                actual = arbol[actual].izquierdo
                                si (actual == 0) {
                                    arbol[padre].izquierdo = temp
                                    encontrado = TRUE
                                }
                            sino
                                actual = arbol[actual].derecho
                                si (actual == 0) {
                                    arbol[padre].derecho = temp
                                    encontrado = TRUE
                                }
                            }
                        hasta (encontrado)
                     }
                }
                //romper

            caso (opcion ==2)
                // Eliminar
                imprimir("\nIntroduce el número a eliminar: ")
                leer(valor)

                actual = raiz
                padre = 0
                encontrado = FALSE

                // Buscar el nodo a eliminar
                mientras (actual <> 0 and not encontrado) {
                    si (valor == arbol[actual].valor) {
                        encontrado = TRUE
                    sino
                        padre = actual
                        si (valor < arbol[actual].valor) {
                            actual = arbol[actual].izquierdo
                        sino
                            actual = arbol[actual].derecho
                        }
                    }
                }

                si (not encontrado) {
                    imprimir("\nEl número no se encuentra en el árbol.")
                sino
                    // Nodo con un solo hijo o sin hijos
                    si (arbol[actual].izquierdo == 0 or arbol[actual].derecho == 0) {
                        si (arbol[actual].izquierdo == 0) {
                            hijo = arbol[actual].derecho
                        sino
                            hijo = arbol[actual].izquierdo
                        }

                        si (padre == 0) {
                            raiz = hijo
                        sino
                            si (actual == arbol[padre].izquierdo) {
                                arbol[padre].izquierdo = hijo
                            sino
                                arbol[padre].derecho = hijo
                            }
                        }
                          sino
                        // Nodo con dos hijos: buscar el sucesor
                        reemplazo = arbol[actual].derecho
                        padre_reemplazo = actual

                        mientras (arbol[reemplazo].izquierdo <> 0) {
                            padre_reemplazo = reemplazo
                            reemplazo = arbol[reemplazo].izquierdo
                        }

                        arbol[actual].valor = arbol[reemplazo].valor

                        si (padre_reemplazo == actual) {
                            arbol[padre_reemplazo].derecho = arbol[reemplazo].derecho
                        sino
                            arbol[padre_reemplazo].izquierdo = arbol[reemplazo].derecho
                        }

                        actual = reemplazo
                    }

                    // Liberar el nodo eliminado
                    arbol[actual].izquierdo = libre
                    libre = actual
                 }
                //romper

            caso (opcion ==3)
                // Mostrar nodos terminales
                imprimir("\nNodos terminales del árbol:")

                mostrar_terminales(raiz)
                //romper

            caso (opcion ==4)
                imprimir("\nSaliendo del programa.")
                //romper

            sino
                imprimir("\nOpción no válida. Por favor, elija una opción válida.")
                //romper
        }
    hasta (opcion == 4)
fin

subrutina mostrar_terminales(nodo: numerico)
inicio
      si (nodo <> 0) {
         si (arbol[nodo].izquierdo == 0 and arbol[nodo].derecho == 0) {
                imprimir(arbol[nodo].valor)
            sino
             mostrar_terminales(arbol[nodo].izquierdo)
             mostrar_terminales(arbol[nodo].derecho)
            }
        }
fin