プログラムについて

質問

２分木のプログラムなのですが、関数部分を作るという学校の問題なのですが、習いはじめで構造体など殆ど分かりません。ヒントでも良いので教えてください。合っていないとは思いますが、一応初期化の部分と、終了の部分、ノードの追加部分は考えました。

typedef struct t_Btree
{
struct t_Btree *left;
struct t_Btree *right;
int data;
} Btree;

// Btreeの初期化
void Btree_ini(Btree *a, int b)
{
a->left=NULL;
a->right=NULL;
a->data=b;
a = (Btree *)malloc(sizeof(Btree));
}
// 領域の開放
void Btree_end(Btree *a, int b)
{
free(a);
}
// 新しいノードを追加
void Btree_ad(Btree *a, int b)
{
Btree_tansaku(a, b);
a = (Btree *)malloc(sizeof(Btree));
self->left_ = NULL;
self->right_ = NULL;
self->data_ = b;
}
// 探索し、bに一致するデータのポインタを返す
void *Btree_tansaku(const Btree *a, int b)
{
}
// aのデータのみを出力
void Btree_pri(const Btree *a)
{
}
// 全体を出力
void Btree_tpri(const Btree *a)
{
}

int main(void)
{
int i;
int d[] = {7,3,6,4,1,9,2,0,10,8};
Btree bt;
Btree_ini(&bt,5);
for(i=0;i<10;i++)
Btree_ad(&bt,x[i]);
Btree_tpri(&bt);
Btree_end(&b);
return 0;
}

おねがいします。

回答No.7

BLUEPIXY

#4>追加しないでやることは可能でしょうか？
関数呼び出ししないで、コードを（もともとやっているように）埋め込みにすればいいだけです。。。

回答No.6

a-saitoh

assert(Btree_tansaku(&b,i) && *Btree_tansaku(&b,i)==i);
は，
Btree_tansaku(&b,i)!=NULL && *Btree_tansaku(&b,i)==i　ってこと
です．つまり，0～10までの数が，バイナリツリーに全部入っているかどうか確認している．

ノードを追加するところは，この問題ではエラーは起きない(mallocに失敗するなどは考えない)のでvoidで出来るでしょう?initの仕様から，addの時には空の木にaddすることは考えなくて良いので．
ただ，void Btree_ad(Btree **a,int b)と，ポインタのポインタを渡す方式の方がシンプルにかけますけどね．

バイナリツリーの定義そのままですので，もう1日よく考えてください．自分で考えて発見する方が本当に身に付くので．

回答No.5

a-saitoh

// 探索し、bに一致するデータのポインタを返す
void *Btree_tansaku(const Btree *a, int b)

データのポインタを返すのなら
int *
でないと駄目なんじゃないですか．

どう考えても，
// 探索し、bに一致するノードのポインタを返す
Btree *Btree_tansaku(const Btree *a, int b)
でないと駄目だと思いますが．
関数の返値だけでなく引数も指定されてて変えてはいけないのでしょうか?

質問文に挙げられた書きかけのプログラムのうち，課題で固定されている変えてはいけない部分とあなたが書いた部分(自由に書いて良い部分)を明確に分離してくださいませんか．

お礼

申し訳ありません。ポインタを返す部分は
const int *Btree_tansaku(const Btree *a, int b)
{
}
の間違いでした。

固定されている関数は
void Btree_ini(Btree *a,int b)
void Btree_end(Btree *a)
void Btree_ad(Btree *a,int b)
const int *Btree_tansaku(const Btree *a,int b)
void Btree_pri(const Btree *a)
void Btree_tpri(const Btree *a)
です。この与えられた関数の形式に従って中身を実装するようです。

メイン部分は以下のとおりです。
int main(void)
{
int i;
int d[] = {7,3,6,4,1,9,2,0,10,8};
Btree bt;
Btree_ini(&bt,5);
for(i=0;i<10;i++)
Btree_ad(&bt,d[i]);
for(i=0;i<=10;i++)
assert(Btree_tansaku(&b,i) && *Btree_tansaku(&b,i)==i);
Btree_tpri(&bt);
Btree_end(&bt);
return 0;
}

色々参考サイトを見てみたのですが、どれもノードを追加する部分で再帰の処理をvoid型でないのを使っていて、void型ではどうして良いのかが、良く分かりません。あと、assertの部分が何をしているのかも良く分かりません。
初期化・開放・プリント部分は分かりました。

回答No.4

BLUEPIXY

#2>関数部分は全てvoidで、変えてはいけないそうです。
＞void *Btree_tansaku(const Btree *a, int b)
は、おかしいんじゃないかと思いますけど・・

