這個高級數(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樹

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)方式哦～
希望大家一起進步～