数据结构笔记--前缀树的实现

1--前缀树的实现

        前缀树的每一个节点拥有三个成员变量，pass表示有多少个字符串经过该节点，end表示有多少个字符串以该节点结尾，nexts表示该字符串可以走向哪些节点；

#include <iostream>
#include <unordered_map>struct TreeNode{TreeNode() : pass(0), end(0){}int pass; // 经过次数int end; // 是多少个字符串的结尾std::unordered_map<char, TreeNode*> nexts;
};class Trie{
public:// 构造函数Trie(){root = new TreeNode();}void insert(std::string word){if(word.length() == 0) return;TreeNode *node = root;node->pass++;for(int i = 0; i < word.length(); i++){if(node->nexts[word[i]] == NULL){ // 哈希表中没有该字符node->nexts[word[i]] = new TreeNode(); // 新建该字符}node = node->nexts[word[i]];node->pass++; // 该字符节点经过的次数++}node->end++; // 遍历word末尾时，节点的end++，表明以该节点结尾的字符串数++}bool search(std::string word){if(word.length() == 0) return true;TreeNode *cur = root;for(int i = 0; i < word.length(); i++){if(cur->nexts[word[i]] == NULL) return 0; // 没有该字符节点cur = cur->nexts[word[i]];}return cur->end; // end不为0表明该字符串出现过}bool startWith(std::string prefix){if(prefix.length() == 0) return 0;TreeNode *cur = root;for(int i = 0; i < prefix.length(); i++){if(cur->nexts[prefix[i]] == NULL) return 0; // 前缀没出现过cur = cur->nexts[prefix[i]];}return cur->pass; // 有多少个字符串经过该前缀，0个表明false;}private:TreeNode *root;
};int main(int argc, char *argv[]){Trie T1;std::string test1 = "hello";T1.insert(test1);bool res1 = T1.search(test1);if(res1) std::cout << "true" << std::endl;else std::cout << "false" << std::endl;bool res2 = T1.startWith("hel");if(res2) std::cout << "true" << std::endl;else std::cout << "false" << std::endl;return 0;
}

2--LeetCode真题

2-1--实现Trie（前缀树）

         本题不能自定义节点，因此将 pass、end 和 nexts 等成员变量转换成类的成员变量，新节点就是类的对象；

class Trie{
public:// 构造函数Trie(){}void insert(std::string word){if(word.length() == 0) return;Trie *node = this;node->pass++;for(int i = 0; i < word.length(); i++){if(node->nexts[word[i]] == NULL){ // 哈希表中没有该字符node->nexts[word[i]] = new Trie(); // 新建该字符}node = node->nexts[word[i]];node->pass++; // 该字符节点经过的次数++}node->end++; // 遍历word末尾时，节点的end++，表明以该节点结尾的字符串数++}bool search(std::string word){if(word.length() == 0) return true;Trie *cur = this;for(int i = 0; i < word.length(); i++){if(cur->nexts[word[i]] == NULL) return 0; // 没有该字符节点cur = cur->nexts[word[i]];}return cur->end; // end不为0表明该字符串出现过}bool startsWith(std::string prefix){if(prefix.length() == 0) return 0;Trie *cur = this;for(int i = 0; i < prefix.length(); i++){if(cur->nexts[prefix[i]] == NULL) return 0; // 前缀没出现过cur = cur->nexts[prefix[i]];}return cur->pass; // 有多少个字符串经过该前缀，0个表明false;}private:int pass = 0; // 经过次数int end = 0; // 是多少个字符串的结尾std::unordered_map<char, Trie*> nexts;
};