質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
87.20%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

解決済

赤黒木の判定について

mizutani.cs
mizutani.cs

総合スコア3

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

1回答

0評価

0クリップ

414閲覧

投稿2022/03/27 01:21

編集2022/03/27 22:35

実現したいこと

赤黒木かどうかの判定基準である「赤い節点の子は黒い節点」と「根から葉までの黒い節点の数が一致」という二つの条件をそれぞれ判定するプログラム「check_color」と「setten」の作成

発生している問題

以下のように作成したところ、どのような木を入力してもcheck_color()は1,setten()は0を毎回出力するようになってしまっています。どこがおかしいのでしょうか。

該当のソースコード

C

#include<stdio.h> #include<stdlib.h> char buf[128]; struct map { int id; char name[32];}; typedef struct map datatype; /* ← 格納するデータは構造体 student */ struct rb_node { datatype data; struct rb_node *left, *right; int black; }; struct rb_node* get_rbtree() { struct rb_node *t; char c; /* ドットだけなら葉 (NULL) を返す */ if(fgets(buf,sizeof(buf),stdin)==NULL || buf[0]=='.') return NULL; else { /* ドットでなければ節点を表す構造体のアドレス t を用意 */ t = (struct rb_node*)malloc(sizeof(struct rb_node)); /* 色を表す文字を c に、id、名前を t->data に格納 */ sscanf(buf,"[%c]%d,%[^,]",&c,&t->data.id,t->data.name); /* 色の文字が b なら 1、r なら 0 */ t->black = (c=='b'); /* 左の子を t->left に、右の子を t->right に格納 */ t->left = get_rbtree(); t->right = get_rbtree(); /* t を返す */ return t; } } int is_red(struct rb_node *t){ return(t != NULL && !t->black); } int check_color(struct rb_node *t){//条件 if(is_red(t) == 1){ if(is_red(t->left) == 1 || is_red(t->right) == 1){//赤い節点の子が赤ならば return 0;//条件に反するので0を返す } } check_color(t->left); check_color(t->right); return 1;//条件に適するので1を返す } int savecount; int setten(struct rb_node *t, int count){//条件3 count += t->black; if(!t->left && !t->right){ if(savecount==-1){ savecount = count; return 1; }else if(savecount != count){ return 0; }else{ return 1; } } if(t->left){ if(setten(t->left,count)==0){ return 0; } } if(t->right){ if(setten(t->right,count)==0){ return 0; } } return 1; } int is_rbtree(struct rb_node *t) {//赤黒木なら1を返す int a = 1; int b = 1; a = check_color(t); b = setten(t, 0); if(a == 1 && b == 1){//条件2,3に適するならば return 1; }else{//条件2,3に反するものがあるならば return 0; } } int main() { struct rb_node *t = get_rbtree(); if(is_rbtree(t)) printf("Yes.\n"); else printf("No.\n"); return 0; }

入出力例

入力
[b]10567,nagano
[r]10234,tokyo
[b]10123,kanagawa
.
.
[b]10345,chiba
.
[r]10456,aomori
.
.
[b]10678,ishikawa
.
.
出力
Yes.

入力
[b]10567,nagano
[r]10234,tokyo
[r]10123,kanagawa
.
.
.
[r]10456,aomori
.
.
出力
No.(check_colorに違反)

入力
[b]chiba
[b]kanagawa
.
[r]tokyo
.
.
[b]10678,ishikawa
[b]10456,aomori
.
[r]10567,nagano
.
.
[r]10890,kumamoto
.
.
出力
No.(setten()に違反)

良い質問の評価を上げる

以下のような質問は評価を上げましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

  • プログラミングに関係のない質問
  • やってほしいことだけを記載した丸投げの質問
  • 問題・課題が含まれていない質問
  • 意図的に内容が抹消された質問
  • 過去に投稿した質問と同じ内容の質問
  • 広告と受け取られるような投稿

評価を下げると、トップページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

mizutani.cs

2022/03/27 01:24

setten()に渡すcountには、main関数から0を渡しています。
y_waiwai

2022/03/27 01:33

コードは全部のせましょう
mizutani.cs

2022/03/27 01:34

はい、お待ちください
shiracamus

2022/03/27 01:41

入力データ例と期待する結果をいくつか、質問に追記していただけませんか?
mizutani.cs

2022/03/27 01:55

違反理由は出力しないですが参考に載せました。
jimbe

2022/03/27 08:50 編集

ご提示のコードを実行しても入出力例のように出来ないみたいですけど。
mizutani.cs

2022/03/27 08:42 編集

入出力例は、あくまで「本来こうなるべき」という意味であって提示したプログラムです。勘違いさせるような記述をしてしまい申し訳ありません。
jimbe

2022/03/27 10:22

入出力例の最初の Yes になるはずの入力では、その入力によってどのようなツリーが出来ているか確認されていますでしょうか。
jimbe

2022/03/27 13:12

ご提示の get_rbtree を使って出来たツリーを見ると、 check_color 違反になる構造になってしまうのですが…。
mizutani.cs

2022/03/27 13:35

ごめんなさい、少しいじったget_rbtreeを提示したためどこかがおかしくなっているのだと思います。shiracamusさんが作成したものを使っていただければ正しく動作すると思います。すみませんでした。

まだ回答がついていません

会員登録して回答してみよう

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
87.20%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。