二分木中の要素数を求める

[ゆきもちこ]

大学の課題でどうしても作成できないプログラムがあります。
どうか力を貸してください!!!
[二分木中の要素数の個数を求める関数 int tree_size(struct _node* tree);を定義せよ。]
と言う問題なんです。

プログラム全体を作る必要はなく、tree_sizeの関数内を
作成すれば良い形になっています。
/*oct10_1.c二分木*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>


/*二分木のデータ構造*/
struct _node
{
struct _node *left;
int data;
struct _node *right;
};

/*プロトタイプ宣言*/
struct _node* new_node(struct _node* left, int data, struct _node* right);
int tree_size(struct _node* tree);

/*main関数*/
int main(void)
{


struct _node* test = new_node(new_node(new_node(NULL, 1, NULL), 6, new_node(NULL, 11, NULL)),
4,
new_node(new_node(NULL, 4, NULL), 5, new_node(NULL, 0, NULL)));

struct _node* test1 = new_node(test, 8, test); // tree_size(test1) の要素数は15になる
struct _node* test2 = new_node(test1, 9, test1); // tree_size(test2) の 要素数は31
struct _node* test3 = new_node(test2, 10, test1); // tree_size(test3) の 要素数は47



printf("要素数:%d", tree_size(test3));

return 0;
}

/*新しいノードを追加*/
struct _node* new_node(struct _node* left, int data, struct _node* right)
{
struct _node* ret = (struct _node*)malloc(sizeof(struct _node));
ret->left = left;
ret->data = data;
ret->right = right;
return ret;
}


/*二分木中の要素数を求める関数*/
int tree_size(struct _node* tree)
{
/*この部分を考える。*/

}

どうすれば要素数を求められるのでしょうか？
どうか教えてくださいお願いします(uc_,u*)

[box]

二分木をなぞっていく方法には
　・行きがけ順（preorder）
　・通りがけ順（inorder）
　・帰りがけ順（postorder）
の３種類があります。

このあたりの話を聞かれたことはありますか？

[ゆきもちこ]

コメントありがとうございます！

二分木のトラバーサルの話は聞いたことがあります。
このプログラムの場合は、（帰りがけ順で表すと）
tree_size(tree->left);
tree_size(tree->right);
printf("%d\n", tree->data);
となると考えています。
この探っていくなかで、どのように要素をカウントすればよいのか分かりません。

質問する前に、大域変数やstatic変数を使って要素数をカウントするように作ったのですが
これは使ってはいけませんと言われました。

[box]

> このプログラムの場合は、（帰りがけ順で表すと）
> tree_size(tree->left);
> tree_size(tree->right);
> printf("%d\n", tree->data);
> となると考えています。

大筋の考え方は正しいです。
ただ、左部分木や右部分木をなぞるには１つ条件を加えることが必要です。
それは、「左右の部分木は、いつかはNULLになることを考慮する」です。
この点を考慮しないと、NULLの先をなぞろうとしてプログラムが異常終了します。

> この探っていくなかで、どのように要素をカウントすればよいのか分かりません。

上記のprintfでノードのデータを参照しているところで、
そのノードに立ち寄ったことになります。
今回はメンバーdataは特に参照する必要がなさそうですので、参照するかわりに
要素数のカウントを１増やせばよいです。

また、左右の部分木をなぞった結果、各々の部分木にいくつ要素があったかが
返ってくるようにする必要もあります。

後は、要素数のカウントの初期化や、呼び出し元にカウント値を返す文を加えれば、完成します。
大域変数やstaticを使わなくてもできます。

なお、要素数のカウントの場合、部分木のなぞり方は
行きがけ順・通りがけ順・帰りがけ順のどれでも同じ結果を得ます。
当たり前のことですけれど。
例えば、帰りがけ順でなぞった結果、
・左部分木には４個の要素があった
・右部分木には７個の要素があった
・自分の分は１個
という場合、全部で４＋７＋１＝１２個の要素があることになります。

[ゆきもちこ]

分かりやすい説明大変感謝します。

次のポイント、
>それは、「左右の部分木は、いつかはNULLになることを考慮する」です。
>今回はメンバーdataは特に参照する必要がなさそうですので、参照するかわりに
要素数のカウントを１増やせばよいです。
>また、左右の部分木をなぞった結果、各々の部分木にいくつ要素があったかが
返ってくるようにする必要もあります。
>後は、要素数のカウントの初期化や、呼び出し元にカウント値を返す文を加えれば、完成します。
大域変数やstaticを使わなくてもできます。
を踏まえて考えてみた結果

/*二分木中の要素数を求める関数*/
int tree_size(struct _node* tree)
{
/*要素数のn, 自分の分n1,左分木n2,右分木n3*/
int n, n1=0, n2,n3;
/*データが存在しない場合*/
if(tree==NULL){
return 0;
/*データが存在する場合*/
}else{
n2=tree_size(tree->left);
n3=tree_size(tree->right);
n1++;
}

n=n1+n2+n3;

return n;
}

となりました。
結果、要素数は47となり、上手く実装できました。
大変ありがとうございます!!!!

このプログラムで、特にもう問題はないでしょうか？

[box]

> このプログラムで、特にもう問題はないでしょうか？

はい。問題ありません。
参考までに、「こんな書き方もある」というのを提示いたします。

int tree_size(struct _node *tree)
{
	return (tree) ? tree_size(tree->left) + tree_size(tree->right) + 1 : 0;
}

ゆきもちこさんのコードを簡略化できないか？について
考えているときに思いつきました。

[ゆきもちこ]

お力添え本当にありがとうございました。


>参考までに、「こんな書き方もある」というのを提示いたします。

boxさんの書き方はとても簡略化されていて素晴らしいです。
大変勉強になりました。
まだまだ私は勉強不足だと痛感しました。

おかげさまで今日無事に課題を提出することが出来ました。
ありがとうございました!!!!!