バイナリーツリーのノードの数をリカージョンを使って数えるメソッド

いつもお世話になっています。
リカージョンを使って、バイナリーツリーのノードの数を調べるメソッドを作っているんですが、

boolean isEmpty()
ツリーのノードが0ならtrueを返す
RecBinTree leftSubtree()
ルートの左のサブツリーを返す
RecBinTree reightSubtree()
ルートの右のサブツリーを返す

この３つのメソッドを使っていいのですが、

public static int numNodes( RecBinTree t){

int result;

if( !t.isEmpty()){
???
}
return result;
}

この？？？部分をどのように埋めたら、resultに全てのノードの数が帰るようにできるでしょうか？
きっと単純なコードなんだろうけど、なんだかさっぱりわからなくなってしまっています。
いってる意味が分からなかったらごめんなさい。
どなたか教えて頂けたら幸いです。私にはもう無理みたいなんで・・。よろしくお願いします。

No.4 ベストアンサー 回答者： BLUEPIXY 回答日時： 2006/08/04 13:51

＃３＞１を足すのは、一番先端のルートを数えるためなんでしょうか？

今調べようとしているノードｔがisEmpty でないということは、
ｔが少なくともノードになっているということですよね。
左のノード←ｔ→右のノード
となっていて
左のノードは、０かもしれないし、いくつかあるかもしれない
右のノードは、０かもしれないし、いくつかあるかもしれない
けど、とりあえず、現時点でｔがノードであることは分かっているので、自分自身の１を足します。

この回答へのお礼

なるほど、分かりました。ありがとうございます。
早くプログラミングになれるように頑張りたいです！

お礼日時：2006/08/04 16:53

No.5 回答者： sakusaker7 回答日時： 2006/08/04 15:07

ちょっと確認です。

いわゆる二分木(バイナリツリー)でいうところの「葉」の数は
「ノード」の数には含まれないのでしょうか?
#「葉」→子供を持たない一番下の要素

isEmptyは葉のときにtrue を返し、かつ全体のノードの数に含めると思ったのですが。

で、

> 右と左のサブツリーを返すメソッドを繰り返していると、最終的にはルート（自分）が返ってくるのでしょうか？

あるノードから数えたすべてのノードの数は、そのノードの右側の
子供の合計と左側の子供の合計＋1（自分）です。で、その子供の下にある
ノードの数を求めるには、その子供が持っている孫の合計＋1とします
（これはいいですか?）
これをひ孫→玄孫→その子供… と末端に行くまで潜っていくわけです。

図が描けるといいんですけどねえ(^^;

参考URL：http://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86% …

この回答へのお礼

葉の数は、ノードの数に含まれています。ツリーの全てのエレメントを数えたかったんです。
おかげで大分分かってきました。本当にありがとうございます。

お礼日時：2006/08/04 16:50

No.3 回答者： BLUEPIXY 回答日時： 2006/08/04 05:55

public static int numNodes( RecBinTree t){

int result;

if( t.isEmpty()){
result = 0;
} else {
result = 1 + numNodes(t.leftSubtree()) + numNodes(t.rightSubtree()); // right → reight?
}
return result;
}
てな感じでいいんじゃないかなあ、よくわからないけど

この回答へのお礼

また回答いただいてありがとうございます！
rightSubtree() と　leftSubtree()　で返ってきた
ものを足すんですね。１を足すのは、一番先端のルートを数えるためなんでしょうか？

お礼日時：2006/08/04 13:00

No.2 回答者： sakusaker7 回答日時： 2006/08/04 00:42

もうちょっとヒントを。

・子供を持たないノード → 1を返す
・子供を持つノード →
　　右の子供のノードの数
　　　　+
　左の子供のノードの数
　　　　+
　　　　1　(自分)

です。これを根元から再帰的に適用してやれば全体のノードの数が求まります。
子供のノードの数を求めるところで、再帰しています。

この回答へのお礼

回答ありがとうございます。
右と左のサブツリーを返すメソッドを繰り返していると、最終的にはルート（自分）が返ってくるのでしょうか？もうちょっと調べてみます。

お礼日時：2006/08/04 12:54

No.1 回答者： noname#19197 回答日時： 2006/08/03 19:57

何かの課題でしょうか？

再帰ロジックを使えば簡単にできますよ。
まずは、再帰について調べてみて下さい。

ツリー構造の操作は再帰が必須になってきますので、覚えて損はないと思います。

この回答へのお礼

ありがとうございます。再帰のことは一応簡単な知識はあるのですが、何せ初心者なもので、実際にコーディングをすると、できなくなってしまうことがよくあるんです。ものすごい時間を費やしてはいるんですが、一度どつぼにはまると大変ですね、プログラミングって。

お礼日時：2006/08/04 12:51