Trie树的基本性质可以归纳为：
（1）根节点不包含字符，除根节点外的每个节点只包含一个字符。
（2）从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
（3）每个节点的所有子节点包含的字符串不相同。

//
// Created by krislyy on 2018/11/1.
// 前缀查询，字典树
//

#include <iostream>

#ifndef ALGORITHM_TRIE_H
#define ALGORITHM_TRIE_H

const static int MAX = 26; //字符集大小

class TrieNode {
public:
    int count;              //统计单词前缀出现的次数
    TrieNode *next[MAX];    //指向各个子树的指针
    bool isWord;           //用来标记是否构成了一个完整的词
};

class Trie {
private:
    TrieNode Memory[1000000]; //TODO：为了省事，此处直接使用数组
    TrieNode* pRoot;

public:
    Trie(){
        pRoot = nullptr;
    }

    //根节点
    TrieNode* RootNode(){
        return pRoot;
    }

    //创建新节点
    TrieNode* CreateTrieNode(){
        static int allocp = 0;
        TrieNode *p;
        p = &Memory[allocp++];
        p->count = 1;
        p->isWord = false;
        for (int i = 0; i < MAX; ++i) {
            p->next[i] = nullptr;
        }
        return p;
    }

    //插入
    void InsertTrie(const char *s){
        int i, k;
        TrieNode *p;
        if(!(p = pRoot)){
            p = pRoot = CreateTrieNode();
        }
        i = 0;
        while(s[i]){
            k = s[i++] - 'a'; //确定branch
            if(k < 0 || k > MAX -1){
                continue;
            }
            if(!p->next[k])
                p->next[k] = CreateTrieNode();
            else
                p->next[k]->count++;
            p = p->next[k];
        }
        p->isWord = true;
    }

    //查找
    int SearchTrie(const char* s) {
        TrieNode *p;
        int i, k;
        if(!(p = pRoot)){
            return 0;
        }
        i = 0;
        while(s[i]){
            k = s[i++] - 'a';
            if(p->next[k] == nullptr)
                return 0;
            p = p->next[k];
        }
        return p->count;
    }

    //遍历
    void TraversalTrie(TrieNode *pNode) {
        int i;
        static char word[100] = {0};
        static int j = 0;

        TrieNode *p;
        if(!(p = pNode))
            return;

        for(i=0; i < MAX; i++) {
            if(p->next[i] == nullptr) {
                continue;
            }
            word[j++] = i + 'a';
            if(p->next[i]->count > 0 && p->next[i]->isWord) {
                word[j] = '\0';
                printf("%-20s %-8d\n", word,  p->next[i]->count);
            }
            TraversalTrie(p->next[i]);
            j--;

        }
        return;
    }
};
#endif //ALGORITHM_TRIE_H