fork(20) download
copy 
  1. /* Arbol Binario de Búsqueda en C      */
  2. /* (C) Abril 2002, Salvador Pozo       */
  3. /* C con Clase: http://c...content-available-to-author-only...e.net  */
  4.  
  5. #include <stdlib.h>
  6. #include <stdio.h>
  7.  
  8. #define TRUE 1
  9. #define FALSE 0
  10.  
  11. /* Estructuras y tipos */
  12. typedef struct _nodo {
  13.    int dato;
  14.    struct _nodo *derecho;
  15.    struct _nodo *izquierdo;
  16. } tipoNodo;
  17.  
  18. typedef tipoNodo *pNodo;
  19. typedef tipoNodo *Arbol;
  20.  
  21. /* Funciones con árboles: */
  22. /* Insertar en árbol ordenado: */
  23. void Insertar(Arbol *a, int dat);
  24. /* Borrar un elemento: */
  25. void Borrar(Arbol *a, int dat);
  26. /* Función de búsqueda: */
  27. int Buscar(Arbol a, int dat);
  28. /* Comprobar si el árbol está vacío: */
  29. int Vacio(Arbol r);
  30. /* Comprobar si es un nodo hoja: */
  31. int EsHoja(pNodo r);
  32. /* Contar número de nodos: */
  33. int NumeroNodos(Arbol a, int* c);
  34. /* Calcular la altura de un árbol: */
  35. int AlturaArbol(Arbol a, int* altura);
  36. /* Calcular altura de un dato: */
  37. int Altura(Arbol a, int dat);
  38. /* Aplicar una función a cada elemento del árbol: */
  39. void InOrden(Arbol, void (*func)(int*));
  40. void PreOrden(Arbol, void (*func)(int*));
  41. void PostOrden(Arbol, void (*func)(int*));
  42.  
  43. /* Funciones auxiliares: */
  44. void Podar(Arbol *a);
  45. void auxContador(Arbol a, int*);
  46. void auxAltura(Arbol a, int, int*);
  47.  
  48. void Mostrar(int *d);
  49.  
  50. /* Programa de ejemplo */
  51. int main()
  52. {
  53.    Arbol ArbolInt=NULL;
  54.    int altura;
  55.    int nnodos;
  56.  
  57.    /* Inserción de nodos en árbol: */
  58.    Insertar(&ArbolInt, 10);
  59.    Insertar(&ArbolInt, 5);
  60.    Insertar(&ArbolInt, 12);
  61.    Insertar(&ArbolInt, 4);
  62.    Insertar(&ArbolInt, 7);
  63.    Insertar(&ArbolInt, 3);
  64.    Insertar(&ArbolInt, 6);
  65.    Insertar(&ArbolInt, 9);
  66.    Insertar(&ArbolInt, 8);
  67.    Insertar(&ArbolInt, 11);
  68.    Insertar(&ArbolInt, 14);
  69.    Insertar(&ArbolInt, 13);
  70.    Insertar(&ArbolInt, 2);
  71.    Insertar(&ArbolInt, 1);
  72.    Insertar(&ArbolInt, 15);
  73.    Insertar(&ArbolInt, 10);
  74.    Insertar(&ArbolInt, 17);
  75.    Insertar(&ArbolInt, 18);
  76.    Insertar(&ArbolInt, 16);
  77.  
  78.    printf("Altura de arbol %d\n", AlturaArbol(ArbolInt, &altura));
  79.  
  80.    /* Mostrar el árbol en tres ordenes distintos: */
  81.    printf("InOrden: ");
  82.    InOrden(ArbolInt, Mostrar);
  83.    printf("\n");
  84.    printf("PreOrden: ");
  85.    PreOrden(ArbolInt, Mostrar);
  86.    printf("\n");
  87.    printf("PostOrden: ");
  88.    PostOrden(ArbolInt, Mostrar);
  89.    printf("\n");
  90.  
  91.    /* Borraremos algunos elementos: */
  92.    printf("N nodos: %d\n", NumeroNodos(ArbolInt, &nnodos));
  93.    Borrar(&ArbolInt, 5);
  94.    printf("Borrar 5: ");
  95.    InOrden(ArbolInt, Mostrar);
  96.    printf("\n");
  97.    Borrar(&ArbolInt, 8);
  98.    printf("Borrar 8: ");
  99.    InOrden(ArbolInt, Mostrar);
  100.    printf("\n");
  101.    Borrar(&ArbolInt, 15);
  102.    printf("Borrar 15: ");
  103.    InOrden(ArbolInt, Mostrar);
  104.    printf("\n");
  105.    Borrar(&ArbolInt, 245);
  106.    printf("Borrar 245: ");
  107.    InOrden(ArbolInt, Mostrar);
  108.    printf("\n");
  109.    Borrar(&ArbolInt, 4);
  110.    printf("Borrar 4: ");
  111.    InOrden(ArbolInt, Mostrar);
  112.    printf("\n");
  113.    Borrar(&ArbolInt, 17);
  114.    printf("Borrar 17: ");
  115.    InOrden(ArbolInt, Mostrar);
  116.    printf("\n");
  117.  
  118.    /* Veamos algunos parámetros */
  119.    printf("N nodos: %d\n", NumeroNodos(ArbolInt, &nnodos));
  120.    printf("Altura de 1 %d\n", Altura(ArbolInt, 1));
  121.    printf("Altura de 10 %d\n", Altura(ArbolInt, 10));
  122.    printf("Altura de arbol %d\n", AlturaArbol(ArbolInt, &altura));
  123.  
  124.    /* Liberar memoria asociada al árbol: */
  125.    Podar(&ArbolInt);
  126.    system("PAUSE");
  127.    return 0;
  128. }
  129.  
  130. /* Poda: borrar todos los nodos a partir de uno, incluido */
  131. void Podar(Arbol *a)
  132. {
  133.    /* Algoritmo recursivo, recorrido en postorden */
  134.    if(*a) {
  135.       Podar(&(*a)->izquierdo); /* Podar izquierdo */
  136.       Podar(&(*a)->derecho);   /* Podar derecho */
  137.       free(*a);                /* Eliminar nodo */
  138.       *a = NULL;
  139.    }
  140. }
  141.  
  142. /* Insertar un dato en el árbol ABB */
  143. void Insertar(Arbol *a, int dat)
  144. {
  145.    pNodo padre = NULL;
  146.    pNodo actual = *a;
  147.  
  148.    /* Buscar el dato en el árbol, manteniendo un puntero al nodo padre */
  149.    while(!Vacio(actual) && dat != actual->dato) {
  150.       padre = actual;
  151.       if(dat < actual->dato) actual = actual->izquierdo;
  152.       else if(dat > actual->dato) actual = actual->derecho;
  153.    }
  154.  
  155.    /* Si se ha encontrado el elemento, regresar sin insertar */
  156.    if(!Vacio(actual)) return;
  157.    /* Si padre es NULL, entonces el árbol estaba vacío, el nuevo nodo será
  158.       el nodo raiz */
  159.    if(Vacio(padre)) {
  160.       *a = (Arbol)malloc(sizeof(tipoNodo));
  161.       (*a)->dato = dat;
  162.       (*a)->izquierdo = (*a)->derecho = NULL;
  163.    }
  164.    /* Si el dato es menor que el que contiene el nodo padre, lo insertamos
  165.       en la rama izquierda */
  166.    else if(dat < padre->dato) {
  167.       actual = (Arbol)malloc(sizeof(tipoNodo));
  168.       padre->izquierdo = actual;
  169.       actual->dato = dat;
  170.       actual->izquierdo = actual->derecho = NULL;
  171.    }
  172.    /* Si el dato es mayor que el que contiene el nodo padre, lo insertamos
  173.       en la rama derecha */
  174.    else if(dat > padre->dato) {
  175.       actual = (Arbol)malloc(sizeof(tipoNodo));
  176.       padre->derecho = actual;
  177.       actual->dato = dat;
  178.       actual->izquierdo = actual->derecho = NULL;
  179.   }
  180. }
  181.  
  182. /* Eliminar un elemento de un árbol ABB */
  183. void Borrar(Arbol *a, int dat)
  184. {
  185.    pNodo padre = NULL;
  186.    pNodo actual;
  187.    pNodo nodo;
  188.    int aux;
  189.  
  190.    actual = *a;
  191.    /* Mientras sea posible que el valor esté en el árbol */
  192.    while(!Vacio(actual)) {
  193.       if(dat == actual->dato) { /* Si el valor está en el nodo actual */
  194.          if(EsHoja(actual)) { /* Y si además es un nodo hoja: lo borramos */
  195.             if(padre) /* Si tiene padre (no es el nodo raiz) */
  196.                /* Anulamos el puntero que le hace referencia */
  197.                if(padre->derecho == actual) padre->derecho = NULL;
  198.                else if(padre->izquierdo == actual) padre->izquierdo = NULL;
  199.             free(actual); /* Borrar el nodo */
  200.             actual = NULL;
  201.             return;
  202.          }
  203.          else { /* Si el valor está en el nodo actual, pero no es hoja */
  204.             padre = actual;
  205.             /* Buscar nodo más izquierdo de rama derecha */
  206.             if(actual->derecho) {
  207.                nodo = actual->derecho;
  208.                while(nodo->izquierdo) {
  209.                   padre = nodo;
  210.                   nodo = nodo->izquierdo;
  211.                }
  212.             }
  213.             /* O buscar nodo más derecho de rama izquierda */
  214.             else {
  215.                nodo = actual->izquierdo;
  216.                while(nodo->derecho) {
  217.                   padre = nodo;
  218.                   nodo = nodo->derecho;
  219.                }
  220.             }
  221.             /* Intercambiar valores de no a borrar u nodo encontrado
  222.                y continuar, cerrando el bucle. El nodo encontrado no tiene
  223.                por qué ser un nodo hoja, cerrando el bucle nos aseguramos
  224.                de que sólo se eliminan nodos hoja. */
  225.             aux = actual->dato;
  226.             actual->dato = nodo->dato;
  227.             nodo->dato = aux;
  228.             actual = nodo;
  229.          }
  230.       }
  231.       else { /* Todavía no hemos encontrado el valor, seguir buscándolo */
  232.          padre = actual;
  233.          if(dat > actual->dato) actual = actual->derecho;
  234.          else if(dat < actual->dato) actual = actual->izquierdo;
  235.       }
  236.    }
  237. }
  238.  
  239. /* Recorrido de árbol en inorden, aplicamos la función func, que tiene
  240.    el prototipo:
  241.    void func(int*);
  242. */
  243. void InOrden(Arbol a, void (*func)(int*))
  244. {
  245.    if(a->izquierdo) InOrden(a->izquierdo, func);
  246.    func(&(a->dato));
  247.    if(a->derecho) InOrden(a->derecho, func);
  248. }
  249.  
  250. /* Recorrido de árbol en preorden, aplicamos la función func, que tiene
  251.    el prototipo:
  252.    void func(int*);
  253. */
  254. void PreOrden(Arbol a, void (*func)(int*))
  255. {
  256.    func(&a->dato);
  257.    if(a->izquierdo) PreOrden(a->izquierdo, func);
  258.    if(a->derecho) PreOrden(a->derecho, func);
  259. }
  260.  
  261. /* Recorrido de árbol en postorden, aplicamos la función func, que tiene
  262.    el prototipo:
  263.    void func(int*);
  264. */
  265. void PostOrden(Arbol a, void (*func)(int*))
  266. {
  267.    if(a->izquierdo) PostOrden(a->izquierdo, func);
  268.    if(a->derecho) PostOrden(a->derecho, func);
  269.    func(&a->dato);
  270. }
  271.  
  272. /* Buscar un valor en el árbol */
  273. int Buscar(Arbol a, int dat)
  274. {
  275.    pNodo actual = a;
  276.  
  277.    /* Todavía puede aparecer, ya que quedan nodos por mirar */
  278.    while(!Vacio(actual)) {
  279.       if(dat == actual->dato) return TRUE; /* dato encontrado */
  280.       else if(dat < actual->dato) actual = actual->izquierdo; /* Seguir */
  281.       else if(dat > actual->dato) actual = actual->derecho;
  282.    }
  283.    return FALSE; /* No está en árbol */
  284. }
  285.  
  286. /* Calcular la altura del nodo que contiene el dato dat */
  287. int Altura(Arbol a, int dat)
  288. {
  289.    int altura = 0;
  290.    pNodo actual = a;
  291.  
  292.    /* Todavía puede aparecer, ya que quedan nodos por mirar */
  293.    while(!Vacio(actual)) {
  294.       if(dat == actual->dato) return altura; /* encontrado: devolver altura */
  295.       else {
  296.          altura++; /* Incrementamos la altura, seguimos buscando */
  297.          if(dat < actual->dato) actual = actual->izquierdo;
  298.          else if(dat > actual->dato) actual = actual->derecho;
  299.       }
  300.    }
  301.    return -1; /* No está en árbol, devolver -1 */
  302. }
  303.  
  304. /* Contar el número de nodos */
  305. int NumeroNodos(Arbol a, int *contador)
  306. {
  307.    *contador = 0;
  308.  
  309.    auxContador(a, contador); /* Función auxiliar */
  310.    return *contador;
  311. }
  312.  
  313. /* Función auxiliar para contar nodos. Función recursiva de recorrido en
  314.    preorden, el proceso es aumentar el contador */
  315. void auxContador(Arbol nodo, int *c)
  316. {
  317.    (*c)++; /* Otro nodo */
  318.    /* Continuar recorrido */
  319.    if(nodo->izquierdo) auxContador(nodo->izquierdo, c);
  320.    if(nodo->derecho)   auxContador(nodo->derecho, c);
  321. }
  322.  
  323. /* Calcular la altura del árbol, que es la altura del nodo de mayor altura. */
  324. int AlturaArbol(Arbol a, int *altura)
  325. {
  326.    *altura = 0;
  327.  
  328.    auxAltura(a, 0, altura); /* Función auxiliar */
  329.    return *altura;
  330. }
  331.  
  332. /* Función auxiliar para calcular altura. Función recursiva de recorrido en
  333.    postorden, el proceso es actualizar la altura sólo en nodos hojas de mayor
  334.    altura de la máxima actual */
  335. void auxAltura(pNodo nodo, int a, int *altura)
  336. {
  337.    /* Recorrido postorden */
  338.    if(nodo->izquierdo) auxAltura(nodo->izquierdo, a+1, altura);
  339.    if(nodo->derecho)   auxAltura(nodo->derecho, a+1, altura);
  340.    /* Proceso, si es un nodo hoja, y su altura es mayor que la actual del
  341.       árbol, actualizamos la altura actual del árbol */
  342.    if(EsHoja(nodo) && a > *altura) *altura = a;
  343. }
  344.  
  345. /* Comprobar si un árbol es vacío */
  346. int Vacio(Arbol r)
  347. {
  348.    return r==NULL;
  349. }
  350.  
  351. /* Comprobar si un nodo es hoja */
  352. int EsHoja(pNodo r)
  353. {
  354.    return !r->derecho && !r->izquierdo;
  355. }
  356.  
  357. /* Función de prueba para recorridos del árbol */
  358. void Mostrar(int *d)
  359. {
  360.    printf("%d, ", *d);
  361. }
  362.  
  363.  
Success #stdin #stdout #stderr 0s 2296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Altura de arbol 5
InOrden: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 
PreOrden: 10, 5, 4, 3, 2, 1, 7, 6, 9, 8, 12, 11, 14, 13, 15, 17, 16, 18, 
PostOrden: 1, 2, 3, 4, 6, 8, 9, 7, 5, 11, 13, 16, 18, 17, 15, 14, 12, 10, 
N nodos: 18
Borrar 5: 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 
Borrar 8: 1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 
Borrar 15: 1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 13, 14, 16, 17, 18, 
Borrar 245: 1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 13, 14, 16, 17, 18, 
Borrar 4: 1, 2, 3, 6, 7, 9, 10, 11, 12, 13, 14, 16, 17, 18, 
Borrar 17: 1, 2, 3, 6, 7, 9, 10, 11, 12, 13, 14, 16, 18, 
N nodos: 13
Altura de 1 4
Altura de 10 0
Altura de arbol 4
stderr
copy 
sh: 1: PAUSE: not found
https://ideone.com/pRXzjW
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!