Trie 树（二）：java 简单实现

本文内容主要来源：https://www.cnblogs.com/konrad/p/7748508.html

1. 定义节点类TrieNode

public class TrieNode {
    private List<TrieNode> children;  //子节点
    private char data; //节点字符
    private int freq; //频率
    boolean isEnd;  //从根节点到该节点是否是一个词

    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) {...}

    //查找返回节点
    public TrieNode searchNode(String word) {...}

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

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

    //获取词频
    public int getFreq(String word) {...}
}

3. 插入节点

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.查找节点

//查找是否存在
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;
}

//查找返回节点
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. 删除节点

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树的实现方法之一，也可以使用其他不同方式来实现。

上一篇：Trie 树（一）：简介
下一篇：java 正则表达式中断言的使用