trie树定义

结构示意图

基本特性

示例代码

trie树定义

Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

结构示意图

基本特性

它有3个基本特性：

1）根节点不包含字符，除根节点外每一个节点都只包含一个字符。

2）从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

3）每个节点的所有子节点包含的字符都不相同。

示例代码

Trie树的类定义：

const int MaxKeySize = 25; //关键码最大位数

typedef struct { //关键码类型

char ch[MaxKeySize]; //关键码存放数组

int currentSize; //关键码当前位数

} KeyType;

class TrieNode { //Trie树结点类定义

friend class Trie;

protected:

enum { branch, element } NodeType; //结点类型

union NodeType { //根据结点类型的两种结构

struct { //分支结点

int num; //本结点关键码个数

TrieNode *link[27]; //指针数组

} brch;

struct { //元素结点

KeyType key; //关键码

recordNode *recptr; //指向数据对象指针

} elem;

}

}

class Trie { //Trie树的类定义

private:

TrieNode *root, *current;

public:

RecordNode* Search ( const keyType & );

int Insert ( const KeyType & );

int Delete ( const KeyType & );

}

Trie树的搜索算法：

RecordNode* Trie::Search ( const KeyType & x ) {

k = x.key;

concatenate ( k, ‘b’ );

current = root;

int i = 0; //扫描初始化

while ( current != NULL && current→NodeType != element && i <= x. ch[i] ) {

current = current→brch.link[ord (x. ch[i])];

i = i++;

};

if ( current != NULL && current→NodeType == element && current→elem.key == x )

return current→recptr;

else

return NULL;

}