Trie|Trie 树内存消耗问题 Trie树内存消耗问题

大家都知道，Trie树（又称字典树）是一种树型数据结构，用于保存大量的字符串。它的优点是：利用字符串的公共前缀来节约存储空间。
相对来说，Trie树是一种比较简单的数据结构，比较易于理解。话说上帝是公平的，简单的东西是要付出相应的代价的！Trie树也有它的缺点，它的内存消耗非常大。下面介绍一个减小内存消耗的小技巧。
【Trie|Trie 树内存消耗问题】我们先看看这个题目：http://acm.sdut.edu.cn/judgeonline/showproblem?problem_id=1500
看看这段程序：

#include
#include
#include
typedef struct node
{
int flag;
struct node *next[26];
}Node;
int tmp;
Node * NewNode()
{
int i;
Node * p = (Node *)malloc(sizeof(Node));
p->flag =0;
for(i =0; i <26; i++)
p->next[i] =0;
return p;
}
void insert(Node * root, char s[])
{
int n = strlen(s);
int i;
Node * p;
p = root;
for(i =0; i < n; i++)
{
if(p->next[s[i] -'a'] == NULL)
p->next[s[i] -'a'] = NewNode();
p = p->next[s[i] -'a'];
}
p->flag =1;
}
void search(Node * root, char s[])
{
int len = strlen(s);
int i;
Node *p;
p = root;
for(i =0; i < len; i++)
{
if(p->next[s[i] -'a'] != NULL)
p = p->next[s[i] -'a'];
}
if(p->flag)
{
p->flag =0;
tmp--;
}
}

void change(char s[])
{
int len, i;
len = strlen(s);
for(i =0; i< len; i++)
if(s[i] >='A'&& s[i] <='Z')
s[i] +=32;
}
int main()
{
int n, m;
char s[11];
Node *root;
while(scanf("%d", &n),n)
{
tmp = n;
scanf("%d", &m);
root = NewNode();
while(n--)
{
scanf("%s", s);
change(s);
insert(root, s);
}
while(m--)
{
scanf("%s", s);
change(s);
search(root, s);
}
printf("%d\n", tmp);
}
return0;
}

这是一个典型的Trie树程序，AC的结果是：

160138

vongang

1500

Accepted

50376K

312MS

GCC

显然，memory很变态！
从上边程序可以看到。root 在while(scanf("%d", &n),n)里边初始化，当一次while(scanf("%d", &n),n)执行完以后，第二次又会给root重新分配空间。这样，原来分配的空间就没有用处了，于是，我们可以在一次程序执行完以后，将root的空间free掉。当然不是简单的free(root)，这里需要一个del（）函数，代码如下：