本文內(nèi)容主要來源：https://www.cnblogs.com/konrad/p/7748508.html

1. 定義節(jié)點類TrieNode

public class TrieNode {
    private List<TrieNode> children;  //子節(jié)點
    private char data; //節(jié)點字符
    private int freq; //頻率
    boolean isEnd;  //從根節(jié)點到該節(jié)點是否是一個詞

    public TrieNode(char data){
        this.children = new LinkedList<>();
        this.freq = 0;
        this.isEnd = false;
        this.data = data;
    }

    public TrieNode childNode(char c){
        if(null != children){
            for(TrieNode child : children){
                if(child.getData() == c){
                    return child;
                }
            }
        }
        return null;
    }

    public List<TrieNode> getChildren() {
        return children;
    }

    public void setChildren(List<TrieNode> children) {
        this.children = children;
    }

    public char getData() {
        return data;
    }

    public void setData(char data) {
        this.data = data;
    }

    public int getFreq() {
        return freq;
    }

    public void setFreq(int freq) {
        this.freq = freq;
    }

    public void addFreq(int step){
        this.freq += step;
    }

    public void subFreq(int step){
        this.freq -= step;
    }

    public boolean isEnd() {
        return isEnd;
    }

    public void setEnd(boolean end) {
        isEnd = end;
    }
}

2. 定義Trie樹類TrieTree

public class TrieTree {

    private TrieNode root;

    public TrieTree() {
        this.root = new TrieNode(' ');
    }

    //查找是否存在
    public boolean search(String word) {...}

    //查找返回節(jié)點
    public TrieNode searchNode(String word) {...}

    //插入
    public void insert(String word) {...}

    //移除
    public void remove(String word) {...}

    //獲取詞頻
    public int getFreq(String word) {...}
}

3. 插入節(jié)點

public void insert(String word) {
    TrieNode current = root;
    for (int i = 0; i < word.length(); i++) {
        TrieNode child = current.childNode(word.charAt(i));
        if (null != child)
            current = child;
        else {
            current.getChildren().add(new Trde(word.charAt(i)));
            current = current.childNode(word.charAt(i));
        }
        current.addFreq(1);
    }
    current.setEnd(true);
}

4.查找節(jié)點

//查找是否存在
public boolean search(String word) {
    TrieNode current = root;
    for (int i = 0; i < word.length(); i++) {
        if (null == current.childNode(word.charAt(i)))
            return false;
        else
            current = current.childNode(word.charAt(i));
    }

    if (current.isEnd())
        return true;
    else
        return false;
}

//查找返回節(jié)點
public TrieNode searchNode(String word) {
    TrieNode current = root;
    for (int i = 0; i < word.length(); i++) {
        if (null == current.childNode(word.charAt(i)))
            return null;
        else
            current = current.childNode(word.charAt(i));
    }

    if (current.isEnd())
        return current;
    else
        return null;
}

5. 刪除節(jié)點

public void remove(String word) {
    if (!search(word))
        return;

    TrieNode current = root;
    for (char c : word.toCharArray()) {
        TrieNode child = current.childNode(c);
        if (child.getFreq() == 1) {
            current.getChildren().remove(child);
            return;
        }else{
            child.subFreq(1);
            current = child;
        }
    }
    current.setEnd(false);
}

6. 獲取某個詞的頻率

//獲取詞頻
public int getFreq(String word) {
    TrieNode trieNode = searchNode(word);
    if(null != trieNode){
        return trieNode.getFreq();
    }else{
        return 0;
    }
}

這只是Trie樹的實現(xiàn)方法之一，也可以使用其他不同方式來實現(xiàn)。

上一篇：Trie 樹（一）：簡介
下一篇：java 正則表達式中斷言的使用