java实现数据结构10（字典树详解代码之自定义字典树）

矫情吗；* 2023-06-23 12:52 1阅读 0赞

## 自定义字典树 ##

import java.util.TreeMap;
    
    /** * @description: 自定义字典树，字典树对于巨量级的数据处理效率非常高，因为他的处理与处理数据的量没有关系 * @author: liangrui * @create: 2019-12-18 21:41 **/
    public class Trie { 
    
        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);
            }
        }
    
        private Node root;
        private int size;
    
        public Trie(){ 
            root=new Node();
            size=0;
        }
    
        /** * 获得字典树中存储的单词数量 * @return */
        public int getSize(){ 
            return size;
        }
    
        /** * 向字典中添加新的单词 * @param word */
        public void add(String word){ 
            //从根节点开始
            Node cur=root;
            //循环遍历单词
            for (int i = 0; i < word.length(); i++) { 
                char c=word.charAt(i);
                System.out.println(c);
                //如果字典树节点中没有这个字母，则添加
                if (cur.next.get(c)==null){ 
                    cur.next.put(c,new Node());
                }
                cur=cur.next.get(c);
            }
            //单词添加结束，如果该节点位置截止不是单词，则标记为单词，个数加1
            if (!cur.isWord){ 
                cur.isWord=true;
                size++;
            }
        }
    
        /** * 查询字典中某单词是否存在 * @param word * @return */
        public boolean contains(String word){ 
            return match(root,word,0);
        }
    
        /** * 查询字典中是否存在某前缀 * @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;
                }else { 
                    cur.next.get(c);
                }
            }
            return true;
        }
    
        /** * 如果输入的单词中右'.',则与所有字母都匹配 * @param node * @param word * @param index * @return */
        private boolean match(Node node,String word,int index){ 
            if (index==word.length()){ 
                return node.isWord;
            }
    
            char c=word.charAt(index);
            if (c!='.'){ 
                if (node.next.get(c)==null){ 
                    return false;
                }else { 
                    return match(node.next.get(c),word,index+1);
                }
            }else { 
                for (char nextChar:node.next.keySet()){ 
                    if (match(node.next.get(nextChar),word,index+1)){ 
                        return true;
                    }
                }
                return false;
            }
        }
    
        /** * 删除指定单词 * @param word */
        public void delete(String word){ 
            delete(root,word,0);
        }
    
        /** * 递归删除指定单词 * @param node * @param word * @param index */
        private void delete(Node node,String word,int index){ 
            if (index==word.length()){ 
                if (node.next.size()>1){ 
                    node.next.remove(word.charAt(index+1));
                }else{ 
                    node.isWord=false;
                }
                size--;
            }else { 
                delete(node.next.get(word.charAt(index)),word,index+1);
            }
        }
    
    }

## main测试 ##

public class Main { 
    
        public static void main(String[] args) { 
            Trie trie=new Trie();
            trie.add("zhangsan");
            System.out.println(trie.contains("zhangsan"));
            trie.delete("zhangsan");
            System.out.println(trie.contains("zhangsan"));
        }
    }

## 测试结果 ##

> z  
> h  
> a  
> n  
> g  
> s  
> a  
> n  
> true  
> false