MovieInfo オブジェクトをキーとしてノードを使用して、二分探索木を作成しています。MovieInfo オブジェクトは、ID、fullName、および shortName の 3 つのフィールドを持つオブジェクトです。二分探索木は、IMDB にリストされているすべての映画を含む入力テキスト ファイルに関する情報を保存します。挿入は、各映画にランダムに関連付けられた ID に基づいています。検索機能では、ユーザーが文字列を入力し、オブジェクトの他のデータ (shortName、ID など) を取得します。 今、私が抱えているエラーはfindExactメソッドにあります。 まず、入力内容に関係なく、「Current Node is null」というメッセージが表示されます。これは、最初の currentNode が常に null になることを意味します。もう 1 つの問題は、ルート ノード (ツリーで最初に検索された currentNode) が適切に初期化されていることを確認する方法がわからないことです。これは私の問題と関係があるかもしれないと感じています。もう 1 つの問題は、最初にノードを挿入する方法にある可能性があります。参考までに、テキスト入力ファイルでこのコード/実行をテストする方法は、IndexTester.java です。
更新：わかりました。すべてが機能するようになりました。私が今抱えている唯一の問題は、私の findExact メソッドが MovieInfo クラスの ID フィールドを変更しているように見えることです。だから私の検索はうまくいきません。たとえば、次のように入力した場合:
1568482 2 White Kids with Problems 2 White Kids with Problems
1568487 Disorient Disorient
1568488 DIY Playgrounds DIY Playgrounds
"disorient" を検索すると、"1568488 Disorient Disorient" が返されます ("2 White Kids with Problems" オブジェクトの ID を含む)。さらに、ID が取得されているため、DIY プレイグラウンドをうまく検索できません。挿入メソッドは機能しますが、findExact メソッドで問題が発生しています。この ID の変更の原因について何か考えはありますか?
MovieInfo クラス (別の .java ファイル) -- 編集できません
public class MovieInfo {
public String shortName;
public String fullName;
static int ID;
public String key;
public MovieInfo(int id, String s, String f) {
ID = id;
shortName = s;
fullName = f;
}
}
BSTIndex.java -- 内部 BST を作成するクラス
import java.util.*;
import java.io.*;
public class BSTIndex extends MovieInfo {
public Node root;
public class Node{
public MovieInfo movie;
public Node left, right;
public Node(MovieInfo movie)
{
this.movie = movie;
//this.val = val;
//this.N = N;
}
}
public BSTIndex()
/**
* constructor to initialize the internal binary search tree.
* The data element should be an object of the type MovieInfo, described above.
*/
{
super(0, "", "");
}
public MovieInfo findExact(String key) {
return findExact(root, key);
}
private MovieInfo findExact(Node x, String key) {
if (x == null) return null;
int cmp = key.compareToIgnoreCase(x.movie.fullName);
if (cmp < 0) return findExact(x.left, key);
else if (cmp > 0) return findExact(x.right, key);
else return x.movie;
}
public void insert(MovieInfo data)
{
if (data == null) {return; }
root = insert(root, data);
}
public Node insert(Node x, MovieInfo data)
{
if (x == null) return new Node(data);
int cmp = data.ID - x.movie.ID;
if (cmp > 0 ) x.right = insert(x.right, data);
else if (cmp < 0) x.left = insert(x.left, data);
else if (cmp == 0) x.movie = data;
return x;
}
}
IndexTester.java
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class IndexTester {
// Test program
public static void main( String [ ] args ) throws FileNotFoundException
{
BSTIndex t = new BSTIndex( );
Scanner scan = new Scanner(new FileInputStream(args[0]));
long start = System.currentTimeMillis();
int i=0;
while(scan.hasNext()){
String line = scan.nextLine();
String [] fields = line.split("\t");
int id = Integer.parseInt(fields[0].trim());
String shortName = fields[1].trim();
String fullName = fields[2].trim();
MovieInfo info = new MovieInfo(id, shortName, fullName);
t.insert(info);
i++;
if(i % 10000 == 0){
System.out.println("Inserted " + i + " records.");
}
}
long end = System.currentTimeMillis();
System.out.println("Index building complete. Inserted " + i +
" records.Elapsed time = " + (end - start )/1000 + " seconds.");
Scanner input = new Scanner(System.in);
System.out.println("Enter search string, end in a '*' for
prefix search. q to quit");
while(input.hasNext()){
String search = input.nextLine().trim();
if(search.equals("q")) break;
if(search.indexOf('*')>0){
//call prefix search.
MovieInfo item = t.findPrefix(search);
if(item==null) System.out.println("Not Found");
else System.out.println(item.ID + " " + item.shortName + "
" + item.fullName);
}
else{
//call exact search, modify to return MovieInfo
MovieInfo item = t.findExact(search);
if(item==null) System.out.println("Not Found");
else System.out.println(item.ID + " " + item.shortName + "
" + item.fullName);
}
}
}
}