字典树

存储方式：数组或struct结构体

数组储存：

const int charsize = 26;//字符集大小
​
//记录此节点的子节点编号
//这里默认的全是小写字母
int nxt[maxn + 1][charsize];
​
//表示此编号节点是否为终止节点
bool isend[maxn + 1];
​
//cnt储存当前的节点编号数
int root = 0, cnt = 0;

字典树的插入

从根节点开始加入一条表示当前字符串的路径，在过程中如果没有对应的字符节点就新建一个

//s为等待插入的字符串，下标从1开始，len为字符串长度
void insert(char s[], int len) {
    int now = 0;
    for (int i = 1; i <= len; i++) {//注意题意是从1至n还是从0至n-1
        int x = s[i] - 'a';
        if (!nxt[now][x]) {//now表示当前位置编号，x表示下一个节点的字母（在这里默认是小写字母）
            nxt[now][x] = ++cnt;
        }
        now = nxt[now][x];
    }
    isend[now] = true;
}

字典树的查找：

从根节点开始，如果有对应的字符就向下跳，如果没有就失败。最后判断字符串末尾的节点有没有结束标记

//s为等待查找的字符串，下标从1开始，len为字符串长度
bool search(char s[], int len) {
    int now = 0;
    for (int i = 1; i <= len; i++) {
        int x = s[i] - 'a';
        if (!nxt[now][x]) {
            return false;
        }
        else now = nxt[now][x];
    }
    return isend[now];
}

字典树的struct存储方式

//简单写法
struct TreeNode {
    int nxt[charsize];
    bool isend;
}tree[maxn + 1];
​
//字符集较大时
struct TreeNode {
    unordered_map<char, int>nxt_map;
    bool isend;
}tree[maxn + 1];
​
//指针
struct TreeNode {
    TreeNode* nxt[charsize];
    bool isend;
}*root;

例题：

给你 n 个两两不同的字符串，你要按字典序从小到大的顺序将这些字符串排好，再按顺序输出。

字符串按字典序排序是指以字符串第 i 个字符作为第 i 关键字进行的排序，空字符小于字符集内任何字符。

int n, m, nxt[500001][26], cnt = 0, a[101];
bool isend[500001];
char str[101];
​
void inline dfs(int now, int depth) {
    if (isend[now]) {
        for (int i = 0; i < depth; i++) {
            printf("%c", a[i] + 'a');
        }
        printf("\n");
    }
    for (int i = 0; i < 26; i++) {
        if (nxt[now][i]) {
            a[depth] = i;
            dfs(nxt[now][i], depth + 1);
        }
    }
}
void solve() {
    int n, m;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", str);
        int len = strlen(str);
        int now = 0;
        for (int j = 0; j < len; j++) {
            int x = str[j] - 'a';
            if (!nxt[now][x]) {
                nxt[now][x] = ++cnt;
            }
            now = nxt[now][x];
        }
        isend[now] = true;
    }
    dfs(0, 0);
}