質問編集履歴
3
入出力例を追加
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -96,6 +96,53 @@
|
|
|
96
96
|
}
|
|
97
97
|
```
|
|
98
98
|
|
|
99
|
+
### 入出力例
|
|
100
|
+
入力
|
|
101
|
+
[b]10567,nagano
|
|
102
|
+
[r]10234,tokyo
|
|
103
|
+
[b]10123,kanagawa
|
|
104
|
+
.
|
|
105
|
+
.
|
|
106
|
+
[b]10345,chiba
|
|
107
|
+
.
|
|
108
|
+
[r]10456,aomori
|
|
109
|
+
.
|
|
110
|
+
.
|
|
111
|
+
[b]10678,ishikawa
|
|
112
|
+
.
|
|
113
|
+
.
|
|
114
|
+
出力
|
|
115
|
+
Yes.
|
|
99
116
|
|
|
117
|
+
入力
|
|
118
|
+
[b]10567,nagano
|
|
119
|
+
[r]10234,tokyo
|
|
120
|
+
[r]10123,kanagawa
|
|
121
|
+
.
|
|
122
|
+
.
|
|
123
|
+
.
|
|
124
|
+
[r]10456,aomori
|
|
125
|
+
.
|
|
126
|
+
.
|
|
127
|
+
出力
|
|
128
|
+
No.(check_colorに違反)
|
|
100
129
|
|
|
130
|
+
入力
|
|
131
|
+
[b]chiba
|
|
132
|
+
[b]kanagawa
|
|
133
|
+
.
|
|
134
|
+
[r]tokyo
|
|
135
|
+
.
|
|
136
|
+
.
|
|
137
|
+
[b]10678,ishikawa
|
|
138
|
+
[b]10456,aomori
|
|
139
|
+
.
|
|
140
|
+
[r]10567,nagano
|
|
141
|
+
.
|
|
142
|
+
.
|
|
143
|
+
[r]10890,kumamoto
|
|
144
|
+
.
|
|
145
|
+
.
|
|
146
|
+
出力
|
|
147
|
+
No.(setten()に違反)
|
|
101
148
|
|
2
追加
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -9,6 +9,32 @@
|
|
|
9
9
|
|
|
10
10
|
|
|
11
11
|
```C
|
|
12
|
+
#include<stdio.h>
|
|
13
|
+
#include<stdlib.h>
|
|
14
|
+
char buf[128];
|
|
15
|
+
struct map { int id; char name[32];};
|
|
16
|
+
typedef struct map datatype; /* ← 格納するデータは構造体 student */
|
|
17
|
+
struct rb_node { datatype data; struct rb_node *left, *right; int black; };
|
|
18
|
+
|
|
19
|
+
struct rb_node* get_rbtree() {
|
|
20
|
+
struct rb_node *t;
|
|
21
|
+
char c;
|
|
22
|
+
/* ドットだけなら葉 (NULL) を返す */
|
|
23
|
+
if(fgets(buf,sizeof(buf),stdin)==NULL || buf[0]=='.')
|
|
24
|
+
return NULL;
|
|
25
|
+
else {
|
|
26
|
+
/* ドットでなければ節点を表す構造体のアドレス t を用意 */
|
|
27
|
+
t = (struct rb_node*)malloc(sizeof(struct rb_node));
|
|
28
|
+
/* 色を表す文字を c に、id、名前を t->data に格納 */
|
|
29
|
+
sscanf(buf,"[%c]%d,%[^,]",&c,&t->data.id,t->data.name);
|
|
30
|
+
/* 色の文字が b なら 1、r なら 0 */
|
|
31
|
+
t->black = (c=='b');
|
|
32
|
+
/* 左の子を t->left に、右の子を t->right に格納 */
|
|
33
|
+
t->left = get_rbtree(); t->right = get_rbtree();
|
|
34
|
+
/* t を返す */
|
|
35
|
+
return t;
|
|
36
|
+
}
|
|
37
|
+
}
|
|
12
38
|
int is_red(struct rb_node *t){
|
|
13
39
|
return(t != NULL && !t->black);
|
|
14
40
|
}
|
|
@@ -31,7 +57,7 @@
|
|
|
31
57
|
if(savecount==-1){
|
|
32
58
|
savecount = count;
|
|
33
59
|
return 1;
|
|
34
|
-
}else if(savecount != count){
|
|
60
|
+
}else if(savecount != count){
|
|
35
61
|
return 0;
|
|
36
62
|
}else{
|
|
37
63
|
return 1;
|
|
@@ -49,6 +75,25 @@
|
|
|
49
75
|
}
|
|
50
76
|
return 1;
|
|
51
77
|
}
|
|
78
|
+
|
|
79
|
+
int is_rbtree(struct rb_node *t) {//赤黒木なら1を返す
|
|
80
|
+
int a = 1;
|
|
81
|
+
int b = 1;
|
|
82
|
+
a = check_color(t);
|
|
83
|
+
b = setten(t, 0);
|
|
84
|
+
if(a == 1 && b == 1){//条件2,3に適するならば
|
|
85
|
+
return 1;
|
|
86
|
+
}else{//条件2,3に反するものがあるならば
|
|
87
|
+
return 0;
|
|
88
|
+
}
|
|
89
|
+
}
|
|
90
|
+
|
|
91
|
+
int main() {
|
|
92
|
+
struct rb_node *t = get_rbtree();
|
|
93
|
+
if(is_rbtree(t)) printf("Yes.\n");
|
|
94
|
+
else printf("No.\n");
|
|
95
|
+
return 0;
|
|
96
|
+
}
|
|
52
97
|
```
|
|
53
98
|
|
|
54
99
|
|
1
発生している問題について修正
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -2,8 +2,8 @@
|
|
|
2
2
|
赤黒木かどうかの判定基準である「赤い節点の子は黒い節点」と「根から葉までの黒い節点の数が一致」という二つの条件をそれぞれ判定するプログラム「check_color」と「setten」の作成
|
|
3
3
|
|
|
4
4
|
|
|
5
|
-
### 発生している問題
|
|
5
|
+
### 発生している問題
|
|
6
|
-
以下のように作成したところ、どのような木を入力してもcheck_color()は1,setten()は0を毎回出力するようになってしまっています。
|
|
6
|
+
以下のように作成したところ、どのような木を入力してもcheck_color()は1,setten()は0を毎回出力するようになってしまっています。どこがおかしいのでしょうか。
|
|
7
7
|
|
|
8
8
|
### 該当のソースコード
|
|
9
9
|
|