＞ノードの追加部分
＃２のプログラムでは、
Btree *Btree_ini(int b){
は、領域の確保と初期化をしています。
なので、
Btree *Btree_new(int b){
とでも名前を変えて別に関数を追加するといいと思います。
その上で
Btree_ini については、
void Btree_ini(Btree *a, int b)
{
if(a){
a->left=NULL;
a->right=NULL;
a->data=b;
}
}
とでもすればいいと思います。
まあ、そんなことは、好きにやればいいかと思いますけど。

お礼

申し訳ありません。

＞＞void *Btree_tansaku(const Btree *a, int b)
＞は、おかしいんじゃないかと思いますけど・・

＃５の方のところに書きました。間違って書いてしまいました。

＞とでもすればいいと思います。
まあ、そんなことは、好きにやればいいかと思いますけど。

追加して、やろうとも思いましたが、問題文を見る限りは追加は良いのかが微妙です。明日聞いてみることにします。追加しないでやることは可能でしょうか？ノードの追加部分がvoid型でなければ色々なサイトに再帰処理で参考になるのが載っているのですが・・・、void型でやっているのを１つも見つけられずに困っています。

回答No.3

Tacosan

この問題と直接の関係はありませんが, 次の 2点を頭の片隅にちょこっと置いておいてください:
Btree と書くと B-tree と思われる可能性があります. 二分探索木 (binary search tree) と B-tree は別物ですので, 名前には一考を要するかと思います.
また, アドバンストな話ですが二分探索木を作るときのセオリーとして
・根になるノードへのポインタを用意しておく
・探索のときには「ノードへのポインタのポインタ」を使う
とプログラムが簡単になります.

お礼

＞Btree と書くと B-tree と思われる可能性があります. 二分探索木 (binary search tree) と B-tree は別物ですので, 名前には一考を要するかと思います.

そうなんですか。問題文にそう書いてあったもので・・・。

＞また, アドバンストな話ですが二分探索木を作るときのセオリーとして
・根になるノードへのポインタを用意しておく
・探索のときには「ノードへのポインタのポインタ」を使う
とプログラムが簡単になります.

ポインタのポインタという概念がいまいち理解できなくて・・・。というか、ポインタ自体まだ習いはじめで殆ど分かっていません。勉強します。

回答No.2

BLUEPIXY

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

typedef struct t_Btree{
struct t_Btree *left;
struct t_Btree *right;
int data;
} Btree;

// Btreeの初期化
Btree *Btree_ini(int b){
Btree *a;

a = (Btree *)malloc(sizeof(Btree));
a->left=NULL;
a->right=NULL;
a->data=b;
return a;
}
// 領域の開放
void Btree_end(Btree *a){
if(a->left!=NULL)
Btree_end(a->left);
if(a->right!=NULL)
Btree_end(a->right);
free(a);
}
// 新しいノードを追加
void Btree_ad(Btree *a, int b){
if(a->data > b){
if(a->left!=NULL){
Btree_ad(a->left, b);
} else {
a->left = Btree_ini(b);
}
} else {
if(a->right!=NULL){
Btree_ad(a->right, b);
} else {
a->right = Btree_ini(b);
}
}
}
// 探索し、bに一致するデータのポインタを返す
const Btree *Btree_tansaku(const Btree *a, int b){
if(a->data == b){
return a;
} else if(a->data > b) {
if(a->left==NULL)
return NULL;
return Btree_tansaku(a->left, b);
} else {
if(a->right==NULL)
return NULL;
return Btree_tansaku(a->right, b);
}
}
// aのデータのみを出力
void Btree_pri(const Btree *a){
if(a!=NULL)
printf("%d\n", a->data);
}
// 全体を出力
void Btree_tpri(const Btree *a){
if(a->left!=NULL)
Btree_tpri(a->left);
Btree_pri(a);
if(a->right!=NULL)
Btree_tpri(a->right);
}

int main(void){
int i;
int d[] = {7,3,6,4,1,9,2,0,10,8};
Btree *bt;

bt=Btree_ini(5);
for(i=0;i<10;i++)
Btree_ad(bt, d[i]);
Btree_tpri(bt);
Btree_end(bt);
return 0;
}

お礼

ありがとうございます。とても参考になったのですが、
関数部分は全てvoidで、変えてはいけないそうです。ですので、ノードの追加部分でヌルだった場合、どう格納すれば良いのでしょうか。

あと、メインでプリントする前にassertを呼び出す場所を書くのを忘れていました。

assert(Btree_tansaku(&bt, i) && *Btree_tansaku(&bt, i) == i);

おねがいします。

回答No.1

a-saitoh

これだと，バイナリツリーにデータが0個格納されている状態が表現できないですね．それで構わないという課題なんでしょうか．

あと根ノードに対応するstruct t_Btreeはmainのauto変数として宣言されていますので，初期化ルーチンでmallocは要りませんね．

・データを入れた　Btreeデータ構造を作る(mallocなど）
・既存の木につなぐ
を分けて考えた方がすっきりすると思います．

補足

ありがとうございます。

関数部分だけを作れという指示で、他は何もありません。