這個高級數(shù)據(jù)結(jié)構(gòu)系列我會寫三中在編程里常見的三種數(shù)據(jù)機構(gòu)徘层，分別是Trie 樹，并查集和線段樹拴驮。
trie樹(字典樹)的基礎(chǔ)知識
trie樹，又稱字典樹或前綴樹柴信，是一種有序的、用于統(tǒng)計宽气、排序和存儲字符串的數(shù)據(jù)結(jié)構(gòu)随常，它與二叉查找樹不同潜沦，關(guān)鍵字不是直接保存在節(jié)點中，而是由節(jié)點在樹中的位置決定绪氛。 一個節(jié)點的所有子孫都有相同的前綴唆鸡，也就是這個節(jié)點對應(yīng)的字符串，而根節(jié)點對應(yīng)空字符串枣察。一般情況下争占，不是所有的節(jié)點都有對應(yīng)的值，只有葉子節(jié)點和部分內(nèi)部節(jié)點所對應(yīng)的鍵才有相關(guān)的值序目。 trie樹的最大優(yōu)點就是利用字符串的公共前綴來減少存儲空間與查詢時間臂痕，從而最大限度地減少無謂的字符串比較，是非常高效的字符串查找數(shù)據(jù)結(jié)構(gòu)猿涨。
Trie樹
首先定義基本的數(shù)據(jù)結(jié)構(gòu)：
class TrieNode
{
bool IsEnd;//是否為一個單詞的結(jié)尾
TrieNode* childnodes[26];
TrieNode(): IsEnd(false)
{
for(int i = 0;i < MAX;i++)
{
childNode = nullptr;
}
}
};
TrieNode
Trie樹的基本功能實現(xiàn)：
class Trie {
private:
std::vector<TrieNode*> _node_vec;
//用來存儲new出來的結(jié)點握童，這樣在析構(gòu)的時候可以釋放內(nèi)存；
TrieNode* new_node()
{
TrieNode* node = new TrieNode();
_node_vec.push_back(node);
return node;
}
public:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
~Trie()
{
for(int i =0;i<_node_vec.size();i++)
{
delete _node_vec[i];
}
}
// Inserts a word into the trie.
void insert(string word) {
}
// Returns if the word is in the trie.
bool search(string word) {
}
// Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix) {
}
};
//獲取trie樹的所有單詞
void get_all_word_from_trie(TrieNode*root,string &word,vector<string> &word_list)
{
}
插入：
void insert(string word) {
TrieNode * p=root;
int length = word.length();
for(int i =0;i<length;i++)
{
if(!p->child[word[i]-'a'])
{
p->child[word[i]]=new TrieNode();
}
p=p->child[word[i]];
}
p->isEnd=true;
}
查找：
bool search(string word) {
int lenth = word.length();
TrieNode *p = root;
for(int i = 0;i<lenth;i++)
{
int index = word[i]-'a';
if(!p->next[index])
{
return false;
}
else
{
p = p->next[index];
}
}
if(p->IsLeave) return true;
else return false;
}
前綴：
bool startsWith(string prefix) {
int lenth = prefix.length();
TrieNode *p = root;
for(int i = 0;i<lenth;i++)
{
int index = prefix[i]-'a';
if(!p->next[index])
{
return false;
}
else
{
p = p->next[index];
}
}
return true;
}
查找Tire樹中所有的單詞：
void get_all_word_from_trie(TrieNode*root,string &word,vector<string> &word_list)
{//word是保存字符串的棧叛赚，
if(!root)
return;
for(int i =0;i<Max;i++)
{
if(root->next[i])
{
word.push_back('a'+i);
if(root->next[i]->IsLeave)
word_list.push_back(word);
//深度遍歷
get_all_word_from_trie(root->next[i],word,word_list);
word.erase(word.length()-1,1);//彈出棧頂字符
}
}
}
完整代碼可以戳??我的GitHub：還有Trie樹的模版實現(xiàn)方式哦～
希望大家一起進步～
