Reiks的技术博客

C/C++/STL/Algorithm/D3D
posts - 17, comments - 2, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Trie树

Posted on 2009-08-28 10:32 reiks 阅读(941) 评论(0)  编辑 收藏 引用 所属分类: 算法与数据结构
/*
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;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理