質問編集履歴
14
修正しました
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -362,6 +362,28 @@
|
|
|
362
362
|
|
|
363
363
|
/* 二分木を通りがけ順でなぞる */
|
|
364
364
|
|
|
365
|
+
/* 全要素を昇順に表示する関数
|
|
366
|
+
|
|
367
|
+
二分探索木の全要素を小→大の順で表示する */
|
|
368
|
+
|
|
369
|
+
/* 全体の流れ
|
|
370
|
+
|
|
371
|
+
ある要素の左枝先を全部調べ終えたら、自身の値を出力し、
|
|
372
|
+
|
|
373
|
+
次にその要素の右枝先の要素を全部調べる
|
|
374
|
+
|
|
375
|
+
左枝を調べる
|
|
376
|
+
|
|
377
|
+
調べ終えたら戻ってくる
|
|
378
|
+
|
|
379
|
+
値を出力する
|
|
380
|
+
|
|
381
|
+
右枝を調べる
|
|
382
|
+
|
|
383
|
+
調べ終えたら戻ってくる
|
|
384
|
+
|
|
385
|
+
関数を終了して、自身を呼び出した関数の元へと戻る */
|
|
386
|
+
|
|
365
387
|
void inorder(NODE *p)
|
|
366
388
|
|
|
367
389
|
{
|
|
@@ -372,7 +394,21 @@
|
|
|
372
394
|
|
|
373
395
|
return;
|
|
374
396
|
|
|
375
|
-
els
|
|
397
|
+
else{
|
|
398
|
+
|
|
399
|
+
/* 引数に左へのポインタを渡すことで、再帰を繰り返して延々と左枝へ移動し
|
|
400
|
+
|
|
401
|
+
一番左、一番小さい値にたどり着く
|
|
402
|
+
|
|
403
|
+
子ノードはないため、引数の値はNULLに当たって戻ってくる
|
|
404
|
+
|
|
405
|
+
一番下位の要素なので、左枝と同様に右枝もない。
|
|
406
|
+
|
|
407
|
+
なので終点である NULL に行き当たり、また return で戻ってくる。
|
|
408
|
+
|
|
409
|
+
そして「一番左を操作する関数」は処理を終える。
|
|
410
|
+
|
|
411
|
+
この関数に戻り値はない。「画面に出力」して、それで終了*/
|
|
376
412
|
|
|
377
413
|
inorder(p->left); /* 左ノードへ移動 */
|
|
378
414
|
|
|
@@ -424,7 +460,7 @@
|
|
|
424
460
|
|
|
425
461
|
int a,key;
|
|
426
462
|
|
|
427
|
-
int mn=0;
|
|
463
|
+
int mn=0;
|
|
428
464
|
|
|
429
465
|
|
|
430
466
|
|
|
@@ -526,7 +562,7 @@
|
|
|
526
562
|
|
|
527
563
|
}
|
|
528
564
|
|
|
529
|
-
``
|
|
565
|
+
``
|
|
530
566
|
|
|
531
567
|
```### 前提・実現したいこと``````
|
|
532
568
|
|
13
誤字の修正です
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -362,28 +362,6 @@
|
|
|
362
362
|
|
|
363
363
|
/* 二分木を通りがけ順でなぞる */
|
|
364
364
|
|
|
365
|
-
/* 全要素を昇順に表示する関数
|
|
366
|
-
|
|
367
|
-
二分探索木の全要素を小→大の順で表示する */
|
|
368
|
-
|
|
369
|
-
/* 全体の流れ
|
|
370
|
-
|
|
371
|
-
ある要素の左枝先を全部調べ終えたら、自身の値を出力し、
|
|
372
|
-
|
|
373
|
-
次にその要素の右枝先の要素を全部調べる
|
|
374
|
-
|
|
375
|
-
左枝を調べる
|
|
376
|
-
|
|
377
|
-
調べ終えたら戻ってくる
|
|
378
|
-
|
|
379
|
-
値を出力する
|
|
380
|
-
|
|
381
|
-
右枝を調べる
|
|
382
|
-
|
|
383
|
-
調べ終えたら戻ってくる
|
|
384
|
-
|
|
385
|
-
関数を終了して、自身を呼び出した関数の元へと戻る */
|
|
386
|
-
|
|
387
365
|
void inorder(NODE *p)
|
|
388
366
|
|
|
389
367
|
{
|
|
@@ -394,60 +372,46 @@
|
|
|
394
372
|
|
|
395
373
|
return;
|
|
396
374
|
|
|
375
|
+
els
|
|
376
|
+
|
|
377
|
+
inorder(p->left); /* 左ノードへ移動 */
|
|
378
|
+
|
|
379
|
+
printf("%d ",p->data); /* 自身の値を出力 */
|
|
380
|
+
|
|
381
|
+
inorder(p->right); /* 右ノードへ移動 */
|
|
382
|
+
|
|
383
|
+
}
|
|
384
|
+
|
|
385
|
+
/* 関数を終了して、自身を呼び出した関数のもとへ戻る */
|
|
386
|
+
|
|
387
|
+
|
|
388
|
+
|
|
389
|
+
}
|
|
390
|
+
|
|
391
|
+
|
|
392
|
+
|
|
393
|
+
/* 二分木を帰りがけ順でなぞる */
|
|
394
|
+
|
|
395
|
+
void postorder(NODE *p)
|
|
396
|
+
|
|
397
|
+
{
|
|
398
|
+
|
|
399
|
+
/* 木が空なら何もしない */
|
|
400
|
+
|
|
401
|
+
if(p==NULL)
|
|
402
|
+
|
|
403
|
+
return;
|
|
404
|
+
|
|
397
405
|
else{
|
|
398
406
|
|
|
399
|
-
/* 引数に左へのポインタを渡すことで、再帰を繰り返して延々と左枝へ移動し
|
|
400
|
-
|
|
401
|
-
一番左、一番小さい値にたどり着く
|
|
402
|
-
|
|
403
|
-
子ノードはないため、引数の値はNULLに当たって戻ってくる
|
|
404
|
-
|
|
405
|
-
一番下位の要素なので、左枝と同様に右枝もない。
|
|
406
|
-
|
|
407
|
-
なので終点である NULL に行き当たり、また return で戻ってくる。
|
|
408
|
-
|
|
409
|
-
そして「一番左を操作する関数」は処理を終える。
|
|
410
|
-
|
|
411
|
-
この関数に戻り値はない。「画面に出力」して、それで終了*/
|
|
412
|
-
|
|
413
|
-
|
|
407
|
+
postorder(p->left); /* 左ノードへ移動 */
|
|
408
|
+
|
|
414
|
-
|
|
409
|
+
postorder(p->right); /* 右ノードへ移動 */
|
|
410
|
+
|
|
415
|
-
|
|
411
|
+
printf("%d ",p->data); /* 自身の値を出力 */
|
|
416
|
-
|
|
417
|
-
inorder(p->right); /* 右ノードへ移動 */
|
|
418
412
|
|
|
419
413
|
}
|
|
420
414
|
|
|
421
|
-
/* 関数を終了して、自身を呼び出した関数のもとへ戻る */
|
|
422
|
-
|
|
423
|
-
|
|
424
|
-
|
|
425
|
-
}
|
|
426
|
-
|
|
427
|
-
|
|
428
|
-
|
|
429
|
-
/* 二分木を帰りがけ順でなぞる */
|
|
430
|
-
|
|
431
|
-
void postorder(NODE *p)
|
|
432
|
-
|
|
433
|
-
{
|
|
434
|
-
|
|
435
|
-
/* 木が空なら何もしない */
|
|
436
|
-
|
|
437
|
-
if(p==NULL)
|
|
438
|
-
|
|
439
|
-
return;
|
|
440
|
-
|
|
441
|
-
else{
|
|
442
|
-
|
|
443
|
-
postorder(p->left); /* 左ノードへ移動 */
|
|
444
|
-
|
|
445
|
-
postorder(p->right); /* 右ノードへ移動 */
|
|
446
|
-
|
|
447
|
-
printf("%d",p->data); /* 自身の値を出力 */
|
|
448
|
-
|
|
449
|
-
}
|
|
450
|
-
|
|
451
415
|
|
|
452
416
|
|
|
453
417
|
}
|
12
見やすくしました
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -112,516 +112,564 @@
|
|
|
112
112
|
|
|
113
113
|
if (key == p->data){
|
|
114
114
|
|
|
115
|
-
/* もしキーと注目している節のデータとが等しければポインタを関数として返す */
|
|
115
|
+
/* もしキーと注目している節のデータとが等しければポインタを関数として返す */
|
|
116
|
-
|
|
116
|
+
|
|
117
|
-
printf("探索した値の番地です>>%
|
|
117
|
+
printf("探索した値の番地です>>%p\n",p);
|
|
118
|
-
|
|
118
|
+
|
|
119
|
-
return p;
|
|
119
|
+
return p;
|
|
120
|
+
|
|
121
|
+
}else if (key < p->data){
|
|
122
|
+
|
|
123
|
+
/* キーの方が小さければ左部分木に進む */
|
|
124
|
+
|
|
125
|
+
p = p->left;
|
|
120
126
|
|
|
121
127
|
}else{
|
|
122
128
|
|
|
123
|
-
if (key < p->data)
|
|
124
|
-
|
|
125
|
-
/* キーの方が小さければ左部分木に進む */
|
|
126
|
-
|
|
127
|
-
p = p->left;
|
|
128
|
-
|
|
129
|
-
else
|
|
130
|
-
|
|
131
129
|
/* キーの方が大きければ右部分木に進む*/
|
|
132
130
|
|
|
133
131
|
p = p->right;
|
|
134
132
|
|
|
133
|
+
}
|
|
134
|
+
|
|
135
|
+
/* ループを抜け出たということは見付からなかったというと
|
|
136
|
+
|
|
137
|
+
NULL返して失敗したことを知らせる */
|
|
138
|
+
|
|
139
|
+
printf("NotExist\n");
|
|
140
|
+
|
|
141
|
+
return NULL;
|
|
142
|
+
|
|
143
|
+
}
|
|
144
|
+
|
|
145
|
+
}
|
|
146
|
+
|
|
147
|
+
|
|
148
|
+
|
|
149
|
+
/* 二分探索木から要素を追加する関数*/
|
|
150
|
+
|
|
151
|
+
/* 探索と同じ要領で木を辿り、辿るべき部分木がなければそこに挿入する */
|
|
152
|
+
|
|
153
|
+
/* 挿入した要素が置かれる節へのポインタを返す
|
|
154
|
+
|
|
155
|
+
すでに要素が登録されているのなら、何もしないでNULLを返す
|
|
156
|
+
|
|
157
|
+
key：挿入するデータ
|
|
158
|
+
|
|
159
|
+
NODE型へのポインターが戻り値 */
|
|
160
|
+
|
|
161
|
+
NODE *insert(int key)
|
|
162
|
+
|
|
163
|
+
{
|
|
164
|
+
|
|
165
|
+
NODE **p,*new;
|
|
166
|
+
|
|
167
|
+
/* 変数pが変数rootを指すように初期化する */
|
|
168
|
+
|
|
169
|
+
p=&root;
|
|
170
|
+
|
|
171
|
+
/* 挿入すべき場所が見つかるまで繰り返す */
|
|
172
|
+
|
|
173
|
+
while (*p != NULL) {
|
|
174
|
+
|
|
175
|
+
/* キーと注目している節のデータが等しいか比較 */
|
|
176
|
+
|
|
177
|
+
if (key == (*p)->data){
|
|
178
|
+
|
|
179
|
+
/* すでに登録されている */
|
|
180
|
+
|
|
181
|
+
printf("AlreadyExsits\n");
|
|
182
|
+
|
|
183
|
+
return NULL;
|
|
184
|
+
|
|
185
|
+
}else if (key < (*p)->data){
|
|
186
|
+
|
|
187
|
+
/* キーの方が小さければ左部分木に進む */
|
|
188
|
+
|
|
189
|
+
p =&(*p)->left;
|
|
190
|
+
|
|
191
|
+
}else{
|
|
192
|
+
|
|
193
|
+
/* キーの方が大きければ右部分木に進む */
|
|
194
|
+
|
|
195
|
+
p =&(*p)->right;
|
|
196
|
+
|
|
197
|
+
}
|
|
198
|
+
|
|
199
|
+
}
|
|
200
|
+
|
|
201
|
+
/* 挿入されるべき場所が見つかったら */
|
|
202
|
+
|
|
203
|
+
/* 挿入される節をつくる */
|
|
204
|
+
|
|
205
|
+
|
|
206
|
+
|
|
207
|
+
/* strct型のメモリを確保した分だけnewに入れる。もしNULLだったらエラー */
|
|
208
|
+
|
|
209
|
+
if((new=malloc(sizeof(NODE)))==NULL)
|
|
210
|
+
|
|
211
|
+
fatal_error("out of memory!!");
|
|
212
|
+
|
|
213
|
+
/* 新しい節には子がないのでNULLにしておく */
|
|
214
|
+
|
|
215
|
+
new->left =NULL;
|
|
216
|
+
|
|
217
|
+
new->right=NULL;
|
|
218
|
+
|
|
219
|
+
/* 要素の値をセットする */
|
|
220
|
+
|
|
221
|
+
new->data=key;
|
|
222
|
+
|
|
223
|
+
/* 正しい場所に挿入する */
|
|
224
|
+
|
|
225
|
+
/* ポインタpは挿入される節へのポインタが入っている場所を指している */
|
|
226
|
+
|
|
227
|
+
*p=new;
|
|
228
|
+
|
|
229
|
+
return new;
|
|
230
|
+
|
|
231
|
+
}
|
|
232
|
+
|
|
233
|
+
|
|
234
|
+
|
|
235
|
+
/* 二分探索木から要素を削除する関数 */
|
|
236
|
+
|
|
237
|
+
/* 削除に成功したら1、要素が存在しなければ0を返す
|
|
238
|
+
|
|
239
|
+
key：削除するデータ */
|
|
240
|
+
|
|
241
|
+
int delete(int key)
|
|
242
|
+
|
|
243
|
+
{
|
|
244
|
+
|
|
245
|
+
/* 親へのポインタを使う */
|
|
246
|
+
|
|
247
|
+
NODE **p, *x;
|
|
248
|
+
|
|
249
|
+
/* 変数pが変数rootを指すように初期化する */
|
|
250
|
+
|
|
251
|
+
p = &root;
|
|
252
|
+
|
|
253
|
+
/* 削除対象となる要素を探す */
|
|
254
|
+
|
|
255
|
+
while (*p != NULL) {
|
|
256
|
+
|
|
257
|
+
/* 見つかった
|
|
258
|
+
|
|
259
|
+
変数pは削除される節の親のメンバleft,right
|
|
260
|
+
|
|
261
|
+
変数xは削除される節そのものを指している */
|
|
262
|
+
|
|
263
|
+
if (key == (*p)->data) {
|
|
264
|
+
|
|
265
|
+
x = *p;
|
|
266
|
+
|
|
267
|
+
/* 1つも子を持っていない、葉である場合 */
|
|
268
|
+
|
|
269
|
+
if (x->left == NULL && x->right == NULL){
|
|
270
|
+
|
|
271
|
+
*p = NULL;
|
|
272
|
+
|
|
273
|
+
/* 右の子のみをもつ */
|
|
274
|
+
|
|
275
|
+
}else if (x->left == NULL){
|
|
276
|
+
|
|
277
|
+
*p = x->right;
|
|
278
|
+
|
|
279
|
+
/* 左の子のみをもつ */
|
|
280
|
+
|
|
281
|
+
}else if (x->right == NULL){
|
|
282
|
+
|
|
283
|
+
*p = x->left;
|
|
284
|
+
|
|
285
|
+
/* 左右2つの子を持つ */
|
|
286
|
+
|
|
287
|
+
}else{
|
|
288
|
+
|
|
289
|
+
/* 部分木から最小の要素を取り去る */
|
|
290
|
+
|
|
291
|
+
*p = deletemin(&x->right);
|
|
292
|
+
|
|
293
|
+
(*p)->right = x->right;
|
|
294
|
+
|
|
295
|
+
(*p)->left = x->left;
|
|
296
|
+
|
|
297
|
+
}
|
|
298
|
+
|
|
299
|
+
/* 取り除いた節を解放させる */
|
|
300
|
+
|
|
301
|
+
free(x);
|
|
302
|
+
|
|
303
|
+
printf("Done\n");
|
|
304
|
+
|
|
305
|
+
return 1;
|
|
306
|
+
|
|
307
|
+
|
|
308
|
+
|
|
309
|
+
}else if (key < (*p)->data){
|
|
310
|
+
|
|
311
|
+
/* 左部分木に進む */
|
|
312
|
+
|
|
313
|
+
p = &(*p)->left;
|
|
314
|
+
|
|
315
|
+
}else{
|
|
316
|
+
|
|
317
|
+
/* 右部分木に進む */
|
|
318
|
+
|
|
319
|
+
p = &(*p)->right;
|
|
320
|
+
|
|
321
|
+
}
|
|
322
|
+
|
|
135
323
|
}
|
|
136
324
|
|
|
325
|
+
/* 削除対象が見つからなかった */
|
|
326
|
+
|
|
327
|
+
printf("NotExist\n");
|
|
328
|
+
|
|
329
|
+
return 0;
|
|
330
|
+
|
|
137
|
-
|
|
331
|
+
}
|
|
138
|
-
|
|
139
|
-
|
|
332
|
+
|
|
140
|
-
|
|
141
|
-
|
|
333
|
+
|
|
142
|
-
|
|
143
|
-
|
|
334
|
+
|
|
144
|
-
|
|
145
|
-
return NULL;
|
|
146
|
-
|
|
147
|
-
}
|
|
148
|
-
|
|
149
|
-
|
|
150
|
-
|
|
151
|
-
/* 二分
|
|
335
|
+
/* 二分木を行きがけ順でなぞる */
|
|
152
|
-
|
|
336
|
+
|
|
153
|
-
NODE *
|
|
337
|
+
void preorder(NODE *p)
|
|
154
338
|
|
|
155
339
|
{
|
|
156
340
|
|
|
157
|
-
NODE **p,*new;
|
|
158
|
-
|
|
159
|
-
/* 変数pが変数rootを指すように初期化する */
|
|
160
|
-
|
|
161
|
-
p=&root;
|
|
162
|
-
|
|
163
|
-
/* 挿入すべき場所が見つかるまで繰り返す */
|
|
164
|
-
|
|
165
|
-
while (*p != NULL) {
|
|
166
|
-
|
|
167
|
-
/* キーと注目している節のデータが等しいか比較 */
|
|
168
|
-
|
|
169
|
-
if (key == (*p)->data){
|
|
170
|
-
|
|
171
|
-
|
|
341
|
+
/* 木が空なら何もしない */
|
|
172
|
-
|
|
342
|
+
|
|
173
|
-
|
|
343
|
+
if(p==NULL)
|
|
174
|
-
|
|
344
|
+
|
|
175
|
-
|
|
345
|
+
return;
|
|
176
|
-
|
|
346
|
+
|
|
177
|
-
|
|
347
|
+
else{
|
|
178
|
-
|
|
348
|
+
|
|
179
|
-
|
|
349
|
+
printf("%d ",p->data); /* 自身の値を出力 */
|
|
180
|
-
|
|
350
|
+
|
|
181
|
-
|
|
351
|
+
preorder(p->left); /* 左ノードへ移動 */
|
|
182
|
-
|
|
183
|
-
|
|
352
|
+
|
|
184
|
-
|
|
185
|
-
else
|
|
186
|
-
|
|
187
|
-
|
|
353
|
+
preorder(p->right); /* 右ノードへ移動 */
|
|
188
|
-
|
|
189
|
-
p =&(*p)->right;
|
|
190
|
-
|
|
191
|
-
}
|
|
192
354
|
|
|
193
355
|
}
|
|
194
356
|
|
|
357
|
+
|
|
358
|
+
|
|
359
|
+
}
|
|
360
|
+
|
|
361
|
+
|
|
362
|
+
|
|
195
|
-
|
|
363
|
+
/* 二分木を通りがけ順でなぞる */
|
|
364
|
+
|
|
196
|
-
|
|
365
|
+
/* 全要素を昇順に表示する関数
|
|
366
|
+
|
|
367
|
+
二分探索木の全要素を小→大の順で表示する */
|
|
368
|
+
|
|
369
|
+
/* 全体の流れ
|
|
370
|
+
|
|
371
|
+
ある要素の左枝先を全部調べ終えたら、自身の値を出力し、
|
|
372
|
+
|
|
373
|
+
次にその要素の右枝先の要素を全部調べる
|
|
374
|
+
|
|
375
|
+
左枝を調べる
|
|
376
|
+
|
|
377
|
+
調べ終えたら戻ってくる
|
|
378
|
+
|
|
379
|
+
値を出力する
|
|
380
|
+
|
|
381
|
+
右枝を調べる
|
|
382
|
+
|
|
383
|
+
調べ終えたら戻ってくる
|
|
384
|
+
|
|
385
|
+
関数を終了して、自身を呼び出した関数の元へと戻る */
|
|
386
|
+
|
|
387
|
+
void inorder(NODE *p)
|
|
388
|
+
|
|
389
|
+
{
|
|
390
|
+
|
|
197
|
-
|
|
391
|
+
/* 木が空なら何もしない */
|
|
392
|
+
|
|
393
|
+
if(p==NULL)
|
|
394
|
+
|
|
395
|
+
return;
|
|
396
|
+
|
|
397
|
+
else{
|
|
398
|
+
|
|
399
|
+
/* 引数に左へのポインタを渡すことで、再帰を繰り返して延々と左枝へ移動し
|
|
400
|
+
|
|
401
|
+
一番左、一番小さい値にたどり着く
|
|
402
|
+
|
|
403
|
+
子ノードはないため、引数の値はNULLに当たって戻ってくる
|
|
404
|
+
|
|
405
|
+
一番下位の要素なので、左枝と同様に右枝もない。
|
|
406
|
+
|
|
407
|
+
なので終点である NULL に行き当たり、また return で戻ってくる。
|
|
408
|
+
|
|
409
|
+
そして「一番左を操作する関数」は処理を終える。
|
|
410
|
+
|
|
411
|
+
この関数に戻り値はない。「画面に出力」して、それで終了*/
|
|
412
|
+
|
|
413
|
+
inorder(p->left); /* 左ノードへ移動 */
|
|
414
|
+
|
|
415
|
+
printf("%d",p->data); /* 自身の値を出力 */
|
|
416
|
+
|
|
417
|
+
inorder(p->right); /* 右ノードへ移動 */
|
|
418
|
+
|
|
419
|
+
}
|
|
420
|
+
|
|
421
|
+
/* 関数を終了して、自身を呼び出した関数のもとへ戻る */
|
|
422
|
+
|
|
423
|
+
|
|
424
|
+
|
|
425
|
+
}
|
|
426
|
+
|
|
427
|
+
|
|
428
|
+
|
|
429
|
+
/* 二分木を帰りがけ順でなぞる */
|
|
430
|
+
|
|
431
|
+
void postorder(NODE *p)
|
|
432
|
+
|
|
433
|
+
{
|
|
434
|
+
|
|
435
|
+
/* 木が空なら何もしない */
|
|
436
|
+
|
|
437
|
+
if(p==NULL)
|
|
438
|
+
|
|
439
|
+
return;
|
|
440
|
+
|
|
441
|
+
else{
|
|
442
|
+
|
|
443
|
+
postorder(p->left); /* 左ノードへ移動 */
|
|
444
|
+
|
|
445
|
+
postorder(p->right); /* 右ノードへ移動 */
|
|
446
|
+
|
|
447
|
+
printf("%d",p->data); /* 自身の値を出力 */
|
|
448
|
+
|
|
449
|
+
}
|
|
450
|
+
|
|
451
|
+
|
|
452
|
+
|
|
453
|
+
}
|
|
454
|
+
|
|
455
|
+
|
|
456
|
+
|
|
457
|
+
int main(void)
|
|
458
|
+
|
|
459
|
+
{
|
|
460
|
+
|
|
461
|
+
int a,key;
|
|
462
|
+
|
|
463
|
+
int mn=0;
|
|
464
|
+
|
|
465
|
+
|
|
466
|
+
|
|
467
|
+
printf("二分探索木をします\n");
|
|
468
|
+
|
|
469
|
+
do{
|
|
470
|
+
|
|
471
|
+
printf("\nメニューを選んでください\n1=追加 2=行きがけ順 3=通りがけ順 4=帰りがけ順 5=指定した値の番地 6=削除 9=終了\n");
|
|
472
|
+
|
|
473
|
+
scanf("%d",&mn);
|
|
474
|
+
|
|
475
|
+
switch(mn){
|
|
476
|
+
|
|
477
|
+
|
|
478
|
+
|
|
479
|
+
case 1:
|
|
480
|
+
|
|
481
|
+
printf("追加する数字を入力してください\n");
|
|
482
|
+
|
|
483
|
+
scanf("%d",&a);
|
|
484
|
+
|
|
485
|
+
insert(a);
|
|
486
|
+
|
|
487
|
+
break;
|
|
488
|
+
|
|
489
|
+
|
|
490
|
+
|
|
491
|
+
case 2:
|
|
492
|
+
|
|
493
|
+
printf("行きがけ順です\n");
|
|
494
|
+
|
|
495
|
+
preorder(root);
|
|
496
|
+
|
|
497
|
+
break;
|
|
198
498
|
|
|
199
499
|
|
|
200
500
|
|
|
201
|
-
|
|
202
|
-
|
|
203
|
-
|
|
204
|
-
|
|
205
|
-
|
|
206
|
-
|
|
207
|
-
|
|
208
|
-
|
|
209
|
-
|
|
210
|
-
|
|
211
|
-
|
|
212
|
-
|
|
213
|
-
|
|
214
|
-
|
|
215
|
-
|
|
216
|
-
|
|
217
|
-
|
|
218
|
-
|
|
219
|
-
|
|
220
|
-
|
|
221
|
-
|
|
222
|
-
|
|
223
|
-
|
|
224
|
-
|
|
225
|
-
|
|
226
|
-
|
|
227
|
-
|
|
228
|
-
|
|
229
|
-
|
|
230
|
-
|
|
231
|
-
|
|
232
|
-
|
|
233
|
-
|
|
501
|
+
case 3:
|
|
502
|
+
|
|
503
|
+
printf("通りがけ順です\n");
|
|
504
|
+
|
|
505
|
+
inorder(root);
|
|
506
|
+
|
|
507
|
+
break;
|
|
508
|
+
|
|
509
|
+
|
|
510
|
+
|
|
511
|
+
case 4:
|
|
512
|
+
|
|
513
|
+
printf("帰りがけ順です\n");
|
|
514
|
+
|
|
515
|
+
postorder(root);
|
|
516
|
+
|
|
517
|
+
break;
|
|
518
|
+
|
|
519
|
+
|
|
520
|
+
|
|
521
|
+
case 5:
|
|
522
|
+
|
|
523
|
+
printf("指定した値の番地を出力します\n");
|
|
524
|
+
|
|
525
|
+
scanf("%d",&key);
|
|
526
|
+
|
|
527
|
+
search(key);
|
|
528
|
+
|
|
529
|
+
break;
|
|
530
|
+
|
|
531
|
+
|
|
532
|
+
|
|
533
|
+
case 6:
|
|
534
|
+
|
|
535
|
+
printf("指定した値を削除します\n");
|
|
536
|
+
|
|
537
|
+
scanf("%d",&key);
|
|
538
|
+
|
|
539
|
+
delete(key);
|
|
540
|
+
|
|
541
|
+
break;
|
|
542
|
+
|
|
543
|
+
|
|
544
|
+
|
|
545
|
+
case 9:
|
|
546
|
+
|
|
547
|
+
printf("終了します\n");
|
|
548
|
+
|
|
549
|
+
break;
|
|
550
|
+
|
|
551
|
+
|
|
552
|
+
|
|
553
|
+
default:
|
|
554
|
+
|
|
555
|
+
printf("エラー：メニューの中の数字を入力してください\n");
|
|
556
|
+
|
|
557
|
+
}
|
|
558
|
+
|
|
559
|
+
}while (mn !=9);
|
|
560
|
+
|
|
561
|
+
return 0;
|
|
562
|
+
|
|
563
|
+
}
|
|
564
|
+
|
|
565
|
+
````
|
|
566
|
+
|
|
567
|
+
```### 前提・実現したいこと``````
|
|
568
|
+
|
|
569
|
+
二分探索木のプログラムを実装したいです
|
|
570
|
+
|
|
571
|
+
仕様は
|
|
572
|
+
|
|
573
|
+
数字を入力して
|
|
574
|
+
|
|
575
|
+
1=追加
|
|
576
|
+
|
|
577
|
+
2=行きがけ順で表示
|
|
578
|
+
|
|
579
|
+
3=通りがけ順で表示
|
|
580
|
+
|
|
581
|
+
4=帰りがけ順で表示
|
|
582
|
+
|
|
583
|
+
5=指定した値の番地で表示
|
|
584
|
+
|
|
585
|
+
6=削除
|
|
586
|
+
|
|
587
|
+
9=終了
|
|
588
|
+
|
|
589
|
+
ができるようにしたいです
|
|
590
|
+
|
|
591
|
+
アドバイスお願いいたします！！
|
|
592
|
+
|
|
593
|
+
|
|
594
|
+
|
|
595
|
+
### 発生している問題・エラーメッセージ
|
|
596
|
+
|
|
597
|
+
|
|
598
|
+
|
|
599
|
+
「34行目」で記述エラーを発見しました。
|
|
600
|
+
|
|
601
|
+
「identifier」を付け忘れています。
|
|
602
|
+
|
|
603
|
+
と出てしまいます
|
|
604
|
+
|
|
605
|
+
```
|
|
606
|
+
|
|
607
|
+
|
|
608
|
+
|
|
609
|
+
### 該当のソースコード
|
|
610
|
+
|
|
611
|
+
``````ここに言語を入力
|
|
612
|
+
|
|
613
|
+
ここに言語を入力
|
|
614
|
+
|
|
615
|
+
```
|
|
616
|
+
|
|
617
|
+
コード
|
|
618
|
+
|
|
619
|
+
```
|
|
620
|
+
|
|
621
|
+
|
|
622
|
+
|
|
623
|
+
|
|
624
|
+
|
|
625
|
+
|
|
626
|
+
|
|
627
|
+
|
|
628
|
+
|
|
629
|
+
### 悩んでいること
|
|
630
|
+
|
|
631
|
+
① まず、
|
|
632
|
+
|
|
633
|
+
NODE *search(int key)
|
|
634
|
+
|
|
635
|
+
教科書に書いてあったこの宣言の仕方がよく分かりません
|
|
636
|
+
|
|
637
|
+
|
|
638
|
+
|
|
639
|
+
型名なしの関数の宣言の仕方を調べると一つだけ解説しているサイトが見つかり、自動的にint型になると書 いてあったのですが正しいのでしょうか？
|
|
640
|
+
|
|
641
|
+
|
|
642
|
+
|
|
643
|
+
引数があり、戻り値がある場合はvoid型ではない、
|
|
644
|
+
|
|
645
|
+
引数があり、戻り値がない場合はvoid型、
|
|
646
|
+
|
|
647
|
+
引数がなし、戻り値がある場合もvoid型、
|
|
648
|
+
|
|
649
|
+
引数がなし、戻り値がない場合もvoid型
|
|
650
|
+
|
|
651
|
+
と学びました
|
|
652
|
+
|
|
653
|
+
|
|
654
|
+
|
|
655
|
+
preorder(NODE *p)
|
|
656
|
+
|
|
657
|
+
postorder(NODE *p)
|
|
658
|
+
|
|
659
|
+
inorder(NODE *p)
|
|
660
|
+
|
|
661
|
+
これらの関数は引数があり、戻り値がない場合なのでvoid型、
|
|
662
|
+
|
|
663
|
+
|
|
234
664
|
|
|
235
665
|
int delete(int key)
|
|
236
666
|
|
|
237
|
-
{
|
|
238
|
-
|
|
239
|
-
/* 親へのポインタを使う */
|
|
240
|
-
|
|
241
|
-
NODE **p, *x;
|
|
242
|
-
|
|
243
|
-
/* 変数pが変数rootを指すように初期化する */
|
|
244
|
-
|
|
245
|
-
p = &root;
|
|
246
|
-
|
|
247
|
-
/* 削除対象となる要素を探す */
|
|
248
|
-
|
|
249
|
-
while (*p != NULL) {
|
|
250
|
-
|
|
251
|
-
/* 見つかった
|
|
252
|
-
|
|
253
|
-
変数pは削除される節の親のメンバleft,right
|
|
254
|
-
|
|
255
|
-
変数xは削除される節そのものを指している */
|
|
256
|
-
|
|
257
|
-
if (key == (*p)->data) {
|
|
258
|
-
|
|
259
|
-
x = *p;
|
|
260
|
-
|
|
261
|
-
/* 1つも子を持っていない、葉である場合 */
|
|
262
|
-
|
|
263
|
-
|
|
667
|
+
この関数も引数があり、戻り値がない場合なのでvoid型だと思われるのですがなぜint型なのでしょうか
|
|
264
|
-
|
|
265
|
-
|
|
668
|
+
|
|
266
|
-
|
|
267
|
-
|
|
669
|
+
|
|
268
|
-
|
|
269
|
-
if (x->left == NULL) {
|
|
270
|
-
|
|
271
|
-
*p = x->right;
|
|
272
|
-
|
|
273
|
-
/* 左の子のみをもつ */
|
|
274
|
-
|
|
275
|
-
} else if (x->right == NULL) {
|
|
276
|
-
|
|
277
|
-
*p = x->left;
|
|
278
|
-
|
|
279
|
-
/* 左右2つの子を持つ */
|
|
280
|
-
|
|
281
|
-
} else {
|
|
282
|
-
|
|
283
|
-
/* 部分木から最小の要素を取り去る */
|
|
284
|
-
|
|
285
|
-
*p = deletemin(&x->right);
|
|
286
|
-
|
|
287
|
-
(*p)->right = x->right;
|
|
288
|
-
|
|
289
|
-
(*p)->left = x->left;
|
|
290
|
-
|
|
291
|
-
}
|
|
292
|
-
|
|
293
|
-
/* 取り除いた節を解放させる */
|
|
294
|
-
|
|
295
|
-
free(x);
|
|
296
|
-
|
|
297
|
-
printf("Done\n");
|
|
298
|
-
|
|
299
|
-
return 1;
|
|
300
|
-
|
|
301
|
-
|
|
302
|
-
|
|
303
|
-
} else if (key < (*p)->data)
|
|
304
|
-
|
|
305
|
-
/* 左部分木に進む */
|
|
306
|
-
|
|
307
|
-
p = &(*p)->left;
|
|
308
|
-
|
|
309
|
-
else
|
|
310
|
-
|
|
311
|
-
/* 右部分木に進む */
|
|
312
|
-
|
|
313
|
-
p = &(*p)->right;
|
|
314
|
-
|
|
315
|
-
}
|
|
316
|
-
|
|
317
|
-
}
|
|
318
|
-
|
|
319
|
-
/* 削除対象が見つからなかった */
|
|
320
|
-
|
|
321
|
-
printf("NotExist\n");
|
|
322
|
-
|
|
323
|
-
return 0;
|
|
324
|
-
|
|
325
|
-
}
|
|
326
|
-
|
|
327
|
-
|
|
328
|
-
|
|
329
|
-
|
|
330
|
-
|
|
331
|
-
|
|
332
|
-
|
|
333
|
-
/* 二分木を行きがけ順でなぞる */
|
|
334
|
-
|
|
335
|
-
void preorder(NODE *p)
|
|
336
|
-
|
|
337
|
-
{
|
|
338
|
-
|
|
339
|
-
/* 木が空なら何もしない */
|
|
340
|
-
|
|
341
|
-
if(p==NULL)
|
|
342
|
-
|
|
343
|
-
return;
|
|
344
|
-
|
|
345
|
-
else{
|
|
346
|
-
|
|
347
|
-
printf("%d",p->data); /* 自身の値を出力 */
|
|
348
|
-
|
|
349
|
-
preorder(p->left); /* 左ノードへ移動 */
|
|
350
|
-
|
|
351
|
-
preorder(p->right); /* 右ノードへ移動 */
|
|
352
|
-
|
|
353
|
-
}
|
|
354
|
-
|
|
355
|
-
}
|
|
356
|
-
|
|
357
|
-
|
|
358
|
-
|
|
359
|
-
/* 二分木を通りがけ順でなぞる */
|
|
360
|
-
|
|
361
|
-
void inorder(NODE *p)
|
|
362
|
-
|
|
363
|
-
{
|
|
364
|
-
|
|
365
|
-
/* 木が空なら何もしない */
|
|
366
|
-
|
|
367
|
-
if(p==NULL)
|
|
368
|
-
|
|
369
|
-
return;
|
|
370
|
-
|
|
371
|
-
else{
|
|
372
|
-
|
|
373
|
-
}
|
|
374
|
-
|
|
375
|
-
}
|
|
376
|
-
|
|
377
|
-
|
|
378
|
-
|
|
379
|
-
/* 二分木を帰りがけ順でなぞる */
|
|
380
|
-
|
|
381
|
-
void postorder(NODE *p)
|
|
382
|
-
|
|
383
|
-
{
|
|
384
|
-
|
|
385
|
-
/* 木が空なら何もしない */
|
|
386
|
-
|
|
387
|
-
if(p==NULL)
|
|
388
|
-
|
|
389
|
-
return;
|
|
390
|
-
|
|
391
|
-
else{
|
|
392
|
-
|
|
393
|
-
postorder(p->left); /* 左ノードへ移動 */
|
|
394
|
-
|
|
395
|
-
postorder(p->right); /* 右ノードへ移動 */
|
|
396
|
-
|
|
397
|
-
printf("%d",p->data); /* 自身の値を出力 */
|
|
398
|
-
|
|
399
|
-
}
|
|
400
|
-
|
|
401
|
-
}
|
|
402
|
-
|
|
403
|
-
|
|
404
|
-
|
|
405
|
-
int main(void)
|
|
406
|
-
|
|
407
|
-
{
|
|
408
|
-
|
|
409
|
-
int a,key1,key2;
|
|
410
|
-
|
|
411
|
-
int mn=0;
|
|
412
|
-
|
|
413
|
-
|
|
414
|
-
|
|
415
|
-
printf("二分探索木をします\n");
|
|
416
|
-
|
|
417
|
-
do{
|
|
418
|
-
|
|
419
|
-
printf("メニューを選んでください\n\n1=追加\n2=行きがけ順\n3=通りがけ順\n4=帰りがけ順\n5=指定した値の番地\n6=削除\n9=終了\n");
|
|
420
|
-
|
|
421
|
-
scanf("%d",&mn);
|
|
422
|
-
|
|
423
|
-
switch(mn){
|
|
424
|
-
|
|
425
|
-
|
|
426
|
-
|
|
427
|
-
case 1:
|
|
428
|
-
|
|
429
|
-
printf("追加する数字を入力してください\n");
|
|
430
|
-
|
|
431
|
-
scanf("%d",&a);
|
|
432
|
-
|
|
433
|
-
insert(a);
|
|
434
|
-
|
|
435
|
-
break;
|
|
436
|
-
|
|
437
|
-
|
|
438
|
-
|
|
439
|
-
case 2:
|
|
440
|
-
|
|
441
|
-
printf("行きがけ順です\n");
|
|
442
|
-
|
|
443
|
-
preorder(root);
|
|
444
|
-
|
|
445
|
-
break;
|
|
446
|
-
|
|
447
|
-
|
|
448
|
-
|
|
449
|
-
case 3:
|
|
450
|
-
|
|
451
|
-
printf("通りがけ順です\n");
|
|
452
|
-
|
|
453
|
-
inorder(root);
|
|
454
|
-
|
|
455
|
-
break;
|
|
456
|
-
|
|
457
|
-
|
|
458
|
-
|
|
459
|
-
case 4:
|
|
460
|
-
|
|
461
|
-
printf("帰りがけ順です\n");
|
|
462
|
-
|
|
463
|
-
postorder(root);
|
|
464
|
-
|
|
465
|
-
break;
|
|
466
|
-
|
|
467
|
-
|
|
468
|
-
|
|
469
|
-
case 5:
|
|
470
|
-
|
|
471
|
-
printf("指定した値の番地を出力します\n");
|
|
472
|
-
|
|
473
|
-
scanf("%d",&key1);
|
|
474
|
-
|
|
475
|
-
search(key1);
|
|
476
|
-
|
|
477
|
-
break;
|
|
478
|
-
|
|
479
|
-
|
|
480
|
-
|
|
481
|
-
case 6:
|
|
482
|
-
|
|
483
|
-
printf("指定した値を削除します\n");
|
|
484
|
-
|
|
485
|
-
scanf("%d",&key2);
|
|
486
|
-
|
|
487
|
-
delete(key2);
|
|
488
|
-
|
|
489
|
-
break;
|
|
490
|
-
|
|
491
|
-
|
|
492
|
-
|
|
493
|
-
case 9:
|
|
494
|
-
|
|
495
|
-
printf("終了します\n");
|
|
496
|
-
|
|
497
|
-
break;
|
|
498
|
-
|
|
499
|
-
|
|
500
|
-
|
|
501
|
-
default:
|
|
502
|
-
|
|
503
|
-
printf("エラー：メニューの中の数字を入力してください\n");
|
|
504
|
-
|
|
505
|
-
}
|
|
506
|
-
|
|
507
|
-
}while (mn !=9);
|
|
508
|
-
|
|
509
|
-
|
|
510
|
-
|
|
511
|
-
kaihou();
|
|
512
|
-
|
|
513
|
-
return 0;
|
|
514
|
-
|
|
515
|
-
}
|
|
516
|
-
|
|
517
|
-
``
|
|
518
|
-
|
|
519
|
-
```### 前提・実現したいこと``````
|
|
520
|
-
|
|
521
|
-
二分探索木のプログラムを実装したいです
|
|
522
|
-
|
|
523
|
-
仕様は
|
|
524
|
-
|
|
525
|
-
数字を入力して
|
|
526
|
-
|
|
527
|
-
1=追加
|
|
528
|
-
|
|
529
|
-
2=行きがけ順で表示
|
|
530
|
-
|
|
531
|
-
3=通りがけ順で表示
|
|
532
|
-
|
|
533
|
-
4=帰りがけ順で表示
|
|
534
|
-
|
|
535
|
-
5=指定した値の番地で表示
|
|
536
|
-
|
|
537
|
-
6=削除
|
|
538
|
-
|
|
539
|
-
9=終了
|
|
540
|
-
|
|
541
|
-
ができるようにしたいです
|
|
542
|
-
|
|
543
|
-
アドバイスお願いいたします！！
|
|
544
|
-
|
|
545
|
-
|
|
546
|
-
|
|
547
|
-
### 発生している問題・エラーメッセージ
|
|
548
|
-
|
|
549
|
-
|
|
550
|
-
|
|
551
|
-
「34行目」で記述エラーを発見しました。
|
|
552
|
-
|
|
553
|
-
「identifier」を付け忘れています。
|
|
554
|
-
|
|
555
|
-
と出てしまいます
|
|
556
|
-
|
|
557
|
-
```
|
|
558
|
-
|
|
559
|
-
|
|
560
|
-
|
|
561
|
-
### 該当のソースコード
|
|
562
|
-
|
|
563
|
-
``````ここに言語を入力
|
|
564
|
-
|
|
565
|
-
ここに言語を入力
|
|
566
|
-
|
|
567
|
-
```
|
|
568
|
-
|
|
569
|
-
コード
|
|
570
|
-
|
|
571
|
-
```
|
|
572
|
-
|
|
573
|
-
|
|
574
|
-
|
|
575
|
-
|
|
576
|
-
|
|
577
|
-
|
|
578
|
-
|
|
579
|
-
|
|
580
|
-
|
|
581
|
-
### 悩んでいること
|
|
582
|
-
|
|
583
|
-
① まず、
|
|
584
670
|
|
|
585
671
|
NODE *search(int key)
|
|
586
672
|
|
|
587
|
-
教科書に書いてあったこの宣言の仕方がよく分かりません
|
|
588
|
-
|
|
589
|
-
|
|
590
|
-
|
|
591
|
-
型名なしの関数の宣言の仕方を調べると一つだけ解説しているサイトが見つかり、自動的にint型になると書 いてあったのですが正しいのでしょうか？
|
|
592
|
-
|
|
593
|
-
|
|
594
|
-
|
|
595
|
-
引数があり、戻り値がある場合はvoid型ではない、
|
|
596
|
-
|
|
597
|
-
引数があり、戻り値がない場合はvoid型、
|
|
598
|
-
|
|
599
|
-
引数がなし、戻り値がある場合もvoid型、
|
|
600
|
-
|
|
601
|
-
引数がなし、戻り値がない場合もvoid型
|
|
602
|
-
|
|
603
|
-
と学びました
|
|
604
|
-
|
|
605
|
-
|
|
606
|
-
|
|
607
|
-
preorder(NODE *p)
|
|
608
|
-
|
|
609
|
-
postorder(NODE *p)
|
|
610
|
-
|
|
611
|
-
inorder(NODE *p)
|
|
612
|
-
|
|
613
|
-
これらの関数は引数があり、戻り値がない場合なのでvoid型、
|
|
614
|
-
|
|
615
|
-
|
|
616
|
-
|
|
617
|
-
int delete(int key)
|
|
618
|
-
|
|
619
|
-
この関数も引数があり、戻り値がない場合なのでvoid型だと思われるのですがなぜint型なのでしょうか
|
|
620
|
-
|
|
621
|
-
|
|
622
|
-
|
|
623
|
-
NODE *search(int key)
|
|
624
|
-
|
|
625
673
|
NODE *insert(int key)
|
|
626
674
|
|
|
627
675
|
NODE *deletemin(NODE **p)
|
11
インデントをきちんとしました
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -150,16 +150,6 @@
|
|
|
150
150
|
|
|
151
151
|
/* 二分探索木から要素を追加する関数*/
|
|
152
152
|
|
|
153
|
-
/* 探索と同じ要領で木を辿り、辿るべき部分木がなければそこに挿入する */
|
|
154
|
-
|
|
155
|
-
/* 挿入した要素が置かれる節へのポインタを返す
|
|
156
|
-
|
|
157
|
-
すでに要素が登録されているのなら、何もしないでNULLを返す
|
|
158
|
-
|
|
159
|
-
key：挿入するデータ
|
|
160
|
-
|
|
161
|
-
NODE型へのポインターが戻り値 */
|
|
162
|
-
|
|
163
153
|
NODE *insert(int key)
|
|
164
154
|
|
|
165
155
|
{
|
|
@@ -246,103 +236,129 @@
|
|
|
246
236
|
|
|
247
237
|
{
|
|
248
238
|
|
|
249
|
-
|
|
250
|
-
|
|
251
|
-
|
|
252
|
-
|
|
253
|
-
|
|
254
|
-
|
|
255
|
-
|
|
256
|
-
|
|
257
|
-
|
|
258
|
-
|
|
259
|
-
|
|
260
|
-
|
|
261
|
-
|
|
262
|
-
|
|
263
|
-
|
|
264
|
-
|
|
265
|
-
|
|
266
|
-
|
|
267
|
-
|
|
268
|
-
|
|
269
|
-
|
|
270
|
-
|
|
271
|
-
|
|
272
|
-
|
|
273
|
-
|
|
274
|
-
|
|
275
|
-
|
|
276
|
-
|
|
277
|
-
|
|
278
|
-
|
|
279
|
-
|
|
280
|
-
|
|
281
|
-
|
|
282
|
-
|
|
283
|
-
|
|
284
|
-
|
|
285
|
-
|
|
286
|
-
|
|
287
|
-
|
|
288
|
-
|
|
289
|
-
|
|
290
|
-
|
|
291
|
-
|
|
292
|
-
|
|
293
|
-
|
|
294
|
-
|
|
295
|
-
|
|
296
|
-
|
|
297
|
-
|
|
298
|
-
|
|
299
|
-
|
|
300
|
-
|
|
301
|
-
|
|
302
|
-
|
|
303
|
-
|
|
304
|
-
|
|
305
|
-
|
|
306
|
-
|
|
307
|
-
|
|
308
|
-
|
|
309
|
-
|
|
310
|
-
|
|
311
|
-
|
|
312
|
-
|
|
313
|
-
|
|
314
|
-
|
|
315
|
-
|
|
316
|
-
|
|
317
|
-
|
|
318
|
-
|
|
319
|
-
|
|
320
|
-
|
|
321
|
-
|
|
322
|
-
|
|
323
|
-
|
|
324
|
-
|
|
325
|
-
|
|
239
|
+
/* 親へのポインタを使う */
|
|
240
|
+
|
|
241
|
+
NODE **p, *x;
|
|
242
|
+
|
|
243
|
+
/* 変数pが変数rootを指すように初期化する */
|
|
244
|
+
|
|
245
|
+
p = &root;
|
|
246
|
+
|
|
247
|
+
/* 削除対象となる要素を探す */
|
|
248
|
+
|
|
249
|
+
while (*p != NULL) {
|
|
250
|
+
|
|
251
|
+
/* 見つかった
|
|
252
|
+
|
|
253
|
+
変数pは削除される節の親のメンバleft,right
|
|
254
|
+
|
|
255
|
+
変数xは削除される節そのものを指している */
|
|
256
|
+
|
|
257
|
+
if (key == (*p)->data) {
|
|
258
|
+
|
|
259
|
+
x = *p;
|
|
260
|
+
|
|
261
|
+
/* 1つも子を持っていない、葉である場合 */
|
|
262
|
+
|
|
263
|
+
if (x->left == NULL && x->right == NULL) {
|
|
264
|
+
|
|
265
|
+
*p = NULL;
|
|
266
|
+
|
|
267
|
+
/* 右の子のみをもつ */
|
|
268
|
+
|
|
269
|
+
if (x->left == NULL) {
|
|
270
|
+
|
|
271
|
+
*p = x->right;
|
|
272
|
+
|
|
273
|
+
/* 左の子のみをもつ */
|
|
274
|
+
|
|
275
|
+
} else if (x->right == NULL) {
|
|
276
|
+
|
|
277
|
+
*p = x->left;
|
|
278
|
+
|
|
279
|
+
/* 左右2つの子を持つ */
|
|
280
|
+
|
|
281
|
+
} else {
|
|
282
|
+
|
|
283
|
+
/* 部分木から最小の要素を取り去る */
|
|
284
|
+
|
|
285
|
+
*p = deletemin(&x->right);
|
|
286
|
+
|
|
287
|
+
(*p)->right = x->right;
|
|
288
|
+
|
|
289
|
+
(*p)->left = x->left;
|
|
290
|
+
|
|
291
|
+
}
|
|
292
|
+
|
|
293
|
+
/* 取り除いた節を解放させる */
|
|
294
|
+
|
|
295
|
+
free(x);
|
|
296
|
+
|
|
297
|
+
printf("Done\n");
|
|
298
|
+
|
|
299
|
+
return 1;
|
|
300
|
+
|
|
301
|
+
|
|
302
|
+
|
|
303
|
+
} else if (key < (*p)->data)
|
|
304
|
+
|
|
305
|
+
/* 左部分木に進む */
|
|
306
|
+
|
|
307
|
+
p = &(*p)->left;
|
|
308
|
+
|
|
309
|
+
else
|
|
310
|
+
|
|
311
|
+
/* 右部分木に進む */
|
|
312
|
+
|
|
313
|
+
p = &(*p)->right;
|
|
314
|
+
|
|
315
|
+
}
|
|
316
|
+
|
|
317
|
+
}
|
|
318
|
+
|
|
319
|
+
/* 削除対象が見つからなかった */
|
|
320
|
+
|
|
321
|
+
printf("NotExist\n");
|
|
322
|
+
|
|
323
|
+
return 0;
|
|
324
|
+
|
|
325
|
+
}
|
|
326
|
+
|
|
327
|
+
|
|
328
|
+
|
|
329
|
+
|
|
330
|
+
|
|
331
|
+
|
|
332
|
+
|
|
333
|
+
/* 二分木を行きがけ順でなぞる */
|
|
334
|
+
|
|
335
|
+
void preorder(NODE *p)
|
|
336
|
+
|
|
337
|
+
{
|
|
338
|
+
|
|
339
|
+
/* 木が空なら何もしない */
|
|
340
|
+
|
|
341
|
+
if(p==NULL)
|
|
342
|
+
|
|
343
|
+
return;
|
|
344
|
+
|
|
345
|
+
else{
|
|
346
|
+
|
|
347
|
+
printf("%d",p->data); /* 自身の値を出力 */
|
|
348
|
+
|
|
349
|
+
preorder(p->left); /* 左ノードへ移動 */
|
|
350
|
+
|
|
351
|
+
preorder(p->right); /* 右ノードへ移動 */
|
|
326
352
|
|
|
327
353
|
}
|
|
328
354
|
|
|
329
|
-
/* 削除対象が見つからなかった */
|
|
330
|
-
|
|
331
|
-
printf("NotExist\n");
|
|
332
|
-
|
|
333
|
-
return 0;
|
|
334
|
-
|
|
335
|
-
}
|
|
355
|
+
}
|
|
336
|
-
|
|
337
|
-
|
|
338
|
-
|
|
339
|
-
|
|
340
|
-
|
|
341
|
-
|
|
342
|
-
|
|
356
|
+
|
|
357
|
+
|
|
358
|
+
|
|
343
|
-
/* 二分木を
|
|
359
|
+
/* 二分木を通りがけ順でなぞる */
|
|
344
|
-
|
|
360
|
+
|
|
345
|
-
void
|
|
361
|
+
void inorder(NODE *p)
|
|
346
362
|
|
|
347
363
|
{
|
|
348
364
|
|
|
@@ -354,11 +370,31 @@
|
|
|
354
370
|
|
|
355
371
|
else{
|
|
356
372
|
|
|
373
|
+
}
|
|
374
|
+
|
|
375
|
+
}
|
|
376
|
+
|
|
377
|
+
|
|
378
|
+
|
|
379
|
+
/* 二分木を帰りがけ順でなぞる */
|
|
380
|
+
|
|
381
|
+
void postorder(NODE *p)
|
|
382
|
+
|
|
383
|
+
{
|
|
384
|
+
|
|
385
|
+
/* 木が空なら何もしない */
|
|
386
|
+
|
|
387
|
+
if(p==NULL)
|
|
388
|
+
|
|
389
|
+
return;
|
|
390
|
+
|
|
391
|
+
else{
|
|
392
|
+
|
|
393
|
+
postorder(p->left); /* 左ノードへ移動 */
|
|
394
|
+
|
|
395
|
+
postorder(p->right); /* 右ノードへ移動 */
|
|
396
|
+
|
|
357
|
-
|
|
397
|
+
printf("%d",p->data); /* 自身の値を出力 */
|
|
358
|
-
|
|
359
|
-
preorder(p->left); /* 左ノードへ移動 */
|
|
360
|
-
|
|
361
|
-
preorder(p->right); /* 右ノードへ移動 */
|
|
362
398
|
|
|
363
399
|
}
|
|
364
400
|
|
|
@@ -366,52 +402,6 @@
|
|
|
366
402
|
|
|
367
403
|
|
|
368
404
|
|
|
369
|
-
/* 二分木を通りがけ順でなぞる */
|
|
370
|
-
|
|
371
|
-
void inorder(NODE *p)
|
|
372
|
-
|
|
373
|
-
{
|
|
374
|
-
|
|
375
|
-
/* 木が空なら何もしない */
|
|
376
|
-
|
|
377
|
-
if(p==NULL)
|
|
378
|
-
|
|
379
|
-
return;
|
|
380
|
-
|
|
381
|
-
else{
|
|
382
|
-
|
|
383
|
-
}
|
|
384
|
-
|
|
385
|
-
}
|
|
386
|
-
|
|
387
|
-
|
|
388
|
-
|
|
389
|
-
/* 二分木を帰りがけ順でなぞる */
|
|
390
|
-
|
|
391
|
-
void postorder(NODE *p)
|
|
392
|
-
|
|
393
|
-
{
|
|
394
|
-
|
|
395
|
-
/* 木が空なら何もしない */
|
|
396
|
-
|
|
397
|
-
if(p==NULL)
|
|
398
|
-
|
|
399
|
-
return;
|
|
400
|
-
|
|
401
|
-
else{
|
|
402
|
-
|
|
403
|
-
postorder(p->left); /* 左ノードへ移動 */
|
|
404
|
-
|
|
405
|
-
postorder(p->right); /* 右ノードへ移動 */
|
|
406
|
-
|
|
407
|
-
printf("%d",p->data); /* 自身の値を出力 */
|
|
408
|
-
|
|
409
|
-
}
|
|
410
|
-
|
|
411
|
-
}
|
|
412
|
-
|
|
413
|
-
|
|
414
|
-
|
|
415
405
|
int main(void)
|
|
416
406
|
|
|
417
407
|
{
|
10
コードをコピペし直しました ながいコメントを削除しました
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -1,683 +1,637 @@
|
|
|
1
|
+
```ここに言語を入力
|
|
2
|
+
|
|
3
|
+
コード
|
|
4
|
+
|
|
5
|
+
`#include <stdio.h>
|
|
6
|
+
|
|
7
|
+
#include <stdlib.h>
|
|
8
|
+
|
|
9
|
+
|
|
10
|
+
|
|
11
|
+
/* 木の節の定義 */
|
|
12
|
+
|
|
13
|
+
typedef struct node{
|
|
14
|
+
|
|
15
|
+
int data; /* 探索のキーになるデータ型 */
|
|
16
|
+
|
|
17
|
+
struct node *left; /* 左の子 */
|
|
18
|
+
|
|
19
|
+
struct node *right; /* 右の子 */
|
|
20
|
+
|
|
21
|
+
}NODE;
|
|
22
|
+
|
|
23
|
+
/* メンバright,leftにNULLポインタがセットされているときは該当する子がいないことを表す */
|
|
24
|
+
|
|
25
|
+
|
|
26
|
+
|
|
27
|
+
/* 初期状態では二分探索木は空の状態。
|
|
28
|
+
|
|
29
|
+
グローバル変数rootが二分探索木の根へのポインタを保持しているものとする */
|
|
30
|
+
|
|
31
|
+
/* グローバル変数rootをNULLで初期化 */
|
|
32
|
+
|
|
33
|
+
NODE *root = NULL;
|
|
34
|
+
|
|
35
|
+
|
|
36
|
+
|
|
37
|
+
/* エラーメッセージをプリントしてexitする関数*/
|
|
38
|
+
|
|
39
|
+
/* ポインタ(アドレス)の先のデータを読み取り専用にする */
|
|
40
|
+
|
|
41
|
+
void fatal_error(const char *s)
|
|
42
|
+
|
|
43
|
+
{
|
|
44
|
+
|
|
45
|
+
/* fprintf関数を使ってstderrで標準エラーを出力する*/
|
|
46
|
+
|
|
47
|
+
fprintf(stderr,"%s", s);
|
|
48
|
+
|
|
49
|
+
exit(1); /* 異常終了 */
|
|
50
|
+
|
|
51
|
+
}
|
|
52
|
+
|
|
53
|
+
|
|
54
|
+
|
|
55
|
+
/* 二分探索木から最小の要素を削除する関数 */
|
|
56
|
+
|
|
57
|
+
/* 削除した節へのポインタを返す
|
|
58
|
+
|
|
59
|
+
p:二分探索木へのポインタへのポインタ
|
|
60
|
+
|
|
61
|
+
(つまり＊pが木へのポインタとなる)
|
|
62
|
+
|
|
63
|
+
NODE型へのポインターが戻り値 */
|
|
64
|
+
|
|
65
|
+
NODE *deletemin(NODE **p)
|
|
66
|
+
|
|
67
|
+
{
|
|
68
|
+
|
|
69
|
+
NODE *x;
|
|
70
|
+
|
|
71
|
+
|
|
72
|
+
|
|
73
|
+
while ((*p)->left != NULL)
|
|
74
|
+
|
|
75
|
+
p=&(*p)->left;
|
|
76
|
+
|
|
77
|
+
x=*p;
|
|
78
|
+
|
|
79
|
+
*p=(*p)->right;
|
|
80
|
+
|
|
81
|
+
return x;
|
|
82
|
+
|
|
83
|
+
}
|
|
84
|
+
|
|
85
|
+
|
|
86
|
+
|
|
87
|
+
/* 二分探索木を探索する関数 */
|
|
88
|
+
|
|
89
|
+
/* パラメータkeyを受け取ってポインタを返す関数として定義
|
|
90
|
+
|
|
91
|
+
key：探索すべきキーの値
|
|
92
|
+
|
|
93
|
+
探索に成功した場合そのデータの節へのポインタを返す
|
|
94
|
+
|
|
95
|
+
NODE型へのポインターが戻り値 */
|
|
96
|
+
|
|
97
|
+
NODE *search(int key)
|
|
98
|
+
|
|
99
|
+
{
|
|
100
|
+
|
|
101
|
+
NODE *p; /* 現在注目している節 */
|
|
102
|
+
|
|
103
|
+
p=root; /* まず根に注目する */
|
|
104
|
+
|
|
105
|
+
|
|
106
|
+
|
|
107
|
+
/* 進むべき子が存在する限り繰り返す */
|
|
108
|
+
|
|
109
|
+
while (p != NULL) {
|
|
110
|
+
|
|
111
|
+
/* キーと注目している節のデータが等しいか比較 */
|
|
112
|
+
|
|
113
|
+
if (key == p->data){
|
|
114
|
+
|
|
115
|
+
/* もしキーと注目している節のデータとが等しければポインタを関数として返す */
|
|
116
|
+
|
|
117
|
+
printf("探索した値の番地です>>%d\n",p);
|
|
118
|
+
|
|
119
|
+
return p;
|
|
120
|
+
|
|
121
|
+
}else{
|
|
122
|
+
|
|
123
|
+
if (key < p->data)
|
|
124
|
+
|
|
125
|
+
/* キーの方が小さければ左部分木に進む */
|
|
126
|
+
|
|
127
|
+
p = p->left;
|
|
128
|
+
|
|
129
|
+
else
|
|
130
|
+
|
|
131
|
+
/* キーの方が大きければ右部分木に進む*/
|
|
132
|
+
|
|
133
|
+
p = p->right;
|
|
134
|
+
|
|
135
|
+
}
|
|
136
|
+
|
|
137
|
+
}
|
|
138
|
+
|
|
139
|
+
/* ループを抜け出たということは見付からなかったというと
|
|
140
|
+
|
|
141
|
+
NULL返して失敗したことを知らせる */
|
|
142
|
+
|
|
143
|
+
printf("NotExist\n");
|
|
144
|
+
|
|
145
|
+
return NULL;
|
|
146
|
+
|
|
147
|
+
}
|
|
148
|
+
|
|
149
|
+
|
|
150
|
+
|
|
151
|
+
/* 二分探索木から要素を追加する関数*/
|
|
152
|
+
|
|
153
|
+
/* 探索と同じ要領で木を辿り、辿るべき部分木がなければそこに挿入する */
|
|
154
|
+
|
|
155
|
+
/* 挿入した要素が置かれる節へのポインタを返す
|
|
156
|
+
|
|
157
|
+
すでに要素が登録されているのなら、何もしないでNULLを返す
|
|
158
|
+
|
|
159
|
+
key：挿入するデータ
|
|
160
|
+
|
|
161
|
+
NODE型へのポインターが戻り値 */
|
|
162
|
+
|
|
163
|
+
NODE *insert(int key)
|
|
164
|
+
|
|
165
|
+
{
|
|
166
|
+
|
|
167
|
+
NODE **p,*new;
|
|
168
|
+
|
|
169
|
+
/* 変数pが変数rootを指すように初期化する */
|
|
170
|
+
|
|
171
|
+
p=&root;
|
|
172
|
+
|
|
173
|
+
/* 挿入すべき場所が見つかるまで繰り返す */
|
|
174
|
+
|
|
175
|
+
while (*p != NULL) {
|
|
176
|
+
|
|
177
|
+
/* キーと注目している節のデータが等しいか比較 */
|
|
178
|
+
|
|
179
|
+
if (key == (*p)->data){
|
|
180
|
+
|
|
181
|
+
/* すでに登録されている */
|
|
182
|
+
|
|
183
|
+
printf("AlreadyExsits\n");
|
|
184
|
+
|
|
185
|
+
return NULL;
|
|
186
|
+
|
|
187
|
+
}else{
|
|
188
|
+
|
|
189
|
+
if (key < (*p)->data)
|
|
190
|
+
|
|
191
|
+
/* キーの方が小さければ左部分木に進む */
|
|
192
|
+
|
|
193
|
+
p =&(*p)->left;
|
|
194
|
+
|
|
195
|
+
else
|
|
196
|
+
|
|
197
|
+
/* キーの方が大きければ右部分木に進む */
|
|
198
|
+
|
|
199
|
+
p =&(*p)->right;
|
|
200
|
+
|
|
201
|
+
}
|
|
202
|
+
|
|
203
|
+
}
|
|
204
|
+
|
|
205
|
+
/* 挿入されるべき場所が見つかったら */
|
|
206
|
+
|
|
207
|
+
/* 挿入される節をつくる */
|
|
208
|
+
|
|
209
|
+
|
|
210
|
+
|
|
211
|
+
/* strct型のメモリを確保した分だけnewに入れる。もしNULLだったらエラー */
|
|
212
|
+
|
|
213
|
+
if((new=malloc(sizeof(NODE)))==NULL)
|
|
214
|
+
|
|
215
|
+
fatal_error("out of memory!!");
|
|
216
|
+
|
|
217
|
+
/* 新しい節には子がないのでNULLにしておく */
|
|
218
|
+
|
|
219
|
+
new->left =NULL;
|
|
220
|
+
|
|
221
|
+
new->right=NULL;
|
|
222
|
+
|
|
223
|
+
/* 要素の値をセットする */
|
|
224
|
+
|
|
225
|
+
new->data=key;
|
|
226
|
+
|
|
227
|
+
/* 正しい場所に挿入する */
|
|
228
|
+
|
|
229
|
+
/* ポインタpは挿入される節へのポインタが入っている場所を指している */
|
|
230
|
+
|
|
231
|
+
*p=new;
|
|
232
|
+
|
|
233
|
+
return new;
|
|
234
|
+
|
|
235
|
+
}
|
|
236
|
+
|
|
237
|
+
|
|
238
|
+
|
|
239
|
+
/* 二分探索木から要素を削除する関数 */
|
|
240
|
+
|
|
241
|
+
/* 削除に成功したら1、要素が存在しなければ0を返す
|
|
242
|
+
|
|
243
|
+
key：削除するデータ */
|
|
244
|
+
|
|
245
|
+
int delete(int key)
|
|
246
|
+
|
|
247
|
+
{
|
|
248
|
+
|
|
249
|
+
/* 親へのポインタを使う */
|
|
250
|
+
|
|
251
|
+
NODE **p,*x;
|
|
252
|
+
|
|
253
|
+
/* 変数pが変数rootを指すように初期化する */
|
|
254
|
+
|
|
255
|
+
p=&root;
|
|
256
|
+
|
|
257
|
+
/* 削除対象となる要素を探す */
|
|
258
|
+
|
|
259
|
+
while (*p != NULL) {
|
|
260
|
+
|
|
261
|
+
/* 見つかった
|
|
262
|
+
|
|
263
|
+
変数pは削除される節の親のメンバleft,right
|
|
264
|
+
|
|
265
|
+
変数xは削除される節そのものを指している */
|
|
266
|
+
|
|
267
|
+
if (key == (*p)->data){
|
|
268
|
+
|
|
269
|
+
x=*p;
|
|
270
|
+
|
|
271
|
+
/* 1つも子を持っていない、葉である場合 */
|
|
272
|
+
|
|
273
|
+
if(x->left==NULL && x->right==NULL){
|
|
274
|
+
|
|
275
|
+
*p=NULL;
|
|
276
|
+
|
|
277
|
+
/* 右の子のみをもつ */
|
|
278
|
+
|
|
279
|
+
if(x->left==NULL){
|
|
280
|
+
|
|
281
|
+
*p=x->right;
|
|
282
|
+
|
|
283
|
+
/* 左の子のみをもつ */
|
|
284
|
+
|
|
285
|
+
}else if(x->right==NULL){
|
|
286
|
+
|
|
287
|
+
*p=x->left;
|
|
288
|
+
|
|
289
|
+
/* 左右2つの子を持つ */
|
|
290
|
+
|
|
291
|
+
}else{
|
|
292
|
+
|
|
293
|
+
/* 部分木から最小の要素を取り去る */
|
|
294
|
+
|
|
295
|
+
*p=deletemin(&x->right);
|
|
296
|
+
|
|
297
|
+
(*p)->right=x->right;
|
|
298
|
+
|
|
299
|
+
(*p)->left=x->left;
|
|
300
|
+
|
|
301
|
+
}
|
|
302
|
+
|
|
303
|
+
/* 取り除いた節を解放させる */
|
|
304
|
+
|
|
305
|
+
free(x);
|
|
306
|
+
|
|
307
|
+
printf("Done\n");
|
|
308
|
+
|
|
309
|
+
return 1;
|
|
310
|
+
|
|
311
|
+
|
|
312
|
+
|
|
313
|
+
}else if(key < (*p)->data)
|
|
314
|
+
|
|
315
|
+
/* 左部分木に進む */
|
|
316
|
+
|
|
317
|
+
p=&(*p)->left;
|
|
318
|
+
|
|
319
|
+
else
|
|
320
|
+
|
|
321
|
+
/* 右部分木に進む */
|
|
322
|
+
|
|
323
|
+
p=&(*p)->right;
|
|
324
|
+
|
|
325
|
+
}
|
|
326
|
+
|
|
327
|
+
}
|
|
328
|
+
|
|
329
|
+
/* 削除対象が見つからなかった */
|
|
330
|
+
|
|
331
|
+
printf("NotExist\n");
|
|
332
|
+
|
|
333
|
+
return 0;
|
|
334
|
+
|
|
335
|
+
}
|
|
336
|
+
|
|
337
|
+
|
|
338
|
+
|
|
339
|
+
|
|
340
|
+
|
|
341
|
+
|
|
342
|
+
|
|
343
|
+
/* 二分木を行きがけ順でなぞる */
|
|
344
|
+
|
|
345
|
+
void preorder(NODE *p)
|
|
346
|
+
|
|
347
|
+
{
|
|
348
|
+
|
|
349
|
+
/* 木が空なら何もしない */
|
|
350
|
+
|
|
351
|
+
if(p==NULL)
|
|
352
|
+
|
|
353
|
+
return;
|
|
354
|
+
|
|
355
|
+
else{
|
|
356
|
+
|
|
357
|
+
printf("%d",p->data); /* 自身の値を出力 */
|
|
358
|
+
|
|
359
|
+
preorder(p->left); /* 左ノードへ移動 */
|
|
360
|
+
|
|
361
|
+
preorder(p->right); /* 右ノードへ移動 */
|
|
362
|
+
|
|
363
|
+
}
|
|
364
|
+
|
|
365
|
+
}
|
|
366
|
+
|
|
367
|
+
|
|
368
|
+
|
|
369
|
+
/* 二分木を通りがけ順でなぞる */
|
|
370
|
+
|
|
371
|
+
void inorder(NODE *p)
|
|
372
|
+
|
|
373
|
+
{
|
|
374
|
+
|
|
375
|
+
/* 木が空なら何もしない */
|
|
376
|
+
|
|
377
|
+
if(p==NULL)
|
|
378
|
+
|
|
379
|
+
return;
|
|
380
|
+
|
|
381
|
+
else{
|
|
382
|
+
|
|
383
|
+
}
|
|
384
|
+
|
|
385
|
+
}
|
|
386
|
+
|
|
387
|
+
|
|
388
|
+
|
|
389
|
+
/* 二分木を帰りがけ順でなぞる */
|
|
390
|
+
|
|
391
|
+
void postorder(NODE *p)
|
|
392
|
+
|
|
393
|
+
{
|
|
394
|
+
|
|
395
|
+
/* 木が空なら何もしない */
|
|
396
|
+
|
|
397
|
+
if(p==NULL)
|
|
398
|
+
|
|
399
|
+
return;
|
|
400
|
+
|
|
401
|
+
else{
|
|
402
|
+
|
|
403
|
+
postorder(p->left); /* 左ノードへ移動 */
|
|
404
|
+
|
|
405
|
+
postorder(p->right); /* 右ノードへ移動 */
|
|
406
|
+
|
|
407
|
+
printf("%d",p->data); /* 自身の値を出力 */
|
|
408
|
+
|
|
409
|
+
}
|
|
410
|
+
|
|
411
|
+
}
|
|
412
|
+
|
|
413
|
+
|
|
414
|
+
|
|
415
|
+
int main(void)
|
|
416
|
+
|
|
417
|
+
{
|
|
418
|
+
|
|
419
|
+
int a,key1,key2;
|
|
420
|
+
|
|
421
|
+
int mn=0;
|
|
422
|
+
|
|
423
|
+
|
|
424
|
+
|
|
425
|
+
printf("二分探索木をします\n");
|
|
426
|
+
|
|
427
|
+
do{
|
|
428
|
+
|
|
429
|
+
printf("メニューを選んでください\n\n1=追加\n2=行きがけ順\n3=通りがけ順\n4=帰りがけ順\n5=指定した値の番地\n6=削除\n9=終了\n");
|
|
430
|
+
|
|
431
|
+
scanf("%d",&mn);
|
|
432
|
+
|
|
433
|
+
switch(mn){
|
|
434
|
+
|
|
435
|
+
|
|
436
|
+
|
|
437
|
+
case 1:
|
|
438
|
+
|
|
439
|
+
printf("追加する数字を入力してください\n");
|
|
440
|
+
|
|
441
|
+
scanf("%d",&a);
|
|
442
|
+
|
|
443
|
+
insert(a);
|
|
444
|
+
|
|
445
|
+
break;
|
|
446
|
+
|
|
447
|
+
|
|
448
|
+
|
|
449
|
+
case 2:
|
|
450
|
+
|
|
451
|
+
printf("行きがけ順です\n");
|
|
452
|
+
|
|
453
|
+
preorder(root);
|
|
454
|
+
|
|
455
|
+
break;
|
|
456
|
+
|
|
457
|
+
|
|
458
|
+
|
|
459
|
+
case 3:
|
|
460
|
+
|
|
461
|
+
printf("通りがけ順です\n");
|
|
462
|
+
|
|
463
|
+
inorder(root);
|
|
464
|
+
|
|
465
|
+
break;
|
|
466
|
+
|
|
467
|
+
|
|
468
|
+
|
|
469
|
+
case 4:
|
|
470
|
+
|
|
471
|
+
printf("帰りがけ順です\n");
|
|
472
|
+
|
|
473
|
+
postorder(root);
|
|
474
|
+
|
|
475
|
+
break;
|
|
476
|
+
|
|
477
|
+
|
|
478
|
+
|
|
479
|
+
case 5:
|
|
480
|
+
|
|
481
|
+
printf("指定した値の番地を出力します\n");
|
|
482
|
+
|
|
483
|
+
scanf("%d",&key1);
|
|
484
|
+
|
|
485
|
+
search(key1);
|
|
486
|
+
|
|
487
|
+
break;
|
|
488
|
+
|
|
489
|
+
|
|
490
|
+
|
|
491
|
+
case 6:
|
|
492
|
+
|
|
493
|
+
printf("指定した値を削除します\n");
|
|
494
|
+
|
|
495
|
+
scanf("%d",&key2);
|
|
496
|
+
|
|
497
|
+
delete(key2);
|
|
498
|
+
|
|
499
|
+
break;
|
|
500
|
+
|
|
501
|
+
|
|
502
|
+
|
|
503
|
+
case 9:
|
|
504
|
+
|
|
505
|
+
printf("終了します\n");
|
|
506
|
+
|
|
507
|
+
break;
|
|
508
|
+
|
|
509
|
+
|
|
510
|
+
|
|
511
|
+
default:
|
|
512
|
+
|
|
513
|
+
printf("エラー：メニューの中の数字を入力してください\n");
|
|
514
|
+
|
|
515
|
+
}
|
|
516
|
+
|
|
517
|
+
}while (mn !=9);
|
|
518
|
+
|
|
519
|
+
|
|
520
|
+
|
|
521
|
+
kaihou();
|
|
522
|
+
|
|
523
|
+
return 0;
|
|
524
|
+
|
|
525
|
+
}
|
|
526
|
+
|
|
527
|
+
``
|
|
528
|
+
|
|
529
|
+
```### 前提・実現したいこと``````
|
|
530
|
+
|
|
531
|
+
二分探索木のプログラムを実装したいです
|
|
532
|
+
|
|
533
|
+
仕様は
|
|
534
|
+
|
|
535
|
+
数字を入力して
|
|
536
|
+
|
|
537
|
+
1=追加
|
|
538
|
+
|
|
539
|
+
2=行きがけ順で表示
|
|
540
|
+
|
|
541
|
+
3=通りがけ順で表示
|
|
542
|
+
|
|
543
|
+
4=帰りがけ順で表示
|
|
544
|
+
|
|
545
|
+
5=指定した値の番地で表示
|
|
546
|
+
|
|
547
|
+
6=削除
|
|
548
|
+
|
|
549
|
+
9=終了
|
|
550
|
+
|
|
551
|
+
ができるようにしたいです
|
|
552
|
+
|
|
553
|
+
アドバイスお願いいたします！！
|
|
554
|
+
|
|
555
|
+
|
|
556
|
+
|
|
557
|
+
### 発生している問題・エラーメッセージ
|
|
558
|
+
|
|
559
|
+
|
|
560
|
+
|
|
561
|
+
「34行目」で記述エラーを発見しました。
|
|
562
|
+
|
|
563
|
+
「identifier」を付け忘れています。
|
|
564
|
+
|
|
565
|
+
と出てしまいます
|
|
566
|
+
|
|
567
|
+
```
|
|
568
|
+
|
|
569
|
+
|
|
570
|
+
|
|
571
|
+
### 該当のソースコード
|
|
572
|
+
|
|
1
573
|
``````ここに言語を入力
|
|
2
574
|
|
|
575
|
+
ここに言語を入力
|
|
576
|
+
|
|
577
|
+
```
|
|
578
|
+
|
|
3
579
|
コード
|
|
4
580
|
|
|
5
|
-
`#include <stdio.h>
|
|
6
|
-
|
|
7
|
-
#include <stdlib.h>
|
|
8
|
-
|
|
9
|
-
|
|
10
|
-
|
|
11
|
-
/* 木の節の定義 */
|
|
12
|
-
|
|
13
|
-
typedef struct node{
|
|
14
|
-
|
|
15
|
-
int data; /* 探索のキーになるデータ型 */
|
|
16
|
-
|
|
17
|
-
struct node *left; /* 左の子 */
|
|
18
|
-
|
|
19
|
-
struct node *right; /* 右の子 */
|
|
20
|
-
|
|
21
|
-
|
|
581
|
+
```
|
|
22
|
-
|
|
23
|
-
|
|
582
|
+
|
|
24
|
-
|
|
25
|
-
|
|
26
|
-
|
|
27
|
-
|
|
583
|
+
|
|
28
|
-
|
|
29
|
-
|
|
584
|
+
|
|
30
|
-
|
|
31
|
-
|
|
585
|
+
|
|
32
|
-
|
|
33
|
-
|
|
586
|
+
|
|
34
|
-
|
|
35
|
-
|
|
36
|
-
|
|
37
|
-
|
|
587
|
+
|
|
38
|
-
|
|
39
|
-
|
|
588
|
+
|
|
40
|
-
|
|
41
|
-
|
|
589
|
+
|
|
42
|
-
|
|
43
|
-
|
|
590
|
+
|
|
44
|
-
|
|
45
|
-
/* fprintf関数を使ってstderrで標準エラーを出力する*/
|
|
46
|
-
|
|
47
|
-
fprintf(stderr,"%s", s);
|
|
48
|
-
|
|
49
|
-
exit(1); /* 異常終了 */
|
|
50
|
-
|
|
51
|
-
}
|
|
52
|
-
|
|
53
|
-
|
|
54
|
-
|
|
55
|
-
/* 二分探索木から最小の要素を削除する関数 */
|
|
56
|
-
|
|
57
|
-
/* 削除した節へのポインタを返す
|
|
58
|
-
|
|
59
|
-
p:二分探索木へのポインタへのポインタ
|
|
60
|
-
|
|
61
|
-
(つまり＊pが木へのポインタとなる)
|
|
62
|
-
|
|
63
|
-
NODE型へのポインターが戻り値 */
|
|
64
|
-
|
|
65
|
-
NODE *deletemin(NODE **p)
|
|
66
|
-
|
|
67
|
-
{
|
|
68
|
-
|
|
69
|
-
|
|
591
|
+
### 悩んでいること
|
|
70
|
-
|
|
71
|
-
|
|
72
|
-
|
|
73
|
-
|
|
592
|
+
|
|
74
|
-
|
|
75
|
-
p=&(*p)->left;
|
|
76
|
-
|
|
77
|
-
|
|
593
|
+
① まず、
|
|
78
|
-
|
|
79
|
-
*p=(*p)->right;
|
|
80
|
-
|
|
81
|
-
return x;
|
|
82
|
-
|
|
83
|
-
}
|
|
84
|
-
|
|
85
|
-
|
|
86
|
-
|
|
87
|
-
/* 二分探索木を探索する関数 */
|
|
88
|
-
|
|
89
|
-
/* パラメータkeyを受け取ってポインタを返す関数として定義
|
|
90
|
-
|
|
91
|
-
key：探索すべきキーの値
|
|
92
|
-
|
|
93
|
-
探索に成功した場合そのデータの節へのポインタを返す
|
|
94
|
-
|
|
95
|
-
NODE型へのポインターが戻り値 */
|
|
96
594
|
|
|
97
595
|
NODE *search(int key)
|
|
98
596
|
|
|
99
|
-
|
|
100
|
-
|
|
101
|
-
|
|
102
|
-
|
|
103
|
-
|
|
104
|
-
|
|
105
|
-
|
|
106
|
-
|
|
107
|
-
|
|
108
|
-
|
|
109
|
-
|
|
110
|
-
|
|
111
|
-
|
|
112
|
-
|
|
113
|
-
|
|
114
|
-
|
|
115
|
-
|
|
116
|
-
|
|
117
|
-
|
|
118
|
-
|
|
119
|
-
|
|
120
|
-
|
|
121
|
-
|
|
122
|
-
|
|
123
|
-
|
|
124
|
-
|
|
125
|
-
|
|
126
|
-
|
|
127
|
-
|
|
128
|
-
|
|
129
|
-
else
|
|
130
|
-
|
|
131
|
-
/* キーの方が大きければ右部分木に進む*/
|
|
132
|
-
|
|
133
|
-
p = p->right;
|
|
134
|
-
|
|
135
|
-
}
|
|
136
|
-
|
|
137
|
-
}
|
|
138
|
-
|
|
139
|
-
/* ループを抜け出たということは見付からなかったというと
|
|
140
|
-
|
|
141
|
-
NULL返して失敗したことを知らせる */
|
|
142
|
-
|
|
143
|
-
printf("NotExist\n");
|
|
144
|
-
|
|
145
|
-
return NULL;
|
|
146
|
-
|
|
147
|
-
}
|
|
148
|
-
|
|
149
|
-
|
|
150
|
-
|
|
151
|
-
/* 二分探索木から要素を追加する関数*/
|
|
152
|
-
|
|
153
|
-
/* 探索と同じ要領で木を辿り、辿るべき部分木がなければそこに挿入する */
|
|
154
|
-
|
|
155
|
-
/* 挿入した要素が置かれる節へのポインタを返す
|
|
156
|
-
|
|
157
|
-
すでに要素が登録されているのなら、何もしないでNULLを返す
|
|
158
|
-
|
|
159
|
-
key：挿入するデータ
|
|
160
|
-
|
|
161
|
-
NODE型へのポインターが戻り値 */
|
|
162
|
-
|
|
163
|
-
NODE *insert(int key)
|
|
164
|
-
|
|
165
|
-
{
|
|
166
|
-
|
|
167
|
-
NODE **p,*new;
|
|
168
|
-
|
|
169
|
-
/* 変数pが変数rootを指すように初期化する */
|
|
170
|
-
|
|
171
|
-
p=&root;
|
|
172
|
-
|
|
173
|
-
/* 挿入すべき場所が見つかるまで繰り返す */
|
|
174
|
-
|
|
175
|
-
while (*p != NULL) {
|
|
176
|
-
|
|
177
|
-
/* キーと注目している節のデータが等しいか比較 */
|
|
178
|
-
|
|
179
|
-
if (key == (*p)->data){
|
|
180
|
-
|
|
181
|
-
/* すでに登録されている */
|
|
182
|
-
|
|
183
|
-
printf("AlreadyExsits\n");
|
|
184
|
-
|
|
185
|
-
return NULL;
|
|
186
|
-
|
|
187
|
-
}else{
|
|
188
|
-
|
|
189
|
-
if (key < (*p)->data)
|
|
190
|
-
|
|
191
|
-
/* キーの方が小さければ左部分木に進む */
|
|
192
|
-
|
|
193
|
-
p =&(*p)->left;
|
|
194
|
-
|
|
195
|
-
else
|
|
196
|
-
|
|
197
|
-
/* キーの方が大きければ右部分木に進む */
|
|
198
|
-
|
|
199
|
-
p =&(*p)->right;
|
|
200
|
-
|
|
201
|
-
}
|
|
202
|
-
|
|
203
|
-
}
|
|
204
|
-
|
|
205
|
-
/* 挿入されるべき場所が見つかったら */
|
|
206
|
-
|
|
207
|
-
/* 挿入される節をつくる */
|
|
208
|
-
|
|
209
|
-
|
|
210
|
-
|
|
211
|
-
/* strct型のメモリを確保した分だけnewに入れる。もしNULLだったらエラー */
|
|
212
|
-
|
|
213
|
-
if((new=malloc(sizeof(NODE)))==NULL)
|
|
214
|
-
|
|
215
|
-
fatal_error("out of memory!!");
|
|
216
|
-
|
|
217
|
-
/* 新しい節には子がないのでNULLにしておく */
|
|
218
|
-
|
|
219
|
-
new->left =NULL;
|
|
220
|
-
|
|
221
|
-
new->right=NULL;
|
|
222
|
-
|
|
223
|
-
/* 要素の値をセットする */
|
|
224
|
-
|
|
225
|
-
new->data=key;
|
|
226
|
-
|
|
227
|
-
/* 正しい場所に挿入する */
|
|
228
|
-
|
|
229
|
-
/* ポインタpは挿入される節へのポインタが入っている場所を指している */
|
|
230
|
-
|
|
231
|
-
*p=new;
|
|
232
|
-
|
|
233
|
-
return new;
|
|
234
|
-
|
|
235
|
-
}
|
|
236
|
-
|
|
237
|
-
|
|
238
|
-
|
|
239
|
-
/* 二分探索木から要素を削除する関数 */
|
|
240
|
-
|
|
241
|
-
/* 削除に成功したら1、要素が存在しなければ0を返す
|
|
242
|
-
|
|
243
|
-
key：削除するデータ */
|
|
597
|
+
教科書に書いてあったこの宣言の仕方がよく分かりません
|
|
598
|
+
|
|
599
|
+
|
|
600
|
+
|
|
601
|
+
型名なしの関数の宣言の仕方を調べると一つだけ解説しているサイトが見つかり、自動的にint型になると書 いてあったのですが正しいのでしょうか？
|
|
602
|
+
|
|
603
|
+
|
|
604
|
+
|
|
605
|
+
引数があり、戻り値がある場合はvoid型ではない、
|
|
606
|
+
|
|
607
|
+
引数があり、戻り値がない場合はvoid型、
|
|
608
|
+
|
|
609
|
+
引数がなし、戻り値がある場合もvoid型、
|
|
610
|
+
|
|
611
|
+
引数がなし、戻り値がない場合もvoid型
|
|
612
|
+
|
|
613
|
+
と学びました
|
|
614
|
+
|
|
615
|
+
|
|
616
|
+
|
|
617
|
+
preorder(NODE *p)
|
|
618
|
+
|
|
619
|
+
postorder(NODE *p)
|
|
620
|
+
|
|
621
|
+
inorder(NODE *p)
|
|
622
|
+
|
|
623
|
+
これらの関数は引数があり、戻り値がない場合なのでvoid型、
|
|
624
|
+
|
|
625
|
+
|
|
244
626
|
|
|
245
627
|
int delete(int key)
|
|
246
628
|
|
|
247
|
-
{
|
|
248
|
-
|
|
249
|
-
/* 親へのポインタを使う */
|
|
250
|
-
|
|
251
|
-
NODE **p,*x;
|
|
252
|
-
|
|
253
|
-
/* 変数pが変数rootを指すように初期化する */
|
|
254
|
-
|
|
255
|
-
p=&root;
|
|
256
|
-
|
|
257
|
-
/* 削除対象となる要素を探す */
|
|
258
|
-
|
|
259
|
-
while (*p != NULL) {
|
|
260
|
-
|
|
261
|
-
/* 見つかった
|
|
262
|
-
|
|
263
|
-
変数pは削除される節の親のメンバleft,right
|
|
264
|
-
|
|
265
|
-
変数xは削除される節そのものを指している */
|
|
266
|
-
|
|
267
|
-
if (key == (*p)->data){
|
|
268
|
-
|
|
269
|
-
x=*p;
|
|
270
|
-
|
|
271
|
-
/* 1つも子を持っていない、葉である場合 */
|
|
272
|
-
|
|
273
|
-
if(x->left==NULL && x->right==NULL){
|
|
274
|
-
|
|
275
|
-
*p=NULL;
|
|
276
|
-
|
|
277
|
-
/* 右の子のみをもつ */
|
|
278
|
-
|
|
279
|
-
if(x->left==NULL){ //ここからif文の書き方変えました
|
|
280
|
-
|
|
281
|
-
*p=x->right;
|
|
282
|
-
|
|
283
|
-
/* 左の子のみをもつ */
|
|
284
|
-
|
|
285
|
-
}else if(x->right==NULL){
|
|
286
|
-
|
|
287
|
-
*p=x->left;
|
|
288
|
-
|
|
289
|
-
/* 左右2つの子を持つ */
|
|
290
|
-
|
|
291
|
-
}else{
|
|
292
|
-
|
|
293
|
-
/* 部分木から最小の要素を取り去る */
|
|
294
|
-
|
|
295
|
-
*p=deletemin(&x->right);
|
|
296
|
-
|
|
297
|
-
(*p)->right=x->right;
|
|
298
|
-
|
|
299
|
-
(*p)->left=x->left;
|
|
300
|
-
|
|
301
|
-
}
|
|
302
|
-
|
|
303
|
-
/* 取り除いた節を解放させる */
|
|
304
|
-
|
|
305
|
-
free(x);
|
|
306
|
-
|
|
307
|
-
printf("Done\n");
|
|
308
|
-
|
|
309
|
-
return 1;
|
|
310
|
-
|
|
311
|
-
|
|
312
|
-
|
|
313
|
-
}else if(key < (*p)->data)
|
|
314
|
-
|
|
315
|
-
/* 左部分木に進む */
|
|
316
|
-
|
|
317
|
-
p=&(*p)->left;
|
|
318
|
-
|
|
319
|
-
else
|
|
320
|
-
|
|
321
|
-
/* 右部分木に進む */
|
|
322
|
-
|
|
323
|
-
p=&(*p)->right;
|
|
324
|
-
|
|
325
|
-
}
|
|
326
|
-
|
|
327
|
-
}
|
|
328
|
-
|
|
329
|
-
/* 削除対象が見つからなかった */
|
|
330
|
-
|
|
331
|
-
printf("NotExist\n");
|
|
332
|
-
|
|
333
|
-
return 0;
|
|
334
|
-
|
|
335
|
-
}
|
|
336
|
-
|
|
337
|
-
|
|
338
|
-
|
|
339
|
-
|
|
340
|
-
|
|
341
|
-
|
|
342
|
-
|
|
343
|
-
/* 二分木を行きがけ順でなぞる */
|
|
344
|
-
|
|
345
|
-
void preorder(NODE *p)
|
|
346
|
-
|
|
347
|
-
{
|
|
348
|
-
|
|
349
|
-
/* 木が空なら何もしない */
|
|
350
|
-
|
|
351
|
-
if(p==NULL)
|
|
352
|
-
|
|
353
|
-
return;
|
|
354
|
-
|
|
355
|
-
else{
|
|
356
|
-
|
|
357
|
-
printf("%d",p->data); /* 自身の値を出力 */
|
|
358
|
-
|
|
359
|
-
preorder(p->left); /* 左ノードへ移動 */
|
|
360
|
-
|
|
361
|
-
preorder(p->right); /* 右ノードへ移動 */
|
|
362
|
-
|
|
363
|
-
}
|
|
364
|
-
|
|
365
|
-
}
|
|
366
|
-
|
|
367
|
-
|
|
368
|
-
|
|
369
|
-
/* 二分木を通りがけ順でなぞる */
|
|
370
|
-
|
|
371
|
-
/* 全要素を昇順に表示する関数
|
|
372
|
-
|
|
373
|
-
二分探索木の全要素を小→大の順で表示する */
|
|
374
|
-
|
|
375
|
-
/* 全体の流れ
|
|
376
|
-
|
|
377
|
-
ある要素の左枝先を全部調べ終えたら、自身の値を出力し、
|
|
378
|
-
|
|
379
|
-
次にその要素の右枝先の要素を全部調べる
|
|
380
|
-
|
|
381
|
-
左枝を調べる
|
|
382
|
-
|
|
383
|
-
調べ終えたら戻ってくる
|
|
384
|
-
|
|
385
|
-
値を出力する
|
|
386
|
-
|
|
387
|
-
右枝を調べる
|
|
388
|
-
|
|
389
|
-
調べ終えたら戻ってくる
|
|
390
|
-
|
|
391
|
-
関数を終了して、自身を呼び出した関数の元へと戻る */
|
|
392
|
-
|
|
393
|
-
void inorder(NODE *p)
|
|
394
|
-
|
|
395
|
-
{
|
|
396
|
-
|
|
397
|
-
/* 木が空なら何もしない */
|
|
398
|
-
|
|
399
|
-
if(p==NULL)
|
|
400
|
-
|
|
401
|
-
return;
|
|
402
|
-
|
|
403
|
-
else{
|
|
404
|
-
|
|
405
|
-
/* 引数に左へのポインタを渡すことで、再帰を繰り返して延々と左枝へ移動し
|
|
406
|
-
|
|
407
|
-
一番左、一番小さい値にたどり着く
|
|
408
|
-
|
|
409
|
-
子ノードはないため、引数の値はNULLに当たって戻ってくる
|
|
410
|
-
|
|
411
|
-
一番下位の要素なので、左枝と同様に右枝もない。
|
|
412
|
-
|
|
413
|
-
なので終点である NULL に行き当たり、また return で戻ってくる。
|
|
414
|
-
|
|
415
|
-
そして「一番左を操作する関数」は処理を終える。
|
|
416
|
-
|
|
417
|
-
|
|
629
|
+
この関数も引数があり、戻り値がない場合なのでvoid型だと思われるのですがなぜint型なのでしょうか
|
|
418
|
-
|
|
419
|
-
|
|
630
|
+
|
|
420
|
-
|
|
421
|
-
|
|
631
|
+
|
|
422
|
-
|
|
423
|
-
inorder(p->right); /* 右ノードへ移動 */
|
|
424
|
-
|
|
425
|
-
}
|
|
426
|
-
|
|
427
|
-
/* 関数を終了して、自身を呼び出した関数のもとへ戻る */
|
|
428
|
-
|
|
429
|
-
}
|
|
430
|
-
|
|
431
|
-
|
|
432
|
-
|
|
433
|
-
/* 二分木を帰りがけ順でなぞる */
|
|
434
|
-
|
|
435
|
-
void postorder(NODE *p)
|
|
436
|
-
|
|
437
|
-
{
|
|
438
|
-
|
|
439
|
-
/* 木が空なら何もしない */
|
|
440
|
-
|
|
441
|
-
if(p==NULL)
|
|
442
|
-
|
|
443
|
-
return;
|
|
444
|
-
|
|
445
|
-
else{
|
|
446
|
-
|
|
447
|
-
postorder(p->left); /* 左ノードへ移動 */
|
|
448
|
-
|
|
449
|
-
postorder(p->right); /* 右ノードへ移動 */
|
|
450
|
-
|
|
451
|
-
printf("%d",p->data); /* 自身の値を出力 */
|
|
452
|
-
|
|
453
|
-
}
|
|
454
|
-
|
|
455
|
-
}
|
|
456
|
-
|
|
457
|
-
|
|
458
|
-
|
|
459
|
-
|
|
460
|
-
|
|
461
|
-
int main(void)
|
|
462
|
-
|
|
463
|
-
{
|
|
464
|
-
|
|
465
|
-
int a,key1,key2;
|
|
466
|
-
|
|
467
|
-
int mn=0;
|
|
468
|
-
|
|
469
|
-
|
|
470
|
-
|
|
471
|
-
printf("二分探索木をします\n");
|
|
472
|
-
|
|
473
|
-
do{
|
|
474
|
-
|
|
475
|
-
printf("メニューを選んでください\n\n1=追加\n2=行きがけ順\n3=通りがけ順\n4=帰りがけ順\n5=指定した値の番地\n6=削除\n9=終了\n");
|
|
476
|
-
|
|
477
|
-
scanf("%d",&mn);
|
|
478
|
-
|
|
479
|
-
switch(mn){
|
|
480
|
-
|
|
481
|
-
|
|
482
|
-
|
|
483
|
-
|
|
484
|
-
|
|
485
|
-
case 1:
|
|
486
|
-
|
|
487
|
-
printf("追加する数字を入力してください\n");
|
|
488
|
-
|
|
489
|
-
scanf("%d",&a);
|
|
490
|
-
|
|
491
|
-
insert(a);
|
|
492
|
-
|
|
493
|
-
break;
|
|
494
|
-
|
|
495
|
-
|
|
496
|
-
|
|
497
|
-
case 2:
|
|
498
|
-
|
|
499
|
-
printf("行きがけ順です\n");
|
|
500
|
-
|
|
501
|
-
preorder(root);
|
|
502
|
-
|
|
503
|
-
break;
|
|
504
|
-
|
|
505
|
-
|
|
506
|
-
|
|
507
|
-
case 3:
|
|
508
|
-
|
|
509
|
-
printf("通りがけ順です\n");
|
|
510
|
-
|
|
511
|
-
inorder(root);
|
|
512
|
-
|
|
513
|
-
break;
|
|
514
|
-
|
|
515
|
-
|
|
516
|
-
|
|
517
|
-
case 4:
|
|
518
|
-
|
|
519
|
-
printf("帰りがけ順です\n");
|
|
520
|
-
|
|
521
|
-
postorder(root);
|
|
522
|
-
|
|
523
|
-
break;
|
|
524
|
-
|
|
525
|
-
|
|
526
|
-
|
|
527
|
-
case 5:
|
|
528
|
-
|
|
529
|
-
printf("指定した値の番地を出力します\n");
|
|
530
|
-
|
|
531
|
-
scanf("%d",&key1);
|
|
532
|
-
|
|
533
|
-
search(key1);
|
|
534
|
-
|
|
535
|
-
break;
|
|
536
|
-
|
|
537
|
-
|
|
538
|
-
|
|
539
|
-
case 6:
|
|
540
|
-
|
|
541
|
-
printf("指定した値を削除します\n");
|
|
542
|
-
|
|
543
|
-
scanf("%d",&key2);
|
|
544
|
-
|
|
545
|
-
delete(key2);
|
|
546
|
-
|
|
547
|
-
break;
|
|
548
|
-
|
|
549
|
-
|
|
550
|
-
|
|
551
|
-
case 9:
|
|
552
|
-
|
|
553
|
-
printf("終了します\n");
|
|
554
|
-
|
|
555
|
-
break;
|
|
556
|
-
|
|
557
|
-
|
|
558
|
-
|
|
559
|
-
default:
|
|
560
|
-
|
|
561
|
-
printf("エラー：メニューの中の数字を入力してください\n");
|
|
562
|
-
|
|
563
|
-
}
|
|
564
|
-
|
|
565
|
-
}while (mn !=9);
|
|
566
|
-
|
|
567
|
-
|
|
568
|
-
|
|
569
|
-
return 0;
|
|
570
|
-
|
|
571
|
-
}
|
|
572
|
-
|
|
573
|
-
``
|
|
574
|
-
|
|
575
|
-
```### 前提・実現したいこと``````
|
|
576
|
-
|
|
577
|
-
二分探索木のプログラムを実装したいです
|
|
578
|
-
|
|
579
|
-
仕様は
|
|
580
|
-
|
|
581
|
-
数字を入力して
|
|
582
|
-
|
|
583
|
-
1=追加
|
|
584
|
-
|
|
585
|
-
2=行きがけ順で表示
|
|
586
|
-
|
|
587
|
-
3=通りがけ順で表示
|
|
588
|
-
|
|
589
|
-
4=帰りがけ順で表示
|
|
590
|
-
|
|
591
|
-
5=指定した値の番地で表示
|
|
592
|
-
|
|
593
|
-
6=削除
|
|
594
|
-
|
|
595
|
-
9=終了
|
|
596
|
-
|
|
597
|
-
ができるようにしたいです
|
|
598
|
-
|
|
599
|
-
アドバイスお願いいたします！！
|
|
600
|
-
|
|
601
|
-
|
|
602
|
-
|
|
603
|
-
### 発生している問題・エラーメッセージ
|
|
604
|
-
|
|
605
|
-
|
|
606
|
-
|
|
607
|
-
「34行目」で記述エラーを発見しました。
|
|
608
|
-
|
|
609
|
-
「identifier」を付け忘れています。
|
|
610
|
-
|
|
611
|
-
と出てしまいます
|
|
612
|
-
|
|
613
|
-
```
|
|
614
|
-
|
|
615
|
-
|
|
616
|
-
|
|
617
|
-
### 該当のソースコード
|
|
618
|
-
|
|
619
|
-
``````ここに言語を入力
|
|
620
|
-
|
|
621
|
-
ここに言語を入力
|
|
622
|
-
|
|
623
|
-
```
|
|
624
|
-
|
|
625
|
-
コード
|
|
626
|
-
|
|
627
|
-
```
|
|
628
|
-
|
|
629
|
-
|
|
630
|
-
|
|
631
|
-
|
|
632
|
-
|
|
633
|
-
|
|
634
|
-
|
|
635
|
-
|
|
636
|
-
|
|
637
|
-
### 悩んでいること
|
|
638
|
-
|
|
639
|
-
① まず、
|
|
640
632
|
|
|
641
633
|
NODE *search(int key)
|
|
642
634
|
|
|
643
|
-
教科書に書いてあったこの宣言の仕方がよく分かりません
|
|
644
|
-
|
|
645
|
-
|
|
646
|
-
|
|
647
|
-
型名なしの関数の宣言の仕方を調べると一つだけ解説しているサイトが見つかり、自動的にint型になると書 いてあったのですが正しいのでしょうか？
|
|
648
|
-
|
|
649
|
-
|
|
650
|
-
|
|
651
|
-
引数があり、戻り値がある場合はvoid型ではない、
|
|
652
|
-
|
|
653
|
-
引数があり、戻り値がない場合はvoid型、
|
|
654
|
-
|
|
655
|
-
引数がなし、戻り値がある場合もvoid型、
|
|
656
|
-
|
|
657
|
-
引数がなし、戻り値がない場合もvoid型
|
|
658
|
-
|
|
659
|
-
と学びました
|
|
660
|
-
|
|
661
|
-
|
|
662
|
-
|
|
663
|
-
preorder(NODE *p)
|
|
664
|
-
|
|
665
|
-
postorder(NODE *p)
|
|
666
|
-
|
|
667
|
-
inorder(NODE *p)
|
|
668
|
-
|
|
669
|
-
これらの関数は引数があり、戻り値がない場合なのでvoid型、
|
|
670
|
-
|
|
671
|
-
|
|
672
|
-
|
|
673
|
-
int delete(int key)
|
|
674
|
-
|
|
675
|
-
この関数も引数があり、戻り値がない場合なのでvoid型だと思われるのですがなぜint型なのでしょうか
|
|
676
|
-
|
|
677
|
-
|
|
678
|
-
|
|
679
|
-
NODE *search(int key)
|
|
680
|
-
|
|
681
635
|
NODE *insert(int key)
|
|
682
636
|
|
|
683
637
|
NODE *deletemin(NODE **p)
|
9
エラーをほとんど消しました
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -1,595 +1,683 @@
|
|
|
1
|
+
``````ここに言語を入力
|
|
2
|
+
|
|
3
|
+
コード
|
|
4
|
+
|
|
5
|
+
`#include <stdio.h>
|
|
6
|
+
|
|
7
|
+
#include <stdlib.h>
|
|
8
|
+
|
|
9
|
+
|
|
10
|
+
|
|
11
|
+
/* 木の節の定義 */
|
|
12
|
+
|
|
13
|
+
typedef struct node{
|
|
14
|
+
|
|
15
|
+
int data; /* 探索のキーになるデータ型 */
|
|
16
|
+
|
|
17
|
+
struct node *left; /* 左の子 */
|
|
18
|
+
|
|
19
|
+
struct node *right; /* 右の子 */
|
|
20
|
+
|
|
21
|
+
}NODE;
|
|
22
|
+
|
|
23
|
+
/* メンバright,leftにNULLポインタがセットされているときは該当する子がいないことを表す */
|
|
24
|
+
|
|
25
|
+
|
|
26
|
+
|
|
27
|
+
/* 初期状態では二分探索木は空の状態。
|
|
28
|
+
|
|
29
|
+
グローバル変数rootが二分探索木の根へのポインタを保持しているものとする */
|
|
30
|
+
|
|
31
|
+
/* グローバル変数rootをNULLで初期化 */
|
|
32
|
+
|
|
33
|
+
NODE *root = NULL;
|
|
34
|
+
|
|
35
|
+
|
|
36
|
+
|
|
37
|
+
/* エラーメッセージをプリントしてexitする関数*/
|
|
38
|
+
|
|
39
|
+
/* ポインタ(アドレス)の先のデータを読み取り専用にする */
|
|
40
|
+
|
|
41
|
+
void fatal_error(const char *s)
|
|
42
|
+
|
|
43
|
+
{
|
|
44
|
+
|
|
45
|
+
/* fprintf関数を使ってstderrで標準エラーを出力する*/
|
|
46
|
+
|
|
47
|
+
fprintf(stderr,"%s", s);
|
|
48
|
+
|
|
49
|
+
exit(1); /* 異常終了 */
|
|
50
|
+
|
|
51
|
+
}
|
|
52
|
+
|
|
53
|
+
|
|
54
|
+
|
|
55
|
+
/* 二分探索木から最小の要素を削除する関数 */
|
|
56
|
+
|
|
57
|
+
/* 削除した節へのポインタを返す
|
|
58
|
+
|
|
59
|
+
p:二分探索木へのポインタへのポインタ
|
|
60
|
+
|
|
61
|
+
(つまり＊pが木へのポインタとなる)
|
|
62
|
+
|
|
63
|
+
NODE型へのポインターが戻り値 */
|
|
64
|
+
|
|
65
|
+
NODE *deletemin(NODE **p)
|
|
66
|
+
|
|
67
|
+
{
|
|
68
|
+
|
|
69
|
+
NODE *x;
|
|
70
|
+
|
|
71
|
+
|
|
72
|
+
|
|
73
|
+
while ((*p)->left != NULL)
|
|
74
|
+
|
|
75
|
+
p=&(*p)->left;
|
|
76
|
+
|
|
77
|
+
x=*p;
|
|
78
|
+
|
|
79
|
+
*p=(*p)->right;
|
|
80
|
+
|
|
81
|
+
return x;
|
|
82
|
+
|
|
83
|
+
}
|
|
84
|
+
|
|
85
|
+
|
|
86
|
+
|
|
87
|
+
/* 二分探索木を探索する関数 */
|
|
88
|
+
|
|
89
|
+
/* パラメータkeyを受け取ってポインタを返す関数として定義
|
|
90
|
+
|
|
91
|
+
key：探索すべきキーの値
|
|
92
|
+
|
|
93
|
+
探索に成功した場合そのデータの節へのポインタを返す
|
|
94
|
+
|
|
95
|
+
NODE型へのポインターが戻り値 */
|
|
96
|
+
|
|
97
|
+
NODE *search(int key)
|
|
98
|
+
|
|
99
|
+
{
|
|
100
|
+
|
|
101
|
+
NODE *p; /* 現在注目している節 */
|
|
102
|
+
|
|
103
|
+
p=root; /* まず根に注目する */
|
|
104
|
+
|
|
105
|
+
|
|
106
|
+
|
|
107
|
+
/* 進むべき子が存在する限り繰り返す */
|
|
108
|
+
|
|
109
|
+
while (p != NULL) {
|
|
110
|
+
|
|
111
|
+
/* キーと注目している節のデータが等しいか比較 */
|
|
112
|
+
|
|
113
|
+
if (key == p->data){
|
|
114
|
+
|
|
115
|
+
/* もしキーと注目している節のデータとが等しければポインタを関数として返す */
|
|
116
|
+
|
|
117
|
+
printf("探索した値の番地です>>%d\n",p);
|
|
118
|
+
|
|
119
|
+
return p;
|
|
120
|
+
|
|
121
|
+
}else{
|
|
122
|
+
|
|
123
|
+
if (key < p->data)
|
|
124
|
+
|
|
125
|
+
/* キーの方が小さければ左部分木に進む */
|
|
126
|
+
|
|
127
|
+
p = p->left;
|
|
128
|
+
|
|
129
|
+
else
|
|
130
|
+
|
|
131
|
+
/* キーの方が大きければ右部分木に進む*/
|
|
132
|
+
|
|
133
|
+
p = p->right;
|
|
134
|
+
|
|
135
|
+
}
|
|
136
|
+
|
|
137
|
+
}
|
|
138
|
+
|
|
139
|
+
/* ループを抜け出たということは見付からなかったというと
|
|
140
|
+
|
|
141
|
+
NULL返して失敗したことを知らせる */
|
|
142
|
+
|
|
143
|
+
printf("NotExist\n");
|
|
144
|
+
|
|
145
|
+
return NULL;
|
|
146
|
+
|
|
147
|
+
}
|
|
148
|
+
|
|
149
|
+
|
|
150
|
+
|
|
151
|
+
/* 二分探索木から要素を追加する関数*/
|
|
152
|
+
|
|
153
|
+
/* 探索と同じ要領で木を辿り、辿るべき部分木がなければそこに挿入する */
|
|
154
|
+
|
|
155
|
+
/* 挿入した要素が置かれる節へのポインタを返す
|
|
156
|
+
|
|
157
|
+
すでに要素が登録されているのなら、何もしないでNULLを返す
|
|
158
|
+
|
|
159
|
+
key：挿入するデータ
|
|
160
|
+
|
|
161
|
+
NODE型へのポインターが戻り値 */
|
|
162
|
+
|
|
163
|
+
NODE *insert(int key)
|
|
164
|
+
|
|
165
|
+
{
|
|
166
|
+
|
|
167
|
+
NODE **p,*new;
|
|
168
|
+
|
|
169
|
+
/* 変数pが変数rootを指すように初期化する */
|
|
170
|
+
|
|
171
|
+
p=&root;
|
|
172
|
+
|
|
173
|
+
/* 挿入すべき場所が見つかるまで繰り返す */
|
|
174
|
+
|
|
175
|
+
while (*p != NULL) {
|
|
176
|
+
|
|
177
|
+
/* キーと注目している節のデータが等しいか比較 */
|
|
178
|
+
|
|
179
|
+
if (key == (*p)->data){
|
|
180
|
+
|
|
181
|
+
/* すでに登録されている */
|
|
182
|
+
|
|
183
|
+
printf("AlreadyExsits\n");
|
|
184
|
+
|
|
185
|
+
return NULL;
|
|
186
|
+
|
|
187
|
+
}else{
|
|
188
|
+
|
|
189
|
+
if (key < (*p)->data)
|
|
190
|
+
|
|
191
|
+
/* キーの方が小さければ左部分木に進む */
|
|
192
|
+
|
|
193
|
+
p =&(*p)->left;
|
|
194
|
+
|
|
195
|
+
else
|
|
196
|
+
|
|
197
|
+
/* キーの方が大きければ右部分木に進む */
|
|
198
|
+
|
|
199
|
+
p =&(*p)->right;
|
|
200
|
+
|
|
201
|
+
}
|
|
202
|
+
|
|
203
|
+
}
|
|
204
|
+
|
|
205
|
+
/* 挿入されるべき場所が見つかったら */
|
|
206
|
+
|
|
207
|
+
/* 挿入される節をつくる */
|
|
208
|
+
|
|
209
|
+
|
|
210
|
+
|
|
211
|
+
/* strct型のメモリを確保した分だけnewに入れる。もしNULLだったらエラー */
|
|
212
|
+
|
|
213
|
+
if((new=malloc(sizeof(NODE)))==NULL)
|
|
214
|
+
|
|
215
|
+
fatal_error("out of memory!!");
|
|
216
|
+
|
|
217
|
+
/* 新しい節には子がないのでNULLにしておく */
|
|
218
|
+
|
|
219
|
+
new->left =NULL;
|
|
220
|
+
|
|
221
|
+
new->right=NULL;
|
|
222
|
+
|
|
223
|
+
/* 要素の値をセットする */
|
|
224
|
+
|
|
225
|
+
new->data=key;
|
|
226
|
+
|
|
227
|
+
/* 正しい場所に挿入する */
|
|
228
|
+
|
|
229
|
+
/* ポインタpは挿入される節へのポインタが入っている場所を指している */
|
|
230
|
+
|
|
231
|
+
*p=new;
|
|
232
|
+
|
|
233
|
+
return new;
|
|
234
|
+
|
|
235
|
+
}
|
|
236
|
+
|
|
237
|
+
|
|
238
|
+
|
|
239
|
+
/* 二分探索木から要素を削除する関数 */
|
|
240
|
+
|
|
241
|
+
/* 削除に成功したら1、要素が存在しなければ0を返す
|
|
242
|
+
|
|
243
|
+
key：削除するデータ */
|
|
244
|
+
|
|
245
|
+
int delete(int key)
|
|
246
|
+
|
|
247
|
+
{
|
|
248
|
+
|
|
249
|
+
/* 親へのポインタを使う */
|
|
250
|
+
|
|
251
|
+
NODE **p,*x;
|
|
252
|
+
|
|
253
|
+
/* 変数pが変数rootを指すように初期化する */
|
|
254
|
+
|
|
255
|
+
p=&root;
|
|
256
|
+
|
|
257
|
+
/* 削除対象となる要素を探す */
|
|
258
|
+
|
|
259
|
+
while (*p != NULL) {
|
|
260
|
+
|
|
261
|
+
/* 見つかった
|
|
262
|
+
|
|
263
|
+
変数pは削除される節の親のメンバleft,right
|
|
264
|
+
|
|
265
|
+
変数xは削除される節そのものを指している */
|
|
266
|
+
|
|
267
|
+
if (key == (*p)->data){
|
|
268
|
+
|
|
269
|
+
x=*p;
|
|
270
|
+
|
|
271
|
+
/* 1つも子を持っていない、葉である場合 */
|
|
272
|
+
|
|
273
|
+
if(x->left==NULL && x->right==NULL){
|
|
274
|
+
|
|
275
|
+
*p=NULL;
|
|
276
|
+
|
|
277
|
+
/* 右の子のみをもつ */
|
|
278
|
+
|
|
279
|
+
if(x->left==NULL){ //ここからif文の書き方変えました
|
|
280
|
+
|
|
281
|
+
*p=x->right;
|
|
282
|
+
|
|
283
|
+
/* 左の子のみをもつ */
|
|
284
|
+
|
|
285
|
+
}else if(x->right==NULL){
|
|
286
|
+
|
|
287
|
+
*p=x->left;
|
|
288
|
+
|
|
289
|
+
/* 左右2つの子を持つ */
|
|
290
|
+
|
|
291
|
+
}else{
|
|
292
|
+
|
|
293
|
+
/* 部分木から最小の要素を取り去る */
|
|
294
|
+
|
|
295
|
+
*p=deletemin(&x->right);
|
|
296
|
+
|
|
297
|
+
(*p)->right=x->right;
|
|
298
|
+
|
|
299
|
+
(*p)->left=x->left;
|
|
300
|
+
|
|
301
|
+
}
|
|
302
|
+
|
|
303
|
+
/* 取り除いた節を解放させる */
|
|
304
|
+
|
|
305
|
+
free(x);
|
|
306
|
+
|
|
307
|
+
printf("Done\n");
|
|
308
|
+
|
|
309
|
+
return 1;
|
|
310
|
+
|
|
311
|
+
|
|
312
|
+
|
|
313
|
+
}else if(key < (*p)->data)
|
|
314
|
+
|
|
315
|
+
/* 左部分木に進む */
|
|
316
|
+
|
|
317
|
+
p=&(*p)->left;
|
|
318
|
+
|
|
319
|
+
else
|
|
320
|
+
|
|
321
|
+
/* 右部分木に進む */
|
|
322
|
+
|
|
323
|
+
p=&(*p)->right;
|
|
324
|
+
|
|
325
|
+
}
|
|
326
|
+
|
|
327
|
+
}
|
|
328
|
+
|
|
329
|
+
/* 削除対象が見つからなかった */
|
|
330
|
+
|
|
331
|
+
printf("NotExist\n");
|
|
332
|
+
|
|
333
|
+
return 0;
|
|
334
|
+
|
|
335
|
+
}
|
|
336
|
+
|
|
337
|
+
|
|
338
|
+
|
|
339
|
+
|
|
340
|
+
|
|
341
|
+
|
|
342
|
+
|
|
343
|
+
/* 二分木を行きがけ順でなぞる */
|
|
344
|
+
|
|
345
|
+
void preorder(NODE *p)
|
|
346
|
+
|
|
347
|
+
{
|
|
348
|
+
|
|
349
|
+
/* 木が空なら何もしない */
|
|
350
|
+
|
|
351
|
+
if(p==NULL)
|
|
352
|
+
|
|
353
|
+
return;
|
|
354
|
+
|
|
355
|
+
else{
|
|
356
|
+
|
|
357
|
+
printf("%d",p->data); /* 自身の値を出力 */
|
|
358
|
+
|
|
359
|
+
preorder(p->left); /* 左ノードへ移動 */
|
|
360
|
+
|
|
361
|
+
preorder(p->right); /* 右ノードへ移動 */
|
|
362
|
+
|
|
363
|
+
}
|
|
364
|
+
|
|
365
|
+
}
|
|
366
|
+
|
|
367
|
+
|
|
368
|
+
|
|
369
|
+
/* 二分木を通りがけ順でなぞる */
|
|
370
|
+
|
|
371
|
+
/* 全要素を昇順に表示する関数
|
|
372
|
+
|
|
373
|
+
二分探索木の全要素を小→大の順で表示する */
|
|
374
|
+
|
|
375
|
+
/* 全体の流れ
|
|
376
|
+
|
|
377
|
+
ある要素の左枝先を全部調べ終えたら、自身の値を出力し、
|
|
378
|
+
|
|
379
|
+
次にその要素の右枝先の要素を全部調べる
|
|
380
|
+
|
|
381
|
+
左枝を調べる
|
|
382
|
+
|
|
383
|
+
調べ終えたら戻ってくる
|
|
384
|
+
|
|
385
|
+
値を出力する
|
|
386
|
+
|
|
387
|
+
右枝を調べる
|
|
388
|
+
|
|
389
|
+
調べ終えたら戻ってくる
|
|
390
|
+
|
|
391
|
+
関数を終了して、自身を呼び出した関数の元へと戻る */
|
|
392
|
+
|
|
393
|
+
void inorder(NODE *p)
|
|
394
|
+
|
|
395
|
+
{
|
|
396
|
+
|
|
397
|
+
/* 木が空なら何もしない */
|
|
398
|
+
|
|
399
|
+
if(p==NULL)
|
|
400
|
+
|
|
401
|
+
return;
|
|
402
|
+
|
|
403
|
+
else{
|
|
404
|
+
|
|
405
|
+
/* 引数に左へのポインタを渡すことで、再帰を繰り返して延々と左枝へ移動し
|
|
406
|
+
|
|
407
|
+
一番左、一番小さい値にたどり着く
|
|
408
|
+
|
|
409
|
+
子ノードはないため、引数の値はNULLに当たって戻ってくる
|
|
410
|
+
|
|
411
|
+
一番下位の要素なので、左枝と同様に右枝もない。
|
|
412
|
+
|
|
413
|
+
なので終点である NULL に行き当たり、また return で戻ってくる。
|
|
414
|
+
|
|
415
|
+
そして「一番左を操作する関数」は処理を終える。
|
|
416
|
+
|
|
417
|
+
この関数に戻り値はない。「画面に出力」して、それで終了*/
|
|
418
|
+
|
|
419
|
+
inorder(p->left); /* 左ノードへ移動 */
|
|
420
|
+
|
|
421
|
+
printf("%d",p->data); /* 自身の値を出力 */
|
|
422
|
+
|
|
423
|
+
inorder(p->right); /* 右ノードへ移動 */
|
|
424
|
+
|
|
425
|
+
}
|
|
426
|
+
|
|
427
|
+
/* 関数を終了して、自身を呼び出した関数のもとへ戻る */
|
|
428
|
+
|
|
429
|
+
}
|
|
430
|
+
|
|
431
|
+
|
|
432
|
+
|
|
433
|
+
/* 二分木を帰りがけ順でなぞる */
|
|
434
|
+
|
|
435
|
+
void postorder(NODE *p)
|
|
436
|
+
|
|
437
|
+
{
|
|
438
|
+
|
|
439
|
+
/* 木が空なら何もしない */
|
|
440
|
+
|
|
441
|
+
if(p==NULL)
|
|
442
|
+
|
|
443
|
+
return;
|
|
444
|
+
|
|
445
|
+
else{
|
|
446
|
+
|
|
447
|
+
postorder(p->left); /* 左ノードへ移動 */
|
|
448
|
+
|
|
449
|
+
postorder(p->right); /* 右ノードへ移動 */
|
|
450
|
+
|
|
451
|
+
printf("%d",p->data); /* 自身の値を出力 */
|
|
452
|
+
|
|
453
|
+
}
|
|
454
|
+
|
|
455
|
+
}
|
|
456
|
+
|
|
457
|
+
|
|
458
|
+
|
|
459
|
+
|
|
460
|
+
|
|
461
|
+
int main(void)
|
|
462
|
+
|
|
463
|
+
{
|
|
464
|
+
|
|
465
|
+
int a,key1,key2;
|
|
466
|
+
|
|
467
|
+
int mn=0;
|
|
468
|
+
|
|
469
|
+
|
|
470
|
+
|
|
471
|
+
printf("二分探索木をします\n");
|
|
472
|
+
|
|
473
|
+
do{
|
|
474
|
+
|
|
475
|
+
printf("メニューを選んでください\n\n1=追加\n2=行きがけ順\n3=通りがけ順\n4=帰りがけ順\n5=指定した値の番地\n6=削除\n9=終了\n");
|
|
476
|
+
|
|
477
|
+
scanf("%d",&mn);
|
|
478
|
+
|
|
479
|
+
switch(mn){
|
|
480
|
+
|
|
481
|
+
|
|
482
|
+
|
|
483
|
+
|
|
484
|
+
|
|
485
|
+
case 1:
|
|
486
|
+
|
|
487
|
+
printf("追加する数字を入力してください\n");
|
|
488
|
+
|
|
489
|
+
scanf("%d",&a);
|
|
490
|
+
|
|
491
|
+
insert(a);
|
|
492
|
+
|
|
493
|
+
break;
|
|
494
|
+
|
|
495
|
+
|
|
496
|
+
|
|
497
|
+
case 2:
|
|
498
|
+
|
|
499
|
+
printf("行きがけ順です\n");
|
|
500
|
+
|
|
501
|
+
preorder(root);
|
|
502
|
+
|
|
503
|
+
break;
|
|
504
|
+
|
|
505
|
+
|
|
506
|
+
|
|
507
|
+
case 3:
|
|
508
|
+
|
|
509
|
+
printf("通りがけ順です\n");
|
|
510
|
+
|
|
511
|
+
inorder(root);
|
|
512
|
+
|
|
513
|
+
break;
|
|
514
|
+
|
|
515
|
+
|
|
516
|
+
|
|
517
|
+
case 4:
|
|
518
|
+
|
|
519
|
+
printf("帰りがけ順です\n");
|
|
520
|
+
|
|
521
|
+
postorder(root);
|
|
522
|
+
|
|
523
|
+
break;
|
|
524
|
+
|
|
525
|
+
|
|
526
|
+
|
|
527
|
+
case 5:
|
|
528
|
+
|
|
529
|
+
printf("指定した値の番地を出力します\n");
|
|
530
|
+
|
|
531
|
+
scanf("%d",&key1);
|
|
532
|
+
|
|
533
|
+
search(key1);
|
|
534
|
+
|
|
535
|
+
break;
|
|
536
|
+
|
|
537
|
+
|
|
538
|
+
|
|
539
|
+
case 6:
|
|
540
|
+
|
|
541
|
+
printf("指定した値を削除します\n");
|
|
542
|
+
|
|
543
|
+
scanf("%d",&key2);
|
|
544
|
+
|
|
545
|
+
delete(key2);
|
|
546
|
+
|
|
547
|
+
break;
|
|
548
|
+
|
|
549
|
+
|
|
550
|
+
|
|
551
|
+
case 9:
|
|
552
|
+
|
|
553
|
+
printf("終了します\n");
|
|
554
|
+
|
|
555
|
+
break;
|
|
556
|
+
|
|
557
|
+
|
|
558
|
+
|
|
559
|
+
default:
|
|
560
|
+
|
|
561
|
+
printf("エラー：メニューの中の数字を入力してください\n");
|
|
562
|
+
|
|
563
|
+
}
|
|
564
|
+
|
|
565
|
+
}while (mn !=9);
|
|
566
|
+
|
|
567
|
+
|
|
568
|
+
|
|
569
|
+
return 0;
|
|
570
|
+
|
|
571
|
+
}
|
|
572
|
+
|
|
573
|
+
``
|
|
574
|
+
|
|
575
|
+
```### 前提・実現したいこと``````
|
|
576
|
+
|
|
577
|
+
二分探索木のプログラムを実装したいです
|
|
578
|
+
|
|
579
|
+
仕様は
|
|
580
|
+
|
|
581
|
+
数字を入力して
|
|
582
|
+
|
|
583
|
+
1=追加
|
|
584
|
+
|
|
585
|
+
2=行きがけ順で表示
|
|
586
|
+
|
|
587
|
+
3=通りがけ順で表示
|
|
588
|
+
|
|
589
|
+
4=帰りがけ順で表示
|
|
590
|
+
|
|
591
|
+
5=指定した値の番地で表示
|
|
592
|
+
|
|
593
|
+
6=削除
|
|
594
|
+
|
|
595
|
+
9=終了
|
|
596
|
+
|
|
597
|
+
ができるようにしたいです
|
|
598
|
+
|
|
599
|
+
アドバイスお願いいたします！！
|
|
600
|
+
|
|
601
|
+
|
|
602
|
+
|
|
603
|
+
### 発生している問題・エラーメッセージ
|
|
604
|
+
|
|
605
|
+
|
|
606
|
+
|
|
607
|
+
「34行目」で記述エラーを発見しました。
|
|
608
|
+
|
|
609
|
+
「identifier」を付け忘れています。
|
|
610
|
+
|
|
611
|
+
と出てしまいます
|
|
612
|
+
|
|
1
613
|
```
|
|
2
614
|
|
|
3
|
-
|
|
615
|
+
|
|
4
|
-
|
|
5
|
-
|
|
616
|
+
|
|
6
|
-
|
|
7
|
-
|
|
617
|
+
### 該当のソースコード
|
|
8
|
-
|
|
618
|
+
|
|
9
|
-
|
|
619
|
+
``````ここに言語を入力
|
|
10
|
-
|
|
620
|
+
|
|
11
|
-
|
|
621
|
+
ここに言語を入力
|
|
622
|
+
|
|
12
|
-
|
|
623
|
+
```
|
|
624
|
+
|
|
625
|
+
コード
|
|
626
|
+
|
|
627
|
+
```
|
|
628
|
+
|
|
629
|
+
|
|
630
|
+
|
|
631
|
+
|
|
632
|
+
|
|
633
|
+
|
|
634
|
+
|
|
635
|
+
|
|
636
|
+
|
|
13
|
-
|
|
637
|
+
### 悩んでいること
|
|
14
|
-
|
|
15
|
-
|
|
638
|
+
|
|
16
|
-
|
|
17
|
-
|
|
639
|
+
① まず、
|
|
18
|
-
|
|
19
|
-
|
|
20
|
-
|
|
21
|
-
/* 初期状態では二分探索木は空の状態。
|
|
22
|
-
|
|
23
|
-
グローバル変数rootが二分探索木の根へのポインタを保持しているものとする */
|
|
24
|
-
|
|
25
|
-
/* グローバル変数rootをNULLで初期化 */
|
|
26
|
-
|
|
27
|
-
NODE *root = NULL;
|
|
28
|
-
|
|
29
|
-
|
|
30
|
-
|
|
31
|
-
/* エラーメッセージをプリントしてexitする関数*/
|
|
32
|
-
|
|
33
|
-
/* ポインタ(アドレス)の先のデータを読み取り専用にする */
|
|
34
|
-
|
|
35
|
-
void fatal_error(const char *s)
|
|
36
|
-
|
|
37
|
-
{
|
|
38
|
-
|
|
39
|
-
/* fprintf関数を使ってstderrで標準エラーを出力する*/
|
|
40
|
-
|
|
41
|
-
fprintf(stderr,"%s", s);
|
|
42
|
-
|
|
43
|
-
exit(1); /* 異常終了 */
|
|
44
|
-
|
|
45
|
-
|
|
46
|
-
|
|
47
|
-
}
|
|
48
|
-
|
|
49
|
-
|
|
50
|
-
|
|
51
|
-
/* 二分探索木を探索する関数 */
|
|
52
640
|
|
|
53
641
|
NODE *search(int key)
|
|
54
642
|
|
|
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
|
-
p = p->right;
|
|
86
|
-
|
|
87
|
-
}
|
|
88
|
-
|
|
89
|
-
printf("NotExist\n");
|
|
90
|
-
|
|
91
|
-
return NULL;
|
|
92
|
-
|
|
93
|
-
}
|
|
94
|
-
|
|
95
|
-
|
|
96
|
-
|
|
97
|
-
/* 二分探索木から要素を追加する関数*/
|
|
98
|
-
|
|
99
|
-
NODE *insert(int key)
|
|
100
|
-
|
|
101
|
-
{
|
|
102
|
-
|
|
103
|
-
int key;
|
|
104
|
-
|
|
105
|
-
NODE **p,*new;
|
|
106
|
-
|
|
107
|
-
/* 変数pが変数rootを指すように初期化する */
|
|
108
|
-
|
|
109
|
-
p=&root;
|
|
110
|
-
|
|
111
|
-
/* 挿入すべき場所が見つかるまで繰り返す */
|
|
112
|
-
|
|
113
|
-
while (*p != NULL) {
|
|
114
|
-
|
|
115
|
-
/* キーと注目している節のデータが等しいか比較 */
|
|
116
|
-
|
|
117
|
-
if (key == (*p)->data)
|
|
118
|
-
|
|
119
|
-
/* すでに登録されている */
|
|
120
|
-
|
|
121
|
-
return NULL;
|
|
122
|
-
|
|
123
|
-
else if (key < (*p)->data) {
|
|
124
|
-
|
|
125
|
-
/* キーの方が小さければ左部分木に進む */
|
|
126
|
-
|
|
127
|
-
p =&(*p)->left;
|
|
128
|
-
|
|
129
|
-
else
|
|
130
|
-
|
|
131
|
-
/* キーの方が大きければ右部分木に進む */
|
|
132
|
-
|
|
133
|
-
p =&(*p)->right;
|
|
134
|
-
|
|
135
|
-
}
|
|
136
|
-
|
|
137
|
-
/* 挿入されるべき場所が見つかったら */
|
|
138
|
-
|
|
139
|
-
/* 挿入される節をつくる */
|
|
140
|
-
|
|
141
|
-
if((new=malloc(sizeof(NODE)))=NULL)
|
|
142
|
-
|
|
143
|
-
fatal_error("out of memory!!");
|
|
144
|
-
|
|
145
|
-
/* 新しい節には子がないのでNULLにしておく */
|
|
146
|
-
|
|
147
|
-
new->left =NULL;
|
|
148
|
-
|
|
149
|
-
new->right=NULL;
|
|
150
|
-
|
|
151
|
-
/* 要素の値をセットする */
|
|
152
|
-
|
|
153
|
-
new->data=key;
|
|
154
|
-
|
|
155
|
-
/* 正しい場所に挿入する */
|
|
156
|
-
|
|
157
|
-
/* ポインタpは挿入される節へのポインタが入っている場所を指している */
|
|
158
|
-
|
|
159
|
-
*p=new;
|
|
160
|
-
|
|
161
|
-
return new;
|
|
162
|
-
|
|
163
|
-
}
|
|
164
|
-
|
|
165
|
-
|
|
166
|
-
|
|
167
|
-
/* 二分探索木から要素を削除する関数 */
|
|
643
|
+
教科書に書いてあったこの宣言の仕方がよく分かりません
|
|
644
|
+
|
|
645
|
+
|
|
646
|
+
|
|
647
|
+
型名なしの関数の宣言の仕方を調べると一つだけ解説しているサイトが見つかり、自動的にint型になると書 いてあったのですが正しいのでしょうか？
|
|
648
|
+
|
|
649
|
+
|
|
650
|
+
|
|
651
|
+
引数があり、戻り値がある場合はvoid型ではない、
|
|
652
|
+
|
|
653
|
+
引数があり、戻り値がない場合はvoid型、
|
|
654
|
+
|
|
655
|
+
引数がなし、戻り値がある場合もvoid型、
|
|
656
|
+
|
|
657
|
+
引数がなし、戻り値がない場合もvoid型
|
|
658
|
+
|
|
659
|
+
と学びました
|
|
660
|
+
|
|
661
|
+
|
|
662
|
+
|
|
663
|
+
preorder(NODE *p)
|
|
664
|
+
|
|
665
|
+
postorder(NODE *p)
|
|
666
|
+
|
|
667
|
+
inorder(NODE *p)
|
|
668
|
+
|
|
669
|
+
これらの関数は引数があり、戻り値がない場合なのでvoid型、
|
|
670
|
+
|
|
671
|
+
|
|
168
672
|
|
|
169
673
|
int delete(int key)
|
|
170
674
|
|
|
171
|
-
{
|
|
172
|
-
|
|
173
|
-
int key;
|
|
174
|
-
|
|
175
|
-
/* 親へのポインタを使う */
|
|
176
|
-
|
|
177
|
-
NODE **p,*x;
|
|
178
|
-
|
|
179
|
-
/* 変数pが変数rootを指すように初期化する */
|
|
180
|
-
|
|
181
|
-
p=&root;
|
|
182
|
-
|
|
183
|
-
/* 削除対象となる要素を探す */
|
|
184
|
-
|
|
185
|
-
while (*p != NULL) {
|
|
186
|
-
|
|
187
|
-
/* 見つかった
|
|
188
|
-
|
|
189
|
-
変数pは削除される節の親のメンバleft,right
|
|
190
|
-
|
|
191
|
-
変数xは削除される節そのものを指している */
|
|
192
|
-
|
|
193
|
-
if (key == (*p)->data){
|
|
194
|
-
|
|
195
|
-
x=*p;
|
|
196
|
-
|
|
197
|
-
/* 1つも子を持っていない、葉である場合 */
|
|
198
|
-
|
|
199
|
-
|
|
675
|
+
この関数も引数があり、戻り値がない場合なのでvoid型だと思われるのですがなぜint型なのでしょうか
|
|
200
|
-
|
|
201
|
-
|
|
676
|
+
|
|
202
|
-
|
|
203
|
-
|
|
677
|
+
|
|
204
|
-
|
|
205
|
-
else if (x->left==NULL)
|
|
206
|
-
|
|
207
|
-
*p=x->right;
|
|
208
|
-
|
|
209
|
-
/* 左の子のみをもつ */
|
|
210
|
-
|
|
211
|
-
else if (x->right==NULL)
|
|
212
|
-
|
|
213
|
-
*p=x->left;
|
|
214
|
-
|
|
215
|
-
/* 左右2つの子を持つ */
|
|
216
|
-
|
|
217
|
-
else{
|
|
218
|
-
|
|
219
|
-
/* 部分木から最小の要素を取り去る */
|
|
220
|
-
|
|
221
|
-
*p=deletemin(&x->right);
|
|
222
|
-
|
|
223
|
-
&(*p)->right=x->right;
|
|
224
|
-
|
|
225
|
-
&(*p)->left=x->left;
|
|
226
|
-
|
|
227
|
-
}
|
|
228
|
-
|
|
229
|
-
/* 取り除いた節を解放させる */
|
|
230
|
-
|
|
231
|
-
free(x);
|
|
232
|
-
|
|
233
|
-
printf("Done\n");
|
|
234
|
-
|
|
235
|
-
return 1;
|
|
236
|
-
|
|
237
|
-
}else if(key < (*p)->data)
|
|
238
|
-
|
|
239
|
-
/* 左部分木に進む */
|
|
240
|
-
|
|
241
|
-
p=&(*p)->left;
|
|
242
|
-
|
|
243
|
-
else
|
|
244
|
-
|
|
245
|
-
/* 右部分木に進む */
|
|
246
|
-
|
|
247
|
-
p=&(*p)->right;
|
|
248
|
-
|
|
249
|
-
}
|
|
250
|
-
|
|
251
|
-
/* 削除対象が見つからなかった */
|
|
252
|
-
|
|
253
|
-
printf("NotExist\n");
|
|
254
|
-
|
|
255
|
-
return 0;
|
|
256
|
-
|
|
257
|
-
}
|
|
258
|
-
|
|
259
|
-
|
|
260
|
-
|
|
261
|
-
/* 二分探索木から最小の要素を削除する関数 */
|
|
262
|
-
|
|
263
|
-
|
|
264
|
-
|
|
265
|
-
NODE *deletemin(NODE **p)
|
|
266
|
-
|
|
267
|
-
{
|
|
268
|
-
|
|
269
|
-
NODE *x;
|
|
270
|
-
|
|
271
|
-
|
|
272
|
-
|
|
273
|
-
while ((*p)->left != NULL)
|
|
274
|
-
|
|
275
|
-
p=&(*p)->left;
|
|
276
|
-
|
|
277
|
-
x=*p;
|
|
278
|
-
|
|
279
|
-
*p=(*p)->right;
|
|
280
|
-
|
|
281
|
-
return x;
|
|
282
|
-
|
|
283
|
-
}
|
|
284
|
-
|
|
285
|
-
|
|
286
|
-
|
|
287
|
-
/* 二分木を行きがけ順でなぞる */
|
|
288
|
-
|
|
289
|
-
preorder(NODE *p)
|
|
290
|
-
|
|
291
|
-
{
|
|
292
|
-
|
|
293
|
-
/* 木が空なら何もしない */
|
|
294
|
-
|
|
295
|
-
if(p==NULL)
|
|
296
|
-
|
|
297
|
-
return;
|
|
298
|
-
|
|
299
|
-
else{
|
|
300
|
-
|
|
301
|
-
printf("%d",p->data); /* 自身の値を出力 */
|
|
302
|
-
|
|
303
|
-
preorder(p->left); /* 左ノードへ移動 */
|
|
304
|
-
|
|
305
|
-
preorder(p->right); /* 右ノードへ移動 */
|
|
306
|
-
|
|
307
|
-
}
|
|
308
|
-
|
|
309
|
-
}
|
|
310
|
-
|
|
311
|
-
|
|
312
|
-
|
|
313
|
-
/* 二分木を通りがけ順でなぞる */
|
|
314
|
-
|
|
315
|
-
|
|
316
|
-
|
|
317
|
-
inorder(NODE *p)
|
|
318
|
-
|
|
319
|
-
{
|
|
320
|
-
|
|
321
|
-
/* 木が空なら何もしない */
|
|
322
|
-
|
|
323
|
-
if(p==NULL)
|
|
324
|
-
|
|
325
|
-
return;
|
|
326
|
-
|
|
327
|
-
else{
|
|
328
|
-
|
|
329
|
-
inorder(p->left); /* 左ノードへ移動 */
|
|
330
|
-
|
|
331
|
-
printf("%d",p->data); /* 自身の値を出力 */
|
|
332
|
-
|
|
333
|
-
inorder(p->right); /* 右ノードへ移動 */
|
|
334
|
-
|
|
335
|
-
}
|
|
336
|
-
|
|
337
|
-
}
|
|
338
|
-
|
|
339
|
-
|
|
340
|
-
|
|
341
|
-
/* 二分木を帰りがけ順でなぞる */
|
|
342
|
-
|
|
343
|
-
postorder(NODE *p)
|
|
344
|
-
|
|
345
|
-
{
|
|
346
|
-
|
|
347
|
-
/* 木が空なら何もしない */
|
|
348
|
-
|
|
349
|
-
if(p==NULL)
|
|
350
|
-
|
|
351
|
-
return;
|
|
352
|
-
|
|
353
|
-
else{
|
|
354
|
-
|
|
355
|
-
postorderr(p->left); /* 左ノードへ移動 */
|
|
356
|
-
|
|
357
|
-
postorder(p->right); /* 右ノードへ移動 */
|
|
358
|
-
|
|
359
|
-
printf("%d",p->data); /* 自身の値を出力 */
|
|
360
|
-
|
|
361
|
-
}
|
|
362
|
-
|
|
363
|
-
}
|
|
364
|
-
|
|
365
|
-
|
|
366
|
-
|
|
367
|
-
|
|
368
|
-
|
|
369
|
-
int main(void)
|
|
370
|
-
|
|
371
|
-
{
|
|
372
|
-
|
|
373
|
-
int i;
|
|
374
|
-
|
|
375
|
-
int n;
|
|
376
|
-
|
|
377
|
-
int a,b,c;
|
|
378
|
-
|
|
379
|
-
int mn=0;
|
|
380
|
-
|
|
381
|
-
|
|
382
|
-
|
|
383
|
-
printf("二分探索木をします\n");
|
|
384
|
-
|
|
385
|
-
do{
|
|
386
|
-
|
|
387
|
-
printf("メニューを選んでください\n\n1=追加\n2=行きがけ順\n3=通りがけ順\n4=帰りがけ順\n5=指定した値の番地\n6=削除\n9=終了\n");
|
|
388
|
-
|
|
389
|
-
scanf("%d",&mn);
|
|
390
|
-
|
|
391
|
-
switch(mn){
|
|
392
|
-
|
|
393
|
-
|
|
394
|
-
|
|
395
|
-
|
|
396
|
-
|
|
397
|
-
case 1:
|
|
398
|
-
|
|
399
|
-
printf("追加する数字を入力してください\n");
|
|
400
|
-
|
|
401
|
-
scanf("%d",&a);
|
|
402
|
-
|
|
403
|
-
insert(a);
|
|
404
|
-
|
|
405
|
-
break;
|
|
406
|
-
|
|
407
|
-
|
|
408
|
-
|
|
409
|
-
case 2:
|
|
410
|
-
|
|
411
|
-
printf("行きがけ順です\n");
|
|
412
|
-
|
|
413
|
-
preorder();
|
|
414
|
-
|
|
415
|
-
break;
|
|
416
|
-
|
|
417
|
-
|
|
418
|
-
|
|
419
|
-
case 3:
|
|
420
|
-
|
|
421
|
-
printf("通りがけ順です\n");
|
|
422
|
-
|
|
423
|
-
inorder();
|
|
424
|
-
|
|
425
|
-
break;
|
|
426
|
-
|
|
427
|
-
|
|
428
|
-
|
|
429
|
-
case 4:
|
|
430
|
-
|
|
431
|
-
printf("帰りがけ順です\n");
|
|
432
|
-
|
|
433
|
-
postorder();
|
|
434
|
-
|
|
435
|
-
break;
|
|
436
|
-
|
|
437
|
-
|
|
438
|
-
|
|
439
|
-
case 5:
|
|
440
|
-
|
|
441
|
-
printf("指定した値の番地を出力します\n");
|
|
442
|
-
|
|
443
|
-
search(key);
|
|
444
|
-
|
|
445
|
-
break;
|
|
446
|
-
|
|
447
|
-
|
|
448
|
-
|
|
449
|
-
case 6:
|
|
450
|
-
|
|
451
|
-
printf("指定した値を削除します\n");
|
|
452
|
-
|
|
453
|
-
delete(key);
|
|
454
|
-
|
|
455
|
-
break;
|
|
456
|
-
|
|
457
|
-
|
|
458
|
-
|
|
459
|
-
case 9:
|
|
460
|
-
|
|
461
|
-
printf("終了します\n");
|
|
462
|
-
|
|
463
|
-
break;
|
|
464
|
-
|
|
465
|
-
|
|
466
|
-
|
|
467
|
-
default:
|
|
468
|
-
|
|
469
|
-
printf("エラー：メニューの中の数字を入力してください\n");
|
|
470
|
-
|
|
471
|
-
}
|
|
472
|
-
|
|
473
|
-
}while (mn !=9);
|
|
474
|
-
|
|
475
|
-
|
|
476
|
-
|
|
477
|
-
return 0;
|
|
478
|
-
|
|
479
|
-
}
|
|
480
|
-
|
|
481
|
-
ここに言語を入力
|
|
482
|
-
|
|
483
|
-
コード
|
|
484
|
-
|
|
485
|
-
```
|
|
486
|
-
|
|
487
|
-
```### 前提・実現したいこと``````
|
|
488
|
-
|
|
489
|
-
二分探索木のプログラムを実装したいです
|
|
490
|
-
|
|
491
|
-
仕様は
|
|
492
|
-
|
|
493
|
-
数字を入力して
|
|
494
|
-
|
|
495
|
-
1=追加
|
|
496
|
-
|
|
497
|
-
2=行きがけ順で表示
|
|
498
|
-
|
|
499
|
-
3=通りがけ順で表示
|
|
500
|
-
|
|
501
|
-
4=帰りがけ順で表示
|
|
502
|
-
|
|
503
|
-
5=指定した値の番地で表示
|
|
504
|
-
|
|
505
|
-
6=削除
|
|
506
|
-
|
|
507
|
-
9=終了
|
|
508
|
-
|
|
509
|
-
ができるようにしたいです
|
|
510
|
-
|
|
511
|
-
アドバイスお願いいたします！！
|
|
512
|
-
|
|
513
|
-
|
|
514
|
-
|
|
515
|
-
### 発生している問題・エラーメッセージ
|
|
516
|
-
|
|
517
|
-
|
|
518
|
-
|
|
519
|
-
「34行目」で記述エラーを発見しました。
|
|
520
|
-
|
|
521
|
-
「identifier」を付け忘れています。
|
|
522
|
-
|
|
523
|
-
と出てしまいます
|
|
524
|
-
|
|
525
|
-
```
|
|
526
|
-
|
|
527
|
-
|
|
528
|
-
|
|
529
|
-
### 該当のソースコード
|
|
530
|
-
|
|
531
|
-
``````ここに言語を入力
|
|
532
|
-
|
|
533
|
-
ここに言語を入力
|
|
534
|
-
|
|
535
|
-
```
|
|
536
|
-
|
|
537
|
-
コード
|
|
538
|
-
|
|
539
|
-
```
|
|
540
|
-
|
|
541
|
-
|
|
542
|
-
|
|
543
|
-
|
|
544
|
-
|
|
545
|
-
|
|
546
|
-
|
|
547
|
-
|
|
548
|
-
|
|
549
|
-
### 悩んでいること
|
|
550
|
-
|
|
551
|
-
① まず、
|
|
552
678
|
|
|
553
679
|
NODE *search(int key)
|
|
554
680
|
|
|
555
|
-
教科書に書いてあったこの宣言の仕方がよく分かりません
|
|
556
|
-
|
|
557
|
-
|
|
558
|
-
|
|
559
|
-
型名なしの関数の宣言の仕方を調べると一つだけ解説しているサイトが見つかり、自動的にint型になると書 いてあったのですが正しいのでしょうか？
|
|
560
|
-
|
|
561
|
-
|
|
562
|
-
|
|
563
|
-
引数があり、戻り値がある場合はvoid型ではない、
|
|
564
|
-
|
|
565
|
-
引数があり、戻り値がない場合はvoid型、
|
|
566
|
-
|
|
567
|
-
引数がなし、戻り値がある場合もvoid型、
|
|
568
|
-
|
|
569
|
-
引数がなし、戻り値がない場合もvoid型
|
|
570
|
-
|
|
571
|
-
と学びました
|
|
572
|
-
|
|
573
|
-
|
|
574
|
-
|
|
575
|
-
preorder(NODE *p)
|
|
576
|
-
|
|
577
|
-
postorder(NODE *p)
|
|
578
|
-
|
|
579
|
-
inorder(NODE *p)
|
|
580
|
-
|
|
581
|
-
これらの関数は引数があり、戻り値がない場合なのでvoid型、
|
|
582
|
-
|
|
583
|
-
|
|
584
|
-
|
|
585
|
-
int delete(int key)
|
|
586
|
-
|
|
587
|
-
この関数も引数があり、戻り値がない場合なのでvoid型だと思われるのですがなぜint型なのでしょうか
|
|
588
|
-
|
|
589
|
-
|
|
590
|
-
|
|
591
|
-
NODE *search(int key)
|
|
592
|
-
|
|
593
681
|
NODE *insert(int key)
|
|
594
682
|
|
|
595
683
|
NODE *deletemin(NODE **p)
|
8
直しました
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -2,7 +2,7 @@
|
|
|
2
2
|
|
|
3
3
|
`#include <stdio.h>
|
|
4
4
|
|
|
5
|
-
|
|
5
|
+
#include <stdlib.h>
|
|
6
6
|
|
|
7
7
|
/* 木の節の定義 */
|
|
8
8
|
|
7
ミスを直しました
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -306,6 +306,8 @@
|
|
|
306
306
|
|
|
307
307
|
}
|
|
308
308
|
|
|
309
|
+
}
|
|
310
|
+
|
|
309
311
|
|
|
310
312
|
|
|
311
313
|
/* 二分木を通りがけ順でなぞる */
|
|
@@ -358,6 +360,8 @@
|
|
|
358
360
|
|
|
359
361
|
}
|
|
360
362
|
|
|
363
|
+
}
|
|
364
|
+
|
|
361
365
|
|
|
362
366
|
|
|
363
367
|
|
6
test
CHANGED
|
File without changes
|
test
CHANGED
|
File without changes
|
5
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -518,10 +518,6 @@
|
|
|
518
518
|
|
|
519
519
|
と出てしまいます
|
|
520
520
|
|
|
521
|
-
恐らくkeyの宣言の仕方がおかしいと思われます。
|
|
522
|
-
|
|
523
|
-
他にも凡ミスがあるかもしれません
|
|
524
|
-
|
|
525
521
|
```
|
|
526
522
|
|
|
527
523
|
|
4
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -28,7 +28,7 @@
|
|
|
28
28
|
|
|
29
29
|
|
|
30
30
|
|
|
31
|
-
* エラーメッセージをプリントしてexitする関数*/
|
|
31
|
+
/* エラーメッセージをプリントしてexitする関数*/
|
|
32
32
|
|
|
33
33
|
/* ポインタ(アドレス)の先のデータを読み取り専用にする */
|
|
34
34
|
|
3
ミスがあったので直しました
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -14,8 +14,6 @@
|
|
|
14
14
|
|
|
15
15
|
struct node *right; /* 右の子 */
|
|
16
16
|
|
|
17
|
-
char label; /* この節のラベル */
|
|
18
|
-
|
|
19
17
|
}NODE;
|
|
20
18
|
|
|
21
19
|
|
|
@@ -30,6 +28,24 @@
|
|
|
30
28
|
|
|
31
29
|
|
|
32
30
|
|
|
31
|
+
* エラーメッセージをプリントしてexitする関数*/
|
|
32
|
+
|
|
33
|
+
/* ポインタ(アドレス)の先のデータを読み取り専用にする */
|
|
34
|
+
|
|
35
|
+
void fatal_error(const char *s)
|
|
36
|
+
|
|
37
|
+
{
|
|
38
|
+
|
|
39
|
+
/* fprintf関数を使ってstderrで標準エラーを出力する*/
|
|
40
|
+
|
|
41
|
+
fprintf(stderr,"%s", s);
|
|
42
|
+
|
|
43
|
+
exit(1); /* 異常終了 */
|
|
44
|
+
|
|
45
|
+
|
|
46
|
+
|
|
47
|
+
}
|
|
48
|
+
|
|
33
49
|
|
|
34
50
|
|
|
35
51
|
/* 二分探索木を探索する関数 */
|
|
@@ -38,8 +54,6 @@
|
|
|
38
54
|
|
|
39
55
|
{
|
|
40
56
|
|
|
41
|
-
struct node key;
|
|
42
|
-
|
|
43
57
|
NODE *p; /* 現在注目している節 */
|
|
44
58
|
|
|
45
59
|
p=root; /* まず根に注目する */
|
|
@@ -126,7 +140,7 @@
|
|
|
126
140
|
|
|
127
141
|
if((new=malloc(sizeof(NODE)))=NULL)
|
|
128
142
|
|
|
129
|
-
error("out of memory!!");
|
|
143
|
+
fatal_error("out of memory!!");
|
|
130
144
|
|
|
131
145
|
/* 新しい節には子がないのでNULLにしておく */
|
|
132
146
|
|
|
@@ -532,15 +546,137 @@
|
|
|
532
546
|
|
|
533
547
|
|
|
534
548
|
|
|
535
|
-
###
|
|
549
|
+
### 悩んでいること
|
|
536
|
-
|
|
550
|
+
|
|
537
|
-
|
|
551
|
+
① まず、
|
|
552
|
+
|
|
538
|
-
|
|
553
|
+
NODE *search(int key)
|
|
554
|
+
|
|
555
|
+
教科書に書いてあったこの宣言の仕方がよく分かりません
|
|
556
|
+
|
|
557
|
+
|
|
558
|
+
|
|
559
|
+
型名なしの関数の宣言の仕方を調べると一つだけ解説しているサイトが見つかり、自動的にint型になると書 いてあったのですが正しいのでしょうか？
|
|
560
|
+
|
|
561
|
+
|
|
562
|
+
|
|
563
|
+
引数があり、戻り値がある場合はvoid型ではない、
|
|
564
|
+
|
|
565
|
+
引数があり、戻り値がない場合はvoid型、
|
|
566
|
+
|
|
567
|
+
引数がなし、戻り値がある場合もvoid型、
|
|
568
|
+
|
|
569
|
+
引数がなし、戻り値がない場合もvoid型
|
|
570
|
+
|
|
571
|
+
と学びました
|
|
572
|
+
|
|
573
|
+
|
|
574
|
+
|
|
575
|
+
preorder(NODE *p)
|
|
576
|
+
|
|
577
|
+
postorder(NODE *p)
|
|
578
|
+
|
|
579
|
+
inorder(NODE *p)
|
|
580
|
+
|
|
581
|
+
これらの関数は引数があり、戻り値がない場合なのでvoid型、
|
|
582
|
+
|
|
583
|
+
|
|
584
|
+
|
|
539
|
-
|
|
585
|
+
int delete(int key)
|
|
586
|
+
|
|
540
|
-
|
|
587
|
+
この関数も引数があり、戻り値がない場合なのでvoid型だと思われるのですがなぜint型なのでしょうか
|
|
588
|
+
|
|
589
|
+
|
|
590
|
+
|
|
541
|
-
|
|
591
|
+
NODE *search(int key)
|
|
592
|
+
|
|
542
|
-
|
|
593
|
+
NODE *insert(int key)
|
|
594
|
+
|
|
595
|
+
NODE *deletemin(NODE **p)
|
|
596
|
+
|
|
543
|
-
|
|
597
|
+
これらの関数は引数があり、戻り値がある場合はvoid型ではない、int型だと思います。
|
|
598
|
+
|
|
599
|
+
|
|
600
|
+
|
|
601
|
+
②keyの扱い方についてです
|
|
602
|
+
|
|
603
|
+
|
|
604
|
+
|
|
605
|
+
if (key == p->data)
|
|
606
|
+
|
|
607
|
+
ここの部分で教科書では関数を使って比べていましたがむずかしいので不等号を使って比べることにしました
|
|
608
|
+
|
|
609
|
+
keyは値ですが、p->dataは番地ですよね
|
|
610
|
+
|
|
611
|
+
同じように値同士で扱うにはどのようにしたら良いのでしょうか
|
|
612
|
+
|
|
613
|
+
構造体の場合、アロー演算子は番地、ドットが実体だと習いましたがエラーが出てしまいます
|
|
614
|
+
|
|
615
|
+
|
|
616
|
+
|
|
617
|
+
|
|
618
|
+
|
|
619
|
+
③関数の値渡しについてです
|
|
620
|
+
|
|
621
|
+
case 1:
|
|
622
|
+
|
|
623
|
+
printf("追加する数字を入力してください\n");
|
|
624
|
+
|
|
625
|
+
scanf("%d",&a);
|
|
626
|
+
|
|
627
|
+
insert(a);
|
|
628
|
+
|
|
629
|
+
break;
|
|
630
|
+
|
|
631
|
+
case 5:
|
|
632
|
+
|
|
633
|
+
printf("指定した値の番地を出力します\n");
|
|
634
|
+
|
|
635
|
+
scanf("%d",&key1);
|
|
636
|
+
|
|
637
|
+
search(key1);
|
|
638
|
+
|
|
639
|
+
break;
|
|
640
|
+
|
|
641
|
+
|
|
642
|
+
|
|
643
|
+
case 6:
|
|
644
|
+
|
|
645
|
+
printf("指定した値を削除します\n");
|
|
646
|
+
|
|
647
|
+
scanf("%d",&key2);
|
|
648
|
+
|
|
649
|
+
delete(key2);
|
|
650
|
+
|
|
651
|
+
break;
|
|
652
|
+
|
|
653
|
+
|
|
654
|
+
|
|
655
|
+
ここの部分で出力する場合の値と指定した値の変数名はそれぞれ変えたほうが良いですよね？
|
|
656
|
+
|
|
657
|
+
|
|
658
|
+
|
|
659
|
+
④探索した値の番地を出力する際に、
|
|
660
|
+
|
|
661
|
+
|
|
662
|
+
|
|
663
|
+
/* もしキーと注目している節のデータとが等しければポインタを関数として返す */
|
|
664
|
+
|
|
665
|
+
printf("探索した値の番地です>>%d\n",p->data);
|
|
666
|
+
|
|
667
|
+
return p;
|
|
668
|
+
|
|
669
|
+
|
|
670
|
+
|
|
671
|
+
としていますが、めちゃくちゃな状態です
|
|
672
|
+
|
|
673
|
+
探索した値の番地を返す場合、 return pはどのように扱えば良いのか悩みます。
|
|
674
|
+
|
|
675
|
+
|
|
676
|
+
|
|
677
|
+
|
|
678
|
+
|
|
679
|
+
|
|
544
680
|
|
|
545
681
|
|
|
546
682
|
|
|
@@ -552,8 +688,8 @@
|
|
|
552
688
|
|
|
553
689
|
初心者で使い方がよく分かっていません
|
|
554
690
|
|
|
691
|
+
自分の理解が正しいのか不安なのでコメント多いです
|
|
692
|
+
|
|
693
|
+
見づらければ修正します
|
|
694
|
+
|
|
555
695
|
ご指摘ください
|
|
556
|
-
|
|
557
|
-
|
|
558
|
-
|
|
559
|
-
コードの挿入の仕方がよく分かっていません
|
2
コードの挿入ができたと思います
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -1,3 +1,5 @@
|
|
|
1
|
+
```
|
|
2
|
+
|
|
1
3
|
`#include <stdio.h>
|
|
2
4
|
|
|
3
5
|
|
|
@@ -458,7 +460,7 @@
|
|
|
458
460
|
|
|
459
461
|
}
|
|
460
462
|
|
|
461
|
-
|
|
463
|
+
ここに言語を入力
|
|
462
464
|
|
|
463
465
|
コード
|
|
464
466
|
|
|
@@ -554,4 +556,4 @@
|
|
|
554
556
|
|
|
555
557
|
|
|
556
558
|
|
|
557
|
-
コードの挿入の仕方
|
|
559
|
+
コードの挿入の仕方がよく分かっていません
|
1
コードの挿入の仕方は合っていますでしょうか？？？？
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -1,4 +1,470 @@
|
|
|
1
|
+
`#include <stdio.h>
|
|
2
|
+
|
|
3
|
+
|
|
4
|
+
|
|
5
|
+
/* 木の節の定義 */
|
|
6
|
+
|
|
7
|
+
typedef struct node{
|
|
8
|
+
|
|
9
|
+
int data; /* 探索のキーになるデータ型 */
|
|
10
|
+
|
|
11
|
+
struct node *left; /* 左の子 */
|
|
12
|
+
|
|
13
|
+
struct node *right; /* 右の子 */
|
|
14
|
+
|
|
15
|
+
char label; /* この節のラベル */
|
|
16
|
+
|
|
17
|
+
}NODE;
|
|
18
|
+
|
|
19
|
+
|
|
20
|
+
|
|
21
|
+
/* 初期状態では二分探索木は空の状態。
|
|
22
|
+
|
|
23
|
+
グローバル変数rootが二分探索木の根へのポインタを保持しているものとする */
|
|
24
|
+
|
|
25
|
+
/* グローバル変数rootをNULLで初期化 */
|
|
26
|
+
|
|
27
|
+
NODE *root = NULL;
|
|
28
|
+
|
|
29
|
+
|
|
30
|
+
|
|
31
|
+
|
|
32
|
+
|
|
33
|
+
/* 二分探索木を探索する関数 */
|
|
34
|
+
|
|
35
|
+
NODE *search(int key)
|
|
36
|
+
|
|
37
|
+
{
|
|
38
|
+
|
|
39
|
+
struct node key;
|
|
40
|
+
|
|
41
|
+
NODE *p; /* 現在注目している節 */
|
|
42
|
+
|
|
43
|
+
p=root; /* まず根に注目する */
|
|
44
|
+
|
|
45
|
+
/* 進むべき子が存在する限り繰り返す */
|
|
46
|
+
|
|
47
|
+
while (p != NULL) {
|
|
48
|
+
|
|
49
|
+
/* キーと注目している節のデータが等しいか比較 */
|
|
50
|
+
|
|
51
|
+
if (key == p->data)
|
|
52
|
+
|
|
53
|
+
/* もしキーと注目している節のデータとが等しければポインタを関数として返す */
|
|
54
|
+
|
|
55
|
+
printf("探索した値の番地です>>%d\n",p->data);
|
|
56
|
+
|
|
57
|
+
return p;
|
|
58
|
+
|
|
59
|
+
else if (key < (p->data)) {
|
|
60
|
+
|
|
61
|
+
/* キーの方が小さければ左部分木に進む */
|
|
62
|
+
|
|
63
|
+
p = p->left;
|
|
64
|
+
|
|
65
|
+
else
|
|
66
|
+
|
|
67
|
+
/* キーの方が大きければ右部分木に進む*/
|
|
68
|
+
|
|
69
|
+
p = p->right;
|
|
70
|
+
|
|
71
|
+
}
|
|
72
|
+
|
|
73
|
+
printf("NotExist\n");
|
|
74
|
+
|
|
75
|
+
return NULL;
|
|
76
|
+
|
|
77
|
+
}
|
|
78
|
+
|
|
79
|
+
|
|
80
|
+
|
|
81
|
+
/* 二分探索木から要素を追加する関数*/
|
|
82
|
+
|
|
83
|
+
NODE *insert(int key)
|
|
84
|
+
|
|
85
|
+
{
|
|
86
|
+
|
|
87
|
+
int key;
|
|
88
|
+
|
|
89
|
+
NODE **p,*new;
|
|
90
|
+
|
|
91
|
+
/* 変数pが変数rootを指すように初期化する */
|
|
92
|
+
|
|
93
|
+
p=&root;
|
|
94
|
+
|
|
95
|
+
/* 挿入すべき場所が見つかるまで繰り返す */
|
|
96
|
+
|
|
97
|
+
while (*p != NULL) {
|
|
98
|
+
|
|
99
|
+
/* キーと注目している節のデータが等しいか比較 */
|
|
100
|
+
|
|
101
|
+
if (key == (*p)->data)
|
|
102
|
+
|
|
103
|
+
/* すでに登録されている */
|
|
104
|
+
|
|
105
|
+
return NULL;
|
|
106
|
+
|
|
107
|
+
else if (key < (*p)->data) {
|
|
108
|
+
|
|
109
|
+
/* キーの方が小さければ左部分木に進む */
|
|
110
|
+
|
|
111
|
+
p =&(*p)->left;
|
|
112
|
+
|
|
113
|
+
else
|
|
114
|
+
|
|
115
|
+
/* キーの方が大きければ右部分木に進む */
|
|
116
|
+
|
|
117
|
+
p =&(*p)->right;
|
|
118
|
+
|
|
119
|
+
}
|
|
120
|
+
|
|
121
|
+
/* 挿入されるべき場所が見つかったら */
|
|
122
|
+
|
|
123
|
+
/* 挿入される節をつくる */
|
|
124
|
+
|
|
125
|
+
if((new=malloc(sizeof(NODE)))=NULL)
|
|
126
|
+
|
|
127
|
+
error("out of memory!!");
|
|
128
|
+
|
|
129
|
+
/* 新しい節には子がないのでNULLにしておく */
|
|
130
|
+
|
|
131
|
+
new->left =NULL;
|
|
132
|
+
|
|
133
|
+
new->right=NULL;
|
|
134
|
+
|
|
135
|
+
/* 要素の値をセットする */
|
|
136
|
+
|
|
137
|
+
new->data=key;
|
|
138
|
+
|
|
139
|
+
/* 正しい場所に挿入する */
|
|
140
|
+
|
|
141
|
+
/* ポインタpは挿入される節へのポインタが入っている場所を指している */
|
|
142
|
+
|
|
143
|
+
*p=new;
|
|
144
|
+
|
|
145
|
+
return new;
|
|
146
|
+
|
|
147
|
+
}
|
|
148
|
+
|
|
149
|
+
|
|
150
|
+
|
|
151
|
+
/* 二分探索木から要素を削除する関数 */
|
|
152
|
+
|
|
153
|
+
int delete(int key)
|
|
154
|
+
|
|
155
|
+
{
|
|
156
|
+
|
|
157
|
+
int key;
|
|
158
|
+
|
|
159
|
+
/* 親へのポインタを使う */
|
|
160
|
+
|
|
161
|
+
NODE **p,*x;
|
|
162
|
+
|
|
163
|
+
/* 変数pが変数rootを指すように初期化する */
|
|
164
|
+
|
|
165
|
+
p=&root;
|
|
166
|
+
|
|
167
|
+
/* 削除対象となる要素を探す */
|
|
168
|
+
|
|
169
|
+
while (*p != NULL) {
|
|
170
|
+
|
|
171
|
+
/* 見つかった
|
|
172
|
+
|
|
173
|
+
変数pは削除される節の親のメンバleft,right
|
|
174
|
+
|
|
175
|
+
変数xは削除される節そのものを指している */
|
|
176
|
+
|
|
177
|
+
if (key == (*p)->data){
|
|
178
|
+
|
|
179
|
+
x=*p;
|
|
180
|
+
|
|
181
|
+
/* 1つも子を持っていない、葉である場合 */
|
|
182
|
+
|
|
183
|
+
if(x->left==NULL && x->right==NULL)
|
|
184
|
+
|
|
185
|
+
*p=NULL;
|
|
186
|
+
|
|
187
|
+
/* 右の子のみをもつ */
|
|
188
|
+
|
|
189
|
+
else if (x->left==NULL)
|
|
190
|
+
|
|
191
|
+
*p=x->right;
|
|
192
|
+
|
|
193
|
+
/* 左の子のみをもつ */
|
|
194
|
+
|
|
195
|
+
else if (x->right==NULL)
|
|
196
|
+
|
|
197
|
+
*p=x->left;
|
|
198
|
+
|
|
199
|
+
/* 左右2つの子を持つ */
|
|
200
|
+
|
|
201
|
+
else{
|
|
202
|
+
|
|
203
|
+
/* 部分木から最小の要素を取り去る */
|
|
204
|
+
|
|
205
|
+
*p=deletemin(&x->right);
|
|
206
|
+
|
|
207
|
+
&(*p)->right=x->right;
|
|
208
|
+
|
|
209
|
+
&(*p)->left=x->left;
|
|
210
|
+
|
|
211
|
+
}
|
|
212
|
+
|
|
213
|
+
/* 取り除いた節を解放させる */
|
|
214
|
+
|
|
215
|
+
free(x);
|
|
216
|
+
|
|
217
|
+
printf("Done\n");
|
|
218
|
+
|
|
219
|
+
return 1;
|
|
220
|
+
|
|
221
|
+
}else if(key < (*p)->data)
|
|
222
|
+
|
|
223
|
+
/* 左部分木に進む */
|
|
224
|
+
|
|
225
|
+
p=&(*p)->left;
|
|
226
|
+
|
|
227
|
+
else
|
|
228
|
+
|
|
229
|
+
/* 右部分木に進む */
|
|
230
|
+
|
|
231
|
+
p=&(*p)->right;
|
|
232
|
+
|
|
233
|
+
}
|
|
234
|
+
|
|
235
|
+
/* 削除対象が見つからなかった */
|
|
236
|
+
|
|
237
|
+
printf("NotExist\n");
|
|
238
|
+
|
|
239
|
+
return 0;
|
|
240
|
+
|
|
241
|
+
}
|
|
242
|
+
|
|
243
|
+
|
|
244
|
+
|
|
245
|
+
/* 二分探索木から最小の要素を削除する関数 */
|
|
246
|
+
|
|
247
|
+
|
|
248
|
+
|
|
249
|
+
NODE *deletemin(NODE **p)
|
|
250
|
+
|
|
251
|
+
{
|
|
252
|
+
|
|
253
|
+
NODE *x;
|
|
254
|
+
|
|
255
|
+
|
|
256
|
+
|
|
257
|
+
while ((*p)->left != NULL)
|
|
258
|
+
|
|
259
|
+
p=&(*p)->left;
|
|
260
|
+
|
|
261
|
+
x=*p;
|
|
262
|
+
|
|
263
|
+
*p=(*p)->right;
|
|
264
|
+
|
|
265
|
+
return x;
|
|
266
|
+
|
|
267
|
+
}
|
|
268
|
+
|
|
269
|
+
|
|
270
|
+
|
|
271
|
+
/* 二分木を行きがけ順でなぞる */
|
|
272
|
+
|
|
273
|
+
preorder(NODE *p)
|
|
274
|
+
|
|
275
|
+
{
|
|
276
|
+
|
|
277
|
+
/* 木が空なら何もしない */
|
|
278
|
+
|
|
279
|
+
if(p==NULL)
|
|
280
|
+
|
|
281
|
+
return;
|
|
282
|
+
|
|
283
|
+
else{
|
|
284
|
+
|
|
285
|
+
printf("%d",p->data); /* 自身の値を出力 */
|
|
286
|
+
|
|
287
|
+
preorder(p->left); /* 左ノードへ移動 */
|
|
288
|
+
|
|
289
|
+
preorder(p->right); /* 右ノードへ移動 */
|
|
290
|
+
|
|
291
|
+
}
|
|
292
|
+
|
|
293
|
+
|
|
294
|
+
|
|
295
|
+
/* 二分木を通りがけ順でなぞる */
|
|
296
|
+
|
|
297
|
+
|
|
298
|
+
|
|
299
|
+
inorder(NODE *p)
|
|
300
|
+
|
|
301
|
+
{
|
|
302
|
+
|
|
303
|
+
/* 木が空なら何もしない */
|
|
304
|
+
|
|
305
|
+
if(p==NULL)
|
|
306
|
+
|
|
307
|
+
return;
|
|
308
|
+
|
|
309
|
+
else{
|
|
310
|
+
|
|
311
|
+
inorder(p->left); /* 左ノードへ移動 */
|
|
312
|
+
|
|
313
|
+
printf("%d",p->data); /* 自身の値を出力 */
|
|
314
|
+
|
|
315
|
+
inorder(p->right); /* 右ノードへ移動 */
|
|
316
|
+
|
|
317
|
+
}
|
|
318
|
+
|
|
319
|
+
}
|
|
320
|
+
|
|
321
|
+
|
|
322
|
+
|
|
323
|
+
/* 二分木を帰りがけ順でなぞる */
|
|
324
|
+
|
|
325
|
+
postorder(NODE *p)
|
|
326
|
+
|
|
327
|
+
{
|
|
328
|
+
|
|
329
|
+
/* 木が空なら何もしない */
|
|
330
|
+
|
|
331
|
+
if(p==NULL)
|
|
332
|
+
|
|
333
|
+
return;
|
|
334
|
+
|
|
335
|
+
else{
|
|
336
|
+
|
|
337
|
+
postorderr(p->left); /* 左ノードへ移動 */
|
|
338
|
+
|
|
339
|
+
postorder(p->right); /* 右ノードへ移動 */
|
|
340
|
+
|
|
341
|
+
printf("%d",p->data); /* 自身の値を出力 */
|
|
342
|
+
|
|
343
|
+
}
|
|
344
|
+
|
|
345
|
+
|
|
346
|
+
|
|
347
|
+
|
|
348
|
+
|
|
349
|
+
int main(void)
|
|
350
|
+
|
|
351
|
+
{
|
|
352
|
+
|
|
353
|
+
int i;
|
|
354
|
+
|
|
355
|
+
int n;
|
|
356
|
+
|
|
357
|
+
int a,b,c;
|
|
358
|
+
|
|
359
|
+
int mn=0;
|
|
360
|
+
|
|
361
|
+
|
|
362
|
+
|
|
363
|
+
printf("二分探索木をします\n");
|
|
364
|
+
|
|
365
|
+
do{
|
|
366
|
+
|
|
367
|
+
printf("メニューを選んでください\n\n1=追加\n2=行きがけ順\n3=通りがけ順\n4=帰りがけ順\n5=指定した値の番地\n6=削除\n9=終了\n");
|
|
368
|
+
|
|
369
|
+
scanf("%d",&mn);
|
|
370
|
+
|
|
371
|
+
switch(mn){
|
|
372
|
+
|
|
373
|
+
|
|
374
|
+
|
|
375
|
+
|
|
376
|
+
|
|
377
|
+
case 1:
|
|
378
|
+
|
|
379
|
+
printf("追加する数字を入力してください\n");
|
|
380
|
+
|
|
381
|
+
scanf("%d",&a);
|
|
382
|
+
|
|
383
|
+
insert(a);
|
|
384
|
+
|
|
385
|
+
break;
|
|
386
|
+
|
|
387
|
+
|
|
388
|
+
|
|
389
|
+
case 2:
|
|
390
|
+
|
|
391
|
+
printf("行きがけ順です\n");
|
|
392
|
+
|
|
393
|
+
preorder();
|
|
394
|
+
|
|
395
|
+
break;
|
|
396
|
+
|
|
397
|
+
|
|
398
|
+
|
|
399
|
+
case 3:
|
|
400
|
+
|
|
401
|
+
printf("通りがけ順です\n");
|
|
402
|
+
|
|
403
|
+
inorder();
|
|
404
|
+
|
|
405
|
+
break;
|
|
406
|
+
|
|
407
|
+
|
|
408
|
+
|
|
409
|
+
case 4:
|
|
410
|
+
|
|
411
|
+
printf("帰りがけ順です\n");
|
|
412
|
+
|
|
413
|
+
postorder();
|
|
414
|
+
|
|
415
|
+
break;
|
|
416
|
+
|
|
417
|
+
|
|
418
|
+
|
|
419
|
+
case 5:
|
|
420
|
+
|
|
421
|
+
printf("指定した値の番地を出力します\n");
|
|
422
|
+
|
|
423
|
+
search(key);
|
|
424
|
+
|
|
425
|
+
break;
|
|
426
|
+
|
|
427
|
+
|
|
428
|
+
|
|
429
|
+
case 6:
|
|
430
|
+
|
|
431
|
+
printf("指定した値を削除します\n");
|
|
432
|
+
|
|
433
|
+
delete(key);
|
|
434
|
+
|
|
435
|
+
break;
|
|
436
|
+
|
|
437
|
+
|
|
438
|
+
|
|
439
|
+
case 9:
|
|
440
|
+
|
|
441
|
+
printf("終了します\n");
|
|
442
|
+
|
|
443
|
+
break;
|
|
444
|
+
|
|
445
|
+
|
|
446
|
+
|
|
447
|
+
default:
|
|
448
|
+
|
|
449
|
+
printf("エラー：メニューの中の数字を入力してください\n");
|
|
450
|
+
|
|
451
|
+
}
|
|
452
|
+
|
|
453
|
+
}while (mn !=9);
|
|
454
|
+
|
|
455
|
+
|
|
456
|
+
|
|
457
|
+
return 0;
|
|
458
|
+
|
|
459
|
+
}
|
|
460
|
+
|
|
461
|
+
``ここに言語を入力
|
|
462
|
+
|
|
463
|
+
コード
|
|
464
|
+
|
|
465
|
+
```
|
|
466
|
+
|
|
1
|
-
### 前提・実現したいこと
|
|
467
|
+
```### 前提・実現したいこと``````
|
|
2
468
|
|
|
3
469
|
二分探索木のプログラムを実装したいです
|
|
4
470
|
|
|
@@ -46,471 +512,15 @@
|
|
|
46
512
|
|
|
47
513
|
### 該当のソースコード
|
|
48
514
|
|
|
49
|
-
|
|
50
|
-
|
|
51
|
-
|
|
52
|
-
|
|
53
|
-
|
|
54
|
-
|
|
55
|
-
|
|
56
|
-
|
|
57
|
-
|
|
58
|
-
|
|
59
|
-
struct node *left; /* 左の子 */
|
|
60
|
-
|
|
61
|
-
struct node *right; /* 右の子 */
|
|
62
|
-
|
|
63
|
-
char label; /* この節のラベル */
|
|
64
|
-
|
|
65
|
-
}NODE;
|
|
66
|
-
|
|
67
|
-
|
|
68
|
-
|
|
69
|
-
/* 初期状態では二分探索木は空の状態。
|
|
70
|
-
|
|
71
|
-
グローバル変数rootが二分探索木の根へのポインタを保持しているものとする */
|
|
72
|
-
|
|
73
|
-
/* グローバル変数rootをNULLで初期化 */
|
|
74
|
-
|
|
75
|
-
NODE *root = NULL;
|
|
76
|
-
|
|
77
|
-
|
|
78
|
-
|
|
79
|
-
|
|
80
|
-
|
|
81
|
-
/* 二分探索木を探索する関数 */
|
|
82
|
-
|
|
83
|
-
NODE *search(int key)
|
|
84
|
-
|
|
85
|
-
{
|
|
86
|
-
|
|
87
|
-
struct node key;
|
|
88
|
-
|
|
89
|
-
NODE *p; /* 現在注目している節 */
|
|
90
|
-
|
|
91
|
-
p=root; /* まず根に注目する */
|
|
92
|
-
|
|
93
|
-
/* 進むべき子が存在する限り繰り返す */
|
|
94
|
-
|
|
95
|
-
while (p != NULL) {
|
|
96
|
-
|
|
97
|
-
/* キーと注目している節のデータが等しいか比較 */
|
|
98
|
-
|
|
99
|
-
if (key == p->data)
|
|
100
|
-
|
|
101
|
-
/* もしキーと注目している節のデータとが等しければポインタを関数として返す */
|
|
102
|
-
|
|
103
|
-
printf("探索した値の番地です>>%d\n",p->data);
|
|
104
|
-
|
|
105
|
-
return p;
|
|
106
|
-
|
|
107
|
-
else if (key < (p->data)) {
|
|
108
|
-
|
|
109
|
-
/* キーの方が小さければ左部分木に進む */
|
|
110
|
-
|
|
111
|
-
p = p->left;
|
|
112
|
-
|
|
113
|
-
else
|
|
114
|
-
|
|
115
|
-
/* キーの方が大きければ右部分木に進む*/
|
|
116
|
-
|
|
117
|
-
p = p->right;
|
|
118
|
-
|
|
119
|
-
}
|
|
120
|
-
|
|
121
|
-
printf("NotExist\n");
|
|
122
|
-
|
|
123
|
-
return NULL;
|
|
124
|
-
|
|
125
|
-
}
|
|
126
|
-
|
|
127
|
-
|
|
128
|
-
|
|
129
|
-
/* 二分探索木から要素を追加する関数*/
|
|
130
|
-
|
|
131
|
-
NODE *insert(int key)
|
|
132
|
-
|
|
133
|
-
{
|
|
134
|
-
|
|
135
|
-
int key;
|
|
136
|
-
|
|
137
|
-
NODE **p,*new;
|
|
138
|
-
|
|
139
|
-
/* 変数pが変数rootを指すように初期化する */
|
|
140
|
-
|
|
141
|
-
p=&root;
|
|
142
|
-
|
|
143
|
-
/* 挿入すべき場所が見つかるまで繰り返す */
|
|
144
|
-
|
|
145
|
-
while (*p != NULL) {
|
|
146
|
-
|
|
147
|
-
/* キーと注目している節のデータが等しいか比較 */
|
|
148
|
-
|
|
149
|
-
if (key == (*p)->data)
|
|
150
|
-
|
|
151
|
-
/* すでに登録されている */
|
|
152
|
-
|
|
153
|
-
return NULL;
|
|
154
|
-
|
|
155
|
-
else if (key < (*p)->data) {
|
|
156
|
-
|
|
157
|
-
/* キーの方が小さければ左部分木に進む */
|
|
158
|
-
|
|
159
|
-
p =&(*p)->left;
|
|
160
|
-
|
|
161
|
-
else
|
|
162
|
-
|
|
163
|
-
/* キーの方が大きければ右部分木に進む */
|
|
164
|
-
|
|
165
|
-
p =&(*p)->right;
|
|
166
|
-
|
|
167
|
-
}
|
|
168
|
-
|
|
169
|
-
/* 挿入されるべき場所が見つかったら */
|
|
170
|
-
|
|
171
|
-
/* 挿入される節をつくる */
|
|
172
|
-
|
|
173
|
-
if((new=malloc(sizeof(NODE)))=NULL)
|
|
174
|
-
|
|
175
|
-
error("out of memory!!");
|
|
176
|
-
|
|
177
|
-
/* 新しい節には子がないのでNULLにしておく */
|
|
178
|
-
|
|
179
|
-
new->left =NULL;
|
|
180
|
-
|
|
181
|
-
new->right=NULL;
|
|
182
|
-
|
|
183
|
-
/* 要素の値をセットする */
|
|
184
|
-
|
|
185
|
-
new->data=key;
|
|
186
|
-
|
|
187
|
-
/* 正しい場所に挿入する */
|
|
188
|
-
|
|
189
|
-
/* ポインタpは挿入される節へのポインタが入っている場所を指している */
|
|
190
|
-
|
|
191
|
-
*p=new;
|
|
192
|
-
|
|
193
|
-
return new;
|
|
194
|
-
|
|
195
|
-
}
|
|
196
|
-
|
|
197
|
-
|
|
198
|
-
|
|
199
|
-
/* 二分探索木から要素を削除する関数 */
|
|
200
|
-
|
|
201
|
-
int delete(int key)
|
|
202
|
-
|
|
203
|
-
{
|
|
204
|
-
|
|
205
|
-
int key;
|
|
206
|
-
|
|
207
|
-
/* 親へのポインタを使う */
|
|
208
|
-
|
|
209
|
-
NODE **p,*x;
|
|
210
|
-
|
|
211
|
-
/* 変数pが変数rootを指すように初期化する */
|
|
212
|
-
|
|
213
|
-
p=&root;
|
|
214
|
-
|
|
215
|
-
/* 削除対象となる要素を探す */
|
|
216
|
-
|
|
217
|
-
while (*p != NULL) {
|
|
218
|
-
|
|
219
|
-
/* 見つかった
|
|
220
|
-
|
|
221
|
-
変数pは削除される節の親のメンバleft,right
|
|
222
|
-
|
|
223
|
-
変数xは削除される節そのものを指している */
|
|
224
|
-
|
|
225
|
-
if (key == (*p)->data){
|
|
226
|
-
|
|
227
|
-
x=*p;
|
|
228
|
-
|
|
229
|
-
/* 1つも子を持っていない、葉である場合 */
|
|
230
|
-
|
|
231
|
-
if(x->left==NULL && x->right==NULL)
|
|
232
|
-
|
|
233
|
-
*p=NULL;
|
|
234
|
-
|
|
235
|
-
/* 右の子のみをもつ */
|
|
236
|
-
|
|
237
|
-
else if (x->left==NULL)
|
|
238
|
-
|
|
239
|
-
*p=x->right;
|
|
240
|
-
|
|
241
|
-
/* 左の子のみをもつ */
|
|
242
|
-
|
|
243
|
-
else if (x->right==NULL)
|
|
244
|
-
|
|
245
|
-
*p=x->left;
|
|
246
|
-
|
|
247
|
-
/* 左右2つの子を持つ */
|
|
248
|
-
|
|
249
|
-
else{
|
|
250
|
-
|
|
251
|
-
/* 部分木から最小の要素を取り去る */
|
|
252
|
-
|
|
253
|
-
*p=deletemin(&x->right);
|
|
254
|
-
|
|
255
|
-
&(*p)->right=x->right;
|
|
256
|
-
|
|
257
|
-
&(*p)->left=x->left;
|
|
258
|
-
|
|
259
|
-
}
|
|
260
|
-
|
|
261
|
-
/* 取り除いた節を解放させる */
|
|
262
|
-
|
|
263
|
-
free(x);
|
|
264
|
-
|
|
265
|
-
printf("Done\n");
|
|
266
|
-
|
|
267
|
-
return 1;
|
|
268
|
-
|
|
269
|
-
}else if(key < (*p)->data)
|
|
270
|
-
|
|
271
|
-
/* 左部分木に進む */
|
|
272
|
-
|
|
273
|
-
p=&(*p)->left;
|
|
274
|
-
|
|
275
|
-
else
|
|
276
|
-
|
|
277
|
-
/* 右部分木に進む */
|
|
278
|
-
|
|
279
|
-
p=&(*p)->right;
|
|
280
|
-
|
|
281
|
-
}
|
|
282
|
-
|
|
283
|
-
/* 削除対象が見つからなかった */
|
|
284
|
-
|
|
285
|
-
printf("NotExist\n");
|
|
286
|
-
|
|
287
|
-
return 0;
|
|
288
|
-
|
|
289
|
-
}
|
|
290
|
-
|
|
291
|
-
|
|
292
|
-
|
|
293
|
-
/* 二分探索木から最小の要素を削除する関数 */
|
|
294
|
-
|
|
295
|
-
|
|
296
|
-
|
|
297
|
-
NODE *deletemin(NODE **p)
|
|
298
|
-
|
|
299
|
-
{
|
|
300
|
-
|
|
301
|
-
NODE *x;
|
|
302
|
-
|
|
303
|
-
|
|
304
|
-
|
|
305
|
-
while ((*p)->left != NULL)
|
|
306
|
-
|
|
307
|
-
p=&(*p)->left;
|
|
308
|
-
|
|
309
|
-
x=*p;
|
|
310
|
-
|
|
311
|
-
*p=(*p)->right;
|
|
312
|
-
|
|
313
|
-
return x;
|
|
314
|
-
|
|
315
|
-
}
|
|
316
|
-
|
|
317
|
-
|
|
318
|
-
|
|
319
|
-
/* 二分木を行きがけ順でなぞる */
|
|
320
|
-
|
|
321
|
-
preorder(NODE *p)
|
|
322
|
-
|
|
323
|
-
{
|
|
324
|
-
|
|
325
|
-
/* 木が空なら何もしない */
|
|
326
|
-
|
|
327
|
-
if(p==NULL)
|
|
328
|
-
|
|
329
|
-
return;
|
|
330
|
-
|
|
331
|
-
else{
|
|
332
|
-
|
|
333
|
-
printf("%d",p->data); /* 自身の値を出力 */
|
|
334
|
-
|
|
335
|
-
preorder(p->left); /* 左ノードへ移動 */
|
|
336
|
-
|
|
337
|
-
preorder(p->right); /* 右ノードへ移動 */
|
|
338
|
-
|
|
339
|
-
}
|
|
340
|
-
|
|
341
|
-
|
|
342
|
-
|
|
343
|
-
/* 二分木を通りがけ順でなぞる */
|
|
344
|
-
|
|
345
|
-
|
|
346
|
-
|
|
347
|
-
inorder(NODE *p)
|
|
348
|
-
|
|
349
|
-
{
|
|
350
|
-
|
|
351
|
-
/* 木が空なら何もしない */
|
|
352
|
-
|
|
353
|
-
if(p==NULL)
|
|
354
|
-
|
|
355
|
-
return;
|
|
356
|
-
|
|
357
|
-
else{
|
|
358
|
-
|
|
359
|
-
inorder(p->left); /* 左ノードへ移動 */
|
|
360
|
-
|
|
361
|
-
printf("%d",p->data); /* 自身の値を出力 */
|
|
362
|
-
|
|
363
|
-
inorder(p->right); /* 右ノードへ移動 */
|
|
364
|
-
|
|
365
|
-
}
|
|
366
|
-
|
|
367
|
-
}
|
|
368
|
-
|
|
369
|
-
|
|
370
|
-
|
|
371
|
-
/* 二分木を帰りがけ順でなぞる */
|
|
372
|
-
|
|
373
|
-
postorder(NODE *p)
|
|
374
|
-
|
|
375
|
-
{
|
|
376
|
-
|
|
377
|
-
/* 木が空なら何もしない */
|
|
378
|
-
|
|
379
|
-
if(p==NULL)
|
|
380
|
-
|
|
381
|
-
return;
|
|
382
|
-
|
|
383
|
-
else{
|
|
384
|
-
|
|
385
|
-
postorderr(p->left); /* 左ノードへ移動 */
|
|
386
|
-
|
|
387
|
-
postorder(p->right); /* 右ノードへ移動 */
|
|
388
|
-
|
|
389
|
-
printf("%d",p->data); /* 自身の値を出力 */
|
|
390
|
-
|
|
391
|
-
}
|
|
392
|
-
|
|
393
|
-
|
|
394
|
-
|
|
395
|
-
|
|
396
|
-
|
|
397
|
-
int main(void)
|
|
398
|
-
|
|
399
|
-
{
|
|
400
|
-
|
|
401
|
-
int i;
|
|
402
|
-
|
|
403
|
-
int n;
|
|
404
|
-
|
|
405
|
-
int a,b,c;
|
|
406
|
-
|
|
407
|
-
int mn=0;
|
|
408
|
-
|
|
409
|
-
|
|
410
|
-
|
|
411
|
-
printf("二分探索木をします\n");
|
|
412
|
-
|
|
413
|
-
do{
|
|
414
|
-
|
|
415
|
-
printf("メニューを選んでください\n\n1=追加\n2=行きがけ順\n3=通りがけ順\n4=帰りがけ順\n5=指定した値の番地\n6=削除\n9=終了\n");
|
|
416
|
-
|
|
417
|
-
scanf("%d",&mn);
|
|
418
|
-
|
|
419
|
-
switch(mn){
|
|
420
|
-
|
|
421
|
-
|
|
422
|
-
|
|
423
|
-
|
|
424
|
-
|
|
425
|
-
case 1:
|
|
426
|
-
|
|
427
|
-
printf("追加する数字を入力してください\n");
|
|
428
|
-
|
|
429
|
-
scanf("%d",&a);
|
|
430
|
-
|
|
431
|
-
insert(a);
|
|
432
|
-
|
|
433
|
-
break;
|
|
434
|
-
|
|
435
|
-
|
|
436
|
-
|
|
437
|
-
case 2:
|
|
438
|
-
|
|
439
|
-
printf("行きがけ順です\n");
|
|
440
|
-
|
|
441
|
-
preorder();
|
|
442
|
-
|
|
443
|
-
break;
|
|
444
|
-
|
|
445
|
-
|
|
446
|
-
|
|
447
|
-
case 3:
|
|
448
|
-
|
|
449
|
-
printf("通りがけ順です\n");
|
|
450
|
-
|
|
451
|
-
inorder();
|
|
452
|
-
|
|
453
|
-
break;
|
|
454
|
-
|
|
455
|
-
|
|
456
|
-
|
|
457
|
-
case 4:
|
|
458
|
-
|
|
459
|
-
printf("帰りがけ順です\n");
|
|
460
|
-
|
|
461
|
-
postorder();
|
|
462
|
-
|
|
463
|
-
break;
|
|
464
|
-
|
|
465
|
-
|
|
466
|
-
|
|
467
|
-
case 5:
|
|
468
|
-
|
|
469
|
-
printf("指定した値の番地を出力します\n");
|
|
470
|
-
|
|
471
|
-
search(key);
|
|
472
|
-
|
|
473
|
-
break;
|
|
474
|
-
|
|
475
|
-
|
|
476
|
-
|
|
477
|
-
case 6:
|
|
478
|
-
|
|
479
|
-
printf("指定した値を削除します\n");
|
|
480
|
-
|
|
481
|
-
delete(key);
|
|
482
|
-
|
|
483
|
-
break;
|
|
484
|
-
|
|
485
|
-
|
|
486
|
-
|
|
487
|
-
case 9:
|
|
488
|
-
|
|
489
|
-
printf("終了します\n");
|
|
490
|
-
|
|
491
|
-
break;
|
|
492
|
-
|
|
493
|
-
|
|
494
|
-
|
|
495
|
-
default:
|
|
496
|
-
|
|
497
|
-
printf("エラー：メニューの中の数字を入力してください\n");
|
|
498
|
-
|
|
499
|
-
}
|
|
500
|
-
|
|
501
|
-
}while (mn !=9);
|
|
502
|
-
|
|
503
|
-
|
|
504
|
-
|
|
505
|
-
return 0;
|
|
506
|
-
|
|
507
|
-
}
|
|
508
|
-
|
|
509
|
-
|
|
510
|
-
|
|
511
|
-
|
|
512
|
-
|
|
513
|
-
|
|
515
|
+
``````ここに言語を入力
|
|
516
|
+
|
|
517
|
+
ここに言語を入力
|
|
518
|
+
|
|
519
|
+
```
|
|
520
|
+
|
|
521
|
+
コード
|
|
522
|
+
|
|
523
|
+
```
|
|
514
524
|
|
|
515
525
|
|
|
516
526
|
|
|
@@ -534,8 +544,14 @@
|
|
|
534
544
|
|
|
535
545
|
|
|
536
546
|
|
|
537
|
-
### 補足情報（FW/ツールのバージョンなど
|
|
547
|
+
### 補足情報（FW/ツールのバージョンなど
|
|
538
|
-
|
|
539
|
-
|
|
540
|
-
|
|
548
|
+
|
|
549
|
+
|
|
550
|
+
|
|
541
|
-
|
|
551
|
+
初心者で使い方がよく分かっていません
|
|
552
|
+
|
|
553
|
+
ご指摘ください
|
|
554
|
+
|
|
555
|
+
|
|
556
|
+
|
|
557
|
+
コードの挿入の仕方は合っていますでしょうか？？？？
|