下のプログラムは、問4.3, 4.4の巻末解答 p.179を最小限変更しています。
解答例
#include <stdio.h>
#include <stdlib.h>

typedef struct node{
   int data;
   struct node *leftson;
   struct node *rightson;
} Node;

Node *search (int x);
void new (Node **w);
void insert (int x);
void delete (int x);
void nfree (Node *n);
void printtree(Node *n, int h);
int max_v(Node *n);

//int S[11] = {59,38,7,42,16,81,4,32,95,18,25};
int S[11] = {32, 16, 38, 7, 25, 59, 42, 95, 4, 18, 81};
Node *v, *root;   /* 変数rootはNodeを指すポインターを格納する */

/* xを探索する。ノードへのポインターが戻り値 */
Node *search(int x){
   v = root; /* v, rootは大域変数 vは注目しているノード(木)へのポインター。
           rootは、根にあたるノード（木）へのポインター */

   while(v != NULL){          /* vが葉でないノードへのポインターの間 */
      if (v->data == x) {
         return(v);          /* 発見。vをリターン */
      }
      if (v->data > x) {     /* xは、ポインターvの指すノードのdataより小さい */
         v = v->leftson;     /* 左にあるはず。左の木へポインターを更新 */
      }
      else {
         v = v->rightson;    /* 右へ更新 */
      }
   }
   /* 見つけられない場合。例外処理 */
   printf ("The element is not in S.\n");
   return (NULL); /* NULLアドレスを戻り値 */
}


/* ノードを確保 ダブルポインターが使用されているのに注意。wをアドレス1とすると、アドレス1は、Node *を指すアドレス2を格納するポインター変数のアドレス。*/
void new (Node **w) {
   /* wはアドレス。*wもアドレス。wを宣言するには、Node **wとなる */
   *w = (Node *)malloc(sizeof(Node));
   (*w)->leftson = NULL;  /* 教科書は初期化せず、それでもNULLになるのだが */
   (*w)->rightson = NULL; /* ここは、絶対に初期化すべきだ！ */
}

/* xを二分探索木に追加する */
void insert(int x){
   Node *p = NULL; /* pはNodeへのポインター NULLに初期化 */
   Node *w;        /* 新規ノードへのポインター */

   v = root; /* 大域変数 vとroot。vの初期値は、根のノードへのポインター */
             /* vは注目しているノードへのポインター */

   while(v != NULL) { /* 葉に到達するまで */
      p = v; /* 次のvへ更新する前に、ポインターをバックアップ */
      if (v->data > x){ /* xが、dataより小さいなら、左の木へ */
         v = v->leftson;
      } else {
         v = v->rightson;
      }
   }

   new(&w);      /* wはノードへのポインター。そのポインター変数のアドレスを関数 に渡している */
   w->data = x;  /* *w.data = xと同じ */

   /* wをpの指すノードのどちら側につなぐのかを再計算。そこは上のv, NULLのはず */
   if (p->data > x){
      p->leftson = w;
   }
   else {
      p->rightson = w;
   }
}

/* 二分探索木から、xを削除し、場合に応じて木を再構成する */
void delete(int x){
   Node *p, *q;   /* p, qは、ノードへのポインター */
   v = root;      /* vは、注目ノード（木）へのポインター */

   /* xがあるノードを探す insertと同じ vは、削除ノードへのポインター */
   while(v->data != x){
      p = v;                /* vを一つ進ませる前に、pへバックアップ */
      if(v->data > x){
         v = v->leftson;
      } else {
         v = v->rightson;
      }
   }

   if (v->leftson == NULL || v->rightson == NULL) { /* 子が１つか0。ノードの片側がNULL。もう一方の子を上のノードに持ち上げ(上のノードを親に) */
      if (v->leftson == NULL) {
         q = v->rightson;  /* もう一方のノード情報をqにバックアップ */
      } else {
         q = v->leftson;
      }
      if (p->leftson == v) { /* 削除するノードvは、pのどちらにあるか */
         p->leftson = q;     /* 左なら、pの左にqをつなぐ */
      } else {
         p->rightson = q;
      }
   } else {                                         /* 子が２つ。左側はさわらない。右にあたる木を再構成しなければならない */
      q = v->rightson;    /* 削除するvの右側の根にあたるノードをq */
      /* qを根とする木の最小値を探す */
      while(q->leftson != NULL) { /* 左を探し回って葉へ */
         p = q;                   /* qを1つ進ませる前に、pへバックアップ */     
         q = q->leftson;
      }                           /* qは最小ノードへのポインター。最小ノードは左がNULL */

      v->data = q->data;          /* その値を削除ノードの位置へ移動。qの右側があるかも */

      /* ここからが問題。最小値のノードが、葉のときと、1つの子を持つとき */
      if (q == v -> rightson) {      /* vの右直下が最小値だったという特殊な場合 木の構造を考えてみること。*/
         v->rightson = q->rightson;  /* vの右側に、qの右側を接続  右を一つ繰り上げるというイメージ*/
      } else {
         p->leftson = q->rightson;   /* pの左側に、qの右側を接続。qはpの左にあったはず。*/
      }
   }
}

void nfree(Node *n){
   if(n->leftson != NULL) {
      nfree(n->leftson);
   }
   if(n->rightson != NULL){
      nfree(n->rightson);
   }
   free(n);
}

int main(void){
   int i;
   new(&root);    /* 変数rootのアドレスを引数に。rootには、根にあたる
                     ノードへのポインター */
   root->data = S[0]; /* 根のノードのdataをS[0]にセット *root.data = S[0]と同じ */

   /* insertした順序をプリント */
   printf("INSERT:%3d", S[0]);
   for (i=1; i<11; i++){
      insert(S[i]);
      printf("%3d", S[i]);
   }
   printf("\n");

   /*
   printtree(root,0); printf("\n\n");
   */

   insert(23); printf("insert 23\n");
   /*
   printtree(root,0); printf("\n\n");
   */

   delete(59); printf("delete 59\n");
   /*
   printtree(root,0);printf("\n\n");
   */

   printf("The element 23 is found at %p.\n",search(23));
   /*
   printf("max_v is %d.\n",max_v(root));
   */

   nfree(root);
   return 0;
}
STEP 7.2 2分探索木 - delete

STEP 7.2　2分探索木 - delete
