Q&A
newp は実際には使われていないので無視。削除してもOK。
前提・実現したいこと
現在、大学の課題のアルゴリズムで２分木のところをやっているのですが、資料も全然説明がないので困っています。
C言語は基本的な知識しかなく、まだまだ未熟です。
このサイトを使うのは初めてなので、失礼なことがあったら申し訳ありません。
２時間くらいコードを見つめて考えていたんですが、やっぱりわからないです。
知りたいのはこのinsert関数でどのように処理をしているのかということです。
まず初めに、最初のstruct vertex f とnewpを宣言していますがこのfとnewpって何かわかりますか？
do~whileはまずdoの中身を実行してからwhile文の条件式に当てはまれば繰り返し実行するのですよね。
insert(10)ってところまではなんとなく？わかったのですが、insert(11)からf->dataやf->lがでてきて？？ってなりました。
fのdataなんかどこにも設定はされていないはずだし、比較する意味はあるのか？と全然わからないです。
この関数においてfやnewpはなんのことなのでしょうか？
lとrはなんとなくleftとrightなんだなというのはわかるのですが...
わからないコード
void insert(struct vertex *p, int x) /* 2分木にxを挿入 */ { struct vertex *f, *newp; do { /* insert(1) */ f = p; /* insert(2) */ if (x < p->data) /* insert(3) */ p = p->l; /* insert(4) */ else /* insert(5) */ p = p->r; /* insert(6) */ } while (p != NULL); /* insert(7) */ p = newv(); /* insert(8) */ p->data = x; /* insert(9) */ p->l = p->r = NULL; /* insert(10) */ if (x < f->data) /* insert(11) */ f->l = p; /* insert(12) */ else /* insert(13) */ f->r = p; /* insert(14) */ }
該当のソースコード
C言語
1#include <stdio.h> 2#include <stdlib.h> 3 4 5struct vertex { /*頂点を表す構造体の定義 */ 6 int data; 7 struct vertex *l, *r; 8}; 9 10struct vertex *newv() /* ヘッダのメモリー領域を確保 */ 11{ 12 return((struct vertex *) malloc(sizeof(struct vertex))); 13} 14 15struct vertex *create() /* 空の2分木のセルを生成 */ 16{ 17 struct vertex *p; 18 19 p = newv(); /* create(1) */ 20 p->data = 0; /* create(2) */ 21 p->r = NULL; /* create(3) */ 22 p->l = NULL; /* create(4) */ 23 return(p); 24} 25 26 27 28void insert(struct vertex *p, int x) /* 2分木にxを挿入 */ 29{ 30 struct vertex *f, *newp; 31 do { /* insert(1) */ 32 f = p; /* insert(2) */ 33 if (x < p->data) /* insert(3) */ 34 p = p->l; /* insert(4) */ 35 else /* insert(5) */ 36 p = p->r; /* insert(6) */ 37 } while (p != NULL); /* insert(7) */ 38 39 p = newv(); /* insert(8) */ 40 p->data = x; /* insert(9) */ 41 p->l = p->r = NULL; /* insert(10) */ 42 if (x < f->data) /* insert(11) */ 43 f->l = p; /* insert(12) */ 44 else /* insert(13) */ 45 f->r = p; /* insert(14) */ 46} 47 48 49 50int member(struct vertex *p, int x) /* 2分木内のセルの探索 */ 51{ 52 do { /* member(1) */ 53 if (x < p->data) /* member(2) */ 54 p = p->l; /* member(3) */ 55 else /* member(4) */ 56 p = p->r; /* member(5) */ 57 } while(p != NULL && x != p->data); /* member(6) */ 58 return(p != NULL); /* member(7) */ 59} 60 61void deleteb(struct vertex *p, int x) /* 2分木内にあるセルを削除 */ 62{ 63 struct vertex *f, *q; 64 65 do { /* deleteb(1) */ 66 f = p; /* deleteb(2) */ 67 if (x < p->data) /* deleteb(3) */ 68 p = p->l; /* deleteb(4) */ 69 else /* deleteb(5) */ 70 p = p->r; /* deleteb(6) */ 71 } while(p != NULL && x != p->data); /* ｘを探索 deleteb(7) */ 72 if (p == NULL) /* ｘが見つからない deleteb(8) */ 73 return; /* deleteb(9) */ 74 if (p->l == NULL || p->r == NULL){ /* 一方の子がない deleteb(10) */ 75 if (p->r == NULL) /* deleteb(11) */ 76 q = p->l; /* deleteb(12) */ 77 else /* deleteb(13) */ 78 q = p->r; /* deleteb(14) */ 79 if (f->l == p) /* deleteb(15) */ 80 f->l = q; /* deleteb(16) */ 81 else /* deleteb(17) */ 82 f->r = q; /* deleteb(18) */ 83 } 84 else { /* 二つの子がある deleteb(19) */ 85 q = p->r; /* deleteb(20) */ 86 f = q; /* deleteb(21) */ 87 while(q->l != NULL){ /* deleteb(22) */ 88 f = q; /* deleteb(23) */ 89 q = q->l; /* deleteb(24) */ 90 } /* deleteb(25) */ 91 p->data = q->data; /* deleteb(26) */ 92 if (q == f) /* deleteb(27) */ 93 p->r = q->r; /* deleteb(28) */ 94 else /* deleteb(29) */ 95 f->l = q->r; /* deleteb(30) */ 96 } 97} 98 99 100 101void printtree_preorder(struct vertex *p) /* 2分木を行きがけ順に印刷 */ 102{ 103 if(p == NULL) /* printtree_preorder(1) */ 104 return; /* printtree_preorder(2) */ 105 else{ /* printtree_preorder(3) */ 106 printf(" p->data = %d\n", p->data); /* printtree_preorder(4) */ 107 printtree_preorder(p->l); /* printtree_preorder(5) */ 108 printtree_preorder(p->r); /* printtree_preorder(6) */ 109 } 110} 111 112 113 int main() 114{ 115 int x; 116 struct vertex *root; 117 118 root = create(); /* main(1) */ 119 printf("Next integer(0:end) = "); /* main(2) */ 120 scanf("%d", &x); /* main(3) コンソールから整数を読み込む */ 121 while (x != 0) { /* main(4) */ 122 insert(root, x); /* main(5) 2分木に挿入する */ 123 printf("Next integer(0:end) = "); /* main(6) */ 124 scanf("%d", &x); /* main(7) */ 125 } 126 printtree_preorder(root->r); /* main(8) */ 127 128 printf("member(0:end) = "); /* main(9) */ 129 scanf("%d", &x); /* main(10) */ 130 while (x != 0 ){ /* main(11) */ 131 if (member(root, x) == 1) /* main(12) */ 132 printf("Yes\n"); /* main(13) */ 133 else printf("No\n"); /* main(14) */ 134 printf("member(0:end) = "); /* main(15) */ 135 scanf("%d", &x); /* main(16) */ 136 } 137 138 printf("add(0:end) = "); /* main(17) */ 139 scanf("%d", &x); /* main(18) */ 140 while (x != 0 ){ /* main(19) */ 141 insert(root, x); /* main(20) */ 142 printtree_preorder(root->r); /* main(21) 2分木の印刷 */ 143 printf("add(0:end) = "); /* main(22) */ 144 scanf("%d", &x); /* main(23) */ 145 } 146 147 printf("delete(0:end) = "); /* main(24) */ 148 scanf("%d", &x); /* main(25) */ 149 while (x != 0 ){ /* main(26) */ 150 deleteb(root, x); /* main(27) */ 151 printtree_preorder(root->r); /* main(28) 2分木の印刷 */ 152 printf("delete(0:end) = "); /* main(29) */ 153 scanf("%d", &x); /* main(30) */ 154 } 155 156 } 157
補足情報（FW/ツールのバージョンなど）
Cygwinで実行しています。
回答3件
0
何をしているかわからないのであれば、まず日本語の文章で理解してみてはいかがでしょうか。
コードを見ると、これは単なる二分木ではなく二分探索木ですね。
の「操作」のあたりの文章を読んでからコードを読めばいいかと。
なお、insertの中のfは、最初のdo whileループの中で既存のノードをたどりつつ得られたpの値が設定されているので、f->dataは存在します。
投稿2020/06/17 09:45
編集2020/06/17 09:46総合スコア11990
回答ありがとうございます。
ちょっとずつわかりつつあるのですが、insert(4)とinsert(6)は何をしているのでしょうか？
p->lとp->rは両方ともNULLで何も入っていないですよね。
それにｐの中にいれているのに、そのあとのinsert(8)でnewv()を使ったら上書きされて、探索した
意味がなくなりませんか...?
初歩的な質問ですみません。
0
ベストアンサー
f は新たなノードを繋ぐ親。
- (1)～(7)でノードをどの親に繋ぐかをfに求め、
- (8)～(10)で新たなノードpを作り、
- (11)～(14)でfの子としてpを(右か左に)繋いでる。
投稿2020/06/17 09:39
編集2020/06/17 10:43
総合スコア16612
回答ありがとうございます。
ちょっとずつわかりつつあるのですが、insert(4)とinsert(6)は何をしているのでしょうか？
p->lとp->rは両方ともNULLで何も入っていないですよね。
それにｐの中にいれているのに、そのあとのinsert(8)でnewv()を使ったら上書きされて、探索した
意味がなくなりませんか...?
初歩的な質問ですみません。
「(1)～(7)でノードをどの親に繋ぐかを f に求め、」です。「pに求め」ではありません。
でもfに求めとおっしゃっていますが、（１）～（７）でｆを使っているのはinsert(2)だけじゃないですか？
そうですよ。子の枝がNULLである(からソコに繋ぐことができる)ノードが f です。
0
たぶんですが
f: found、挿入箇所
newp: 新規ノード(のつもりが、未使用)
です。
do-whileループにて挿入箇所を探索し
insert(8～10)にて新規ノードを作成し
fを親として挿入しています。
投稿2020/06/17 09:38
総合スコア15149
あなたの回答
tips
プレビュー
