SHARE
TWEET

Untitled

a guest Oct 18th, 2019 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _POSIX_C_SOURCE 200809L
  2. #include "abb.h"
  3. #include "pila.h"
  4. #include <stdbool.h>
  5. #include <stdlib.h>
  6. #include <stdio.h>
  7. #include <string.h>
  8.  
  9. typedef struct nodo{
  10.     struct nodo* izq;
  11.     struct nodo* der;
  12.     void* dato;
  13.     char* clave;
  14. }nodo_t;
  15.  
  16. struct abb{
  17.     struct nodo* raiz;
  18.     abb_destruir_dato_t destruir_dato;
  19.     abb_comparar_clave_t cmp;
  20.     size_t cantidad;
  21. };
  22.  
  23. void destruir(abb_t* arbol, nodo_t* nodo);
  24. void borrar_nodo(nodo_t* nodo);
  25.  
  26. void* averiguar_caso(abb_t* arbol, nodo_t* padre, nodo_t* hijo);
  27. void* ver_caso_3(abb_t* arbol, nodo_t* padre, nodo_t* hijo, nodo_t* reemplazante);
  28. void* ver_caso_2(abb_t* arbol, nodo_t* padre, nodo_t* hijo);
  29. void* ver_caso_1(abb_t* arbol, nodo_t* padre, nodo_t* hijo);
  30.  
  31. void* borrar(abb_t* arbol, nodo_t* nodo, const char* clave);
  32.  
  33. void* buscar(const abb_t* arbol, nodo_t* nodo, const char* clave);
  34.  
  35. bool guardar(abb_t* arbol, nodo_t* raiz, nodo_t* nodo, bool es_guardar);
  36.  
  37. nodo_t* crear_nodo(const char* clave, void* dato){
  38.     nodo_t* nodo = malloc(sizeof(nodo_t));
  39.     nodo->izq = NULL;
  40.     nodo->der = NULL;
  41.     nodo->dato = dato;
  42.     nodo->clave = strdup(clave);
  43.     return nodo;
  44. }
  45.  
  46. abb_t* abb_crear(abb_comparar_clave_t cmp, abb_destruir_dato_t destruir_dato){
  47.     abb_t* arbol = malloc(sizeof(abb_t));
  48.     if (destruir_dato) arbol->destruir_dato = destruir_dato;
  49.     else arbol->destruir_dato = NULL;
  50.     if (cmp) arbol->cmp = cmp;
  51.     else return false;
  52.     arbol->cantidad = 0;
  53.     arbol->raiz = NULL;
  54.     return arbol;
  55. }
  56.  
  57. size_t abb_cantidad(abb_t *arbol){
  58.     return arbol->cantidad;
  59. }
  60.  
  61. bool abb_pertenece(const abb_t *arbol, const char *clave){
  62.     nodo_t* aux = buscar(arbol, arbol->raiz, clave);
  63.     if ((aux) && arbol->cmp(aux->clave, clave) == 0){
  64.         return true;
  65.     }
  66.     return false;
  67. }
  68.  
  69. void* buscar(const abb_t* arbol, nodo_t* nodo, const char* clave){
  70.     if (!nodo) return NULL;
  71.     if (arbol->cmp(nodo->clave, clave) > 0) return buscar(arbol, nodo->izq, clave);
  72.     else if (arbol->cmp(nodo->clave, clave) < 0) return buscar(arbol, nodo->der, clave);
  73.     return nodo;
  74. }
  75.  
  76. void* abb_obtener(const abb_t *arbol, const char *clave){
  77.     if (!abb_pertenece(arbol, clave)) return NULL;
  78.     nodo_t* aux = buscar(arbol, arbol->raiz, clave);
  79.     if (!aux) return NULL;
  80.     return aux->dato;
  81. }
  82.  
  83.  
  84. bool abb_guardar(abb_t *arbol, const char *clave, void *dato){
  85.     nodo_t* nodo = crear_nodo(clave, dato);
  86.     if (!nodo) return false;
  87.     bool pertenece = abb_pertenece(arbol, nodo->clave);
  88.     if(!pertenece) arbol->cantidad++;
  89.     return guardar(arbol, arbol->raiz, nodo, pertenece);
  90. }
  91. bool guardar(abb_t* arbol, nodo_t* raiz, nodo_t* nodo, bool es_guardar){
  92.     if (!arbol->raiz){
  93.         arbol->raiz = nodo;
  94.         return true;
  95.     }
  96.     if (arbol->cmp(raiz->clave, nodo->clave) > 0){
  97.         if (raiz->izq == NULL){
  98.             raiz->izq = nodo;
  99.             return true;
  100.         }
  101.         return guardar(arbol, raiz->izq, nodo, es_guardar);
  102.     }
  103.     else if (arbol->cmp(raiz->clave, nodo->clave) < 0){
  104.         if (raiz->der == NULL){
  105.             raiz->der = nodo;
  106.             return true;
  107.         }
  108.         return guardar(arbol, raiz->der, nodo, es_guardar);
  109.     }
  110.     else if (es_guardar){
  111.         if(arbol->destruir_dato) arbol->destruir_dato(raiz->dato);
  112.         raiz->dato = nodo->dato;
  113.         borrar_nodo(nodo);
  114.         return true;
  115.     }
  116.     return true;
  117. }
  118.  
  119. void *abb_borrar(abb_t *arbol, const char *clave){
  120.     if (!abb_pertenece(arbol, clave)) return NULL;
  121.     void* aux = borrar(arbol, arbol->raiz, clave);
  122.     arbol->cantidad--;
  123.     return aux;
  124. }
  125.  
  126. void* borrar(abb_t* arbol, nodo_t* nodo, const char* clave){
  127.     void* aux = NULL;
  128.     if (arbol->cmp(arbol->raiz->clave, clave) == 0){
  129.         aux = averiguar_caso(arbol, NULL, nodo);
  130.         return aux;
  131.     }
  132.     if (arbol->cmp(nodo->clave, clave) > 0){
  133.         if (arbol->cmp(nodo->izq->clave, clave) == 0){
  134.             aux = averiguar_caso(arbol, nodo, nodo->izq);
  135.             return aux;
  136.         }
  137.         return borrar(arbol, nodo->izq, clave);
  138.     }
  139.     else if (arbol->cmp(nodo->clave, clave) < 0){
  140.         if (arbol->cmp(nodo->der->clave, clave) == 0){
  141.             aux = averiguar_caso(arbol, nodo, nodo->der);
  142.             return aux;
  143.         }
  144.         return borrar(arbol, nodo->der, clave);
  145.     }
  146.     return aux;
  147. }
  148. void* averiguar_caso(abb_t* arbol, nodo_t* padre, nodo_t* hijo){
  149.     void* aux;
  150.     if (hijo->izq == NULL && hijo->der == NULL){
  151.         if (padre == NULL){
  152.             aux = ver_caso_1(arbol, NULL, hijo);
  153.             return aux;
  154.         }
  155.         aux = ver_caso_1(arbol, padre, hijo);
  156.         return aux;
  157.     }
  158.     else if (hijo->izq == NULL || hijo->der == NULL){
  159.         aux = ver_caso_2(arbol, padre, hijo);
  160.         return aux;
  161.     }
  162.     else {
  163.         nodo_t* reemplazante = hijo->der;
  164.         aux = ver_caso_3(arbol, padre, hijo, reemplazante);
  165.     }
  166.     return aux;
  167. }
  168. void* ver_caso_3(abb_t* arbol, nodo_t* padre, nodo_t* hijo, nodo_t* reemplazante){
  169.     if (reemplazante->izq == NULL){
  170.         char* clave_aux = reemplazante->clave;
  171.         void* dato_aux = reemplazante->dato;
  172.         if (reemplazante->der){
  173.             if (arbol->cmp(hijo->der->clave, reemplazante->clave) == 0) hijo->der = reemplazante->der;
  174.             else padre->izq = reemplazante->der;
  175.         }
  176.         else if (arbol->cmp(hijo->der->clave, reemplazante->clave) == 0) hijo->der = NULL;
  177.         else padre->izq = NULL;
  178.         free(hijo->clave);
  179.         hijo->clave = strdup(clave_aux);
  180.         borrar_nodo(reemplazante);
  181.         void* aux =  hijo->dato;
  182.         hijo->dato = dato_aux;
  183.         return aux; //Tener en cuenta si hace falta usar Free en clave aux
  184.     }
  185.     return ver_caso_3(arbol, reemplazante, hijo, reemplazante->izq);
  186. }
  187. void* ver_caso_2(abb_t* arbol, nodo_t* padre, nodo_t* hijo){
  188.     if (hijo->izq == NULL){
  189.         if (padre == NULL){
  190.             arbol->raiz = hijo->der;
  191.         }else{
  192.             if (arbol->cmp(padre->clave,hijo->clave) > 0) padre->izq = hijo->der;
  193.             else padre->der = hijo->der;
  194.             }
  195.         }
  196.     if (hijo->der == NULL){
  197.         if (padre == NULL){
  198.             arbol->raiz = hijo->izq;
  199.         }else{
  200.             if (arbol->cmp(padre->clave,hijo->clave) > 0) padre->izq = hijo->izq;
  201.             else padre->der = hijo->izq;
  202.             }
  203.         }
  204.     void* aux = hijo->dato;
  205.     borrar_nodo(hijo);
  206.     return aux;
  207. }
  208.  
  209. void* ver_caso_1(abb_t* arbol,nodo_t* padre, nodo_t* hijo){
  210.     void* aux = hijo->dato;
  211.     if (padre == NULL) arbol->raiz = NULL;
  212.     else if (arbol->cmp(padre->clave,hijo->clave) > 0) padre->izq = NULL;
  213.     else padre->der = NULL;
  214.     borrar_nodo(hijo);
  215.     return aux;
  216. }
  217.  
  218. void borrar_nodo(nodo_t* nodo){
  219.     free(nodo->clave);
  220.     free(nodo);
  221. }
  222.  
  223. void abb_destruir(abb_t *arbol){
  224.     destruir(arbol, arbol->raiz);
  225.     free(arbol);
  226. }
  227. void destruir(abb_t* arbol, nodo_t* nodo){
  228.     if (nodo){
  229.         destruir(arbol, nodo->izq);
  230.         if (arbol->destruir_dato) arbol->destruir_dato(nodo->dato);
  231.         destruir(arbol, nodo->der);
  232.         borrar_nodo(nodo);
  233.     }
  234. }
  235.  
  236. /////////////////////// Iterador Interno //////////////////////////
  237. bool in_order(bool aux, nodo_t* nodo, bool visitar(const char*, void*, void*), void* extra){
  238.     if (!nodo) return aux;
  239.     if (!in_order(aux, nodo->izq, visitar, extra)){
  240.         aux = false;
  241.         return aux;
  242.     }
  243.     if (!visitar(nodo->clave, nodo->dato, extra)){
  244.         aux = false;
  245.         return aux;
  246.     }
  247.     return in_order(aux, nodo->der, visitar, extra);
  248. }
  249.  
  250. void abb_in_order(abb_t *arbol, bool visitar(const char *, void *, void *), void *extra){
  251.     bool aux = true;
  252.     in_order(aux, arbol->raiz, visitar, extra);
  253. }
  254. //////////////////////////////////////////////////////////////////
  255. ////////////////////// Iterador Externo /////////////////////////
  256. ////////////////////////////////////////////////////////////////
  257.  
  258. struct abb_iter{
  259.     abb_t* arbol;
  260.     nodo_t* nodo;
  261.     pila_t* pila;
  262. };
  263.  
  264. void inicializar0avanzar_iter_abb(nodo_t* nodo, abb_iter_t* iter){
  265.     if (!nodo) return;
  266.     pila_apilar(iter->pila, nodo->clave);
  267.     inicializar0avanzar_iter_abb(nodo->izq, iter);
  268. }
  269.  
  270. abb_iter_t* abb_iter_in_crear(const abb_t *arbol){
  271.     abb_iter_t* iter = malloc(sizeof(abb_iter_t));
  272.     if (!iter) return NULL;
  273.     iter->pila = pila_crear();
  274.     if (!iter->pila) return NULL;
  275.     iter->arbol =(abb_t*)arbol;
  276.     iter->nodo = arbol->raiz;
  277.     inicializar0avanzar_iter_abb(iter->nodo, iter);
  278.     return iter;
  279. }
  280.  
  281. void* buscar_iter(nodo_t* nodo, abb_iter_t* iter, char* clave){
  282.     if (!nodo) return NULL;
  283.     if (iter->arbol->cmp(nodo->clave, clave) > 0) return buscar_iter(nodo->izq, iter, clave);
  284.     else if (iter->arbol->cmp(nodo->clave, clave) < 0) return buscar_iter(nodo->der, iter, clave);
  285.     else return nodo;
  286. }
  287.  
  288. bool abb_iter_in_avanzar(abb_iter_t *iter){
  289.     if (abb_iter_in_al_final(iter)) return false;
  290.     char* clave = (char*)pila_desapilar(iter->pila);
  291.     iter->nodo = buscar_iter(iter->arbol->raiz, iter, clave);
  292.     if (iter->nodo->der) inicializar0avanzar_iter_abb(iter->nodo->der, iter);
  293.     return true;
  294. }
  295.  
  296. const char *abb_iter_in_ver_actual(const abb_iter_t *iter){
  297.     return (const char*)pila_ver_tope(iter->pila);
  298. }
  299.  
  300. bool abb_iter_in_al_final(const abb_iter_t *iter){
  301.     return pila_esta_vacia(iter->pila);
  302. }
  303.  
  304. void abb_iter_in_destruir(abb_iter_t* iter){
  305.     pila_destruir(iter->pila);
  306.     free(iter);
  307. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top