こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

C言語 2分木探索について質問です

C言語初心者です。

2分木構造体
struct node{
int data;
Tree left_subtree;
Tree right_subtree;
}
を上記のように定義した場合、
2分木の根節点のポインタ struct node *Tree を引数として与えられたとき、
2分木内の節点に保持された整数データの総和を戻り値として返す関数 int sum_data(Tree t);を再帰呼び出しで作成してみたのですが、正しいでしょうか?

■2分木内の節点に保持された整数データの総和を戻り値として返す関数
int sum_data(Tree t)
{
    // 左分木、右分木のどちらも存在しなければ根節点の値を返す
    if ((t->left_subtree == NULL) && (t->right_subtree == NULL)) 
    {
     return t->data;
   }
    else// どちらか存在していれば再帰呼び出しする
   {
     return (t->data + sum_data(t->left_subtree) + sum_data(t->right_subtree))
   }
}

ご指摘ありましたら、お願いしますm(_ _)m

投稿日時 - 2011-05-27 22:20:05

QNo.6768059

困ってます

質問者が選んだベストアンサー

No.6です。

> No.8様
同じ初心者の立場から言わせていただくと、まず2分木のデータを作成すること自体が難しいと思います。
少なくとも私はそうでした。


>トピ主様
私も勉強がてら、試してみました。
2分木作成関数と、mainのみ書いてみますのでご参考になれば幸いです。

Tree new_tree(int data, Tree left, Tree right){
Tree p;
p = (Tree )malloc(sizeof(struct node));
p->data = data;
p->left_subtree = left;
p->right_subtree = right;
return p;
}


int main(void){
Tree top, left, right, bottom;

bottom = new_tree(3, NULL, NULL);
right = new_tree(4, bottom, NULL);
left = new_tree(5, NULL, NULL);
top = new_tree(6, left, right);


printf("sum = %d\n",sum_data(top)); // sum = 18
return 0;
}

投稿日時 - 2011-05-28 11:35:38

お礼

丁寧な回答ありがとうございました。
2分木作成についてもご教授いただきありがとうございました。

他の回答者の方から指摘いただきましたが、
確かに自分でプログラムの動作確認をするという基本的なことをせずに、質問してしまったのは反省すべきだと思いました。次回からの教訓にしたいと思います。

ご回答頂いた皆様ありがとうございました。

投稿日時 - 2011-05-30 19:50:33

ANo.9

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(10)

ANo.10

>#9さん
>2分木のデータを作成すること自体が難しい

まあそりゃそうかもしれませんが、せっかく読み込み用の関数を作ったんだから、
書き込み用も作ってみようかなぁ、なんていう風に質問者さんには思ってほしいなぁ、
なんて思ったりしてるのです。

いちっばん肝心なところを人任せにしてると、いつまでたっても質問者さんの
プログラミング能力は向上しないんじゃないかなぁ、なんて、老婆心ながら。
まあ、人のことだからどうでもいいっちゃいいんですけど。

投稿日時 - 2011-05-28 12:14:26

お礼

プログラミングを学ぶ上で重要な姿勢を教えていただき、ありがとうございました。

投稿日時 - 2011-05-30 19:54:11

ANo.8

自分が作った関数の動きが正しいかどうか、他人にゆだねてどうするんでしょうね。
自分で動かそうとすることに興味がないのかな?

投稿日時 - 2011-05-28 11:20:18

ANo.7

>以下のように関数を作り直してみたのですが、これで良いのでしょうか?

その関数を呼び出すmain関数などを書いて、動作確認してみればいいんじゃないでしょうか。

投稿日時 - 2011-05-28 10:23:55

ANo.6

私も初心者ですが回答させていただきますね。

> // 左分木、右分木のどちらも存在しなければ根節点の値を返す
>     if ((t->left_subtree == NULL) && (t->right_subtree == NULL))

左分木と右分木のどちらか一方だけ存在した場合には対応できずエラーになります。
また、

> t->left_subtree

の様に、引数のメンバのポインタをいきなり参照しているので、引数 tがNULLの場合には対応できません。
(NULLでないという保証があれば良いと思いますが)

ですから、No.4さんの仰るように
・引数tがNULLだったら、0を返す
・そうでなければ、t->data + sum_data(t->left_subtree) + sum_data(t->right_subtree) を返す
というのが良いのではないでしょうか。

投稿日時 - 2011-05-28 08:21:20

補足

引数tはNULLでは無いという前提を書き忘れていました。申し訳ありません。

ご指摘いただいた内容を踏まえて、以下のように関数を作り直してみたのですが、これで良いのでしょうか?


■2分木内の節点に保持された整数データの総和を戻り値として返す関数
int sum_data(Tree t)
{
    // 引数tがNULLならばゼロを返す
    if (t == NULL) 
   {
    return 0;
   }
    else// そうでなけれは、左分木と右分木が存在するか確認する
   {
    return (t->data + sum_data(t->left_subtree) + sum_data(t->right_subtree))
   }
}

投稿日時 - 2011-05-28 09:22:19

ANo.5

>#4さん
もとはと言えば、質問者さんのコードが中途半端であることが原因ですので、
我々(部外者)同士でもめることはやめておきましょうね。

投稿日時 - 2011-05-28 01:18:51

ANo.4

むしろ「2分木の根節点のポインタ struct node *Tree を引数として与えられたとき」と書いてあるだけに困ったんだけど>#3. これだと Tree が引数の名前のように読める.

struct node の宣言の前に
typedef struct node *Tree;
とあって, かつ上の「~」がもっと適切に書いてあれば明瞭なんだが.

「引数が NULL かどうか」でわけるという方針もありますね.

投稿日時 - 2011-05-28 00:53:49

ANo.3

>#2さん
>せめて「Tree とはなんぞや」くらい書いてほしぃ....

>2分木の根節点のポインタ struct node *Tree

って書いてあるように見えるんですが、目の錯覚でしょうか。

投稿日時 - 2011-05-28 00:20:54

ANo.2

せめて「Tree とはなんぞや」くらい書いてほしぃ....

投稿日時 - 2011-05-27 23:32:41

補足

説明不足ですいません。
Treeは構造体node型ポインタで、2分木の根節点(2分木の最上位)へのポインタが格納されています。

まだ不明点があれば、ご指摘願います。

投稿日時 - 2011-05-27 23:45:58

ANo.1

ここまで考えてんならやってみればいいのに。
# おそらくダメですけどね。 NULL参照が発生しますから。

投稿日時 - 2011-05-27 22:26:55

あなたにオススメの質問