c++ 前缀树

时间：2014-02-25 20:07:10 收藏：0 阅读：465

Trie树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构，如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。

Trie树可以利用字符串的公共前缀来节约存储空间。

参考：http://hi.baidu.com/zealot886/item/08ef4cbe791c404ebb0e124f

下面是我自己实现的trie树

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

#include <iostream>
#include <string>
#include <set>
#include <fstream>
using 
namespace std;
#define MAXSIZE 26
class 
TrieNode
{
public:
    int 
freq;
    char 
nodechar;
    TrieNode *children[MAXSIZE];
    set<int> hashset;
    TrieNode()
    {
        for(int 
i=0; i<MAXSIZE; i++)
        {
            children[i] = NULL;
        }
        freq = 0;
    }
};
 
class 
TrieTree
{
public:
    void 
AddTrieNode(TrieNode *root, string word, int 
id);
    void 
DeleteTrieNode(TrieNode *root, string word);
    int 
wordCount( TrieNode *root, string word);
    set<int> SearchTrie( TrieNode *root,string word);
    TrieTree()
    {
        p_root = new 
TrieNode();
    }
public:
    TrieNode *p_root;
 };
 
void 
TrieTree::AddTrieNode(TrieNode *root, string word, int 
id)
{
 //cout<<word<<endl;
    if(word.length() == 0)
    {return 
;}
    int 
k = tolower(word.at(0)) - ‘a‘;
    if(root->children[k] == NULL)
    {
        root->children[k] = new 
TrieNode();
        root->children[k]->nodechar = word.at(0);
    }
    root->children[k]->freq++;
    root->children[k]->hashset.insert(id);
    string nextword = word.substr(1, string::npos);
  
    AddTrieNode(root->children[k], nextword, id);
}
 
void 
TrieTree::DeleteTrieNode(TrieNode *root, string word)
{
    if(word.length() == 0)
    {return 
;}
    int 
k = word.at(0) - ‘a‘;
    if(root->children[k] == NULL)
    {return 
;}
    if 
(root->children[k]->freq > 0)
    {
        root->children[k]->freq--;
    }
    
    string nextword = word.substr(1, string::npos);
    DeleteTrieNode(root->children[k], nextword);
}
 
int 
TrieTree::wordCount(TrieNode *root, string word)
{
    if(root == NULL)
    {return 
0;}
    int 
num = 0;
    int 
k = word.at(0) - ‘a‘;
    string nextword = word.substr(1, string::npos);
    if(nextword.length() == 0)
    {
        num = root->children[k]->freq;
    }
    else
    {
        if(root->children[k] != NULL)
        {
            num = wordCount(root->children[k], nextword);
        }
    }
 return 
num;
}
 
set<int> TrieTree::SearchTrie( TrieNode *root, string word)
{
    set<int> rset;
    if(root == NULL || word.length() == 0)
    {
        cout<<"str is null"<<endl;
        return 
rset;
    }
    int 
k = word.at(0) - ‘a‘;
    string nextword = word.substr(1, string::npos);
    if(root->children[k] == NULL)
    {
        return 
rset;
    }
    if(nextword.length() == 0)
    {
        return 
root->children[k]->hashset;
    }
    if 
(root->children[k] != NULL)
    {
        rset = SearchTrie(root->children[k], nextword);
    }
  
 return 
rset;
}

原文：http://www.cnblogs.com/laon/p/3566194.html