C++ 高级数据结构——Trie树_marisa trie

trie树，又称字典树或前缀树，是一种有序的、用于统计、排序和存储字符串的数据结构，它与二叉查找树不同，关键字不是直接保存在节点中，而是由节点在书中的位置决定。
一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。
trie树的最大优点就是利用字符串的公共前缀来减少存储空间与查询时间，从而最大限度地减少无谓的字符串比较，是非常高效的字符串查找数据结构。

#include<stdio.h>
#define TRIE_MAX_CHAR_NUM 26
//定义TrieNode
struct TrieNode
{
   
 TrieNode* child[TRIE_MAX_CHAR_NUM];
 bool is_end;
 TrieNode() : is_end(false)
 {
   
  for (int i = 0; i < TRIE_MAX_CHAR_NUM; i++)
  {
   
   child[i] = 0;
  }
 }
};
//TrieNode的前序遍历
void preorder_trie(TrieNode* node, int layer)
{
   
 for (int i = 0; i < TRIE_MAX_CHAR_NUM; i++)
 {
   
  if (node->child[i])
  {
   
   for (int j = 0; j < layer; j++)
   {
   
    printf("---");
   }
   printf("%c", i+'a');
   if (node->child[i]->is_end)
   {
   
    printf("(end)");
   }
   printf("\n");
   preorder_trie(node->child[i], layer + 1);
  }
 }
}
int main()
{
   
 TrieNode root;
 TrieNode n1;
 TrieNode n2;
 TrieNode n3;
 root.child['a' - 'a'] = &n1;
 root.child['b' - 'a'] = &n2;
 root.child['e' - 'a'] = &n3;
 n2.is_end = true;
 TrieNode n4;
 TrieNode n5;
 TrieNode n6;
 n1.child['b' - 'a'] = &n4;
 n2.child['c' - 'a'] = &n5;
 n3.child['f' - 'a'] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60