网站 地区加关键词,eclipse做网站代码,公司电商网站建设费用怎么记账,自己建设网站不会咋办呀前缀树 1. 前缀树的的介绍2.前缀树的实现2.1插入功能2.2删除功能2.3查找前缀和查找单词功能2.4 哈希表版本 1. 前缀树的的介绍 在计算机科学中#xff0c;trie#xff0c;又称前缀树或字典树#xff0c;是一种有序树#xff0c;用于保存关联数组#xff0c;其中的键通常是… 前缀树 1. 前缀树的的介绍2.前缀树的实现2.1插入功能2.2删除功能2.3查找前缀和查找单词功能2.4 哈希表版本 1. 前缀树的的介绍 在计算机科学中trie又称前缀树或字典树是一种有序树用于保存关联数组其中的键通常是字符串。与二叉查找树不同键不是直接保存在节点中而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀也就是这个节点对应的字符串而根节点对应空字符串。一般情况下不是所有的节点都有对应的值只有叶子节点和部分内部节点所对应的键才有相关的值。 2.前缀树的实现
如何实现一颗前缀树呢这里有两种实现的方法对应了不同的情况。
我们首先来定义一下前缀树的节点我们让每一个根节点有两个值一个为pass一个为endpass表示经过这个节点的次数end表示走到叶子节点的次数(也就是这个单词出现的次数)。
我们先看看这棵树的结构。比如我们插入字符串{“aa”“aaa”“bba”“ssba”}我们看看这颗树的结构。 现在我们模拟这个过程来写代码 先来定义好节点
struct TreeNode // 创建结点
{TreeNode *next[26];int end;int pass;TreeNode() // 初始化结点{end 0;path 0;for(int i0;i26;i)next[i]NULL;}
};下面我们实现树的部分我们就储存一个头节点和所需要的接口
class Trie
{
private:TreeNode* root;
public:Trie(){root new TreeNode;}void insert_Node(string word); // 插入void Delete_Node(string word); // 删除int search(string word); // 查找int prefixNumber(string word);//查找有多少以word作为前缀的单词
};2.1插入功能
void Trie::insert_Node(string wrod)
{if (wrod ) return;int idx 0;TreeNode* node root;root-pass;for (int i 0; i wrod.size(); i){idx wrod[i] - a;if (node-next[idx]nullptr)node-next[idx] new TreeNode;node node-next[idx];node-pass;}node-end;
}2.2删除功能
//这个函数java的可以不用写因为Java有JVM垃圾回收机制。
void Delete(TreeNode* node)
{if (node NULL)return;for (int num 0; num 26; num){if (node-next[num]){Delete(node-next[num]);}}delete(node);nodeNULL;
}void Trie::Delete_Node(string word)
{if (!search(word))return;int index 0;TreeNode* node root;node-pass--;for (int i 0; i word.size(); i){index word[i] - a;if (--node-next[index]-pass 0){// Java的直接将 node。next[index] NULL 即可Delete(node-next[index]);node-next[index] NULL;return;}node node-next[index];}node-end--;
}
2.3查找前缀和查找单词功能
int Trie::prefixNumber(string word)
{if (word ) return 0;int idx 0;TreeNode* node root;for (int i 0; i word.size(); i){idx word[i] - a;if (node-next[idx] nullptr) return 0;node node-next[idx];}return node-pass;
}int Trie::search(string word)
{if (word ) return 0;int idx 0;TreeNode* node root;for(int i0;iword.size();i){ idx word[i] - a;if (node-next[idx] nullptr) return 0;node node-next[idx];}return node-end;
}2.4 哈希表版本
如何单词不只有26个小写字母我们该如何去实现呢我们可以通过哈希表去进行映射来实现。 只需要以ASIII作为key代码稍微改动一下就可以了。
#include iostream
#include string
#include algorithm
#include unordered_map
using namespace std;struct TreeNode
{int pass;int end;unordered_mapint, TreeNode* next;TreeNode(){pass 0;end 0;}};class Trie
{
private:TreeNode* root;
public:Trie(){root new TreeNode;}void insert_Node(string word); // 插入void Delete_Node(string word); // 删除int search(string word); // 查找int prefixNumber(string word);//查找有多少以word作为前缀的单词
};void Trie::insert_Node(string wrod)
{if (wrod ) return;int idx 0;TreeNode* node root;root-pass;for (int i 0; i wrod.size(); i){idx (int)wrod[i];if (!node-next.count(idx)){node-next[idx] new TreeNode;}node node-next[idx];node-pass;}node-end;
}int Trie::search(string word)
{if (word ) return 0;int idx 0;TreeNode* node root;for(int i0;iword.size();i){ idx (int)word[i];if (!node-next.count(idx)) return 0;node node-next[idx];}return node-end;
}
//这个函数java的可以不用写因为Java有JVM垃圾回收机制。
void Delete(TreeNode* node)
{if (node NULL)return;for (int num 0; num 26; num){if (node-next[num]){Delete(node-next[num]);}}delete(node);node NULL;
}void Trie::Delete_Node(string word)
{if (!search(word))return;int index 0;TreeNode* node root;node-pass--;for (int i 0; i word.size(); i){index (int)word[i];if (--node-next[index]-pass 0){// Java的直接将 node。next[index] NULL 即可Delete(node-next[index]);node-next[index] NULL;return;}node node-next[index];}node-end--;
}int Trie::prefixNumber(string word)
{if (word ) return 0;int idx 0;TreeNode* node root;for (int i 0; i word.size(); i){idx (int)word[i];if (!node-next.count(idx)) return 0;node node-next[idx];}return node-pass;
}int main()
{Trie tr;tr.insert_Node(aad);tr.insert_Node(jjafp);tr.insert_Node(jjdafp);tr.insert_Node(jjdafp);tr.insert_Node(jjafp);tr.insert_Node(jjdap);cout tr.search(jjdafp) endl;cout tr.prefixNumber(j) endl;return 0;
}
