c言語 2分木の探索

Question

###前提・実現したいこと
関数int search_tree(int x, struct node *p)だけが空欄になっていて、これを埋めて2文木の中に入力した数字が含まれていればreturn 1、含まれていなければreturn 0となるようにしたいです。main関数でsearch_treeを実行していて、1が返ってこればFound、そうでなければNot Foundと表示されるようになっているみたいです。

###発生している問題・エラーメッセージ
含まれている数字を入力すると全部Not Found(つまりreturn 0になっている)、含まれない数字を入力するとSegmentation fault: 11と出てきます。原因が全く分かりません。どう直せば良いのでしょうか？

(追記)2分木の定義通り、最初の節を見て一致していればreturn 1、値が最初の節より大きければ右の枝に移動、小さければ左の枝に移動して再帰、これを最後に到達するまで続ける、という風にしたつもりでしたが、馬鹿なので30分考えても何がおかしいのか全くわかりませんでした。お願いします。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
1: Not found
19
Segmentation fault: 11

上記は実行結果で、1〜18は木に含まれている数字、下4行は実際に1と19を探索した結果です。

###該当のソースコード

ごめんなさい、一部コピペ漏れがありました…

#include <stdio.h>
#include <stdlib.h>

struct node {
  int data;
  struct node *left;
  struct node *right;
};

struct node *insert_data(int x, struct node *p);
int search_tree(int x, struct node *p);
void print_tree(struct node *p);

int main(int argc, char *argv[]) {
  FILE *fp;
  int i, x;
  struct node *root;

  if (argc != 2) {
    printf("missing file argument\n");
    return 1;
  }

  fp = fopen(argv[1], "r");
  if (fp == NULL) {
    printf("can't open %s\n", argv[1]);
    return 1;
  }

  root = NULL;

  for (i = 0; i < 20; i++) {
    fscanf(fp, "%d", &x);
    root = insert_data(x, root);
  }

  print_tree(root);

  while (1) {
    scanf("%d", &x);
    if (x <= 0)
      break;
    if (search_tree(x, root) == 1)
      printf("%d: Found\n", x);
    else
      printf("%d: Not found\n", x);
  }

  fclose(fp);

  return 0;
}

struct node *insert_data(int x, struct node *p) {
  if (p == NULL) {
    p = (struct node *) malloc(sizeof(struct node));
    if (p == NULL) {
      printf("Out of memory\n");
      exit(1);
    }
    p->data = x;
    p->left = NULL;
    p->right = NULL;

    return p;
  }

  if (x == p->data)
    return p;

  if (x < p->data)
    p->left = insert_data(x, p->left);
  else
    p->right = insert_data(x, p->right);

  return p;
}


int search_tree(int x, struct node *p) {   //自分で書いたのはここです
  if (x == p->data)
    return 1;
  else if (x < p->data)
    search_tree(x, p->left);
  else
    search_tree(x, p->right);

  return 0;
}

void print_tree(struct node *p) {
  if (p == NULL)
    return;

  print_tree(p->left);
  printf("%d\n", p->data);
  print_tree(p->right);
}

Comments

[PineMatsu]

これ、insert_data()が尻切れトンボになっているようです。（括弧の対応がおかしい）。もう一度よく見直して貼り付けなおしてください。このままではコンパイルが通りません。

[sharow]

「学校の課題ではない」と明言されるか何かしたほうがいいと思います。 http://www.hpcs.cs.tsukuba.ac.jp/~msato/lecture-note/sys-prog-ex/sys-prog-ex5.html 。ここは課題を無料でやってもらう場所ではありません。

Answer 1

他の方の回答で解決するはずなので、少しだけ小難しい話をします。

自分でコードを書いているとき、何か警告で悩みませんでしたか? C4715って警告が出たから、return 0;を追加した、とか。そういう情報があると、回答者が「あ、もしかして」と気付けるかもしれません。
(他のとある回答者の回答を見た上で、ちょっと気になったので)

んで、今回の問題は、search_tree関数の中の2箇所の間違いが原因です。

1つ目は、xがp->dataと異なるときの挙動です。再帰を使って探しに行く、これはokです。問題は探した後。枝の先で見つかろうが見つからまいが、0を返してします。見つかったら1を返す必要がありますよね。
(枝の先のほうで見つけてreturnしても、一気にmain関数まで戻れません。1つ1つ戻る必要があります。)

2つ目は、枝の先がない場合の処理です。19を探したときにセグメンテーションフォルトというものが出たと思いますが、これは、アクセスしてはいけない場所をアクセスした、という情報です。例えば、メモリの0番地は、BIOSという別のプログラムがいて、勝手に触ってはいけないことになっています(例外あり)。
プログラムの他の部分で、ポインタにNULLを代入している場所がありますよね? このNULLはヌルポインタと呼ばれ、C言語では「触ってはいけない場所」を意味しています。この中身にアクセスしようとすると、フォルトが発生します。
今回、枝の先を探していくと、枝の先がヌルポインタになっていることがあります。この中身を触ろうとしたため、フォルトが発生して異常終了したのです。
では、どうすればいいのか。簡単です。「中身に」触らなければいいのです。pがヌルポインタの場合はそれ以上探索せず、見つからなかったと報告するようにすればいいのです。

