1
所以我建立了自己的java数据结构trie，而不是包含LinkedList的数组到每个节点的子节点。但我有一些问题。第一个单词被添加得很好，但第二个单词总是比较错误的前缀。例如，我首先添加“at”。这工作。然后，添加“你好”，这是结果：Java中的Trie数据结构
adding 'at'
CURRENT CHAR IS: a
List is empty, can't iterate
List is empty, can't iterate
Can't find this char, adding node...
Returning child
CURRENT CHAR IS: t
List is empty, can't iterate
List is empty, can't iterate
Can't find this char, adding node...
END OF LINE; SET IT TO TRUE--------------
Returning child
adding 'Hello'
CURRENT CHAR IS: H
List is NOT empty
char H lista a?
false
List is empty, can't iterate
List is NOT empty
char H lista a?
false
List is empty, can't iterate
Can't find this char, adding node...
Returning child
CURRENT CHAR IS: e
List is NOT empty
char e lista at?
false
List is empty, can't iterate
List is NOT empty
char e lista at?
false
List is empty, can't iterate
Can't find this char, adding node...
Returning child
CURRENT CHAR IS: l
List is empty, can't iterate
List is empty, can't iterate
Can't find this char, adding node...
Returning child
CURRENT CHAR IS: l
List is empty, can't iterate
List is empty, can't iterate
Can't find this char, adding node...
Returning child
CURRENT CHAR IS: o
List is empty, can't iterate
List is empty, can't iterate
Can't find this char, adding node...
END OF LINE; SET IT TO TRUE--------------
这里是我的代码（对不起，所有的印刷品和意见，已调试了几个小时） 特里
public class Trie {
private Node root;
private int size;
/**
* Creates the root node and sets the size to 0.
*/
public Trie() {
root = new Node();
size = 0;
}
/**
* Adds a new word to the trie.
*
* @param word
* @return
*/
//vi lägger in "Hello"
public boolean add(String word) {
System.out.println("adding " + word);
Node curr = root;
if (curr == null || word == null) {
return false;
}
int i = 0;
char[] chars = word.toCharArray();
// Loop through all letters in the word.
while (i < chars.length) {
System.out.println("lengt = " + chars.length);
LinkedList<Node> children = curr.getChildren();
// If the children nodes does not contain the letter at i.
System.out.println("BEFORE CURRENT CHAR IS: " + chars[i]);
if (!childContain(children, String.valueOf(chars[i]))) {//TODO? listan är tom.
// Insert a new node
insertNode(curr, chars[i]);
System.out.println("Can't find this word, adding...");
// if we have traversed all letters.
if (i == chars.length - 1) {
System.out.println("END OF LINE; SET IT TO TRUE--------------");
// Get the child and set word to true ie we have found it.
getChild(curr, chars[i]).setWord(true);
size++;
return true;
}
}
// get the current child.
curr = getChild(curr, chars[i]); //NOT SURE ABOUT THIS!
// If the current childs text is equal the word or not the word.
if (curr.getText().equals(word) && !curr.isWord()) {
// set the current word to true.
curr.setWord(true);
size++;
return true;
}
i++;
}
return false;
}
/**
* Returns true if the given string is found.
* TODO: FIX!
* @param str
* @return
*/
public boolean find(String str) {
System.out.println(str);
System.out.println("-----------------------------------------");
LinkedList<Node> children = root.getChildren();
Node node = null;
char[] chars = str.toCharArray();
//Loop over all letters.
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
//If child contains c.
if (childContain(children, String.valueOf(c))) {
System.out.println("DET FINNS");
//get the child and it's children.
node = getChild(root, c);
children = node.getChildren();
} else {
System.out.println("DET FINNS INGET");
return false;
}
}
return true;
}
/**
* Inserts a new Node with a char.
*
* @param node
* @param c
* @return
*/
private Node insertNode(Node node, Character c) {
if (childContain(node.getChildren(), String.valueOf(c))) {
return null;
}
Node next = new Node(node.getText() + c.toString());
node.getChildren().add(next);
return next;
}
/**
* Retrieves a given node's child with the character c
*
* @param trie
* @param c
* @return
*/
private Node getChild(Node node, Character c) {
LinkedList<Node> list = node.getChildren();
Iterator<Node> iter = list.iterator();
while (iter.hasNext()) {
Node n = iter.next();
if (n.getText().equals(String.valueOf(c)));
{
System.out.println("Returning child");
return n;
}
}
System.out.println("Returning null"); // This could never happen
return null;
}
/**
* Checks if any child contains the char c.
*
* @param list
* @param c
* @return
*/
private boolean childContain(LinkedList<Node> list, String c) {
Iterator<Node> iter = list.iterator();
while (iter.hasNext()) {
System.out.println("List is NOT empty");
Node n = iter.next();
//GÖr en substräng av den existerande noden
System.out.println("char " + (c) +" lista " + n.getText() + "?");
System.out.println(n.getText().equals(c));
if (n.getText().equals(c))
{
return true;
}
}
System.out.println("List is empty, can't iterate");
return false;
}
/**
* Returns the trie's size.
*
* @return
*/
public int getSize() {
return size;
}
}
节点：
public class Node {
private boolean isWord;
private String text;
private LinkedList<Node> children;
public Node() {
children = new LinkedList<Node>();
text = "";
isWord = false;
}
public Node(String text) {
this();
this.text = text;
}
public LinkedList<Node> getChildren(){
return children;
}
public boolean isWord() {
return isWord;
}
public void setWord(boolean isWord) {
this.isWord = isWord;
}
public String getText() {
return text;
}
public void setText(String text) {
this.text = text;
}
@Override
public String toString(){
return text;
}
}
什么类型的线索是它？你有每个节点或字符串一个字符？ – Asoub
我已经使用了调试器。主要的问题是我添加的algrotihm似乎先深入，而不是创建一个新的节点。首先，我将H与a进行比较，然后将H与t进行比较。然后，我和爱玛一起去了。然后我在列表的最后。当我设定我们在哪个节点时有什么不对。 我的节点有String作为它们的数据类型，但实际上我只是在它们中存储一个字符。 – ioou
你应该首先重构你的代码：当然，除了'addWord（String s）'外，在每个地方都使用'char'。然后，在'Trie'中使用'Node'，而不是'LinkedList'。这意味着'Node'应该有'getChild（）'方法，如果没有孩子的话就会返回null。 'insertNode（）'也应该在'Node'类中。所以'Trie'将只检查节点是否有一个字母一个孩子，如果没有，插入，如果it'es最后的字符，设置有“真”。这应该会减轻您的调试。 – Asoub