2022-03-10

前缀树代码
适用于有相同前缀路径的字符串相关问题

package com.Tree.TireTreeExe;

/**
 * @author xiuxiaoran
 * @date 2022/3/10 12:52
 * 构造前缀树进行处理
 */
public class TrieTree {
    public static class TrieNode{
        public int pass;  //字符路过这条路径的时候就+1  ; 可以查询集合中以某些字母为前缀的数量
        public int end;   // 字符以当前节点结尾时end+1  ； 可以查询某个字符是否存在这个集合中
        public TrieNode[] nexts;
        public TrieNode(){
            pass = 0;
            end =0;
            nexts = new TrieNode[26];  //这是路径节点的，假设是只有a-z小写字母组成
        }
    }

    public static class Trie{
        private TrieNode root;
        public Trie(){
            root = new TrieNode();
        }
        //插入一个节点
        public void insert(String word){
            if(word==null) return;
            char[] ch = word.toCharArray();
            TrieNode node = root;
            node.pass++;
            int index =0;
            for(int i=0;i<ch.length;i++){
                index = ch[i]-'a';   //寻找对应的字母
                if(node.nexts[index]==null){  //如果当前的下标处没有节点，构建一个
                    node.nexts[index] = new TrieNode();
                }
                node =node.nexts[index];   //如果有，就沿着这个节点继续遍历即可
                node.pass++;  //没有就构建初始也要加1，有也要统计路过的次数
            }
            node.end++;     //到达字符串的末尾，end++
        }

        //删除一个字符串,需要遍历一下在不在树中，如果在再遍历一遍删除
        public void delete(String s){
            if(s==null || search(s)==0) return;
            char[] ch = s.toCharArray();
            TrieNode node = root;
            node.pass--;
            int index = 0;
            for(int i=0;i<ch.length;i++){
                index = ch[i]-'a';
                //预判下一个标记的节点将要变为0，也就是之后都没有路径经过了，需要删除节点
                if(--node.nexts[index].pass==0){  //这里的node.pass确实已经删除过了
                    //这里的node是前缀节点
                    node.nexts[index] = null;
                    return ;   //类似于删除了，之后的节点直接断开连接
                }
                node = node.nexts[index];
            }
            node.end--;
        }

        //查询一下word这个单词出现了几次
        public int search(String word){
            if(word==null){
                return 0;
            }
            char[] ch = word.toCharArray();
            TrieNode node = root;
            int index = 0;
            for(int i=0;i<ch.length;i++){
                index = ch[i]-'a';
                if(node.nexts[index]==null){  //查找的字符都找到尾部了都不找到返回0
                    return 0;
                }
                node = node.nexts[index];  //node移动
            }
            return node.end;   //循环结束应该遍历到字符串尾部了，返回end表示以当前node结尾的字符串数量
        }

        //查询一下以word这个单词作为前缀的有几个字符,逻辑一样的
        public int prefixNUmber(String pre){
            if(pre==null) return 0;
            char[] ch = pre.toCharArray();
            int index =0;
            TrieNode node = root;
            for(int i=0;i<ch.length;i++){
                index = ch[i]-'a';
                if(node.nexts[index]==null) return 0;
                node = node.nexts[index];
            }
            return node.pass;
        }
    }
}