字典樹 (Trie) 是一種樹狀結構，可以用來儲存 字串 或是 層狀資料夾 類型的資料，每個節點分別可以儲存一個字元或是資料夾名稱，並且可以進行插入、查詢等操作。

儲存字串

結構

node 中包含了儲存的字元、後續字元的位置、以及目前位置是否是一個字串的結尾，如果能夠確定後續字元的種類的話 (如 ‘a’ ~ ‘z’)，也可以使用一般的陣列來儲存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct node{
    char ch; //字元
    unordered_map<char, int> nextNode; //後續字元位置
    bool wordEnd; //是否為字串結尾

    node(){
        nextNode.clear();
        wordEnd = false;
    }
    node(char c){
        ch = c;
        nextNode.clear();
        wordEnd = false;
    }
};

vector<node> dict; //用來儲存節點

注意每次使用前要先清空 dict，並建立根結點，可以使用以下代碼：

1
2
dict.clear(); // 初始化 dict
dict.push_back(node()); //建立根結點

或是在每次 insertString 時判斷 dict 是否為空，如果為空的話再補上根結點。

插入

從根結點開始進行插入，記得最後要把字串的結尾進行標註。

1
2
3
4
5
6
7
8
9
10
11
void insertString(string str){
    int cur = 0; //目前所在字元
    for(int i = 0; i < str.size(); i++){
        if((dict[cur].nextNode).count(str[i]) == 0){ //如果該字元不存在
            dict.push_back(node(str[i])); //加入字元
            dict[cur].nextNode[str[i]] = dict.size() - 1;
        }
        cur = dict[cur].nextNode[str[i]]; //下一層
    }
    dict[cur].wordEnd = true;
}

查詢

從根結點開始查找，如果不存在就直接退出，到最後還要進行是否為字串結尾的判斷，因為查找的字串可能是其他字串的前綴。

1
2
3
4
5
6
7
8
9
10
bool searchString(string str){
    int cur = 0; //目前所在字元
    for(int i = 0; i < str.size(); i++){
        if((dict[cur].nextNode).count(str[i]) == 0){ //如果該字元不存在
            return false;
        }
        cur = dict[cur].nextNode[str[i]]; //下一層
    }
    return dict[cur].wordEnd;
}

儲存層狀資料夾

以 UVA-1556 Disk Tree 為例。

結構

依照題目要求可以建立一個字典樹，每個節點儲存的是該資料夾的名稱，以及子資料夾對應的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct node{
    string name; //資料夾名稱
    map<string, int> nextNode; //子資料夾位置

    node(){
        nextNode.clear();
    }
    node(string s){
        name = s;
        nextNode.clear();
    }
};

vector<node> dict; //用來儲存節點

可以注意這裡使用的是 map，而不是 unordered_map，以便於在後面輸出時以字典序輸出。因為題目沒有要求儲存功能，因此不需要多加一個確認是否為結尾的變數。

插入

根據傳入的 vector 來插入對應的資料夾，如果對應的資料夾不存在，就將其加入字典樹中。

1
2
3
4
5
6
7
8
9
10
void insertNode(vector<string> v){
    int cur = 0; //目前所在資料夾
    for(int i = 0; i < v.size(); i++){
        if((dict[cur].nextNode).count(v[i]) == 0){ //如果資料夾不存在
            dict.push_back(node(v[i])); //加入資料夾
            dict[cur].nextNode[v[i]] = dict.size() - 1;
        }
        cur = dict[cur].nextNode[v[i]]; //下一層
    }
}

遍歷

題目要求需要輸出所有資料夾，並且根據資料夾的層數位移，同一層的資料夾需要依照字典序進行輸出，這邊我們利用 map 的 iterator 來進行照字典序的遍歷。

1
2
3
4
5
6
7
8
9
10
11
12
13
void dfs(int cur, int d){
    if(cur){ //根結點 0 不需要輸出
        for(int i = 1; i < d; i++){ //根據層數位移
            cout << " ";
        }
        cout << dict[cur].name << endl;
    }
    if(!(dict[cur].nextNode).empty()){ //如果不是葉節點就繼續遍歷子資料夾
        for(auto k = dict[cur].nextNode.begin(); k != dict[cur].nextNode.end(); k++){
            dfs(k -> second, d + 1);
        }
    }
}

主程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int n;
string str, s;

int main(){
    while(cin >> n){
        dict.clear(); // 初始化 dict
        dict.push_back(node()); //建立根結點
        while(n--){
            cin >> str;
            for(int i = 0; i < str.size(); i++){
                if(str[i] == '\\') str[i] = ' '; //把 '\' 替換為 ' '
            }
            stringstream ss(str);
            vector<string> tmp;
            while(ss >> s){
                tmp.push_back(s);
            }
            insertNode(tmp);
        }
        dfs(0, 0); //輸出資料夾，從根結點 0 開始，層數也是從 0 開始
        cout << endl;
    }
    return 0;
}