実現したいこと
赤黒木かどうかの判定基準である「赤い節点の子は黒い節点」と「根から葉までの黒い節点の数が一致」という二つの条件をそれぞれ判定するプログラム「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()に違反)
まだ回答がついていません
会員登録して回答してみよう