前缀树实现思路和例题

前缀树：每次加字符都从头结点开始加，看有没有通向该字符的路有就复用，没有就新建。
e（end）:到该字符为止，该字符串被加入几次。例如：问“bk”字符串被加入几次，发现k处的e=0，则说明一次都没被加入过。
p(pass)：经过该字符有几次。例如：问以”ab“开头的字符串有几个，发现b的p=3，所以有3个。

头节点即代表有多少个以空“”开头的字符串，也代表你总共加入多少个字符串

数组（例如：26个字母）
hash表

插入字符串构建前缀树


在前缀树查找字符串出现几次
提前没路
查找有多少个以某字符串开头的字符串

删除

你如果想删abc，是只删一次的。即沿途p–，最后一个e–

在沿途p–的时候减成0了，怎么办？
删除时d的p减为0，将d下面的结点置为空，释放结点

先判断这个word之前加入过没有
下一个节点p减后=0，将其下结点置空

代码：

import java.util.*;


public class Solution {
    

        public class TrieTreeNode{
        public int pass;
        public int end;
        
        public TrieTreeNode[] nexts;//接下来的有26条路

        //构造方法
        public TrieTreeNode() {
            pass = 0;
            end = 0;
            nexts = new TrieTreeNode[26];
            }
        }
        
         private TrieTreeNode root=new TrieTreeNode();//根节点
     
        
         //插入方法
    public void insert(String word) {
        if (word == null) return;
        //先将字符串转为字符数组
        char[] chars = word.toCharArray();
        //从根节点开始遍历，沿途pass++
        TrieTreeNode node = root;
        node.pass++;
        int path = 0;
        for (int i = 0; i < chars.length; i++) {
            //获得要选择的那条路
            path = chars[i] - 'a';
            //如果路不存在就创建
            if (node.nexts[path] == null) {
                node.nexts[path] = new TrieTreeNode();
            }
            //路存在，就将当前节点下移，沿途pass++
            node = node.nexts[path];
            node.pass++;


        }
        //到字符串最后end++
        node.end++;
    }
    
     //删除
    public void delete(String word){
        if (word==null) return;
        //先查找一下看该字符串是否存在，存在再删除
        int searchNumbers = search(word);
        if(searchNumbers==0) return;

        char[] chars = word.toCharArray();
        //从根节点开始
        TrieTreeNode node=root;
        //根节点的pass--
        node.pass--;
        int path=0;
        for (int i = 0; i  list=new ArrayList();
        //TrieTree trie=new TrieTree();
        for(int i=0;i