回答編集履歴

1 加筆修正

majiponi

majiponi score 837

2016/11/16 09:31  投稿

他の方の回答で解決するはずなので、少しだけ小難しい話をします。
自分でコードを書いているとき、何か警告で悩みませんでしたか? C4715って警告が出たから、return 0;を追加した、とか。そういう情報があると、回答者が「あ、もしかして」と気付けるかもしれません。
(他のとある回答者の回答を見た上で、ちょっと気になったので)
んで、今回の問題は、search_tree関数の中の2箇所の間違いが原因です。
1つ目は、xがp->dataと異なるときの挙動です。再帰を使って探しに行く、これはokです。問題は探した後。枝の先で見つかろうが見つからまいが、0を返してします。見つかったら1を返す必要がありますよね。
(枝の先のほうで見つけてreturnしても、一気にmain関数まで戻れません。1つ1つ戻る必要があります。)
2つ目は、枝の先がない場合の処理です。19を探したときにセグメンテーションフォルトというものが出たと思いますが、これは、アクセスしてはいけない場所をアクセスした、という情報です。例えば、メモリの0番地は、BIOSという別のプログラムがいて、勝手に触ってはいけないことになっています。今回、見つからずに枝の先を探していくと、枝の先がヌルポインタを指していることがあり、この中身を触ろうとすると、フォルトを起こして異常終了します。ヌルポインタの場合はそれ以上探索せず、見つからなかったと報告すれば、問題は解決します。
2つ目は、枝の先がない場合の処理です。19を探したときにセグメンテーションフォルトというものが出たと思いますが、これは、アクセスしてはいけない場所をアクセスした、という情報です。例えば、メモリの0番地は、BIOSという別のプログラムがいて、勝手に触ってはいけないことになっています(例外あり)。
プログラムの他の部分で、ポインタにNULLを代入している場所がありますよね? このNULLはヌルポインタと呼ばれ、C言語では「触ってはいけない場所」を意味しています。この中身にアクセスしようとすると、フォルトが発生します。
今回、枝の先を探していくと、枝の先がヌルポインタになっていることがあります。この中身を触ろうとしたため、フォルトが発生して異常終了したのです。
では、どうすればいいのか。簡単です。「中身に」触らなければいいのです。pがヌルポインタの場合はそれ以上探索せず、見つからなかったと報告するようにすればいいのです。
これらを踏まえると、次のコードのようになります。
```C
int search_tree(int x, struct node *p) {
 if (p == NULL)
   return 0;
   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番目の問題を修正  
}
```

思考するエンジニアのためのQ&Aサイト「teratail」について詳しく知る