Imprimer tous les nœuds possibles d'un Trie construit à partir de la liste de chaînes donnée

En C++, un trie est une structure de données de haut niveau utilisée pour stocker une collection d'arbres. Le mot trie vient du mot récupération, on l'appelle arbre de nombres ou arbre de préfixes.

Prenons un exemple de toutes les jointures possibles en prenant une liste de chaînes donnée.

Nous définissons l'entrée de chaîne comme {"tutor", "true", "tuo"}

On peut observer que différentes chaînes sont concaténées en une seule chaîne. Voici donc t et u sont des listes de caractères concaténant toutes les chaînes possibles.

Dans cet article, nous utiliserons la structure de données trie pour résoudre toutes les concaténations possibles dans une liste de chaînes.

Grammaire

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

Paramètres

• struct - Ce mot-clé est utilisé pour représenter le type de données de structure.

• name_of_structure − Nous fournissons n'importe quel nom pour la structure.

• Une structure est un ensemble de diverses variables liées en un seul endroit.

treetrie* alpha[alphabet]

alpha est le nom de la variable pointant vers le pointeur de structure/membre de données nommé treetrie. alphabet est une macro qui définit la valeur totale des caractères, exprimée sous forme d'entier.

Algorithme

• Nous utilisons d'abord un fichier d'en-tête nommé 'bits/stdc++.h', qui contient toutes les bibliothèques de modèles standards du C++.

• Nous définissons deux macros, 'alphabet' et 'max', qui définissent le nombre total de caractères dans l'alphabet et la valeur maximale des caractères.

• Nous créons une structure appelée ‘tree node’ et définissons un pointeur vers ‘tree_node’ pour stocker l’adresse de la lettre. Définissez la variable 'end_word' en utilisant le type de données bool, qui sera utilisé pour le caractère de fin de la chaîne.

• Nous utilisons un pointeur pour nous connecter à un nouveau nœud représentant l'arbre construit par le trie, définissant une fonction appelée 'buildNode'.

• Pour insérer une chaîne, nous avons créé une fonction récursive appelée 'ins_recursive_of_string' qui accepte trois paramètres - itm, str (la chaîne à insérer), i (représentant le caractère en cours de traitement).

La fonction

• ins() est définie dans le code comme une fonction wrapper de ins_recursive_of_str(). Il accepte deux paramètres : tree_trie* itm (un objet tree_trie) et string str (la chaîne à insérer). Il appelle la fonction récursive en utilisant le nœud actuel, la chaîne à insérer et l'index de départ 0.

• Ensuite, nous créons une fonction appelée LeafNode() qui accepte un objet tree_trie comme paramètre et vérifie s'il s'agit d'un nœud feuille, c'est-à-dire s'il n'a pas d'enfants.

La

• fonction display_joint() est définie dans le code et accepte quatre paramètres : tree_trie* root, tree_trie* itm (le nœud en cours de traitement), char str[] (un tableau de caractères str, pour Stores la chaîne de chemin formée du nœud racine au nœud actuel) et un niveau int (un niveau entier représentant la profondeur du nœud actuel).

• Ce code définit la fonction displayJ(), qui est une fonction wrapper pour display_joint(). Il accepte un objet tree_trie comme argument et appelle la fonction display_joint() avec le nœud racine, un tableau de caractères vide et un niveau de départ de 0 comme arguments.

• Ce code définit la fonction main(), qui génère un nouvel objet tree_trie en tant que nœud racine Trie. Il génère un vecteur s contenant une liste de chaînes à insérer dans le Trie. Ensuite, il appelle la fonction ins() pour insérer chaque chaîne dans le Trie.

• Enfin, il imprime un message pour indiquer le début de la sortie et appelle la fonction displayJ() pour afficher tous les points de jointure Trie.

Exemple

Dans ce programme, nous imprimerons tous les points de jointure possibles d'un trie construit à partir d'une liste de chaînes donnée.

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

Sortie

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

Conclusion

Nous avons exploré le concept de structure de données trie, où nous avons construit tous les points de jointure trie possibles à partir d'une liste donnée de chaînes. Nous voyons dans le résultat que les caractères u et t connectent tous les points de connexion possibles du trie en utilisant des chaînes telles que tutor, true et tuo. Un arbre peut donc réduire ses nœuds en donnant des points de connexion possibles.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!