Print all possible nodes of a Trie built from the given list of strings

In C, trie is a high-level data structure used to store a collection of trees. The word trie comes from the word retrieval, it is called a number tree or a prefix tree.

Let’s take an example of all possible joins given a list of strings.

We define the string input as {"tutor", "true", "tuo"}

We can observe that different strings are concatenated with a single string. So t and u here are character lists that connect all possible strings.

In this article, we will use the trie data structure to solve all possible connections in a list of strings.

grammar

struct name_of_structure{
   data_type var_name;   // data member or field of the structure.
}

parameter

• struct − This keyword is used to represent the structure data type.

• name_of_structure − We provide any name for the structure.

• A structure is a collection of various related variables in one place.

treetrie* alpha[alphabet]

alpha is the name of the variable pointing to the structure pointer/data member named treetrie. alphabet is a macro that sets the total value of characters, expressed as an integer.

algorithm

• We first use a header file named ‘bits/stdc .h’, which contains all the standard template libraries of C.

• We are defining two macros, 'alphabet' and 'max', which define the total number of characters in the alphabet and the maximum value of characters .

• We are creating a structure called 'tree node' and defining a pointer to 'tree_node' to store the address of the letter. Define the variable 'end_word' using bool data type, which will be used for the end character of the string.

• We are using a pointer to connect to a new node representing the tree built by the trie, defining a function called 'buildNode'.

• To insert a string, we create a recursive function called 'ins_recursive_of_string' which accepts three parameters - itm, str (the string to be inserted), i (which represents the current character being processed).

• Function ins() is defined in the code as a wrapper function for ins_recursive_of_str(). It accepts two parameters: tree_trie* itm (a tree_trie object) and string str (the string to be inserted). It calls the recursive function using the current node, the string to be inserted, and the starting index 0.

• Next, we are creating a function called LeafNode() which accepts a tree_trie object as a parameter and checks if it is a leaf node, i.e. if it has no child nodes.

• Functiondisplay_joint() is defined in the code and accepts four parameters: tree_trie* root, tree_trie* itm (the node currently being processed), char str[] (a character array str, used to store the path string formed from the root node to the current node), and an int level (an integer level representing the depth of the current node).

• This code defines the displayJ() function, which is the wrapper function of display_joint(). It accepts a tree_trie object as a parameter and calls the display_joint() function with the root node, an empty character array, and a starting level of 0 as parameters.

• This code defines the main() function, which generates a new tree_trie object as the Trie root node. It generates a vector s containing a list of strings to be inserted into the Trie. Then, it calls the ins() function to insert each string into the Trie.

• Finally, it prints a message to indicate the start of output and calls the displayJ() function to display all Trie connection points.

Example

In this program, we will print all possible join points of a trie built from a given list of strings.

#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;
}

Output

All possible joint of trie using the given list of string
u
t

in conclusion

We explored the concept of a trie data structure, where we built all possible trie join points from a given list of strings. We see in the output that the characters u and t connect all possible join points of the trie by using strings like tutor, true and tuo. Therefore, a tree can reduce its nodes by giving possible connection points.

The above is the detailed content of Print all possible nodes of a Trie built from the given list of strings. For more information, please follow other related articles on the PHP Chinese website!