赤黒木の判定について

Question

実現したいこと

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

発生している問題

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

該当のソースコード

#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()に違反)

Comments

[mizutani.cs]

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

[y_waiwai]

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

[mizutani.cs]

はい、お待ちください

[shiracamus]

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

[mizutani.cs]

わかりました

[mizutani.cs]

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

[thkana]

クラスメイトかしら? ご参考まで。
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q10259174745

[jimbe]

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

[mizutani.cs]

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

[jimbe]

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

[mizutani.cs]

はい。

[jimbe]

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

[mizutani.cs]

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