字典树（Trie树）的 Java 实现

落日映苍穹つ 2022-11-01 10:54 211阅读 0赞

## 定义 ##

用了两个第三方jar包，lombok 和 hutool，可自行替换

@Data
    public class TrieNode {
        
        private final int SIZE = 26;
        /**
         * 有多少个单词通过这个节点
         */
        private int num;
        /**
         * 所有的儿子节点
         */
        private TrieNode[] son;
        /**
         * 是不是结束节点
         */
        private boolean isEnd;
        /**
         * 节点值
         */
        private char value;
        /**
         * 是否有儿子节点
         */
        private boolean hasSon;
    
        public TrieNode() {
        
            num = 1;
            son = new TrieNode[SIZE];
            isEnd = false;
            hasSon = false;
        }
    
    }

## 操作类（插入，前缀查找，查找所有） ##

/**
     * 字典树工具
     *
     * @author wangql
     * @date 2021/02/24
     */
    public class TrieTreeUtil {
        
    
        /**
         * 字典树插入字符串
         *
         * @param node 节点
         * @param str  str
         */
        public static void insert(TrieNode node, String str) {
        
            if (StrUtil.isBlank(str)) {
        
                return;
            }
            char[] chars = str.toCharArray();
            for (char val : chars) {
        
                // 当前字符对应的数字位置
                int positionNum = val - 'a';
                // 获取儿子
                TrieNode[] sons = node.getSon();
                if (sons == null) {
        
                    sons = new TrieNode[26];
                }
                if (sons[positionNum] == null) {
        
                    // 设置当前位置有儿子节点
                    node.setHasSon(true);
                    sons[positionNum] = new TrieNode();
                    sons[positionNum].setValue(val);
                } else {
        
                    // 当前节点的前缀数量+1
                    sons[positionNum].setNum(sons[positionNum].getNum() + 1);
                }
                node = sons[positionNum];
            }
            node.setEnd(true);
        }
    
        /**
         * 计算单词前缀的数量
         *
         * @param prefix 前缀
         * @return int
         */
        public static int calculateNumberOfWordPrefixes(TrieNode tree, String prefix) {
        
            if (StrUtil.isBlankIfStr(prefix)) {
        
                return -1;
            }
            char[] chars = prefix.toCharArray();
            for (char val : chars) {
        
                // 获取位置
                int positionNum = val - 'a';
                TrieNode[] sons = tree.getSon();
                if (sons == null || sons[positionNum] == null) {
        
                    return 0;
                } else {
        
                    tree = sons[positionNum];
                }
            }
            return tree.getNum();
        }
    
        /**
         * 获取具有指定前缀的单词
         *
         * @param tree   树
         * @param prefix 前缀
         * @return {@link List<String>}
         */
        public static List<String> getWordWithSpecifiedPrefix(TrieNode tree, String prefix) {
        
            if (StrUtil.isBlankIfStr(prefix)) {
        
                return null;
            }
            char[] chars = prefix.toCharArray();
            for (char val : chars) {
        
                int positionNum = val - 'a';
                TrieNode[] son = tree.getSon();
                if (son != null && son[positionNum] != null) {
        
                    tree = son[positionNum];
                } else {
        
                    return null;
                }
            }
            return preTraverse(tree, prefix, new ArrayList<String>());
        }
    
        /**
         * 遍历某节点下的所有单词
         *
         * @param tree   树
         * @param prefix 前缀
         * @param list   列表
         * @return {@link List<String>}
         */
        public static List<String> preTraverse(TrieNode tree, String prefix, List<String> list) {
        
            if (tree.isHasSon()) {
        
                TrieNode[] son = tree.getSon();
                for (TrieNode child : son) {
        
                    if (child != null) {
        
                        list = preTraverse(child, prefix + child.getValue(), list);
                    }
                }
            }
            // 只有单词才输出
            if (tree.isEnd()) {
        
                list.add(prefix);
                System.out.println(prefix);
            }
            return list;
        }
    
        /**
         * 匹配词
         *
         * @param tree 树
         * @param str  字符串
         * @return boolean
         */
        public static boolean matchWord(TrieNode tree, String str) {
        
            if (StrUtil.isBlankIfStr(str)) {
        
                return false;
            }
            char[] chars = str.toCharArray();
            for (char val : chars) {
        
                int positionNum = val - 'a';
                TrieNode[] sons = tree.getSon();
                if (sons != null && sons[positionNum] != null) {
        
                    tree = sons[positionNum];
                } else {
        
                    return false;
                }
            }
            // 判断是否为 end 节点
            return tree.isEnd();
        }
    
        /**
         * 获取所有单词
         *
         * @param tree 树
         * @param str  字符串
         * @param list 列表
         * @return {@link List<String>}
         */
        public static List<String> getAllWords(TrieNode tree, String str, List<String> list) {
        
            if(tree.isHasSon()) {
        
                TrieNode[] sons = tree.getSon();
                for (TrieNode son : sons) {
        
                    if(son != null){
        
                        getAllWords(son, str+son.getValue(), list);
                    }
                }
            }
            if(tree.isEnd()){
        
                list.add(str);
            }
            return list;
        }
    }

## 测试 ##

/**
     * 测试
     *
     * @author wangql
     * @date 2021/02/24
     */
    public class Test {
        
        public static void main(String[] args) {
        
            TrieNode root = new TrieNode();
            // 插入
            TrieTreeUtil.insert(root, "dog");
            TrieTreeUtil.insert(root, "egg");
            TrieTreeUtil.insert(root, "art");
            TrieTreeUtil.insert(root, "cat");
            TrieTreeUtil.insert(root, "cats");
            TrieTreeUtil.insert(root, "cap");
            TrieTreeUtil.insert(root, "captain");
            TrieTreeUtil.insert(root, "caps");
    
            // 计算前缀开头的单词数量
            System.out.println(TrieTreeUtil.calculateNumberOfWordPrefixes(root, "c"));
            System.out.println(TrieTreeUtil.calculateNumberOfWordPrefixes(root, "cap"));
    
            // 获取前缀开头的单词
            List<String> cap = TrieTreeUtil.getWordWithSpecifiedPrefix(root, "cap");
            System.out.println(cap);
    
            // 遍历所有单词
            List<String> list = TrieTreeUtil.getAllWords(root, "", new ArrayList<String>());
            System.out.println("所有单词:"+list);
    
            System.out.println("是否完全匹配单词ca:"+TrieTreeUtil.matchWord(root, "ca"));
        }
    }