- ベストアンサー
バイナリーツリーのノードの数をリカージョンを使って数えるメソッド
いつもお世話になっています。 リカージョンを使って、バイナリーツリーのノードの数を調べるメソッドを作っているんですが、 boolean isEmpty() ツリーのノードが0ならtrueを返す RecBinTree leftSubtree() ルートの左のサブツリーを返す RecBinTree reightSubtree() ルートの右のサブツリーを返す この３つのメソッドを使っていいのですが、 public static int numNodes( RecBinTree t){ int result; if( !t.isEmpty()){ ??? } return result; } この？？？部分をどのように埋めたら、resultに全てのノードの数が帰るようにできるでしょうか？ きっと単純なコードなんだろうけど、なんだかさっぱりわからなくなってしまっています。 いってる意味が分からなかったらごめんなさい。 どなたか教えて頂けたら幸いです。私にはもう無理みたいなんで・・。よろしくお願いします。
- yukikoba1977
- お礼率80% (12/15)
- Java
- 回答数5
- ありがとう数5
- みんなの回答 （5）
- 専門家の回答
質問者が選んだベストアンサー
＃３＞１を足すのは、一番先端のルートを数えるためなんでしょうか？ 今調べようとしているノードｔがisEmpty でないということは、 ｔが少なくともノードになっているということですよね。 左のノード←ｔ→右のノード となっていて 左のノードは、０かもしれないし、いくつかあるかもしれない 右のノードは、０かもしれないし、いくつかあるかもしれない けど、とりあえず、現時点でｔがノードであることは分かっているので、自分自身の１を足します。
その他の回答 (4)
- sakusaker7
- ベストアンサー率62% (800/1280)
ちょっと確認です。 いわゆる二分木(バイナリツリー)でいうところの「葉」の数は 「ノード」の数には含まれないのでしょうか? #「葉」→子供を持たない一番下の要素 isEmptyは葉のときにtrue を返し、かつ全体のノードの数に含めると思ったのですが。 で、 > 右と左のサブツリーを返すメソッドを繰り返していると、最終的にはルート（自分）が返ってくるのでしょうか？ あるノードから数えたすべてのノードの数は、そのノードの右側の 子供の合計と左側の子供の合計＋1（自分）です。で、その子供の下にある ノードの数を求めるには、その子供が持っている孫の合計＋1とします （これはいいですか?） これをひ孫→玄孫→その子供… と末端に行くまで潜っていくわけです。 図が描けるといいんですけどねえ(^^;
お礼
葉の数は、ノードの数に含まれています。ツリーの全てのエレメントを数えたかったんです。 おかげで大分分かってきました。本当にありがとうございます。
- BLUEPIXY
- ベストアンサー率50% (3003/5914)
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() で返ってきた ものを足すんですね。１を足すのは、一番先端のルートを数えるためなんでしょうか？
- sakusaker7
- ベストアンサー率62% (800/1280)
もうちょっとヒントを。 ・子供を持たないノード → 1を返す ・子供を持つノード → 右の子供のノードの数 + 左の子供のノードの数 + 1 (自分) です。これを根元から再帰的に適用してやれば全体のノードの数が求まります。 子供のノードの数を求めるところで、再帰しています。
お礼
回答ありがとうございます。 右と左のサブツリーを返すメソッドを繰り返していると、最終的にはルート（自分）が返ってくるのでしょうか？もうちょっと調べてみます。
何かの課題でしょうか？ 再帰ロジックを使えば簡単にできますよ。 まずは、再帰について調べてみて下さい。 ツリー構造の操作は再帰が必須になってきますので、覚えて損はないと思います。
お礼
ありがとうございます。再帰のことは一応簡単な知識はあるのですが、何せ初心者なもので、実際にコーディングをすると、できなくなってしまうことがよくあるんです。ものすごい時間を費やしてはいるんですが、一度どつぼにはまると大変ですね、プログラミングって。
関連するQ&A
- メソッドの中に、作ったメソッドを呼び込みたいんですが
メソッドの中に、作ったメソッドを呼び込みたいんですが シグネチャを int argCheck(String args[]) に指定して、 引数のチェック処理メソッドというものを作成してるんですが、 よくわからないんです。 内容は (1) 引数の数が１個でない場合、1を返却 (2) 引数が『aaa』でも『ZZZ』でもない場合、99を返却 (3) 以外は、0を返却 public class Test { public static void main(String args[]) { Test test = new Test(); int result = test.argCheck(args); test.argCheck(); //メソッドを呼び込み } private int argCheck(String args[]) { if(args[0].length != 1) // 引数の数が1以外の場合 { return 1; // 1を返す } else if (!args[0].equalsIgnoreCase("aaa") && !args[0].equalsIgnoreCase("ZZZ")) //引数が aaa でも ZZZ でもない場合(大/小文字区別せず) { return 99; // 99を返す } else // それ以外の場合 { return 0; // 0を返す } } }
- ベストアンサー
- Java
- staticメソッドの長所短所
初めまして。 ｃ言語からjavaの勉強を始めたものです。 javaには共通ライブラリをstaticなメソッド（この言い方に慣れない）で作ることが多いようですが、なぜですか？ 私の認識は、 staticはメモリの共有領域に確保され誰からも参照できる。 よって、メモリの効率的な確保が出来る。 でも、メソッドを共有領域に持つと各ユーザからそのメソッドが呼ばれたときに同じメモリをさすメソッドが使用される。 つまり、違うユーザがパラメタ違いで同じメソッドを使用すると、処理の途中でパラメタが書き換わってしまう可能性があるかと思います。 これって問題ないのでしょうか？ Sumple public static boolean check(String str){ if(str==null){ return false; } int num = Integer.parseInt(str); if(num < 0){ retrun true; } else { retrun false; } } こんなメソッドがあり、パラメタが「２」の人と「-10」の人が同時にアクセスすると結果が変わりそうな気がします。 よろしくお願いします。
- 締切済み
- Java
- メソッドの命名の仕方
変数やメソッドの名前を決めるのは、 簡単なことのようで難しかったりします。 それでいて重要であったりもします。 そこで、1つ気になる点があるので質問させていただきます。 例えばある Util クラスがあるとします。(例として StringUtils クラス) この StringUtils は static なメソッドの集まりをもつように実装します。 文字列が空かどうか調べるために、よく使用されているのが public static boolean isEmpty(String value) というメソッドがありますが、これに疑問があります。 このメソッドを使用する場合は、StringUtils.isEmpty("abc") などとなると思いますが、これって英語の意味的におかしい気がします。(私は英語がまったくできないので偉そうなことは言えませんが、、) これだと、「StringUtlsは空だ」みたいな意味になってしまいませんか？ 私はこういうときには「checkIfValueIsEmpty(String value)」のようにしています。StringUtils.checkIfValueIsEmpty("abc") これだと「StringUtils が value を空かどうかチェックする」という意味になりませんか？ 皆さんはこういう場合、どのように命名されていますか？ 確かに boolean を返す場合には定例や規約として「is～」が使われていますが、どうも気持ちが悪いので質問させていただきました。 以上、よろしくお願いいたします。
- ベストアンサー
- Java
- ParseとTryParseを実装するなら
こんにちは。c#初心者です。 c++にも、c#にもintにParseメソッドと、TryParseメソッドがあると思いますが、intのように比較的簡単に解析できるもの（比較的簡単なメソッド）ならParseメソッドをコピペして、例外の部分を「return false;」に変えるだけで十分だと思うのですが、問題は、Color構造体のような（やや）複雑なものです。 R, G, Bに加え、α値があり、また、名前で色を表す可能性もあります。考えただけで（intと比べると）かなり面倒なメソッドになることが分かると思うのですが、とりあえずParseメソッドを実装したとしましょう。 次にどうせならTryParseメソッドも実装したいところなのですが、初心者が考えた方法は３つあります。 １、Parseメソッドをコピペして（FormatExceptionなどの）例外部分を「return false;」に変える。 ２、Parseメソッドをtryブロックに入れて、catchブロックで「return false;」とする。 ３、privateなtryParseメソッドを用意し、それをベースにする。戻り値はException型で、Parseメソッドではnullで無ければスロー、TryParseメソッドでは「return exception == null;」とする。 （ソースコードは一番下） １は保守性上、少々問題ありかと。２は利用側がちょっと楽になることには変わりないが、パフォーマンス重視には向かない（というかテキストを解析している時点でパフォーマンス低いかな？）、３は１、２の問題を克服しているもののこのような設計でよいのか自信なし。 という訳で悩んでいます。どれが一番良いでしょうか？ もっと良い案があればそれでも良いです。どなたかわかる方がいらしゃいましたら教えてください。 ----------- 簡易ソースコード -------------- c#で書いています。また読みやすく（なっているかどうかは分かりませんが）するため、１行で書けるところも２行以上で書いている部分もあります。 案１ public static Color Parse(string text) { …… if ( invalid ) throw new FormatException(); …… } public static bool TryParse(string text, out Color result) { …… if ( invalid ) { result = Color.Empty; return false; } …… } ------------------------------------------------ 案２ public static Color Parse(string text); // 略 public static bool TryParse(string text, out Color result) { try { result = Parse(text); return true; } catch ( FormatException ) { result = Color.Empty; return false; } } --------------------------------------------------- 案３ private static Exception tryParse(string text, out Color result) { …… if ( invalid ) { result = Color.Empty; return new FormatException(); // スローせずに返す } …… } public static Color Parse(string text) { Color result; Exception exception = tryParse(text, out result); if ( exception != null ) throw exception; else return result; } public static Color TryParse(string text, out Color result) { Exception exception = tryParse(text, out result); if ( exception == null ) return true; // 例外が無ければ成功 else return false; }
- ベストアンサー
- C・C++・C#
- テストメソッド
先ほどはありがとうございました。テストメソッドで一つ質問があります。 もしinNorthernHemisphere（北半球）ならTrue。!inNorthernHemisphere（南半球）ならFalse。その月の四季を返します。 ｛12月、1月、2月｝ 北半球→"Winter" 南半球→"Summer" ｛３月、４月、５月｝ 北→"Spring" 南→"Fall" ｛6月、7月、8月｝ 北→"Summer" 南→"Winter" ｛9月、10月、11月｝ 北→"Fall" 南→"Spring" プログラムはこのように組んでみました。 public class ControlFun { public String season(int month, boolean inNorthernHemisphere){ if (month == 12 || month ==1 || month == 2) { if (inNorthernHemisphere) { return "Winter"; } else { return "Summer"; } } else if(month == 3 || month == 4 || month == 5 ){ if (inNorthernHemisphere) { return "Spring"; } else { return "Fall"; } }else if(month == 6 || month == 7 || month == 8){ if (inNorthernHemisphere) { return "Summer"; } else { return "Winter"; } }else{ if (inNorthernHemisphere) { return "Fall"; } else { return "Spring"; } } } 問題のテストメソッドですが、 public class ControlFunTest { @Test public void testseason(){ ControlFun myFuns = new ControlFun(); assertEquals("Winter", myFuns.season(12,？)); } } boolean型のinNorthernHemisphereはどのように書けばテストできますでしょうか。？ このテストでは、monthは12月。 inNorthernHemisphereはTrue。結果Winterを返したいのです。宜しくお願いします。
- ベストアンサー
- Java
- メソッドが値を返すとき
”メソッドが値を返さない”というエラーで困っています。 次のようなプログラムでは、メソッドが値を返せないのは当たり前なのでしょうか？？ public int A(){ int a= 3; int b= 5; if(条件式){ return (Math.sin(a*x)); }else if(条件式){ return (Math.cos(b*x)); }else if(条件式){ return 式 ; } } 「return」をif文のなかに入れてしまうことが，いけないのでしょうか？ また，それがしてはいけない事ならば，条件式によって扱うreturn文を変えるには， どうしたら良いかアドバイスを下さい。 よろしくお願いします。
- ベストアンサー
- Java
- 静的変数と静的メソッドの使い方について
独習ＪＡＶＡにてＪＡＶＡを学習しています。「コマンドライン引数を受け取り、それをスペイン語表記に変換して表示するアプリケーションを作成しなさい。例えば、OneはUno、・・・、FiveはCincoになります。静的メソッドを使って実現しなさい」という問題で躓きました。以下、私が作成したプログラムです。 class Language { static String st[] = new String[5]; //静的初期化ブロックは実行しない。 //コマンドライン引数を受け取るmainメソッドが使えないため //静的メソッド static String translation(){ for(int i = 0; i < st.length; i++) { if(st[i] == "One") return st[i] = "Uno"; if(st[i] == "Two") return st[i] = "Dos"; if(st[i] == "Three") return st[i] = "Tres"; if(st[i] == "Four") return st[i] = "Quatro"; if(st[i] == "Five") return st[i] = "Cinco"; } } //21行目 } class StaticalMethodPractice { public static void main(String args[]) { //mainメソッドが登場したので、静的変数を初期化する for(int i = 0; i < Language.st.length; i++) Language.st[i] = args[i]; //静的メソッドを実行 System.out.println(Language.translation()); } } このプログラムに対して、21行目return文が指定されていませんというエラーメッセージが出てくるのですが、そもそもreturnの使い方もよく分からないので右往左往している状況です。低級な質問かもしれませんが、よかったらアドバイスの方よろしくお願いします。
- 締切済み
- Java
- javaプログラムについて
mainメソッド内の指定された部分の処理を、 別のメソッドに分けてください。 mainメソッド内から作成した別メソッドを呼び出して 実行できるようにしてください。 ※分ける前と分けた後で処理結果が変わらないこと (入力された文字が"A"の場合true, それ以外の場合falseを返すように) */ class MethodAdd1{ public static void main(String[] args){ /* // ★ここから if("A".equals(args[0])){ judge = true; }else{ judge = false; } // ★ここまで */ boolean judge; if("A".equals(args[0])){ System.out.println("true"); }else{ System.out.println("false"); } } /* **戻り値：boolean **引数：String */ //ここにメソッドを作成 public static boolean equals(String a){ String str="A"; if("A".equals(str)){ return true; }else{ return false; } } } これで一応trueかfalseと表示されるのですが、合っているのか分かりません。 お時間のある方で、手直しをして頂ける方お願い致します。
- 締切済み
- SE・インフラ・Webエンジニア
- return文について質問
以下は、あるJavaの参考書の問題を僕が解いてソースコードに起こしたものです。その際のエラーが出てしまうことについて、その原因を質問させていただきます。 package 第16章; public class 練習16_4_4 { public static void main(String[]arg){ double[]dt={55.1,23.0,168.8,25.6,33.1,101.5}; System.out.println(isOver100(dt)); } public static boolean isOver100(double[]a){ for(double x:a){ if(x>100.0){ return true; }else{ return false; } } } } 質問：『public static boolean isOver100(double[]a){』、ここの部分でエラーとして「このメソッドは型booleanの結果を戻す必要があります」と表示されます。何故ですか？だって、return文で型booleanであるtrueやfalse返してるのに、、 まったく原因わかりません。
- ベストアンサー
- Java
- C#でのDLLのメソッドの作り方
MEFを使ってC#のプログラムを作っています。 DLL側のメソッドとして public bool ブーリアン(){ return true; } public string ストリングス(){ return "文字列"; } のような、戻り値をDLLからメインに送ることはできるのですが、 public void ナビ(int a){ webBrowser1.Navigate(http・・・・); Thread.Sleep(a); webBrowser1.Navigate(http・・・・); Thread.Sleep(a); }//webBrowser1はメインにある このような処理をDLLに入れようとすると、当たり前ですが「webBrowser1」なんてないぞ っと怒られてしまいます。 どのように渡せばよいのでしょうか？
- ベストアンサー
- C・C++・C#
お礼
なるほど、分かりました。ありがとうございます。 早くプログラミングになれるように頑張りたいです！