当前位置: 首页 >> 程序设计 >> 数据结构和算法 >> Trie 树实现源码

Trie 树实现源码

作者：来源：zz 发表时间：2008-05-26 浏览次数：字号：大 中 小

这个应该算是比较标准的trie树结构，但是他的插入实现起来不仅仅是插入本身的单词，可能还需要修改原来的数结构
比如说本身已经存在了bobwhite，现在添加bobwhq，就要在第二层的基础上继续扩展，bobwhite的位置也要重新定位，删除操作也是这样
可能还要上移某些单词，这个昨天试了很久，写出来的都不行。
而且对这种字典树的结构本身我的理解就很混乱。
简化版的trie树

以下这种实现方法是根据别人改编的，昨天被逼得没办法还是觉得简化版的，突然发现个牛人的写法和我的很相似（这着实还让我激动了下下），就边学习边改了，呵呵
它是根据杭电的一道题来写的，以下是我的代码：
http://acm.hdu.edu.cn/showproblem.php?pid=1247

#include<iostream>

#define keyNum 26

#define MaxN 50

struct trie{

struct trieNode{//trie结点的结构

trieNode *link[keyNum];//下标为 'A' , 'B' , 'C' , , 'Z' 的指针数组

int num[keyNum];//插入key的次数

trieNode(){

memset(num,0,sizeof(num));

memset(link,NULL,sizeof(link));

}

void init(){

memset(link,NULL,sizeof(link));

memset(num,0,sizeof(num));

}

};

trieNode* root;

trie()

{

root=(trieNode*)malloc(sizeof(trieNode));//初始化时为root申请了空间

root->init();

}

bool Search(char *);

void Insert(char []);

void Delete(trieNode*);

};

bool trie::Search(char * x)

{

if(*x==0)return false;

trieNode* current=root;

x++;

while(*x){

if(current->link[*(x-1)-'a'])

current=current->link[*(x-1)-'a'];

else break;

x++;

}

if(*x==0&&current->num[*(x-1)-'a'])

return true;

else return false;

}

void trie::Delete(trieNode* t)

{

int i;

for(i=0;i<keyNum;i++)

if(t->link[i])Delete(t->link[i]);

memset(t->num,0,sizeof(t->num));

delete(t);

}

void trie::Insert(char x[])

{

trieNode *current=root;

int i=1;

while(x[i]){

if(current->link[x[i-1]-'a']==NULL){

current->link[x[i-1]-'a']=(trieNode*)malloc(sizeof(trieNode));

(current->link[x[i-1]-'a'])->init();

}

current=current->link[x[i-1]-'a'];

i++;

}

(current->num[x[i-1]-'a'])++;

}

char c[ 50000 ][MaxN],tmp;

int main()

{

trie a;

int i=0,j,num;

while(scanf("%s",c[i])!=EOF)

a.Insert(c[i++]);

num=i;

for(i=0;i<num;i++)

for(j=1;c[i][j];j++){

tmp=c[i][j];

c[i][j]=0;

if(a.Search(c[i])){

c[i][j]=tmp;

if(a.Search(&c[i][j])){

printf("%s ",c[i]);

break;}

}

else c[i][j]=tmp;

}

a.Delete(a.root);

return 0;

}

这个模版还不是很完善~用起来还是不大方便，比如删除节点，我的删除只是写了删所有的，用递归写的。
还有遍历节点，都不是很方便的。
以上代码解释几点：
首先我构造了一格trie的结构：在此结构中有root，和这棵树的基本三个操作
再次trie结构中的每个节点都是trieNode的结构，包括root也是
这棵树是动态生成的，所以对trieNode的init很重要，这点写过的就知道，不Init会出现很多问题的,
在trieNode结构中主要有26个link和26个num，刚开始我自己写的时候就是这26个num搞不清，只写了一个num，这是对树结构的理解混乱造成的
num在这里是标记这个单词插入的次数，为0表示这个单词还没有被插入过
trieNode还有个很重要的成员函数就是init了。

责任编辑 webmaster

相关链接