1

在这个 Trie 中，我正在尝试实现自动完成功能，我确信插入 trie 是正确的，但是在尝试打印时我无法打印每个单词的第一个字母，因为在回溯时它没有打印父节点，我必须以某种方式打印父节点，为此我已将 parent_letter 添加到节点，但在某些情况下它会失败。

例如：这些是 Trie 中的单词：

dehradun
delhi
dhanbad
dhule
dibrugarh
dimapur
dindigul
durgapur

如果我通过了字母“d”。

我得到：

dehradun
elhi
dhanbad
hule
dibrugarh
imapur
indigul
durgapur

源代码 ：

class TrieNode {
    char letter; // to store the letter
    TrieNode[] links; // array of 26 Nodes
    boolean fullword; // check for word
    public TrieNode parent; // storing parent letter

    TrieNode(char letter, boolean fullword, TrieNode p) {
        this.letter = letter;
        links = new TrieNode[26];
        this.fullword = fullword;
        this.parent = p;

    }
}

class temp8 {
    boolean new_word = false;
    ArrayList<String> al = new ArrayList<String>();

    TrieNode root = new TrieNode('!', false, null);

    void construct_trie(String s) {
        TrieNode temp = root; // copy root node
        TrieNode check;
        TrieNode par = root; // initially parent is root

        for (int i = 0; i < s.length(); i++) // loop over each character in word
        {
            int t = s.charAt(i); // integer value of character

            t = t - 97; // calculate appropriate index for array

            while ((check = temp.links[t]) != null) // check if root is null..
            {
                temp = temp.links[t]; // go forward
                t = s.charAt(++i);
                t = t - 97;
                par = temp; // update parent
            }

            if (i != s.length() - 1) // if not end of word..pass false
            {
                temp.links[t] = new TrieNode((char) (t + 97), false, par);
                par = temp.links[t];
            } else // if end of word..pass true to full word
            {
                temp.links[t] = new TrieNode((char) (t + 97), true, par);
                par = temp.links[t];
            }

            temp = temp.links[t]; // update temp..

        }
    }

    void read_trie(String find) // pass the intial string
    {
        int len = find.length();
        int i = 0;

        TrieNode temp = root; // copy root

        while (i != len) // go until the string matches
        {
            int t = find.charAt(i);
            t = t - 97;

            temp = temp.links[t];

            i++;

        }

        print_all(temp); // pass the node

    }

    void print_all(TrieNode t) // from here we have to recursively print all
                                // nodes if they are not null
    {

        if (t == null) // base condition
        {
            return;
        }

        if (new_word) // initially for first time don't print parent letter
        {
            System.out.print(t.parent.letter);
            new_word = false;
        }

        System.out.print(t.letter);

        if (t.fullword) {
            System.out.println();
            new_word = true;
        }

        for (int i = 0; i < 26; i++) {
            print_all(t.links[i]);

        }
    }
}
4

1 回答 1

1

你父母的信只从根的每个分支打印一次；最好将父母的字符串传递给孩子，并且仅在达到完整单词时才打印。

阅读代码：

    void read_trie(String find) // pass the intial string
    {
        int len = find.length();
        int i = 0;

        TrieNode temp = root; // copy root

        String match = "";
        while (i != len) // go until the string matches
        {
            int t = find.charAt(i);
            t = t - 97;

            temp = temp.links[t];
            if (temp==null) break;
            match += temp.letter;

            i++;
        }

        // Remove the last letter since it's added in the print code below
        if (match.length()>0) match = match.substring(0, match.length()-1);
        print_all(temp, match); // pass the node
    }

打印代码：

    void print_all(TrieNode t, String parent) 
            // from here we have to recursively print all nodes if they are not null
    {
        if (t == null) // base condition
        {
            return;
        }

        parent += t.letter; // prepend parent to child
        if (t.fullword) {
                // only print when you reach a full word
            System.out.println(parent);
        }

        for (int i = 0; i < 26; i++) {
                // recurse into each child, prepending the parent's string
            print_all(t.links[i],parent);
        }
    }
于 2013-11-12T04:20:44.233 回答