一、字典树
1，概述
字典树是一种前缀查找树，在前缀匹配查找中应用比较多，查找树的层级取决于字符串长度，时间复杂度o(1),但是他要求每个节点都有26各分支，所以空间开销比较大，是一种典型的以空间换时间的数据结构。
2、实现原理
1）、字典树快速查找是依赖于将一个字符串分解成单个字符，然后每个字符单独作为一个节点，按字符串顺序链接，到达单词结尾时做一个结束标记。一个单词构成一个链表，多个单词时相同位置层级的节点可以合并，就能形成一个树，这个树就是字典树。
字典树要求所有字符串共用一个根起始点，起始点为空不存数据。到达单词结尾点用红色标记。
2）结构体定义
typedef struct Trie{
int count;//用于计数当前节点作为末尾的单词数量，同时作为查找时判断单词到达末尾的标记
Trienode[26];//节点的26个分支
}Trie;
3）、实现
1，初始化
一棵空trie仅包含一个根节点，该点的字符指针均指向空
Tire TireNodeInit()
{
Tire head=(Tire)calloc(1,sizeof(Tire));
head->count=0;
return head;
}
2,插入
当需要插入一个字符串S时，我们令一个指针P起初指向根节点。然后，一次扫描S中的每个字符c：
1.当P的c字符指针指向一个已存在的节点Q,则令P=Q。
2.当P的c字符指针指向空，则新建一个节点Q,令P的c字符指针指向Q,然后令P=Q。
当S中的字符扫描完毕时，在当前节点P上标记它是一个字符串的末尾。

/输入的统一是小写26个字母组成的字符串，这里就不做判断了/
int TrieInsert(char* str, Trie* head)
{
char* p = str;
Trie* node = head;
int idx = 0;
/循环遍历字符串，将每个字符加入到指定节点/
while(p != '\0'){
/*取当前字符相对'a'字符的偏移/
idx = p - 'a';
/*node指向下一层树节点/
node = node[idx];
/如果下一层树为空，则初始化该节点/
if(!node){
node = TrieNodeInit();
}
p++;
}
/此时node处就是该字符串的结尾，结尾标记自增/
node->count++;
return 0;
}
3、查找
当需要检索一个字符串S在Trie中是否存在时，我们令一个指针P起初指向根节点，然后一次扫描s中的每个字符c:
1.若P的c字符指针指向空，则说明S没有被插入过Trie，结束检索。
2.若P的c字符指针指向一个已经存在的节点Q,则令P=Q。
当S中的字符扫描完毕时，若当前节点P被标记为一个字符串的末尾，则说明S在Trie中存在，否则说明S没有被插入过Trie.
可以看出在Trie中，字符数据都体现在树的边（指针）上，树的节点仅保存一些额外信息。例如单词结尾标记等。
int TrieSearch(Trie* head, const char* str){
char* p = str;
Trie* node = head;
int idx = 0;
while(p != '\0'){
idx = p - 'a';
node = node[idx];
/当前字符串不在树内，直接返回0/
if(!node)
return 0;
p++;
}
/返回当前字符串计数个数/
return node->count;
}