java - Java中的Trie数据结构

Question

因此，我在 java 中为自己构建了一个 trie 数据结构，而不是包含每个节点子节点的 LinkedList 的数组。但我遇到了一些问题。第一个单词添加得很好，但在第二个单词上，它总是比较错误的前缀。例如，我首先添加“at”。这有效。然后我添加“Hello”，这就是结果:

    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;
    }
}

Answer 1

我发现了 3 个错误。

首先，这个 getChild() 方法放错了分号，导致您的方法在第一个节点返回:

if (n.getText().equals(String.valueOf(c)))/*; - remove this semicolon*/
        {
            System.out.println("Returning child");
            return n;
        }

其次，我假设您希望 trie 中的每个节点仅包含一个字母。因此，您必须像这样更正 insertNode() 方法:

Node next = new Node(/*node.getText() +  - remove this*/c.toString());

如果您运行该代码，您将在尝试查找您添加的单词时遇到 NullPointerException。这是因为您的 find 方法有一些错误。我重写了它并添加了一些注释来解释这些更改。如果不清楚，请告诉我:

public boolean find(String str) {

    LinkedList<Node> children = root.getChildren();
    // start the node at the root
    Node node = root;
    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))) {
            //get the child *of the node, not root* and it's children.
            node = getChild(node, c);

            // there are better ways to handle this, but I think this explicitly shows what the situations is
            if (node == null) {
                // we have reached a node that does not have children
                if (i == chars.length - 1) {
                    // we are at the end of the word - it is found
                    return true;
                } else {
                    // we are in the middle of the word - it is not present
                    return false;
                }
            }

            // if we have reached the end of the word this will cause NullPointer
            children = node.getChildren();

        } else {
            return false;
        }
    }
    return true;
}

当我运行此代码片段时:

public static void main(String[] args) {
    Trie trie = new Trie();
    trie.add("at");
    trie.add("Hello");
    System.out.println(trie.find("at"));
    System.out.println(trie.find("Hello"));
    System.out.println(trie.find("yea"));
}

我得到“真”，“真”，“假”