以下の実行例は、図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); /* 作成せよ */
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;
}

/* 解答例 いわゆる間順の走査を行い、各ノードをプリントする。これも、再帰の定番プログラムです */
void printtree(Node *v ,int h) {
   int j;
   if (v != NULL) {
      printtree (v -> leftson, h+1); /* 左の部分木を出力 */
      for (j = 0 ; j < h; j++)
         printf(" ");         /* 節点を出力 */
      printf("%3d\n", v -> data);
      printtree (v -> rightson, h+1); /* 右の部分木を出力 */
   }
}

/* 二分探索木のノードの削除では、ノードの右の部分木中の最小値（左端）を見つける。下のプログラムは、最大値（右端）を求めている */
int max_v(Node *v) {
   if (v->rightson == NULL)
      return (v -> data);
   else
      return (max_v(v -> rightson));
}

/* 最大値を見つける非再帰型プログラム 
int max_v1(Node *v) {
   while (v -> rightson !=  NULL) {
      v = v -> rightson;
   }
   return (v -> data);
}
*/

STEP 7.1 2分探索木

STEP 7.1　2分探索木