C++前綴樹字典樹的學習與模擬實現(xiàn)代碼示例

更新時間：2023年07月12日 09:28:30 作者：魏天樂大帥哥

這篇文章主要介紹了C++前綴樹字典樹的學習與模擬實現(xiàn)代碼示例,Trie又被稱為前綴樹、字典樹，所以當然是一棵樹,上面這棵Trie樹包含的字符串集合是{in,inn,int,tea,ten,to},每個節(jié)點的編號是我們?yōu)榱嗣枋龇奖慵由先サ?需要的朋友可以參考下

前綴樹介紹

在計算機科學中，trie，又稱前綴樹或字典樹，是一種有序樹，用于保存關聯(lián)數(shù)組，其中的鍵通常是字符串。常用與拼寫檢查自動補全等; 是一種查找結(jié)構(gòu)他的存儲邏輯類似于哈希表，但是它相對于哈希表來說，限制更多，通用性較差，但是它的功能更加強大，可定制性也更強。 leetcode指路：實現(xiàn)Trie(前綴樹)

如圖可以查看trie樹的基本結(jié)構(gòu)：

在這里插入圖片描述

與二叉查找樹不同，鍵不是直接保存在節(jié)點中，而是由節(jié)點在樹中的位置決定。(這個是前綴樹的精髓，也是難理解的地方，他不用存儲某個節(jié)點的實際字符，他的對應下標映射出了需要存儲的字符！)

一個節(jié)點的所有子孫都有相同的前綴，也就是這個節(jié)點對應的字符串，而根節(jié)點對應空字符串。

一般情況下，不是所有的節(jié)點都有對應的值（他們只是前綴），只有葉子節(jié)點和部分內(nèi)部節(jié)點所對應的鍵才有相關的值。

C++實現(xiàn)

核心思想

單鏈表:通過Node中封裝的Node* next來找下一個連著的節(jié)點;

二叉樹:通過Node中封裝的Node* left 和 Node* right來找左右孩子節(jié)點;

前綴樹？

因為維護了26個可能的Node*節(jié)點，所以跟上面一個道理，只是不能枚舉出來了，用了一個Node*arr[26]來維護，恰巧把這個數(shù)組的下標設計成了某個字符的種類，就可以達到利用邏輯下標存儲一個實際字符的作用了！

前綴樹插入示意圖

在這里插入圖片描述

上圖中，每經(jīng)過一個節(jié)點，將該節(jié)點的pass值加一，將末尾節(jié)點的end值加一。通過這種操作記錄所有經(jīng)過的數(shù)據(jù)記錄

前綴樹的插入是靈魂所在，搞懂了之后結(jié)構(gòu)就明白了，不管是查找還是刪除無非就是類似對鏈表的相關操作;

前綴樹的大致框架

假設只存小寫字符:

#include <iostream>
#include <vector>
#include <string>
using namespace std;
//26 個小寫英文字母
#define NUM 26
class Trie{
private:
    Trie* arr[NUM];//多叉樹(最大26個分支，因為26個小寫字母嘛)
    int end;  //代表word完整單詞的個數(shù)，0就是無此單詞，只是一個前綴;insert一個單詞的時候，這個單詞的end首次出現(xiàn)就置為1;之后重復插入就end++;
    int pass; //代表以此前綴為公共前綴的節(jié)點個數(shù),每次insert的時候會調(diào)整;
public:
    Trie() {
        memset(arr,0,sizeof(arr));//每個新節(jié)點的映射數(shù)組內(nèi)容置nullptr
	    end = 0;
        ncount = 0; //初始化時以該映射信息字符為前綴的個數(shù)為1(這個字符本身算的1)
    }
    //插入單詞
    void Insert(string &x)
    {
    }
    //查找 完全匹配字符串x 的數(shù)量
    int Find(string &x)
    {
    }
    //查找 前綴為字符串x 的數(shù)量
    int FindContain(string& x)
    {
    }
    //刪除某個單詞(前綴)
    bool Erase(string &x)
    {
    }
    ~Trie()
    {
        //因為new了26個連續(xù)的tire*空間，不要某個節(jié)點，不要把它對應給下層準備的26個空間也delete掉 防止內(nèi)存泄漏
        for (int i = 0; i < NUMBER; i++)
		{
			if (nexts[i]){
                delete nexts[i];
            }
		}
    }
};

二叉樹，父節(jié)點之下包含兩個節(jié)點，分別為左右子節(jié)點，分別開辟空間，進行數(shù)據(jù)存儲。
前綴樹的結(jié)構(gòu)也是類似的，它的每個節(jié)點包含兩個部分: 值部分和指針部分。
它的存儲方式為：在一棵樹上，從根到子節(jié)點，分別存儲所有目標數(shù)據(jù)的每一個下標位置上的數(shù)據(jù)
值部分主要又包含兩個數(shù)據(jù): 路過該節(jié)點的數(shù)量為pass，以該節(jié)點為結(jié)尾的數(shù)量為end。
指針部分主要包含它的所有子節(jié)點（比如26個小寫字母），記為arr

下面的實現(xiàn)給出了四個接口:

