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