arboles.c

SUBMITTED BY: albermonte

DATE: Sept. 3, 2017, 11:41 a.m.

FORMAT: C

SIZE: 2.8 kB

Raw Download

HITS: 125701

Report
  1. /*
  2. * arboles.c
  3. *
  4. * Created on: Jan 26, 2017
  5. * Author: Departamento de Automática - UAH
  6. */
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9. #include <string.h>
  10. #include "arboles.h"
  14. /* Añade un nuevo nodo a un árbol binario ordenado. Si el árbol está vacio crea el primer nodo.
  15. * Si el id es mayor que el nodo padre se inserta a la derecha. Si es menor a la izquierda.
  16. * Si es igual no se inserta y se devuelve -1
  17. * Esta función se debe implementar recursivamente.
  18. * [OUT] puntero al nodo padre
  19. * [IN] identificador de un punto
  20. * [IN] distancia del punto del nodo padre al nuevo punto
  21. * [RET] return: devuelve -1 si la operación no se ha podido realizar */
  22. int aniadirNodo(Nodo_t** nodo, char id, float distancia)
  23. {
  25. if((*nodo)==NULL)
  26. {
  27. (*nodo)=(Nodo_t *)malloc(sizeof(Nodo_t));
  28. if((*nodo)==NULL)
  29. {
  30. printf("Falta memoria");
  31. return -1;
  32. }
  33. else
  34. {
  35. (*nodo)->punto.id=id;
  36. (*nodo)->punto.distancia=distancia;
  37. (*nodo)->hijoIzq=(*nodo)->hijoDer=NULL;
  38. return 1;
  39. }
  40. }
  41. else
  42. {
  43. if((*nodo)->punto.id>id) //Izq
  44. {
  45. return aniadirNodo(&((*nodo)->hijoIzq),id,distancia);
  46. }
  47. else if((*nodo)->punto.id<id) //Der
  48. {
  49. return aniadirNodo(&((*nodo)->hijoDer),id,distancia);
  50. }
  51. else
  52. {
  53. return -1;
  54. }
  55. }
  56. return 1;
  57. }
  60. /* Elimina un nodo del arbol y todo lo que cuelga de él. Esta función es recursiva
  61. * [OUT] nodo raiz de árbol
  62. * [IN] identificador del punto a eliminar
  63. * [RET] return: devuelve -1 si la operación no se ha podido realizar */
  64. int eliminarNodo(Nodo_t** nodo, char id)
  65. {
  66. if(*nodo==NULL)
  67. {
  68. return -1;
  69. }
  70. else if(id>(*nodo)->punto.id)
  71. {
  72. return eliminarNodo(&((*nodo)->hijoDer), id);
  73. }
  74. else if (id<(*nodo)->punto.id)
  75. {
  76. return eliminarNodo(&((*nodo)->hijoIzq), id);
  77. }
  78. else
  79. {
  80. free(*nodo);
  81. return 0;
  82. }
  84. }
  87. /* Cuenta el número de nodos del arbol. Esta función es recursiva
  88. * [IN] nodo raiz de árbol
  89. * [RET] return: devuelve el número de nodos */
  90. int contarNodos(const Nodo_t* nodo)
  91. {
  92. int nIzq=0, nDer=0;
  93. if(nodo==NULL)
  94. {
  95. return 0;
  96. }
  97. if((nodo->hijoIzq)!=NULL || (nodo->hijoDer)!=NULL)
  98. {
  99. nIzq += contarNodos(nodo->hijoIzq);
  100. nDer += contarNodos(nodo->hijoDer);
  101. }
  102. else
  103. {
  104. return 1;
  105. }
  107. return nIzq+nDer+1; // +1 porque el primer nodo no se cuenta
  108. }
  111. /* Libera la memoria del árbol. Va liberando la memoria de las hojas a la raiz.
  112. * Esta función es recursiva
  113. * [OUT] puntero a la raiz del árbol
  114. * [RET] return: devuelve -1 si la operación no se ha podido realizar */
  115. int borrarArbol(Nodo_t** nodo)
  116. {
  117. if((*nodo)!=NULL)
  118. {
  119. borrarArbol(&((*nodo)->hijoIzq));
  120. borrarArbol(&((*nodo)->hijoDer));
  121. free((*nodo));
  123. }
  124. *nodo = NULL;
  125. return 0;
  126. }
comments powered by Disqus