The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

Trie树|字典树的简介及实现(转)

Trie,又称字典树、单词查找树,是一种树形结构,用于保存大量的字符串。它的优点是:利用字符串的公共前缀来节约存储空间。
相对来说,Trie树是一种比较简单的数据结构.理解起来比较简单,正所谓简单的东西也得付出代价.故Trie树也有它的缺点,Trie树的内存消耗非常大.当然,或许用左儿子右兄弟的方法建树的话,可能会好点.

其基本性质可以归纳为:
1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。

其基本操作有:查找 插入和删除,当然删除操作比较少见.我在这里只是实现了对整个树的删除操作,至于单个word的删除操作也很简单.

搜索字典项目的方法为:

(1) 从根结点开始一次搜索;

(2) 取得要查找关键词的第一个字母,并根据该字母选择对应的子树并转到该子树继续进行检索;

(3) 在相应的子树上,取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
(4) 迭代过程……
(5) 在某个结点处,关键词的所有字母已被取出,则读取附在该结点上的信息,即完成查找。
其他操作类似处理.


 

/*
Name: Trie树的基本实现 
Author: MaiK 
Description: Trie树的基本实现 ,包括查找 插入和删除操作
*/

#include
<algorithm>
#include
<iostream>
using namespace std;

const int sonnum=26,base='a';
struct Trie
{
    
int num;//to remember how many word can reach here,that is to say,prefix
    bool terminal;//If terminal==true ,the current point has no following point
    struct Trie *son[sonnum];//the following point
}
;
Trie 
*NewTrie()// create a new node
{
    Trie 
*temp=new Trie;
    temp
->num=1;temp->terminal=false;
    
for(int i=0;i<sonnum;++i)temp->son[i]=NULL;
    
return temp;
}

void Insert(Trie *pnt,char *s,int len)// insert a new word to Trie tree
{
    Trie 
*temp=pnt;
    
for(int i=0;i<len;++i)
    
{
        
if(temp->son[s[i]-base]==NULL)temp->son[s[i]-base]=NewTrie();
        
else temp->son[s[i]-base]->num++;
        temp
=temp->son[s[i]-base];
    }

    temp
->terminal=true;
}

void Delete(Trie *pnt)// delete the whole tree
{
    
if(pnt!=NULL)
    
{
        
for(int i=0;i<sonnum;++i)if(pnt->son[i]!=NULL)Delete(pnt->son[i]);
        delete pnt; 
        pnt
=NULL;
    }

}

Trie
* Find(Trie *pnt,char *s,int len)//trie to find the current word
{
    Trie 
*temp=pnt;
    
for(int i=0;i<len;++i)
        
if(temp->son[s[i]-base]!=NULL)temp=temp->son[s[i]-base];
        
else return NULL;
    
return temp;
}
 


转自:http://hi.baidu.com/luyade1987/blog/item/2667811631106657f2de320a.html

posted on 2009-04-21 12:08 abilitytao 阅读(26079) 评论(12)  编辑 收藏 引用

评论

# re: Trie树|字典树的简介及实现(转) 2010-08-25 13:16 renenglish

强,子树查找的时候不用遍历,我的就需要遍历比较…你是咋想到的?  回复  更多评论   

# re: Trie树|字典树的简介及实现(转)[未登录] 2010-08-25 14:00 abilitytao

@renenglish
这个是经典的东西。。。  回复  更多评论   

# re: Trie树|字典树的简介及实现(转)[未登录] 2010-10-30 00:15 Michael

好东西,转了  回复  更多评论   

# re: Trie树|字典树的简介及实现(转) 2011-09-13 17:05 明样

把26个字母的指针都存掉冗余太大了,浪费这么多空间只换了一点点性能不值得- -@renenglish
  回复  更多评论   

# re: Trie树|字典树的简介及实现(转) 2012-07-11 14:40 noah

to 博主:
感觉你的代码实现有点问题,我不知道您测试过没有。
在节点定义中,terminal 为ture的时候,不能有子节点。但是遇到这种单词怎么处理啊。
单词一:blackberry
单词二:black
如果先存储black,然后terminal之后,那blackberry岂不是要又要创建一个子树。这样显然违背trie树的原则。
而且你的插入方法中,只要插入就terminal。
如有问题,可找我讨论。我的mail是nklizhongnan@gmail.com.  回复  更多评论   

# re: Trie树|字典树的简介及实现(转) 2013-01-23 12:05 msa

恩,代码有问题啊  回复  更多评论   

# re: Trie树|字典树的简介及实现(转)[未登录] 2013-03-26 14:49 长风

@明样
同意明样,这样的冗余度非常非常大。  回复  更多评论   

# re: Trie树|字典树的简介及实现(转) 2013-04-22 08:39 ptolemy

而且查找的话,如果已经插入单词blackberry,那么它所有的前缀如black等也都查得出,即使这些单词并没有被插入过?  回复  更多评论   

# re: Trie树|字典树的简介及实现(转) 2013-05-31 17:06 fully

@ptolemy
应该在find到最后一个字符时,判断terminal==true?  回复  更多评论   

# re: Trie树|字典树的简介及实现(转) 2013-11-16 10:12 dellenzhang

所以sonnum应该写为27,其中有一个为空,再terminal=true。相当于结束标记。  回复  更多评论   

# re: Trie树|字典树的简介及实现(转) 2014-01-06 13:31 aa88kk

搜索过来, 大概看了下, 觉得有问题.
trie会多用一些空间,但不是很多. 因为每个节点只是一个字符(或最小的字符组合).
26个子节点只是极端情况.  回复  更多评论   

# re: Trie树|字典树的简介及实现(转) 2014-03-18 16:40

Find函数里的返回是不是有问题呢?不是不能返回局部对象的指针吗  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理