Trie树java实现

阳光穿透心脏的1/2处 2022-12-24 13:55 97阅读 0赞

Trie树又称前缀树或称字典树，是一个多叉树。可以实现前缀匹配查询或者字符串匹配查询。以下是java实现版

import java.util.TreeMap;
    
    /**
     * @Description  Trie树(字典树/前缀树)
     * @Author steve
     * @Date 
     */
    public class TrieTree {
    
        /**
         * 根节点
         */
        private Node root;
    
        /**
         * 存储的单词数量
         */
        private int size;
    
        public TrieTree(){
            this.root = new Node();
            this.size = 0;
        }
    
        /**
         * 获取Trie树种存储的单词数量
         * @return
         */
        public int getSize(){
            return size;
        }
    
        /**
         * 向Trie树中添加一个新的单词word
         * @param word
         */
        public void add(String word){
            Node cur = root;
            for(int i = 0; i < word.length(); i++){
                char c = word.charAt(i);
                if(cur.next.get(c) == null){
                    cur.next.put(c, new Node());
                }
                cur = cur.next.get(c);
            }
            if(!cur.isWord){
                cur.isWord = true;
                size++;
            }
        }
    
        /**
         * 查询单词word是否在Trie树中
         * @param word
         * @return
         */
        public boolean contains(String word){
            Node cur = root;
            for(int i = 0; i < word.length(); i++){
                char c = word.charAt(i);
                if(cur.next.get(c) == null){
                    return false;
                }
                cur = cur.next.get(c);
            }
            return cur.isWord;
        }
    
        /**
         * 查询是否在Trie树种有单词以prefix为前缀
         * @param prefix
         * @return
         */
        public boolean isPrefix(String prefix){
            Node cur = root;
            for(int i = 0; i < prefix.length(); i++){
                char c = prefix.charAt(i);
                if(cur.next.get(c) == null){
                    return false;
                }
                cur = cur.next.get(c);
            }
            return true;
        }
    
        private class Node{
            public boolean isWord;
    
            public TreeMap<Character, Node> next;
    
            public Node(boolean isWord){
                this.isWord = isWord;
                next = new TreeMap<>();
            }
    
            public Node(){
                this(false);
            }
        }
    
        public static void main(String[] args) {
            TrieTree trieTree = new TrieTree();
            trieTree.add("hello");
            trieTree.add("world");
            trieTree.add("java");
            trieTree.add("program");
            trieTree.add("art");
            System.out.println(trieTree.contains("python"));
            System.out.println(trieTree.contains("java"));
        }
    }

实现方式非常的简单易懂，但是功能非常的强大，据说微软的通讯录就是利用Trie树来实现的。