字典树学习材料

字典树，又称单词查找树，Trie树，是一种树形结构，典型应用是用于统计，排序和保存大量的字符串，所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度的减少无谓的字符串比较，查询效率比哈希表高。Trie树示意图如附件图所示：该trie树存有abc、d、da、dda四个字符串，如果是字符串会在节点的尾部进行标记。没有后续字符的branch分支指向NULL。Trie的特点：1. 根结点不包含任何字母。2. 其余结点仅包含一个字母(非元素)3. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。 4. 每个结点的子节点包含字母不同。5. 采用标记的方法确定是否为字符串。Trie的缺点：动态建树时，用new很费时；静态建树时，预存节点数很费空间。

Trie树的模板一：静态建树：

#include<iostream>
using namespace std;
const int Max = 1000;
const int branchNum = 26;
 
struct tree_node{
    int count;
    bool isstr;
    tree_node *next[branchNum];
}root, node[Max];
int p = 0;    //  静态建树的特点，记录用了几个tree_node，则下一个节点为node[p]。
 
void insert(char *word){
    tree_node *location = &root;   //  起初先指向根，再一层层向下查找。
    while(*word){
        if(location->next[*word-'a'] == NULL){
            node[p].count = 0;     //  初始化新节点。
            node[p].is = false;
            memset(node[p].next, NULL, sizeof(node[p].next));
            location->next[*word-'a'] = &node[p ++];
        }
        location = location->next[*word-'a'];
        location->count ++;
        word ++;
    }
    loaction->isstr = true;
}
 
bool search(char *word){
    tree_node *loaction = &root;
    while(*word && loaction){
        loaction = loaction->[*word-'a'];
        word ++;
    }
    return (location != NULL && location->isstr);
}
 

 Trie的模板二：动态建树

 

struct tree_node
{
    bool isstr;     //   记录此处是否构成一个串。
    tree_node  *next[branchNum];    //   指向各个子树的指针,下标0-25代表26字符
    tree_node(){
        isstr = false;
        memset(next, NULL, sizeof(next));
    }
}root;
 
void insert(char *word){     //  向以root为根结点的树中插入串word
    tree_node *location = &root;
    while(*word){
        if(location->next[*word-'a'] == NULL){     //  不存在则建立
            tree_node *tmp = new tree_node;
            location->next[*word-'a'] = tmp;
        }
        location = location->next[*word-'a'];  //  每插入一步，有一个新串经过，指针要向下移动
        word ++;
    }
    location->isstr = true;
}
 
bool search(char *word){
    tree_node *location = &root;
    while(*word && location){
        location = location->next[*word-'a'];
        word ++;
    }
    return (location != NULL && location->isstr);
}

 

关于字典树的材料大多大同小异，需要自己进一步去理解去消化~~