首页 > 代码库 > 字典树

字典树

字典树可以用来快速查找字符串前缀

技术分享

a.b.e.h汇聚于一点,该点为根节点。从根节点开始,每遇到一个红点就可以组成一个单词(相当于红点被标记)。

节点的建立:

 1 struct Nod{
 2      bool is; //bool为布尔型变量,只有真假
 3      Nod *next[26]; //有26个字母
 4      Nod(){
 5          is = false;
 6          for(int i = 0; i < 26; i ++){
 7              next[i] = NULL; //节点所指的位置为空指针
 8          }
 9      }
10  };

插入

1 void mkTrie(Nod *root,char *s){
2      Nod*p = root;
3      for(int i = 0; s[i]; i ++){
4          int a = s[i] - 0; //a为0
5          if(p->next[a]==NULL)p->next[a] = new Nod; //如果a所指的位置下面没有子节点,则在a下面创建一个新的子节点
6          p = p->next[a]; //创建新节点
7      }
8      p->is = true; //表示标记了单词中最后一个字母,可以组成一个单词
9  }

删除:很多题目有很多组数据,如果不删除释放空间的话,很容易导致Memory Limit Exceeded(内存超限)

 1 void deleTrie(Nod *p){
 2      if(p == NULL) return;
 3      for(int i = 0; i < 26; i ++){
 4          if(p->next[i] != NULL){
 5              deleTrie(p->next[i]);
 6          } //循环查找从0到25的字母,若字母的子节点不为零,则继续向下查找,直到找到被标记即为红点的字母,从而删除红点字母,此时循环向上查找,以此类推从而删除所有字母
 7      }
 8      free(p);
 9      return ;
10  }

查找

1 int find(){
2      Nod* p = &t;
3      for(int i = 0; s[i]; i ++){
4          int a = s[i]-a;
5          if(p->next[a]==NULL) return 0;
6          p = p->next[a];
7      }
8      return p->num; //若找到的字母的子节点为零则返回零,否则,继续寻找直到找到被标记的字母
9  }

 

字典树