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

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

ただいまの
回答率

90.51%

  • C

    4529questions

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

c言語 2分木の探索

解決済

回答 4

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 998

前提・実現したいこと

関数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);
}
  • 気になる質問をクリップする

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

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

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

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

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

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

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

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

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • PineMatsu

    2016/11/15 18:26

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

    キャンセル

  • 退会済みユーザー

    2016/11/15 18:27

    こちらの質問が他のユーザから「やってほしいことだけを記載した丸投げの質問」という指摘を受けました
    「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。

  • sharow

    2016/11/15 18:35

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

    キャンセル

回答 4

checkベストアンサー

+2

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

自分でコードを書いているとき、何か警告で悩みませんでしたか? 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番目の問題を修正
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/11/17 08:26

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

    キャンセル

+2

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/11/17 01:45

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

    キャンセル

+2

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);↲
  elsereturn 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);
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/11/16 08:35

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

    キャンセル

  • 2016/11/16 09:16

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

    キャンセル

  • 2016/11/16 09:28

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

    キャンセル

  • 2016/11/17 01:51

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

    キャンセル

+1

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

  • メッセージは日本語にしました。
  • 日本語化にあたり、必ず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分木のメモリ解放を行うようにしました。
  • 真と偽はtruefalseを使うようにしました。
  • ?:演算子の方がわかりやすいような気がするときは、変えました。
  • 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;
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/11/16 09:45

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

    キャンセル

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

  • C

    4529questions

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