<問題>
STEP7.1
に、deleteを追加する
の疑似コードに対応するプログラムを実装せよ。
解答のプログラムは、問4.3, 4.4の巻末解答 p.179を最小限変更しています。
<実行結果 例> INSERT: 32 16 38 7 25 59 42 95 4 18 81 4 7 16 18 25 32 38 42 59 81 95 insert 23 4 7 16 18 23 25 32 38 42 59 81 95 delete 59 4 7 16 18 23 25 32 38 42 81 95 The element 23 is found at 0xdf7170. max_v is 95.
<下のプログラムの実行例> printtreeとmax_vの呼び出しをコメントアウトしてあります
解答例 #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は、注目ノード(木)へのポインター */ 作成しよう コメントをつけよう } 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; }