前缀树笔记

前缀树是一种多叉树，可实现查询以某个字符串作为前缀的字符，有多少个字符串以某一个字符串开头，有多少个字符串以某个节点结尾等

public class QZTree {
    static class Node {
        int through;//通过节点次数
        int end;//该节点结尾次数
        HashMap map;

        public Node() {
            this.map = new HashMap<>();
        }

        public Node(int through, int end) {
            this.through = through;
            this.end = end;
            this.map = new HashMap<>();
        }
    }

    private Node head = null;

    public QZTree() {
        head = new Node();
    }

    public void insert(String str) {
        if (null == str && "".equals(str)) {
            return;
        }
        char[] chars = str.toCharArray();

        insertStr(chars, head, 0);

    }


    public void insertStr(char[] chars, Node node, int i) {
        if (i >= chars.length) {
            return;
        }
        HashMap map = node.map;
        if (map.containsKey(String.valueOf(chars[i]))) {
            Node node1 = map.get(String.valueOf(chars[i]));
            node1.through++;
            if (i == chars.length - 1) {
                node1.end++;
            }
            insertStr(chars, node1, ++i);
        } else {
            Node cha = null;
            if (i == chars.length - 1) {
                cha = new Node(0, 1);
            } else {
                cha = new Node(0, 0);
            }
            map.put(String.valueOf(chars[i]), cha);
            insertStr(chars, node, i);
        }
    }


    public boolean hasStr(String str) {

        if (null == str && "".equals(str)) {
            return false;
        }
        char[] chars = str.toCharArray();


        return search(chars, head, 0);
    }

    public boolean search(char[] chars, Node node, int i) {
        if (i >= chars.length) {
            return false;
        }
        boolean isHas = false;
        HashMap map = node.map;
        if (map.containsKey(String.valueOf(chars[i]))) {
            Node node1 = map.get(String.valueOf(chars[i]));
            if (node1.end != 0 && i == chars.length - 1) {
                return true;
            } else {
                isHas = search(chars, node1, ++i);
            }
        }
        return isHas;
    }


    public void removeStr(String str) {
        if (null == str && "".equals(str)) {
            return;
        }
        char[] chars = str.toCharArray();

        if (search(chars, head, 0)) {
            delectStr(chars, head, 0);
        }
    }

    public void delectStr(char[] chars, Node node, int i) {

        if (i >= chars.length) {
            return;
        }
        HashMap map = node.map;
        if (map.containsKey(String.valueOf(chars[i]))) {
            Node node1 = map.get(String.valueOf(chars[i]));
            node1.through--;
            if (0 == node1.through) {
                map.remove(String.valueOf(chars[i]));
                return;
            } else {
                if (i == chars.length - 1) {
                    node1.end = 0;
                    return;
                } else {
                    delectStr(chars, node1, ++i);
                }
            }
        }
    }

    public static void main(String[] args) {
        QZTree qzTree = new QZTree();
        qzTree.insert("inhu");
        qzTree.insert("inhuyt");
        qzTree.removeStr("inhu");
        boolean inhu = qzTree.hasStr("inhuyt");
        System.out.println(inhu);
    }
}