字典树及其Java实现

简介：
字典树(Trie)也叫前缀树，是一种树形结构，广泛用于统计和保存大量字符串，利用字符串的公共前缀进行查询，有效提高了字符串的查询速度。

结构：
它是一棵多叉树，规定根节点不存字符，除根节点外，每个子节点仅存一个字符，用Java代码可将其节点定义为这样一个类：

public static class Node {
        public int pass;
        public int end;
        public HashMap child;

        public Node() {
            child = new HashMap<>();
        }
    }

图形上是长这样：

我们平时常见的二叉树每个节点最多只有2个子节点，对于字典树的话子节点的数量是未知的，需要用可以存储多个节点的数据结构来表示，这里用的是map结构，用数组也可以。

操作：
基本操作有插入、查找跟删除。
直接上代码：

public void insert(String word) {
        if (word == null) {
            return;
        }
        char[] chars = word.toCharArray();
        Node node = root;
        node.pass++;
        int index;
        for (int i = 0; i < chars.length; i++) {
            index = chars[i];
            if (!node.child.containsKey(index)) {
                node.child.put(index, new Node());
            }
            node = node.child.get(index);
            node.pass++;
        }
        node.end++;
    }

public int search(String word) {
        if (word == null) {
            return 0;
        }
        char[] chars = word.toCharArray();
        Node node = root;
        int index;
        for (int i = 0; i < chars.length; i++) {
            index = chars[i];
            if (!node.child.containsKey(index)) {
                return 0;
            }
            node = node.child.get(index);
        }
        return node.end;
    }

public int prefixNumber(String pre) {
        if (pre == null) {
            return 0;
        }
        char[] chars = pre.toCharArray();
        Node node = root;
        int index;
        for (int i = 0; i < chars.length; i++) {
            index = chars[i];
            if (!node.child.containsKey(index)) {
                return 0;
            }
            node = node.child.get(index);
        }
        return node.pass;
    }

public void delete(String word) {
        if (search(word) != 0) {
            char[] chars = word.toCharArray();
            Node node = root;
            node.pass--;
            int index;
            for (int i = 0; i < chars.length; i++) {
                index = chars[i];
                if (--node.child.get(index).pass == 0) {
                    node.child.remove(index);
                    return;
                }
                node = node.child.get(index);
            }
            node.end--;
        }
    }

变量名定义的比较清晰，代码逻辑也比较简单，就不啰嗦解释了。