二分探索木を使ってリストから特定の名前を見つけたい

java初心者です。

クラスでは、二分技について学習しました。
そして、今出されている課題が以下です。

新生児の名前とその名前の人数が載っているテキスト
例）太郎　４０
花子　２３
二郎　３２
：
：
etc.
があります。それを元に、
入力した名前がリストに入っているかand何人なのかを、二分木探索を使って調べる
例）太郎を調べる

リストに入っている場合→　表示

例）太郎　４0

いない場合　→　終了

どちらの場合でも、何回ノードを訪問したか数を表示させる

つまり整理すると
１）テキスト内の名前と人数を読み込む
２）それらを二分木でソートする
３）探す名前を入力させる
４）ならびかえられた二分木内をinorder, preorder, またはpostorderを使い徘徊
５）a.見つけた場合　名前と人数を出力
b.みつからなかった場合　終了
６）a,bどちらでもノード訪問の回数を出力
ということです。

おそらく読み込みまでだけできていると思います。
なるべく初心者でも理解可能なコードを待っています。
お願いいたします。

（以下が私ができるところまでやって見たコードになります）

java
1
2import java.io.BufferedReader;
3import java.io.FileReader;
4import java.io.IOException;
5import java.io.*;
6import javax.swing.JOptionPane;
7public class HW5
8{
9  public static void main(String[] args) throws IOException
10  {
11    readFile();
12    String name;
13//名前を入力してもらう
14    name = JOptionPane.showInputDialog("Enter the name that you are lookig for. ");
15    BinaryTree(name);
16    System.out.println(name);
17  }
18  
19  private static String readFile() //namae.txtから全ての名前と数字を読み込む
20  {
21    try{
22      File file = new File("namae.txt");
23      FileReader filereader = new FileReader(file);
24      int ch;
25    }catch(FileNotFoundException e){
26      System.out.println(e);
27    }catch(IOException e){
28      System.out.println(e);
29    }return null;
30  }
31  private static Node BinaryTree(String n){
32//ノード作成
33    if(name==foundInText)
34    {
35//ここにif文を使いなまえがあるかどうかを調べる
36      System.out.println((char)ch);
37    }else
38    {
39      System.out.println("The name was not found. Enter anotehr name.");
40    }
41  }
42    
43}
44

file
"name..txt"
Buffy 0
Nathaniel 64
Elyse 823
Shyann 771
Saige 942
Arno 0
Ciara 284
Flo 0
Yamilet 804
Clay 402

Zuishin

2018/05/09 23:23 編集

実用なら二分木をわざわざ実装する必要はないので何かの課題だと思います。何のために学習しているのか、自分が今まで何を習ったのか、実際の正確な課題は何なのかを書くと、課題を効果的に力にできる適切なアドバイスが得られると思います。二分探索木のソースが欲しいだけなら検索すればいくらでもみつかりますが、力をつけず課題を提出すると次の課題で困るでしょう。それにもしかしたら二分探索木を構築せよという課題ではなく、もっと簡単に済むかもしれません。二分木ではなく二分探索ではないですか？

swordone

2018/05/10 01:12

二分木にせよ二分探索にせよ、「何人いるか」を調べるの結構面倒だと思います。

runako67

2018/05/10 02:59

二分木と二分探索の違いをよく理解していませんでした。クラスでは二分探索について学びました。おっしゃる通りです。訂正します。ありがとうございます。

Zuishin

2018/05/10 03:09

何人いるかはノードの数を数えるのでなくノードのプロパティなので大丈夫かと。訂正は質問を編集してください。二分木を作る手順とソート済みデータを二分探索する手順は大きく違いますから回答も全く違うものになります。また配列には binarySearch() というメソッドが実装されていますので、それを使うと一行で済んでしまいます。それを使っていいかどうかも追記しなければなりません。

runako67

2018/05/10 03:36

今変更して見ましたが、予想以上にわかりにくい説明になってしまったかもしれません。二分木を作る→二分探索木で探すが求められていることです。いくつノードを見回ったかを最終的に表示させなくてはいけないので、binarySearchを使うと答えが変わってしまうと思うので使えないと思います。

Zuishin

2018/05/10 05:06

私は二分木と二分探索木は同じ意味で使いました。問題は二分木を構築することが求められるのかそれとも探索だけで良いのかということです。というのも、ソート済みの線形リストは二分木の一種ですが、リストや配列をソートすることをもって「二分木を構築する」とは普通言わないからです。最初に書いたように、あなたが何を知っていてどこまで用語が通じるのかということと、あなたの理解でなく正確な課題を書く必要があります。

行動規範の内容に同意します

回答3件

ベストアンサー

途中までだったので、読み込み部分を作ってみました。
Node クラスが消えているみたいなので、適当に作成。

まず、 Nodeクラス

Java
1class Node
2{
3	public String NodeName = null;
4	public int PersonCount = 0;
5	Node Low = null;
6	Node High = null;
7
8	Node(String name, int count) {
9		NodeName = name;
10		PersonCount = count;
11	}
12
13	public void AddLeaf(Node leaf)
14	{
15		if (PersonCount > leaf.PersonCount) {
16			if (Low == null)	Low = leaf;
17				else			Low.AddLeaf(leaf);
18		} else {
19			if (High == null)	High = leaf;
20				else			High.AddLeaf(leaf);
21		}
22	}
23}

[追記: ここから]
問題文をよく読んでなかった。
名前で検索するので、ソートするキーは、名前にすべきでした。
--> NodeName とname の比較
とすれば、検索も Nodeクラスに、メソッドを追加して、
public int Find(String name) { ... }
として、同じような処理で OK

[追記: ここまで]

最初に、
Node root = null
読み込みは、読み込んだデータを以下の変数に入れる。
String name = 名前
int num = 人数
とし、
Node leaf = new Node(name, num);
if (root == null) root = leaf;
else root.AddLeaf(leaf);

後は適当に考えてください。
久々だったので、ちょっと時間が掛かりましたが、適切に読み込めば、ツリーができる事まで、確認済み。
問題を読み返すと、二分木検索がメインでしたか。と、すると Nodeクラスに検索メソッドを追加して、それを呼べば、良いですね。それも再帰を使えば、簡単に書けますが、ご自身で考えられた方が良いかと思います。 (この目的には、二分木、使う必要は全くなさそうですが)

投稿2018/05/13 12:13

編集2018/05/13 14:07