Advertisement
idsystems

SLE_Practica64_NodosTerminales

Jun 24th, 2024
537
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.04 KB | None | 0 0
  1.  
  2. /* Practica 64
  3.     Mostrar todos los nodos terminales de un árbol binario de búsqueda en el
  4.    que se almacenaron números introducidos por el usuario y son controlados
  5.    mediante el siguiente menú:
  6.  
  7.     1.  Insertar
  8.     2.  Eliminar
  9.     3.  Mostrar nodos terminales
  10.     4.  Salir
  11. */
  12.  
  13. tipos
  14.    Nodo: registro {
  15.     valor: numerico
  16.     izquierdo: numerico
  17.     derecho: numerico
  18.    }
  19.  
  20. var
  21.     arbol: vector [100] Nodo
  22.     raiz, libre, temp, actual, padre, i, opcion, valor, reemplazo, hijo, padre_reemplazo: numerico
  23.     encontrado: logico
  24.  
  25. inicio
  26.    cls()
  27.     raiz = 0
  28.     libre = 1
  29.  
  30.     // Inicializar la lista para el manejo de nodos libres
  31.     desde i=1 hasta 99 {
  32.         arbol[i].izquierdo = i + 1
  33.     }
  34.     arbol[100].izquierdo = 0
  35.  
  36.     repetir
  37.         imprimir("\nMenú:")
  38.         imprimir("\n1. Insertar")
  39.         imprimir("\n2. Eliminar")
  40.         imprimir("\n3. Mostrar nodos terminales")
  41.         imprimir("\n4. Salir")
  42.         imprimir("\nElija una opción: ")
  43.         leer(opcion)
  44.  
  45.         eval {
  46.             caso (opcion ==1)
  47.                 // Insertar
  48.                 si (libre == 0) {
  49.                     imprimir("\nEl árbol está lleno.")
  50.                 sino
  51.                     temp = libre
  52.                     libre = arbol[libre].izquierdo
  53.  
  54.                     imprimir("\nIntroduce el número a insertar: ")
  55.                     leer(valor)
  56.  
  57.                     arbol[temp].valor = valor
  58.                     arbol[temp].izquierdo = 0
  59.                     arbol[temp].derecho = 0
  60.  
  61.                     si (raiz == 0) {
  62.                         raiz = temp
  63.                     sino
  64.                         actual = raiz
  65.                         encontrado = FALSE
  66.                         repetir
  67.                             padre = actual
  68.                             si (valor < arbol[actual].valor) {
  69.                                 actual = arbol[actual].izquierdo
  70.                                 si (actual == 0) {
  71.                                     arbol[padre].izquierdo = temp
  72.                                     encontrado = TRUE
  73.                                 }
  74.                             sino
  75.                                 actual = arbol[actual].derecho
  76.                                 si (actual == 0) {
  77.                                     arbol[padre].derecho = temp
  78.                                     encontrado = TRUE
  79.                                 }
  80.                             }
  81.                         hasta (encontrado)
  82.                      }
  83.                 }
  84.                 //romper
  85.  
  86.             caso (opcion ==2)
  87.                 // Eliminar
  88.                 imprimir("\nIntroduce el número a eliminar: ")
  89.                 leer(valor)
  90.  
  91.                 actual = raiz
  92.                 padre = 0
  93.                 encontrado = FALSE
  94.  
  95.                 // Buscar el nodo a eliminar
  96.                 mientras (actual <> 0 and not encontrado) {
  97.                     si (valor == arbol[actual].valor) {
  98.                         encontrado = TRUE
  99.                     sino
  100.                         padre = actual
  101.                         si (valor < arbol[actual].valor) {
  102.                             actual = arbol[actual].izquierdo
  103.                         sino
  104.                             actual = arbol[actual].derecho
  105.                         }
  106.                     }
  107.                 }
  108.  
  109.                 si (not encontrado) {
  110.                     imprimir("\nEl número no se encuentra en el árbol.")
  111.                 sino
  112.                     // Nodo con un solo hijo o sin hijos
  113.                     si (arbol[actual].izquierdo == 0 or arbol[actual].derecho == 0) {
  114.                         si (arbol[actual].izquierdo == 0) {
  115.                             hijo = arbol[actual].derecho
  116.                         sino
  117.                             hijo = arbol[actual].izquierdo
  118.                         }
  119.  
  120.                         si (padre == 0) {
  121.                             raiz = hijo
  122.                         sino
  123.                             si (actual == arbol[padre].izquierdo) {
  124.                                 arbol[padre].izquierdo = hijo
  125.                             sino
  126.                                 arbol[padre].derecho = hijo
  127.                             }
  128.                         }
  129.                           sino
  130.                         // Nodo con dos hijos: buscar el sucesor
  131.                         reemplazo = arbol[actual].derecho
  132.                         padre_reemplazo = actual
  133.  
  134.                         mientras (arbol[reemplazo].izquierdo <> 0) {
  135.                             padre_reemplazo = reemplazo
  136.                             reemplazo = arbol[reemplazo].izquierdo
  137.                         }
  138.  
  139.                         arbol[actual].valor = arbol[reemplazo].valor
  140.  
  141.                         si (padre_reemplazo == actual) {
  142.                             arbol[padre_reemplazo].derecho = arbol[reemplazo].derecho
  143.                         sino
  144.                             arbol[padre_reemplazo].izquierdo = arbol[reemplazo].derecho
  145.                         }
  146.  
  147.                         actual = reemplazo
  148.                     }
  149.  
  150.                     // Liberar el nodo eliminado
  151.                     arbol[actual].izquierdo = libre
  152.                     libre = actual
  153.                  }
  154.                 //romper
  155.  
  156.             caso (opcion ==3)
  157.                 // Mostrar nodos terminales
  158.                 imprimir("\nNodos terminales del árbol:")
  159.  
  160.                 mostrar_terminales(raiz)
  161.                 //romper
  162.  
  163.             caso (opcion ==4)
  164.                 imprimir("\nSaliendo del programa.")
  165.                 //romper
  166.  
  167.             sino
  168.                 imprimir("\nOpción no válida. Por favor, elija una opción válida.")
  169.                 //romper
  170.         }
  171.     hasta (opcion == 4)
  172. fin
  173.  
  174. subrutina mostrar_terminales(nodo: numerico)
  175. inicio
  176.       si (nodo <> 0) {
  177.          si (arbol[nodo].izquierdo == 0 and arbol[nodo].derecho == 0) {
  178.                 imprimir(arbol[nodo].valor)
  179.             sino
  180.              mostrar_terminales(arbol[nodo].izquierdo)
  181.              mostrar_terminales(arbol[nodo].derecho)
  182.             }
  183.         }
  184. fin
  185.  
Tags: Arboles
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement