Java-前缀树

Bertha 。 2023-10-08 22:07 87阅读 0赞

一个多叉树结构

p:经过的次数 P值代表着有多少个x做前缀

e:结尾的次数

如果有一个字符串数组:\{abc,abd,kst\}

那就是新建a,b,c节点 然后复用ab节点 然后新建d节点,然后新建kst节点

### 代码实现: ###

#### 每个节点定义 ####

p代表着有多少个x做前缀

e代表着有多少个x做前缀

nexts 代表着它的分支,26个英文字母 所以二十六种

class Node{
        int p;
        int e;
        Node [] nexts;
        Node(){
             p = 0;
             e = 0;
             nexts = new Node[26];
         }
    }

//直接创建对象数组是不会实例化的 "里面全是null" 要手动实例化

#### 前缀树功能 ####

##### 首先要初始化一个头结点 #####

class Trie{
        Node head = new Node();
    }

##### add 添加一个元素 #####

public void add(String a) {
            char [] str = a.toCharArray();
            Node node = head;
            node.p++;
            for(char x:str) {
                int n = x-'a';
                if(node.nexts[n]==null) {
                    node.nexts[n] = new Node();
                }
                node.nexts[n].p++;
                node = node.nexts[n];
            }
            node.e++;
        }

##### search 查找元素 #####

开头又相同 过程也相同的基础上 以这个字符为结尾有多少 总共就有多少

public int  search(String a) {
            if (a == null) {
                return 0;
            }
            char [] str = a.toCharArray();
            Node node = head;
            for(char x:str) {
                int n = x-'a';
                if(node.nexts[n]==null) {
                    return 0;
                }
                node = node.nexts[n];
            }
            return node.e;
        }

##### delete删除元素 #####

删除元素要注意的点是 如果这个节点的p为0了 就说明这个没有经过这个元素的路径了 直接把本元素置空

public void delete (String a) {
            if(search(a)==0) {
                System.out.println("没有");
                return;
            }
            char [] str = a.toCharArray();
            Node node = head;
            node.p--;
            for(char x:str) {
                int n = x-'a';
                node.nexts[n].p--;
                if(node.nexts[n].p==0) {
                    node.nexts[n]=null;
                    return;
                }
                node = node.nexts[n];
            }
            node.e--;
        }

##### prefixNumber 所有加入的字符串中，有几个是以a这个字符串作为前缀的 #####

这个方法和search方法的区别仅有是返回最后节点的p还是e

public int prefixNumber(String a) {
            if (a == null) {
                return 0;
            }
            char [] str = a.toCharArray();
            Node node = head;
            for(char x:str) {
                int n = x-'a';
                if(node.nexts[n]==null) {
                    return 0;
                }
                node = node.nexts[n];
            }
            return node.p;        
        }
    }