这个是很基本的数据结构，建议看一下wiki
我前几天实现了它，只有基本的insert和search，没有对查找child list进行优化，代
码贴出来供参考：
#include
#define MAX_LENGTH 64
using namespace std;
static char buff[MAX_LENGTH];
class Trie {
public:
Trie();
Trie(char value);
bool Insert(const char *str);
bool Search(const char *str) const;
void PrintAll(int pos) const;
private:
char _value;
Trie *_sibling;
Trie *_child;
};
Trie::Trie()
{
_value = 0;
_sibling = NULL;
_child = NULL;
}
Trie::Trie(char value)
{
_value = value;
_sibling = NULL;
_child = NULL;
}
bool Trie::Insert(const char *str)
{
char value = str[0];
if(str == NULL)
{
// cannot insert NULL string
return false;
}
else if(_child == NULL)
{
// append a new child
_child = new Trie(value);
if(value != 0)
return _child->Insert(str + 1);
return true;
}
else
{
Trie *cur = _child;
Trie *past = NULL;
while(cur != NULL)
{
if(cur->_value == value)
{
// try to insert to the next level
if(value == 0)
{
// already exists
return false;
}
// go to next level
return cur->Insert(str + 1);
}
else if(cur->_value > value)
{
// insert before current sibling
if(past == NULL)
{
// there is only one child
_child = new Trie(value);
_child->_sibling = cur;
if(value != 0)
return _child->Insert(str + 1);
else
return true;
}
else
{
// insert the new node among siblings
Trie *newnode = new Trie(value);
past->_sibling = newnode;
newnode->_sibling = cur;
if(value != 0)
return newnode->Insert(str + 1);
else
return true;
}
}
past = cur;
cur = cur->_sibling;
}
// append a new node behind the last sibling
Trie *newnode = new Trie(value);
past->_sibling = newnode;
if(value != 0)
return newnode->Insert(str + 1);
else
return true;
}
}
void Trie::PrintAll(int pos) const
{
Trie *cur = _child;
while(cur != NULL)
{
buff[pos] = cur->_value;
if(cur->_value != 0)
cur->PrintAll(pos + 1);
else
printf("%s\n", buff);
cur = cur->_sibling;
}
}
bool Trie::Search(const char *str) const
{
if(_child == NULL)
return false;
else
{
Trie *cur = _child;
char value = str[0];
while(cur != NULL)
{
if(cur->_value == value)
{
if(value != 0)
return cur->Search(str + 1);
else
return true;
}
else if(cur->_value > value)
return false;
else
cur = cur->_sibling;
}
return false;
}
}
int main(int argc, char *argv[])
{
Trie *root = new Trie();
root->Insert("abc");
root->Insert("abd");
root->Insert("bcd");
root->Insert("efg");
root->Insert("bak");
root->Insert("ab");
memset(buff, 0, MAX_LENGTH);
root->PrintAll(0);
for(int i = 1; i < argc; i++)
{
if(root->Search(argv[i]))
printf("Found string %s\n", argv[i]);
else
printf("Did not find string %s\n", argv[i]);
}
return 0;
}
