SLE_Practica65_OrdenPreorden

/* Practica 65
   Leer una expresión aritmética y mostrar los recorridos de orden,
   preorden y suborden utilizando un árbol binario
*/

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

var
    arbol: vector [100] Nodo
    libre, temp, raiz, i: numerico
    expresion: cadena

inicio
   cls()
    libre = 1
    raiz = 0

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

    // Leer la expresión aritmética
    imprimir("\nIntroduce una expresión aritmética: ")
    leer(expresion)

    // Construir el árbol de expresión
    raiz = construir_arbol(expresion)

    // Mostrar los recorridos del árbol
    imprimir("\nRecorrido en Preorden:")
    recorrido_preorden(raiz)
    imprimir("\nRecorrido en Inorden:")
    recorrido_inorden(raiz)
    imprimir("\nRecorrido en Postorden:")
    recorrido_postorden(raiz)

fin


    // Procedimiento para construir el árbol de expresión
subrutina construir_arbol(exp: cadena) retorna numerico
    var
      pila: vector [100] numerico
      topo, temp, actual, izq, der: numerico
      i: numerico
      simbolo: cadena
   inicio
      topo = 1
        i = 1
      mientras (i <= strlen(exp)) {
         simbolo = substr(exp, i, 1)
            si (simbolo >= "0" and simbolo <= "9" or simbolo >= "a" and simbolo <= "z") {
            temp = libre
            libre = arbol[libre].izquierdo
            arbol[temp].valor = simbolo
            arbol[temp].izquierdo = 0
            arbol[temp].derecho = 0
            topo = topo + 1
            pila[topo] = temp
         sino
            der = pila[topo]
            topo = topo - 1
            izq = pila[topo]
            temp = libre
            libre = arbol[libre].izquierdo
            arbol[temp].valor = simbolo
            arbol[temp].izquierdo = izq
            arbol[temp].derecho = der
            pila[topo] = temp
         }
         i = i + 1
        }
      retorna pila[1]
    fin


    // Procedimientos para los recorridos del árbol
subrutina recorrido_preorden(nodo: numerico)
inicio
      si (nodo <> 0) {
         imprimir(arbol[nodo].valor)
         recorrido_preorden(arbol[nodo].izquierdo)
         recorrido_preorden(arbol[nodo].derecho)
      }
fin

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

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