Insert插入字符串，給前綴樹添加一組數(shù)據(jù)

其中Insert方法需要注意插入新單詞的過程中，路徑所有前綴的個數(shù)pass+1

Find查找已存入的完整匹配的字符串個數(shù)
FindContain 查找已存入的前綴匹配的字符串個數(shù)
Erase 從前綴樹中擦除一個完整字符串

Erase方法需要注意的是：

需Find先檢查字符串是否存在；
pass == 1 時，代表其下沒有任何可能存在的字符子串，所以直接將這個節(jié)點delete刪除即可；
pass不為1且存在這個字符串，我們把end有效字符串個數(shù)-1就行
移除節(jié)點時，需要提前寫好析構(gòu)函數(shù)，將其節(jié)點開辟的26個Node*內(nèi)存全部釋放，以免出現(xiàn)內(nèi)存泄漏;

前綴樹插入字符串

另外，下面的功能代碼不過多解釋，代碼注釋自行理解，核心要點就是用數(shù)組下表映射的方式確定前往哪一條鏈表，之后的尋找和插入等操作都有點像鏈表的操作，搞個cur指針向后遍歷等;

//插入單詞
    void Insert(const string &x)
    {
        int size = x.size();
        Node* cur = root;
        cur->pass++;//不管insert啥，我們root空節(jié)點的pass相當于必須+1，最終這個root->pass可以代表一共insert了幾次=-=
        for (int i = 0; i<size; i++) {
            char index = x[i] - 'a';
            //該字符在當前分支下的映射為空，沒有那就new
            if (cur->arr[index] == nullptr) {
                cur->arr[index] = new Node;
            }
            cur->arr[index]->pass++; //不管 cur->arr[index] 是new的還是本來就有，insert要路過他了，他的pass+1,
            cur = cur->arr[index];//同時cur下指過去，進行下一個字符的insert
        }
        cur->end++;//insert最終將完整字符串個數(shù)end+1
    }

前綴樹查找完整的字符串

  //查找 完全匹配字符串 x 的數(shù)量 -->end
    int Find(const string &x)
    {
        int size = x.size();
        Node* cur = root;
        for (int i = 0; i < size; i++) {
            char index = x[i] - 'a';
            //搜索到某個字符斷了，沒有這個完整的字符串x 返回0
            if (cur->arr[index] == nullptr) return 0;
            //沒斷，繼續(xù)向下一個字符搜索;
            cur = cur->arr[index];
        }
        return cur -> end;//返回完整字符串x的有效個數(shù)end
    }

前綴樹查找前綴匹配的字符串

//查找 前綴為字符串 x 的數(shù)量 -->pass
    int FindContain(const string& x)
    {
        //與Find一模一樣的邏輯，只是最后的return 變了，這體現(xiàn)了Node*封裝 int end  和int pass的好處了吧
        int size = x.size();
        Node* cur = root;
        for (int i = 0; i < size; i++) {
            char index = x[i] - 'a';
            if (cur->arr[index] == nullptr) return 0;
            cur = cur->arr[index];
        }
        return cur -> pass;
    }

前綴樹刪除完整字符串

 //刪掉某個完整單詞-以及這個單詞后面可能存在的所有路徑;（end>1 出現(xiàn)了很多次時，只需要end--一下）
    bool Delete(const string &x)
    {
        if (Find(x) == 0) return false;//壓根沒這個單詞，刪除失敗;
        //有這個單詞，我們需要找到他的prev前一個，delete掉他,prev的arr[x]=nullptr!
        Node* cur = root;
        Node* prev = root;
        int size = x.size();
        for (int i = 0; i < size; i++) {
            char index = x[i]-'a';
            //if (cur->arr[index] == nullptr) return false;這句不需要，都過了Find 肯定x每個字符都存在于字典樹中
            cur->pass--;//別忘了路過的路徑都得-1;
            prev = cur;
            cur = cur->arr[index];
        }
        if (cur->end==1) {//代表x所在字符串的個數(shù)只有1，直接遞歸delete刪掉它 和 他后面的子串
            delete cur;//這個delete調(diào)析構(gòu)，我們析構(gòu)已經(jīng)寫好了，防止內(nèi)存泄漏;
            prev->arr[x[size - 1]-'a'] = nullptr; // prev的arr[x最后一個字符-'a'] = nullptr!
        }
        else  cur->end--;//end>1 :end--代表這個節(jié)點的有效字符串個數(shù)-1，end==1 end-- == 0，這個節(jié)點的字符有效個數(shù)為0了，但是他因為pass>1,暫時保存 后面的不刪;
        //end>1,那就end有效個數(shù)-1就行了;
        return true;
    }

總結(jié)

這個字典樹的樹結(jié)構(gòu)可以根據(jù)需求來進行多樣式的處理；比如我為了實現(xiàn)設計的功能，每個節(jié)點都保存了pass和end倆int方便功能記錄和函數(shù)內(nèi)的使用;
字典樹本質(zhì)上是犧牲空間，換查找同前綴的字符串提升時間效率的一種措施，但是我們這種每個節(jié)點都開26個數(shù)組的方式是非常浪費空間的，比如只有一個有效字符下標，其他25個nullptr都浪費了，而且在大量相同的前綴下就是單鏈表，浪費更嚴重。
這時候我們可以把Node*arr[26]數(shù)組換成map<char,Node*>這樣搞(每層某一個char只會出現(xiàn)一次，所以char做key沒問題)，需要配對啥就insert給紅黑樹中添加啥,大大節(jié)省空間;

