概述
在浏览器搜索栏里输入几个字，就弹出了以你的输入为开头的一系列句子。浏览器是怎么知道你接下来要输什么的？
来看看字典树干了什么。
字典树是一种高效记录字符串和查找字符串的数据结构。它以每个字符作为一个节点对字符串进行分割记录，节点形成树状结构，在录入或查找时只需沿着对应的路径进行操作即可。
结构如下：
字典树class类trie由节点class类trie_node相连接构成，每个节点都有以下成员：一个计数器，本节点编号，一个记录此处是否是字符串结尾的变量和一个next指针数组，这个数组的每个元素都指向下一个trie_node节点或是空指针。
概念如下：
根节点root编号为0,表示从此处开始构建字典树。它只有next数组，表示从此以后才是字符串的第一个字符。
对一个字符串进行枚举，取char str[i]=ch；
对于任何一个节点node和任何一个字符char ch，node->next[ch]表示从node节点再加上ch字符会走到的子节点。
如果node=node->next[ch]还不存在（空指针），那就为其创建一个新节点，标记其为整棵树的第i个节点，然后进入那个节点；
如果已经存在，那就将此处的计数器cnt+1，然后继续取下一个ch，继续向下走。
一直到字符串取完，在最后的节点处进行标记，表示到此为止是一个完整的字符串。
如上，遍历字符串"and",取第一个字符'a'。起始node=root，从root开始node=root->next['a']就进入了a节点，a节点的cnt++。现在node在节点a处。依次取'n'和‘’d',从n节点进入d节点后发现字符串已结束，那就在此处记录为结束位置。
形象记忆：
输入的字符串被依次嵌入了这棵树，树上的节点被嵌入的次数越多，这个节点的颜色就越深（cnt越大），黑色的节点是某个字符串的终点。
接下来我们通过封装array类,实现动态数组的一些基本功能 。（Code和测试案例附后）
成员变量
定义class类trie，封装三个成员变量：const int branches; trie_node* root; size_t val_size;
（size_t 是C/C++标准在stddef.h中定义的（这个头文件通常不需要#include），size_t 类型专门用于表示长度，它是无符号整数。）
我们还要额外定义嵌套类trie_node，它只能被trie类使用，这就实现了结构功能的封装。
const int branches表示允许每个节点设置的边数（指针数组的长度），更大的数值可以实现更强的记录能力，我们数值它的值为128，那么数字字符、小写字母与大写字母就都可以储存在trie中。
（注意：node->next[ch]表示从node节点再加上ch字符会走到的子节点。）
trie_node* root指向根节点。
size_t val_size数的大小（真实长度）。
（C++11标准以后提供你在类成员声明时进行初始化，所以size_t size=0是合法的）
class trie {
private:
class trie_node {
private:
friend class trie;
...
};
const int branches;
trie_node* root;
size_t val_size = 0;
public:
...
}定义class类trie，封装四个成员变量：int idx; int cnt; std::string str; trie_node**next
声明友员类friend class trie，这使得trie可以操控trie_node的私有成员，将trie_node的构造函数和析构函数定为私有，这样就只用trie能管理trie_node了。
int idx：本节点编号。
int cnt：记数器（本节点被访问的次数）。
string str：如果插入时某个字符串在此结束，那就保存下来（起始可以直接用bool 量声明是否有字符串结束，但我们希望维护的trie有更强大的功能）。
trie_node**next：指针数组，指向接下来的子节点。
另有构造函数接受一个branch，使该节点获得有branch个子节点。
析构函数无须函数体，完全由trie类代管，略去不表。
class trie_node {
private:
friend class trie;
int idx = 0;
int cnt = 0;
std::string str = "";
trie_node** next;
trie_node(int branch) {
next = new trie_node *[branch]();
};
~trie_node() {};
};创建销毁
提供唯一构造函数：trie(int branch=128)，默认节点边数为128，不更改时无须传参。生成一个根节点。
禁用拷贝构造和重载等于号：默认拷贝构造和等于号进行，指针变量赋值，这存在极大问题（两指针争抢堆上的数据同一块数据），另有深层拷贝解决，略去不表。
析构函数：~trie()，在堆上申请的树状数据结构需要递归清理，用erase函数解决。
trie(int branch=128):branches(branch) {
root = new trie_node(branches);
}
trie(const trie& another) = delete;
~trie() {
erase(root);
}
trie& operator=(const trie& another) = delete;void erase（）：对每个node都遍历子节点，先删子节点，再删父节点。erase需要声明在private中被封存。
void erase(trie_node* node) {
if (!node)return;
for (int i=0;i<128;i++)
erase(node->next[i]);
delete node;
}字符串插入
插入函数：void insert(const std::string str)接收一个字符串string（传入c风格字符串const char*也是合法的，它会作为参数初始化函数中的string str）
定义p指针将string迭代嵌入trie中。
枚举str中的字符ch，如果p->next[ch]不存在就进行构造再迭代，否则直接迭代。
void insert(const std::string str) {
trie_node *p= root;//从根节点root开始
for (const char& ch : str) {//枚举str
if (p->next[ch] == nullptr) {//不存在就构造
p->next[ch] = new trie_node(branches);
p->idx=++val_size;//新节点需要编号
}
p->cnt++;//计数器计数
p = p->next[ch];
}
p->str = str;//在字符串结束的位置保存字符串
}字符串查询
我们提供四种查询。
完整查询：bool query_string(const std::string str)，查询str是否完整记录在案，流程与插入基本一致，遇到空节点或末尾节点无记录则返回false，否则返回true。
前缀查询：bool query_prefix(const std::string str)，与上一个函数基本一致，但不判断末尾节点。
前缀字符串集查询：std::vector<std::string> query_prefix(const std::string str)，返回一个所有以str为前缀的字符串数组。
查询前缀时与上个函数相同，随后使用深度优先搜索进行搜索所有以str为前缀的字符串并收集。
大小查询：size_t size()，返回val_size。
bool query_string(const std::string str) {
trie_node* p = root;
for (const char& ch : str) {
if (p->next[ch] == nullptr) return false;
else p = p->next[ch];
}
if (p->str.empty())return false;
else return true;
}
bool query_prefix(const std::string str) {
trie_node* p = root;
for (const char& ch : str) {
if (p->next[ch] == nullptr) return false;
else p = p->next[ch];
}
return true;
}
std::vector<std::string> query_prefix_all(const std::string str) {
std::vector<std::string> ans;
trie_node* p = root;
for (const char& ch : str) {
if (p->next[ch] == nullptr) return {};
else p = p->next[ch];
}
DFS(p,ans);
return ans;
}
size_t size() {
return size;
}void DFS（const trie_node* node, std::vector<std::string>& ans）：对每个node都遍历子节点，先存本节点，再存子节点。DFS需要声明在private中被封存。
void DFS(const trie_node* node, std::vector<std::string>& ans) {
if (node->str.empty() == false)ans.push_back(node->str);//此处有记录就加入ans
for (int i = 0; i < branches; i++)
if (node->next[i])DFS(node->next[i], ans);//有子节点就进去看看
}复杂度
时间复杂度：插入：O(n) 查询：O(m)
空间复杂度：插入：O(n*m) 查询：O(1)
n：插入字符串数目
m：插入/查询字符串长度
Code
#pragma once
#include <string>
#include <vector>
class trie {
private:
class trie_node {
private:
friend class trie;
int idx = 0;
int cnt = 0;
std::string str = "";
trie_node** next;
trie_node(int branch) {
next = new trie_node *[branch]();
};
~trie_node() {};
};
const int branches;
trie_node* root;
size_t val_size = 0;
void erase(trie_node* node) {
if (!node)return;
for (int i=0;i<128;i++)
erase(node->next[i]);
delete node;
}
void DFS(const trie_node* node, std::vector<std::string>& ans) {
if (node->str.empty() == false)ans.push_back(node->str);
for (int i = 0; i < branches; i++)
if (node->next[i])DFS(node->next[i], ans);
}
public:
trie(int branch=128):branches(branch) {
root = new trie_node(branches);
}
trie(const trie& another) = delete;
~trie() {
erase(root);
}
trie& operator=(const trie& another) = delete;
void insert(const std::string str) {
trie_node *p= root;
for (const char& ch : str) {
if (p->next[ch] == nullptr) {
p->next[ch] = new trie_node(branches);
p->idx=++val_size;
}
p->cnt++;
p = p->next[ch];
}
p->str = str;
}
bool query_string(const std::string str) {
trie_node* p = root;
for (const char& ch : str) {
if (p->next[ch] == nullptr) return false;
else p = p->next[ch];
}
if (p->str.empty())return false;
else return true;
}
bool query_prefix(const std::string str) {
trie_node* p = root;
for (const char& ch : str) {
if (p->next[ch] == nullptr) return false;
else p = p->next[ch];
}
return true;
}
std::vector<std::string> query_prefix_all(const std::string str) {
std::vector<std::string> ans;
trie_node* p = root;
for (const char& ch : str) {
if (p->next[ch] == nullptr) return {};
else p = p->next[ch];
}
DFS(p,ans);
return ans;
}
size_t size() {
return val_size;
}
};测试
#include "trie.h"
#include <iostream>
using namespace std;
int main()
{
trie Trie;
Trie.insert("hello");
Trie.insert("hello world");
string str = "hello world and you";
Trie.insert(str);
vector<string>&& ans1 = Trie.query_prefix_all("hello");
for (const string& i : ans1)cout << i << endl;
cout << endl;
Trie.insert("Hello");
Trie.insert("World!");
Trie.insert("Hello World!");
cout << (Trie.query_string("Hello ") ? "YES" : "NO") << endl;
cout << (Trie.query_prefix("Hello ") ? "YES" : "NO") << endl;
cout << endl;
vector<string>&& ans2 = Trie.query_prefix_all("");
for (const string& i : ans2)cout << i << endl;
cout << endl;
return 0;
}