リストに整数値があるか判定するプログラム

質問

↓のプログラムのint ExistTest(struct BTREE *ptr, int searchdata)を、2分木の生成後に入力した整数値がリストの中にあるかどうかを判定するプログラムにしたいのですが、うまくいきません(>_<)

入力された整数値があれば1、なければ0を返したいのですが。。

どなたかお願いしますm(__)m

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

struct BTREE {int data; struct BTREE *left; struct BTREE *right;};
void AddLeaf(struct BTREE **ptr, int newdata);
void TraverseTree (struct BTREE *ptr);
int ExistTest(struct BTREE *ptr, int searchdata);

int ExistTest(struct BTREE *ptr, int searchdata){
if (ptr->data == searchdata){
return 1;
}
else{
ExistTest(ptr->right, searchdata);
}

}

void AddLeaf(struct BTREE **ptr, int newdata){
if (*ptr == NULL){
*ptr = (struct BTREE *)malloc(sizeof(struct BTREE));
(*ptr)->data = newdata;
(*ptr)->left = NULL;
(*ptr)->right = NULL;
}
else if (newdata < (*ptr)->data){
AddLeaf(&(*ptr)->left, newdata);
}
else{
AddLeaf(&(*ptr)->right, newdata);
}
}

void TraverseTree(struct BTREE *ptr){
if (ptr == NULL){
return;
}
else{
TraverseTree(ptr->left);
printf("%3d", ptr->data);
TraverseTree(ptr->right);
}
}

int main(void){
struct BTREE *root = NULL;
int newdata;
int searchdata;
while(1){
printf("data > ");
scanf("%d", &newdata);
if (newdata < 0)break;
AddLeaf(&root, newdata);
TraverseTree(root);
putchar('\n');
}

/*ExistTest*/

/*
printf("num? : "); scanf("%d", &searchdata);
ExistTest(root ,searchdata);
*/

return 0;
}

回答No.2

Oh-Orange · ベストアンサー

●『ExistTest』関数の考え方
・『ExistTest』関数は『AddLeaf』関数に整数値を判定する部分を追加しれば
　簡単に出来ます。既に『AddLeaf』関数は正しく出来ているので、この関数の
　『malloc』部分を『return(0);』として、整数値を判定する部分を挿入すればよい。
・下にサンプルと追加・変更部分を示します。

●サンプル
int ExistTest( struct BTREE *ptr, int searchdata )
{
　if ( ptr == NULL ){
　　return( 0 );　←ここが重要(変更部分)
　}
　else if ( searchdata == ptr->data ){　←整数値の判定(追加部分)
　　return( 1 );　←一致したら 1 を返す
　}
　else if ( searchdata < ptr->data ){
　　return( ExistTest(ptr->left,searchdata) );　←『AddLeaf』関数の Left とほぼ同じ
　}
　else{
　　return( ExistTest(ptr->right,searchdata) );　←『AddLeaf』関数の right とほぼ同じ
　}
}

●『AddLeaf』関数をもっと分かりやすく記述
int AddLeaf( struct BTREE **ptr, int newdata )
{
　struct BTREE *p = *ptr;

　if ( p == NULL ){
　　if ( (p = (struct BTREE *)malloc(sizeof(struct BTREE))) == NULL ){
　　　return( 0 );　←メモリ不足
　　}
　　p->data = newdata;
　　p->left = NULL;
　　p->right = NULL;
　　*ptr = p;
　　return( 1 );　←確保！
　}
　else if ( newdata < p->data ){
　　return( AddLeaf(&p->left,newdata) );
　}
　else{
　　return( AddLeaf(&p->right,newdata) );
　}
}

最後に:
・『AddLeaf』関数の戻り値は、正常ならば 1 を、メモリ不足ならば 0 を返す。
・以上。おわり。

回答No.1

sakusaker7

「うまくいかない」じゃなくて、もう少し具体的に書きましょう。

で、みたところExistTestが未完成なのが問題みたいなのだけど
わからなくて書いていない?
それともポカミス?

int ExistTest(struct BTREE *ptr, int searchdata)
{
if (!ptr)
return 0;
if (ptr->data == searchdata){
return 1;
}
else if (ptr->data > searchdata) {
return ExistTest(ptr->left, searchdata);
}
else{
return ExistTest(ptr->right, searchdata);
}
}

こんな感じにすればとりあえずは動くと思います。

あとお小言(笑)
木を構成する要素のための構造体に TREE はないのではないでしょうか。

それはおいても、二進木(Binary Tree)以外に
B木(B-Tree)ってのがありますので、その意味からも
BTREEって名前はあまりよくないでしょう。