これらを踏まえると、次のコードのようになります。

int search_tree(int x, struct node *p) {
  if (p == NULL)
    return 0; // 2番目の問題を修正

  if (x == p->data)
    return 1;
  else if (x < p->data)
    return search_tree(x, p->left);
  else
    return search_tree(x, p->right);
  // 1番目の問題を修正
}

Comments

[RinT_hinabita39]

ありがとうございます！とても理解の役に立ちました。1回returnしても、木で言うと1つ上の節までしか戻れないので、最終的に適切な値を返せていなかった(どこかしらで必ずint search_tree内のreturn 0の行に辿り着いてしまう)という点が一番のミスですかね…

Answer 2

２箇所を修正しました。
・ファイル読み込みの終了をEOFとしました。
・searchの戻り条件を先頭にしました。

for (i = 0; i < 20; i++) {

fscanf(fp, "%d", &x);
root = insert_data(x, root);

}

  for (i = 0; fscanf(fp, "%d", &x) != EOF; i++) {↲
    root = insert_data(x, root);↲
  }↲

int search_tree(int x, struct node *p) { //自分で書いたのはここです

if (x == p->data)
return 1;
else if (x < p->data)
search_tree(x, p->left);
else
search_tree(x, p->right);
return 0;
}

int search_tree(int x, struct node *p) {   //自分で書いたのはここです↲
  if (p == NULL) return 0;↲
  if (x == p->data)↲
     return 1;↲
  else if (x < p->data)↲
     return search_tree(x, p->left);↲
  else↲
     return search_tree(x, p->right);↲
}↲

全文

#include <stdio.h>
#include <stdlib.h>

struct node {
  int data;
  struct node *left;
  struct node *right;
};

struct node *insert_data(int x, struct node *p);
int search_tree(int x, struct node *p);
void print_tree(struct node *p);

int main(int argc, char *argv[]) {
  FILE *fp;
  int i, x;
  struct node *root;

  if (argc != 2) {
    printf("missing file argument\n");
    return 1;
  }

  fp = fopen(argv[1], "r");
  if (fp == NULL) {
    printf("can't open %s\n", argv[1]);
    return 1;
  }

  root = NULL;

  for (i = 0; fscanf(fp, "%d", &x) != EOF; i++) {
    root = insert_data(x, root);
  }

  print_tree(root);

  while (1) {
    scanf("%d", &x);
    if (x <= 0)
      break;
    if (search_tree(x, root) == 1)
      printf("%d: Found\n", x);
    else
      printf("%d: Not found\n", x);
  }

  fclose(fp);

  return 0;
}

struct node *insert_data(int x, struct node *p) {
  if (p == NULL) {
      p = (struct node *) malloc(sizeof(struct node));
      if (p == NULL) {
          printf("Out of memory\n");
          exit(1);
      }
      p->data = x;
      p->left = NULL;
      p->right = NULL;

      return p;
    }

  if (x == p->data)
    return p;

  if (x < p->data)
    p->left = insert_data(x, p->left);
  else
    p->right = insert_data(x, p->right);

  return p;
}


int search_tree(int x, struct node *p) {   //自分で書いたのはここです
  if (p == NULL) return 0;
  if (x == p->data)
     return 1;
  else if (x < p->data)
     return search_tree(x, p->left);
  else
     return search_tree(x, p->right);
}

void print_tree(struct node *p) {
  if (p == NULL)
    return;

  print_tree(p->left);
  printf("%d\n", p->data);
  print_tree(p->right);
}

Comments

[majiponi]

xとp->dataが異なるときのコントロールパスがありません。(戻り値は、何?)

[A.Ichi]

