1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

#include <stdio.h>
#include <stdlib.h>
 
typedef enum { FALSE, TRUE } boolean;
 typedef struct tarbol
{
  int clave;
  struct tarbol *izq;
  struct tarbol *der;} tarbol;
 
void crear(tarbol **a);
boolean buscar(tarbol *a, int elem);
void insertar(tarbol **a, int elem);void borrar(tarbol **a, int elem);
 
 
int main(void)
{  tarbol *a;
 
  crear(&a);
  insertar(&a, 5);
  insertar(&a, 2);  insertar(&a, 4);
  insertar(&a, 3);
  insertar(&a, 6);
 
  borrar(&a, 5);  borrar(&a, 4);
  borrar(&a, 3);
 
  return 0;
} 
void crear(tarbol **a)
{
  *a = NULL;
} 
boolean buscar(tarbol *a, int elem)
{
  if (a == NULL) return FALSE;
  else if (a->clave < elem) return buscar(a->der, elem);  else if (a->clave > elem) return buscar(a->izq, elem);
  else return TRUE;
}
 
void insertar(tarbol **a, int elem){
  if (*a == NULL) {
    *a = (tarbol *) malloc(sizeof(tarbol));
    (*a)->clave = elem;
    (*a)->izq = (*a)->der = NULL;  }
  else if ((*a)->clave < elem) insertar(&(*a)->der, elem);
  else if ((*a)->clave > elem) insertar(&(*a)->izq, elem);
}
 void borrar(tarbol **a, int elem)
{
  void sustituir(tarbol **a, tarbol **aux);
  tarbol *aux;
   if (*a == NULL)   /* no existe la clave */
    return;
 
  if ((*a)->clave < elem) borrar(&(*a)->der, elem);
  else if ((*a)->clave > elem) borrar(&(*a)->izq, elem);  else if ((*a)->clave == elem) {
    aux = *a;
    if ((*a)->izq == NULL) *a = (*a)->der;
    else if ((*a)->der == NULL) *a = (*a)->izq;
    else sustituir(&(*a)->izq, &aux); /* se sustituye por la mayor de las menores */ 
    free(aux);
  }
}
 void sustituir(tarbol **a, tarbol **aux)
{
  if ((*a)->der != NULL) sustituir(&(*a)->der, aux);
  else {
    (*aux)->clave = (*a)->clave;    *aux = *a;
    *a = (*a)->izq;
  }
}