做网站公司做网站公司,wordpress京豆插件,做互联网小程序 和网站有没有前景,优化网站排名推广一、字典树
1、字典树介绍
字典树#xff0c;也称为“前缀树”#xff0c;是一种特殊的树状数据结构#xff0c;对于解决字符串相关问题非常有效。典型
用于统计、排序、和保存大量字符串。所以经常被搜索引擎系统用于文本词频统计。它的优点是#xff1a;
利用字符串的…一、字典树
1、字典树介绍
字典树也称为“前缀树”是一种特殊的树状数据结构对于解决字符串相关问题非常有效。典型
用于统计、排序、和保存大量字符串。所以经常被搜索引擎系统用于文本词频统计。它的优点是
利用字符串的公共前缀来减少查询时间最大限度地减少无谓的字符串比较查询效率比哈希树
高。
2、字典树的性质
1根节点不包含字符除了根节点每个节点都只包含一个字符。root节点不含字符这样做的目的是为了能够包括所有字符串。
2从根节点到某一个节点路过字符串起来就是该节点对应的字符串。
3每个节点的子节点字符不同也就是找到对应单词、字符是唯一的。 3、字典树的实现
(1)定义多叉树--孩子表示法
struct TreeNode {ELEMENT_TYPE value; //结点值TreeNode* children[NUM]; //孩子结点
};
(2) 定义字典树
int size 26;
struct TrieNode {bool isEndOfWord; //记录该结点是否是一个串的结束TrieNode* children[SIZE]; //字母映射表
};
二、面试中关于字典树的常见问题
1、计算字典树中的总单词数
题目创建一颗字典树并且计算该字典树中的总单词数。如下字典树[“bag” “ban” “bat” “big”“bil”“bit”]单词数为6。 思路
首先要创建一颗字典树在每个节点上设置一个标记来表示该节点是否是一个单词的结束。
再向字典树中插入单词从根节点开始递归地遍历字典树的所有子节点。
最后计算单词数对于每个子节点如果其标记为结束则将计数器加1。最终计数器的值就是字典树中的总单词数。
#includeiostream
using namespace std;const int ALPHABET_SIZE 26;
// TrieNode表示字典树中的节点
struct TrieNode
{bool isEndOfWord; //用于标记该节点是否是一个单词的结束TrieNode* children[ALPHABET_SIZE]; //包含26个子节点的数组// 构造函数TrieNode():isEndOfWord(false){for(int i 0; i ALPHABET_SIZE; i){children[i] nullptr;}}
};class Trie{private:TrieNode* root;public:Trie(){root new TrieNode();}// 向字典树中插入单词void insert(string word){TrieNode* current root;// 遍历字符串中的字符for(char ch: word){int index ch - a;if(current-children[index] nullptr)current-children[index] new TrieNode();current current-children[index];}// 遍历结束标记该节点单词结束current-isEndOfWord true;}// 计算字典树中的总单词数int countWords(){int count 0;countWordsDFS(root, count);return count;}private:// 深度优先搜索DFS递归地遍历字典树的所有节点并在遇到结束节点时将计数器加1。void countWordsDFS(TrieNode* node, int count){if(node NULL)return;if(node-isEndOfWord) count 1;for(int i 0; i ALPHABET_SIZE; i){if(node-children[i] ! NULL)countWordsDFS(node-children[i], count);}}};int main(){Trie trie;trie.insert(bag);trie.insert(ban);trie.insert(bat);trie.insert(big);trie.insert(bil);trie.insert(bit);int count trie.countWords();cout 字典树中的总单词数 count endl;
}2、查找字典树中某个单词是否存在
题目输入ban返回true输入bad返回False。 思路和插入操作类似。
从字典树的根节点依次遍历单词中的字符如果当前节点的子节点中不存在键为 ch 的节点则说明不存在该单词直接返回 False。如果当前节点的子节点中存在键为 ch 的节点则令当前节点指向新建立的节点然后继续查找下一个字符。在单词处理完成时判断当前节点是否有单词结束标记如果有则说明字典树中存在该单词返回 True。否则则说明字典树中不存在该单词返回 False。
#includeiostream
using namespace std;const int ALPHABET_SIZE 26;
// TrieNode表示字典树中的节点
struct TrieNode
{bool isEndOfWord; //用于标记该节点是否是一个单词的结束TrieNode* children[ALPHABET_SIZE]; //包含26个子节点的数组// 构造函数TrieNode():isEndOfWord(false){for(int i 0; i ALPHABET_SIZE; i){children[i] nullptr;}}
};class Trie{private:TrieNode* root;public:Trie(){root new TrieNode();}// 向字典树中插入单词void insert(string word){TrieNode* current root;// 遍历字符串中的字符for(char ch: word){int index ch - a;if(current-children[index] nullptr)current-children[index] new TrieNode();current current-children[index];}// 遍历结束标记该节点单词结束current-isEndOfWord true;}// 查找字典树中某个单词是否存在bool searchWord(string word){TrieNode* current root;for(char ch: word){int index ch - a;if(current-children[index] NULL)return false; //如果当前节点的子节点中不存在键为 ch 的节点,直接返回falsecurrent current-children[index];}// 判断当前节点是否为空并且是否有单词结束标记return (current-isEndOfWord current ! NULL);}};int main(){Trie trie;trie.insert(bag);trie.insert(ban);trie.insert(bat);trie.insert(big);trie.insert(bil);trie.insert(bit);string word bad;bool b trie.searchWord(word);if(b)cout 该字典树存在 word;elsecout 该字典树不存在 word;}3、查找字典树中某个前缀是否存在
在字典树中查找某个前缀是否存在和字典树的查找单词操作一样不同点在于最后不需要判断是否有单词结束标记。
// 查找字典树中某个前缀是否存在bool searchWord(string word){TrieNode* current root;for(char ch: word){int index ch - a;if(current-children[index] NULL)return false; //如果当前节点的子节点中不存在键为 ch 的节点,直接返回falsecurrent current-children[index];}// 判断当前节点是否为空return current;}
4、打印存储在字典树中的所有单词
题目如下字典树打印[ bagbanbatbigbilbit ]。 思路在哈希遍历树的完整路径中我们使用先序遍历逐步构建叶子节点的路径。本题类似使用
深度遍历递归地遍历字典树的所有子节点并存储每个叶子节点的字符串。遇到叶子节点即
isEndOfWordtrue则打印存储在容器里的字符串字符串组合起来就是一个完整单词。
#includeiostream
using namespace std;const int ALPHABET_SIZE 26;
// TrieNode表示字典树中的节点
struct TrieNode
{bool isEndOfWord; //用于标记该节点是否是一个单词的结束TrieNode* children[ALPHABET_SIZE]; //包含26个子节点的数组// 构造函数TrieNode():isEndOfWord(false){for(int i 0; i ALPHABET_SIZE; i){children[i] nullptr;}}
};class Trie{private:TrieNode* root;public:Trie(){root new TrieNode();}// 向字典树中插入单词void insert(string word){TrieNode* current root;// 遍历字符串中的字符for(char ch: word){int index ch - a;if(current-children[index] nullptr)current-children[index] new TrieNode();current current-children[index];}// 遍历结束标记该节点单词结束current-isEndOfWord true;}void printWord(){string arr;print(root, arr);}private: void print(TrieNode* node, string arr){if(node-isEndOfWord){for(auto a: arr)cout a;cout , ;}for(int i 0; i ALPHABET_SIZE; i){if(node-children[i] ! NULL){char ch i a;arr.push_back(ch);print(node-children[i], arr);}}arr.pop_back();}
};int main(){Trie trie;trie.insert(bag);trie.insert(ban);trie.insert(bat);trie.insert(big);trie.insert(bil);trie.insert(bit);trie.printWord();
}5、使用字典树对数组的元素进行排序
题目
inputarr [apple, banana, application]
outputarr [apple, application, banana]
思路同第二题因为字典树节点的顺序已经确定所以遍历出来的单词即是排序后的单词组。
#includeiostream
#includevector
using namespace std;const int ALPHABET_SIZE 26;
// TrieNode表示字典树中的节点
struct TrieNode
{bool isEndOfWord; //用于标记该节点是否是一个单词的结束TrieNode* children[ALPHABET_SIZE]; //包含26个子节点的数组// 构造函数TrieNode():isEndOfWord(false){for(int i 0; i ALPHABET_SIZE; i){children[i] nullptr;}}
};class Trie{private:TrieNode* root;public:Trie(){root new TrieNode();}// 向字典树中插入单词void insert(string word){TrieNode* current root;// 遍历字符串中的字符for(char ch: word){int index ch - a;if(current-children[index] nullptr)current-children[index] new TrieNode();current current-children[index];}// 遍历结束标记该节点单词结束current-isEndOfWord true;}vectorstring Order(){string arr;vectorstring s;traverse(root, arr, s);return s;}private: // arr:连接字符串组成的单词res排序后的数组void traverse(TrieNode* node, string arr, vectorstring res){if(node-isEndOfWord){res.push_back(arr);}for(int i 0; i ALPHABET_SIZE; i){if(node-children[i] ! NULL){char ch i a;arr.push_back(ch);traverse(node-children[i], arr, res);}}arr.pop_back();}
};int main(){Trie trie;vectorstring arr { apple, banana, application };for (const string word : arr)trie.insert(word);vectorstring sortedArr trie.Order();std::cout 排序后的数组元素 std::endl;for (const std::string word : sortedArr)std::cout word std::endl;
}
