在C 中，trie是一種高階資料結構，用於儲存樹的集合。單字trie來自檢索一詞，它被稱為數字樹或前綴樹。
讓我們透過給定的字串清單來舉出一個所有可能的聯結的例子。
我們將字串輸入定義為 {“tutor”, “true”, “tuo”}
我們可以觀察到不同的字串與單一字串相連。所以這裡的t和u是連接所有可能字串的字元列表。
在本文中，我們將使用trie資料結構來解決一個字串清單中所有可能的連接。
struct name_of_structure{
data_type var_name; // data member or field of the structure.
}
struct − 這個關鍵字用來表示結構資料型態。
name_of_structure − 我們為結構提供任何名稱。
結構是將各種相關變數集中在一個地方的集合。
treetrie* alpha[alphabet]
alpha是指向名為treetrie的結構指標/資料成員的變數的名稱。 alphabet是設定字元總數值的宏，以整數形式表示。
我們首先使用一個名為‘bits/stdc .h’的頭文件，該文件包含了C 的所有標準模板庫。
我們正在定義兩個宏，分別是'alphabet'和'max'，它們定義了字母表中的總字元數和字元的最大值。
我們正在建立一個名為‘tree node’的結構，並定義一個指向‘tree_node’的指標來儲存字母的位址。使用bool資料類型定義變數‘end_word’，該變數將用於字串的結束字元。
我們正在使用一個指標來連接表示trie建構的樹的新節點，定義一個名為‘buildNode’的函數。
為了插入字串，我們創建了一個名為'ins_recursive_of_string'的遞歸函數，它接受三個參數- itm，str（要插入的字串），i（表示正在處理的目前字元）。
函數ins()在程式碼中被定義為ins_recursive_of_str()的包裝函數。它接受兩個參數：tree_trie* itm（一個tree_trie物件）和string str（要插入的字串）。它使用當前節點、要插入的字串和起始索引0來呼叫遞歸函數。
接下來，我們正在建立一個名為 LeafNode() 的函數，它接受一個 tree_trie 物件作為參數，並檢查它是否是葉節點，即它是否沒有子節點。
函數display_joint() 在程式碼中定義，並接受四個參數：tree_trie* root, tree_trie* itm（目前正在處理的節點），char str[]（一個字元陣列str，用於儲存從根節點到目前節點形成的路徑字串），以及一個int level（表示目前節點深度的整數層級）。
程式碼定義了displayJ()函數，它是display_joint()的包裝函數。它接受一個tree_trie物件作為參數，並使用根節點、一個空字元陣列和起始層級為0作為參數呼叫display_joint()函數。
該程式碼定義了main()函數，它產生一個新的tree_trie物件作為Trie根節點。它產生一個包含要插入到Trie中的字串列表的向量s。然後，它會呼叫ins()函數將每個字串插入到Trie中。
最後，它會列印一條訊息來指示輸出的開始，並呼叫 displayJ() 函數來顯示所有的 Trie 連接點。
在這個程式中，我們將列印由給定字串清單建構的trie的所有可能連接點。
#include <bits/stdc++.h>
using namespace std;
#define alphabet 26
#define max 200
// creating a structure for trie node
struct tree_trie {
tree_trie* alpha[alphabet];
bool end_word;
};
tree_trie* buildNode(){
tree_trie* temp = new tree_trie();
temp->end_word = false;
for (int i = 0; i < alphabet; i++) {
temp->alpha[i] = NULL;
}
return temp;
}
// We will insert the string using trie recursively
void ins_recursive_of_str(tree_trie* itm,
string str, int i){
if (i < str.length()) {
int idx = str[i] - 'a';
if (itm->alpha[idx] == NULL) {
// We are creating a new node
itm->alpha[idx] = buildNode();
}
// calling recursion function for inserting a string
ins_recursive_of_str(itm->alpha[idx],
str, i + 1);
}
else {
// We make the end_word true which represents the end of string
itm->end_word = true;
}
}
// By using function call we are inserting a tree
void ins(tree_trie* itm, string str){
// The necessary argument required for function call
ins_recursive_of_str(itm, str, 0);
}
// Using function we check whether the node is a leaf or not
bool isLeafNode(tree_trie* root){
return root->end_word != false;
}
// This function is an important part of the program to display the joints of trie
void display_joint(tree_trie* root, tree_trie* itm,
char str[], int level){
//Using this variable we are counting the current child
int current_alpha = 0;
for (int i = 0; i < alphabet; i++){
if (itm->alpha[i]) {
str[level] = i + 'a';
display_joint(root, itm->alpha[i],
str, level + 1);
current_alpha++;
}
}
// We are printing the character if it has more than 1 character
if (current_alpha > 1 && itm != root) {
cout << str[level - 1] << endl;
}
}
// By using this function call we are diplaying the joint of trie.
void displayJ(tree_trie* root){
int level = 0;
char str[max];
display_joint(root, root, str, level);
}
// main function
int main(){
tree_trie* root = buildNode();
vector<string> s = { "tutor", "true", "tuo"};
for (string str : s) {
ins(root, str);
}
cout<<"All possible joint of trie using the given list of string"<<endl;
displayJ(root);
return 0;
}
All possible joint of trie using the given list of string u t
我們探討了trie資料結構的概念，其中我們從給定的字串列表中建構了所有可能的trie連接點。我們在輸出中看到，字元u和t透過使用諸如tutor、true和tuo等字串連接了trie的所有可能連接點。因此，透過給出可能的連接點，樹可以減少其節點。
以上是列印由給定字串清單建構的Trie的所有可能節點的詳細內容。更多資訊請關注PHP中文網其他相關文章！
