API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Oct 18th, 2019
87
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 8.53 KB | None | 0 0
raw download clone embed print report
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!