Trie 简介

一、Trie简介

　　在计算机科学中，Trie，又称字典树、前缀树、单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

　　Trie树主要是利用词的公共前缀缩小查词范围、通过状态间的映射关系避免了字符的遍历，从而达到高效检索的目的。

　　　　

二、简单代码实现

　　1、结点类

public class TrieNode {
    int level;
    // 只针对英文小写字母
    TrieNode[] children = new TrieNode[26]; // 子节点信息
    TrieNode parent; // 当前节点的父节点

    public boolean isLast;

    public int fre = 1;// 出现频率
}

　　2、Trie类

public class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String str) {
        char[] chars = str.toCharArray();
        TrieNode p = root;
        // 遍历单词的每个字符
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            TrieNode child = p.children[c - 'a'];
            if (child == null) {
                TrieNode nnode = new TrieNode();
                nnode.level = i;
                p.children[c - 'a'] = nnode;
                p = nnode;
            } else {
                p = child;
                child.fre++;
            }
        }
        p.isLast = true;
    }

    /**
     * 深度遍历
     */
    public void printAll() {
        print("", root);
    }

    private void print(String prefix, TrieNode p) {
        if (p.isLast && prefix.length() > 0) {
            System.out.println(prefix + " " + p.fre);
        }
        for (int i = 0; i < 26; i++) {
            if (p.children[i] != null) {
                print(prefix + (char) ('a' + i), p.children[i]);
            }
        }
    }

    public void search(String prefix) {
        char[] chars = prefix.toCharArray();
        TrieNode p = root;
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            TrieNode child = p.children[c - 'a'];
            if (child == null) {// 结算
                return;
            } else {
                p = child;
            }
        }
        print("", p);
    }

}