ご指摘有難うございます、search_treeの最後のリターン値が戻る？(暗黙）でそこではなくて・・・

[A.Ichi]

ご指摘の通りです明示的に戻るように修正いたしました。ご指摘有難うございます。

[RinT_hinabita39]

他の方の説明を読んで理解した後に、searchの戻り条件を先頭にしている訳が理解できました。ありがとうございます。

Answer 3

一つすぐに分かることと言えば、p->leftやp->rightがNULLの場合もあるということです。
NULLならそこからの探索は意味がありません。

Comments

[RinT_hinabita39]

NULLならxはp->dataと等しくなく、それより大きくも小さくもないので、最後のreturn 0をするというつもりだったのですが、他の方の説明から考えると、return 0の行に辿り着くには、NULL->dataに相当することを行わないといけないことになるので、そこが不味かったっぽいですね… ありがとうございました。

Answer 4

気になるところがたくさんあったので、大きく書き換えました。

• メッセージは日本語にしました。
• 日本語化にあたり、必ずUTF-8になるようにしました。UTF-8環境で実行するようにしてください。
• intでは小さいかも知れないので、intmax_tで最大限対応できるようにしました。
• 2分木を解放するためにfree_tree()を追加しました。
• constにできる引数はconstにしました。
• ファイルを読み込んで2分木にするコードをread_data()として分離しました。
• メッセージを吐いて終わる所die()でまとめました。die()はnoreturnをつけて、処理が返らないことを明確にしました。
• エラーメッセージは標準エラー出力に出すようにしました。
• ファイル読み込みは最後まで行うようにしました。20個しか読み込まない理由がわからない。
• 数字でないところは読み飛ばすようにしました。
• ファイルの読み込み途中でエラーが発生した場合は、エラーメッセージを出して終了するようにしました。
• 入力終わりは標準入力が閉じられることで終了するようにしました。MacやLinuxはCtrl+D、WindowsはCtrl+Zで終わります。
• 終わる前に2分木のメモリ解放を行うようにしました。
• 真と偽はtrueとfalseを使うようにしました。
• ?:演算子の方がわかりやすいような気がするときは、変えました。
• if-else分は必ずブロックにするようにしました。
• {の前で改行するかはK&Rスタイルにしました。

#include <errno.h>
#include <inttypes.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdnoreturn.h>
#include <string.h>

#define MSG_ERR_INVALID_ARGS \
	u8"引数が無いか、多すぎます。引数でファイル名を指定してください。"
#define MSG_ERR_FAIL_OPEN_FILE u8"ファイルを開けません。"
#define MSG_ERR_FAIL_READ_FILE u8"ファイルの読み込みに失敗しました。"
#define MSG_ERR_NO_MEMORY u8"メモリ不足です。"
#define MSG_FOUND_NUMBER u8"見つかりました。"
#define MSG_NOT_FOUND_NUMBER u8"見つけられませんでした。"

struct node {
	intmax_t data;
	struct node *left;
	struct node *right;
};

struct node *insert_data(intmax_t x, struct node *p);
void free_tree(struct node *p);
bool search_tree(intmax_t x, const struct node *p);
void print_tree(const struct node *p);
struct node *read_data(FILE *fp);

static inline noreturn void die(const char *restrict format, ...)
{
	va_list args;
	va_start(args, format);
	vfprintf(stderr, format, args);
	va_end(args);
	exit(1);
}

int main(int argc, char *argv[])
{
	if (argc != 2) die("%s\n", MSG_ERR_INVALID_ARGS);

	FILE *fp = fopen(argv[1], "r");
	if (fp == NULL) die("%s: %s\n", MSG_ERR_FAIL_OPEN_FILE, argv[1]);
	struct node *root = read_data(fp);
	fclose(fp);
	if (root == NULL)
		die("%s: %s\n", MSG_ERR_FAIL_READ_FILE, strerror(errno));

	print_tree(root);

	{
		int i;
		intmax_t x;
		while ((i = scanf("%" SCNdMAX, &x)) != EOF) {
			if (i == 0) {
				scanf("%*c");
				continue;
			}
			printf("%" PRIdMAX ": %s\n", x, search_tree(x, root)
				? MSG_FOUND_NUMBER
				: MSG_NOT_FOUND_NUMBER);
		}
	}

	free_tree(root);
	root = NULL;

	return 0;
}

struct node *insert_data(intmax_t x, struct node *p)
{
	if (p == NULL) {
		p = (struct node *)malloc(sizeof(struct node));
		if (p == NULL) die("%s\n", MSG_ERR_NO_MEMORY);
		p->data = x;
		p->left = NULL;
		p->right = NULL;
		return p;
	}

	if (x != p->data) {
		if (x < p->data) {
			p->left = insert_data(x, p->left);
		} else {
			p->right = insert_data(x, p->right);
		}
	}
	return p;
}

void free_tree(struct node *p)
{
	if (p->left != NULL) free_tree(p->left);
	if (p->right != NULL) free_tree(p->right);
	free(p);
}

bool search_tree(intmax_t x, const struct node *p)
{
	if (p == NULL) return false;
	if (x == p->data) return true;
	return search_tree(x, x < p->data ? p->left : p->right);
}

void print_tree(const struct node *p)
{
	if (p == NULL) return;
	print_tree(p->left);
	printf("%" PRIdMAX "\n", p->data);
	print_tree(p->right);
}

struct node *read_data(FILE *fp)
{
	struct node *root = NULL;
	int i;
	intmax_t x;
	errno = 0;
	while ((i = fscanf(fp, "%" SCNdMAX, &x)) != EOF) {
		if (i == 0) {
			fscanf(fp, "%*c");
			continue;
		}
		root = insert_data(x, root);
	}
	if (errno != 0) return NULL;
	return root;
}

Comments

[majiponi]

(私が言えることではないけど)説明が長すぎて分かりづらく、肝心の「探索関数のどこがまずくて、どこをどう修正したか」の説明が抜けています(コード読めば分かりますけど)。ただ、指摘されているような問題があることには、概ね同意します。(評価しないとは言っていない)