字典树（前缀树、Trie）概念介绍、静态实现、动态实现

字典树介绍

又称前缀树，Trie树，是一种多叉树。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串）。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。
它的最基本的操作是插入一个字符串，和查询。

存储原理

多叉树结构：
一般的，如果我们想存储一棵一般的树，树的节点可以这样写：

struct OrdinaryTrieNode{
	int val;
	vector<OrdinaryTrieNode*> childs;
};

而如果是字典树的话：
假设字符串仅由大小为n的字符集中的字符构成（比如26个小写字母），那么每个节点的字节就可以有n个指向。

const int size = 26;
struct TrieNode{
	TrieNode* childs[size];
};

发现，节点本身并没有存储字符的值。那么如何知道它的后继字符有哪些呢？
这个时候，我们可以把将字符映射到一个索引，然后让父节点的childs数组索引存储这个节点。

char c;
TrieNode* parent;
parent->childs[c-'a'] = new TrieNode;

这个时候parent节点就有了一个新的子节点，对应的字符为c;
于是，其实我们发现真正字符的信息其实是存储在父节点与子节点的边上，节点本身只是存储着它的子节点。

（图来自互联网 ）
那么怎么知道记录一个字符串的结束呢，比如字符串aabb，其实并不代表aab出现在字典树里。
根据不同实现，也有不同的解决办法。
一种方法是，在结构体里加一个变量，表明这个节点是否是字符串的结尾。

struct TrieNode{
	bool isEnd;
	TrieNode* childs[size];
};

字典树的静态实现

数组模拟，下标代替指针。
其中，编号为1的节点表示根节点，0表示空指。

const int maxnode = maxn*maxlen;  //字符串个数*字符串的长度
int trie[maxnode][size],tot=1; //size是字符集的大小，tot保存节点个数
bool end[maxnode]  // 结尾标记

int idx(char c)
{
	return c - 'a';
}
//插入字符串的方法
void insert(char* str)
{
	int len = strlen(str),p=1;  //根节点为1
	for(int i=0;i<len;i++)
	{
		int id = idx(str[i]);
		if(!trie[p][id]) //如果这个节点不存在，新建一个
			trie[p][id]= ++tot;
		p = trie[p][id];
	}
	end[p]=true;
}
//查找字符串的方法
bool find(char* str)
{
	int len = strlen(str),p=0;
	for(int i=0;i<len;i++)
	{
		p = trie[p][idx(str[i])];
		if(!p) return false;
	}
	return end[p];
}

字典树的动态实现

版本一：
其中，析构函数用递归实现。

class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new TrieNode;
    }
    
    ~Trie(){
        destroy(root);
    }

    /** Inserts a word into the trie. */
    void insert(const string &word) {
        TrieNode *p = root;
        for(char c:word){
            if(p->childs[c-'a'] == nullptr){
                p->childs[c-'a'] = new TrieNode;
            }
            p = p->childs[c-'a'];
        }
        p->isEnd = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(const string &word) {
        TrieNode *p = root;
        for(char c:word){
            if(p->childs[c-'a']==nullptr){
                return false;
            }
            p = p->childs[c-'a'];
        }
        return p->isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(const string &prefix) {
        TrieNode *p = root;
        for(char c:prefix){
            if(p->childs[c-'a']==nullptr){
                return false;
            }
            p = p->childs[c-'a'];
        }
        return true;
    }
private:
    struct TrieNode{    
        bool isEnd = false;
        TrieNode* childs[26] = {0};
    };
    TrieNode* root ;
    void destroy(TrieNode* root){
        if(!root){
            return ;
        }
        for(TrieNode* pt:root->childs){
            destroy(pt);
        }
        if(root){
            delete root;
            root = nullptr;
        }
    }    
};

版本2：
树的节点用

 struct Node{
        bool isEnd = false;
        unordered_map<char,Node*> childs;
    };

其中析构函数用迭代实现（用一个queue<TrieNode>,遍历这棵树就可）。

class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new Node;
    }

    ~Trie(){
        queue<Node*> q;
        q.push(root);
        while(!q.empty()){
            Node* pn = q.front();
            q.pop();
            for(unordered_map<char,Node*>::iterator it=pn->childs.begin(); it!=pn->childs.end();it++ ){
                q.push(it->second);
            }
            delete pn;
            pn = nullptr;
        }
    }
    
    /** Inserts a word into the trie. */
    void insert(const string &word) {
        Node* p = root;
        for(char c:word){
            if(!p->childs.count(c)){
                p->childs[c] = new Node;
            }
            p = p->childs[c];
        }
        p->isEnd = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(const string &word) {
        Node* p = root;
        for(char c:word){
            if(!p->childs.count(c)){
                return false;
            }
            p = p->childs[c];
        }
        return p->isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(const string &prefix) {
        Node* p = root;
        for(char c:prefix){
            if(!p->childs.count(c)){
                return false;
            }
            p = p->childs[c];
        }
        return true;
    }
private:
    struct Node{
        bool isEnd = false;
        unordered_map<char,Node*> childs;
    };
    Node * root;    
};