Trie tree有时被称为（digital tree）或（radix tree or prefix tree）。
可能是编译器问题，我的实现方法用gcc编译器，debug没问题，但一run就有问题。。。
Debug output:
Starting debugger: C:\TDM-GCC-64\bin\gdb.exe -nx -fullname -quiet -args E:/CodeBlocks_C++Projects/NYOJ/bin/Debug/NYOJ.exe done Setting breakpoints Debugger name and version: GNU gdb (GDB) 7.9.1 Child process PID: 208 [Inferior 1 (process 208) exited normally] Debugger finished with status 0
弄了很久，还以为是我哪里指针处理没做好，但最后不管怎么想都觉得逻辑都没问题，于是换VS，run成功了，而且结果是正确的。
原理很简单，没什么好说的，看wiki上的图就能够明白什么是前缀树，以及如何设计这样的数据结构了。遍历的思路用的是二叉树的后序遍历思想，这里用循环建立了26个子递归，实际上原理是一样的。ps:其实成员letter没有必要有。。。
code：
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 26
#define INDEX(c) ((c) - ‘a‘)
#define ARR_SIZE(strs) (sizeof((strs))/sizeof(strs[0]))
#define FOR(i, range, node) for (i = 0; i < range; i++) node->children[i] = NULL
typedef struct BaseNode {
struct BaseNode* children[SIZE];
char letter;
char*s;
}trie;
trie*init()
{
int i;
trie*root = (trie*)malloc(sizeof(trie));
root->letter = 0;
FOR(i, SIZE, root);
root->s = NULL;
return root;
}
trie*insert(trie*root, char str[])
{
trie*node = root;
int i, j;
for (i = 0; node->children[INDEX(str[i])] != NULL; i++)
{
node = node->children[INDEX(str[i])];
}
while (i < (int)strlen(str))
{
trie*temp = (trie*)malloc(sizeof(trie));
temp->letter = str[i];
FOR(j, SIZE, temp);
temp->s = NULL;
if (i + 1 == (int)strlen(str))
temp->s = str;
node->children[INDEX(str[i])] = temp;
node = temp;
i++;
}
FOR(j, SIZE, node);
return root;
}
trie*search(trie*root, char str[])
{
trie*node = root;
for (int i = 0; i < (int)strlen(str); i++)
{
if (node != NULL)
{
node = node->children[INDEX(str[i])];
// printf("%c -> ", node->letter);
}
else
break;
}
return node;
}
bool remove_helper(trie*node)
{
for (int i = 0; i < SIZE; i++)
{
if (node->children[i] != NULL)
return true;
}
return false;
}
void remove(trie**node, char*str)
{
if (*node != NULL)
{
char c = *str;
++str;
remove(&(*node)->children[INDEX(c)], str);
if (!remove_helper(*node))
{
free(*node);
*node = NULL;
}
}
}
void show(trie*node)
{
if (node != NULL)
{
for (int i = 0; i < SIZE; i++)
{
show(node->children[i]);
}
printf("%s\n", node->s);
}
}
void destory(trie*node)
{
if (node != NULL)
{
for (int i = 0; i < SIZE; i++)
{
destory(node->children[i]);
}
free(node);
node = NULL;
}
}
int main()
{
char strs[][12] = { "tea","eat","engineer","table","profile" };
trie*root;
root = init();
for (int i = 0; i < (int)ARR_SIZE(strs); i++)
{
root = insert(root, strs[i]);
}
show(root);
remove(&root, strs[0]);
// trie*node = search(root, strs[0]);
show(root);
destory(root);
getchar();
return 0;
}
Output:
eat engineer profile table tea (null) (null) (null) eat engineer profile table
参考：
https://github.com/darkchii/cosmos/blob/master/code/data_structures/src/tree/tree/trie/trie.c
https://en.wikipedia.org/wiki/Trie
原文：https://www.cnblogs.com/darkchii/p/9097992.html