在二叉搜索树 Java 中查找单词？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15961436/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Finding a Word in a Binary Search Tree Java?
提问by Maria Stewart
The problem I'm having is that I have a binary search three, and all of the nodes contain string values rather than integer ones. It gets these strings from a txt file and places the individual lines of text from the file as nodes into the tree. There is no problem with this.
我遇到的问题是我有一个二进制搜索三，并且所有节点都包含字符串值而不是整数值。它从 txt 文件中获取这些字符串，并将文件中的各个文本行作为节点放入树中。这没有问题。
My problem is that I need a method that iterates through my tree and finds a specific word. I already have separate classes, BinarySearchTree and BinaryTreeNode to serve as the basis for the tree I'm trying to make. The words it needs to find are located in a file called "lookup test file copy.txt" and it needs to write the words that it finds to another file called "SearchResults.txt"
我的问题是我需要一种方法来遍历我的树并找到一个特定的词。我已经有单独的类 BinarySearchTree 和 BinaryTreeNode 作为我尝试制作的树的基础。它需要查找的单词位于名为“lookup test file copy.txt”的文件中，并且需要将它找到的单词写入另一个名为“SearchResults.txt”的文件中
I just have no idea how to do it, so I'm looking for advice.
我只是不知道该怎么做，所以我正在寻求建议。
This is the method I need help with:
这是我需要帮助的方法：
public boolean SearchWord(String target){
//returns true if the target string exists in the dictionary
// otherwise it returns false
//ALSO you need to write the results of Search
//in an output file called "SearchResults.txt"
return false;
}
Here is all of my code, excluding the two other classes mentioned above, if it helps.
这是我的所有代码，不包括上面提到的其他两个类，如果有帮助的话。
public class Dictionary {
public BinaryTreeNode theBinaryTree;
/**
* I need to read one string by one string
* and then insert it into a tree.
* I need to read all of the strings in the source file, line by line,
* and insert them into my dictionary.
* After readinga single string, it needs to put it into a tree.
* I first need to create the dictionary tree,
* and then implement these methods on the tree.
* The Dictionary type is string.
* @throws FileNotFoundException
*/
private BinaryTreeNode dictionaryTree; // this is the tree within your dictionary class
public Dictionary(String filePath) throws IOException{
BufferedReader br = new BufferedReader(new FileReader("Dictionary.txt"));
this.dictionaryTree = readFile(br);
br.close();
}
public BinaryTreeNode readFile(BufferedReader reader) throws IOException{
String word = reader.readLine();
if(word!=null){
return new BinaryTreeNode(word, readFile(reader), readFile(reader));
}else{
return new BinaryTreeNode() ; // empty node or null?
}
}
/**
* @return
* Once again, I already have this method written and modified
* within the BinarySearchTree class.
* I'm simply going to call it over here.
*/
public int CountWords(){
//returns the number of words in the dictionary
//This is just counting nodes.
BinarySearchTree Aria = new BinarySearchTree();
return Aria.countNodes(dictionaryTree);
}
public boolean SearchWord(String target){
//returns true if the target string exists in the dictionary
// otherwise it returns false
//ALSO you need to write the results of Search
//in an output file called "SearchResults.txt"
return false;
}
/**
* I already modified the print order method
* in BinarySearchTree
* to work with strings.
* So I just called it here on the dictionaryTree.
* @PrintOrderedDict()
*
* However, I also had to modify the method,
* so that it wrote whatever values the method recieved
* to teh output file.
*/
public void PrintOrderedDict() throws IOException{
//Print the dictionary words
//in order in a new file called "OrderedDictionary.txt".
//Just modify print order to work with strings.
try {
BinarySearchTree jojo = new BinarySearchTree();
FileWriter fstream = new FileWriter("OrderedDictionary.txt");
BufferedWriter out = new BufferedWriter(fstream);
out.write(jojo.inorderPrint(dictionaryTree));
out.close();}
catch (Exception e) {
System.err.println("Error");
}
}
public boolean DeleteWord(String target){
//delete the target word if it exits in the dictionary and return true
//otherwise return false
return false;
}
}
Any help or advice would be appreciated.
任何帮助或建议将不胜感激。
----EDIT----
- - 编辑 - -
This is also a small sample of the "dictionary.txt" file (It's too long to put the entire thing in)
这也是“dictionary.txt”文件的一个小样本（把整个东西都放进去太长了）
ourselves
out
over
own
same
shan't
she
all
This is the "lookup test file copy.txt" file:
这是“查找测试文件 copy.txt”文件：
the
program
a
ours
house
ME
ours
main
java
whom
with
回答by Bohemian
You haven't included the most relevant code, which is BinaryTreeNode, so the field names used here are guesswork, however this will do it:
您还没有包含最相关的代码，即 BinaryTreeNode，所以这里使用的字段名称是猜测，但是这样做可以：
Method in Dictionary:
字典中的方法：
public boolean SearchWord(String target){
boolean found = theBinaryTree.contains(word);
// write the values of "target" and "found" to file (code omitted)
return found;
}
Method in BinaryTreeNode:
BinaryTreeNode 中的方法：
private String word;
private BinaryTreeNode left;
private BinaryTreeNode right;
public boolean contains(String target) {
if (target.equals(word))
return true;
BinaryTreeNode next = target.compareTo(word) < 0 ? left : right;
return next != null && next.contains(target);
}
回答by Lajos Arpad
This is obviously a homework, so I will not steal the possibility of resolving it from you, but I will give you hints which you can use to easily solve your problem:
这显然是一个家庭作业，所以我不会从你那里窃取解决它的可能性，但我会给你一些提示，你可以用它来轻松解决你的问题：
You already know the algorithm, if I understood correctly, so you know what you have to do with numbers. You need to do the same with Strings, just you don't know how to compare Strings.
Use the
compareTomethod.s1.compareTo(s2)is:positive, if s1 > s2
negative, if s1 < s2
0, if s1.equals(s2)
Comparable is an interface. If a class implements Comparable, it will have a compareTo method. String happens to implement Comparable, as you can see here.
如果我理解正确的话，您已经知道算法，所以您知道与数字有什么关系。你需要对字符串做同样的事情，只是你不知道如何比较字符串。
使用
compareTo方法。s1.compareTo(s2)是：正，如果 s1 > s2
负数，如果 s1 < s2
0, 如果 s1.equals(s2)
Comparable 是一个接口。如果一个类实现了 Comparable，它将有一个 compareTo 方法。String 恰好实现了 Comparable，正如您在此处看到的。
回答by Pete B.
Break the problem into parts.
把问题分解成几个部分。
1) Do a search on how to read a file. Read the file, and echo the results to standard output. That is pretty easy, and about 1/3 of the work you need to do.
1) 搜索如何读取文件。读取文件，并将结果回显到标准输出。这很容易，并且您需要完成大约 1/3 的工作。
2) Write some random words to a file. Open the file, write the words, then check your work, also not hard to do and you are getting closer.
2）将一些随机单词写入文件。打开文件，写字，然后检查你的工作，也不难做，离你越来越近了。
3) Load your binary search tree and write code to do a look up, it is pretty easy. If your word .equals the current node, return true Otherwise if less than the current node, go left, if greater go right. If your pointer is null, then return false;
3）加载你的二叉搜索树并编写代码进行查找，这很容易。如果您的单词 .equals 当前节点，则返回 true 否则，如果小于当前节点，则向左，如果更大则向右。如果您的指针为空，则返回 false；
4) Put it all together.
4）把它们放在一起。
Conquering this in parts is much less overwhelming.
部分地征服这一点并不那么压倒性。