所以說這個樹沒有啥固定玩法，可塑性太強了…這可能也是不刷題的我不常見的愿因？

完整代碼

#include <iostream>
#include <vector>
#include <string>
using namespace std;
//26 個小寫英文字母
#define NUM 26
//前綴樹節(jié)點
class Node {
public:
    Node* arr[NUM];//多叉樹(最大26個分支，因為26個小寫字母嘛)
    int end;  //代表
    int pass; //代表以此前綴為公共前綴的節(jié)點個數(shù),每次insert的時候會調(diào)整
    Node()
    {
        end = 0;
        pass = 0;
        memset(arr, 0, sizeof(arr));
    }
    ~Node()
    {
        //這里有點遞歸的意思，除了刪除當前節(jié)點，更重要的是如果當前節(jié)點的子節(jié)點還有非空。遞歸delete掉！
        for (int i = 0; i < NUM; i++)
        {
            if (arr[i]!=nullptr) delete arr[i];
        }
    }
};
//前綴樹主體
class Trie{
public:
    Node* root = nullptr;
public:
    Trie() {
        root = new Node;
    }
    //插入單詞
    void Insert(const string &x)
    {
        int size = x.size();
        Node* cur = root;
        cur->pass++;//不管insert啥，我們root空節(jié)點的pass相當于必須+1，最終這個root->pass可以代表一共insert了幾次=-=
        for (int i = 0; i<size; i++) {
            char index = x[i] - 'a';
            //該字符在當前分支下的映射為空，沒有那就new
            if (cur->arr[index] == nullptr) {
                cur->arr[index] = new Node;
            }
            cur->arr[index]->pass++; //不管 cur->arr[index] 是new的還是本來就有，insert要路過他了，他的pass+1,
            cur = cur->arr[index];//同時cur下指過去，進行下一個字符的insert
        }
        cur->end++;//insert最終將完整字符串個數(shù)end+1
    }
    //查找 完全匹配字符串 x 的數(shù)量 -->end
    int Find(const string &x)
    {
        int size = x.size();
        Node* cur = root;
        for (int i = 0; i < size; i++) {
            char index = x[i] - 'a';
            //搜索到某個字符斷了，沒有這個完整的字符串x 返回0
            if (cur->arr[index] == nullptr) return 0;
            //沒斷，繼續(xù)向下一個字符搜索;
            cur = cur->arr[index];
        }
        return cur -> end;//返回完整字符串x的有效個數(shù)end
    }
    //查找 前綴為字符串 x 的數(shù)量 -->pass
    int FindContain(const string& x)
    {
        //與Find一模一樣的邏輯，只是最后的return 變了，這體現(xiàn)了Node*封裝 int end  和int pass的好處了吧
        int size = x.size();
        Node* cur = root;
        for (int i = 0; i < size; i++) {
            char index = x[i] - 'a';
            if (cur->arr[index] == nullptr) return 0;
            cur = cur->arr[index];
        }
        return cur -> pass;
    }
    //刪掉某個完整單詞-以及這個單詞后面可能存在的所有路徑;（end>1 出現(xiàn)了很多次時，只需要end--一下）
    bool Delete(const string &x)
    {
        if (Find(x) == 0) return false;//壓根沒這個單詞，刪除失敗;
        //有這個單詞，我們需要找到他的prev前一個，delete掉他,prev的arr[x]=nullptr!
        Node* cur = root;
        Node* prev = root;
        int size = x.size();
        for (int i = 0; i < size; i++) {
            char index = x[i]-'a';
            //if (cur->arr[index] == nullptr) return false;這句不需要，都過了Find 肯定x每個字符都存在于字典樹中
            cur->pass--;//別忘了路過的路徑都得-1;
            prev = cur;
            cur = cur->arr[index];
        }
        if (cur->end==1) {//代表x所在字符串的個數(shù)只有1，直接遞歸delete刪掉它 和 他后面的子串
            delete cur;//這個delete調(diào)析構(gòu)，我們析構(gòu)已經(jīng)寫好了，防止內(nèi)存泄漏;
            prev->arr[x[size - 1]-'a'] = nullptr; // prev的arr[x最后一個字符-'a'] = nullptr!
        }
        else  cur->end--;//end>1 :end--代表這個節(jié)點的有效字符串個數(shù)-1，end==1 end-- == 0，這個節(jié)點的字符有效個數(shù)為0了，但是他因為pass>1,暫時保存 后面的不刪;
        //end>1,那就end有效個數(shù)-1就行了;
        return true;
    }
};

到此這篇關于C++前綴樹字典樹的學習與模擬實現(xiàn)代碼示例的文章就介紹到這了,更多相關C++前綴樹字典樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: