以下の実行例は、図4.6の2分探索木になるように順にinsertを行ったあと、図4.9のinsertを行った。
続いて、23をsearchしている。アドレスを、printfの%pオプションで出力

実行結果例になるように、下のプログラム中のprinttreeとmax_vを完成させなさい。

下のプログラムは、問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); /* STEP7.1では、未定義 */
void nfree (Node *n);

void printtree(Node *n, int h); /* たとえばの関数 hは高さ。スペースの数にあたる */
int max_v(Node *n); /* 作成せよ */

//int S[11] = {59,38,7,42,16,81,4,32,95,18,25};  p.179の例。
int S[11] = {32, 16, 38, 7, 25, 59, 42, 95, 4, 18, 81}; /* 図4.6 */
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を2分探索木に追加する */
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;
   }
}

/* メモリ解放 */
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");

   /* 2分木をプリント。作成せよ 課題1 図4.6を横から出力したものになっています */
  /*   printtree(root,0);
       printf("\n\n"); */

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

   printf("The element 23 is found at %p.\n",search(23));

   /* 2分探索木中の最大値をプリント。作成せよ。課題2
   printf("max_v is %d.\n",max_v(root));
  */

   nfree(root);
   return 0;
}

STEP 7.1 2分探索木

STEP 7.1　2分探索木