在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的所有可能连接点。因此，通过给出可能的连接点，树可以减少其节点。