列印由給定字串清單建構的Trie的所有可能節點

在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中文網其他相關文章！