Gibt alle möglichen Knoten eines Trie aus, das aus der angegebenen Liste von Zeichenfolgen erstellt wurde

In C++ ist ein Trie eine Datenstruktur auf hoher Ebene, die zum Speichern einer Sammlung von Bäumen verwendet wird. Das Wort Trie kommt vom Wort Retrieval und wird Zahlenbaum oder Präfixbaum genannt.

Nehmen wir ein Beispiel für alle möglichen Verknüpfungen, indem wir eine gegebene Liste von Zeichenfolgen verwenden.

Wir definieren die String-Eingabe als {"tutor", "true", "tuo"}

Wir können beobachten, dass verschiedene Zeichenfolgen zu einer einzigen Zeichenfolge verkettet werden. Hier sind also t und u Listen von Zeichen, die alle möglichen Zeichenfolgen verketten.

In diesem Artikel verwenden wir die Trie-Datenstruktur, um alle möglichen Verkettungen in einer Liste von Zeichenfolgen zu lösen.

Grammatik

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

Parameter

• struct – Dieses Schlüsselwort wird verwendet, um den Strukturdatentyp darzustellen.

• name_of_structure − Wir geben einen beliebigen Namen für die Struktur an.

• Eine Struktur ist eine Sammlung verschiedener verwandter Variablen an einem Ort.

treetrie* alpha[alphabet]

alpha ist der Name der Variablen, die auf den Strukturzeiger/Datenelement mit dem Namen „treetrie“ zeigt. alphabet ist ein Makro, das den Gesamtwert der Zeichen festlegt, ausgedrückt als Ganzzahl.

Algorithmus

• Wir verwenden zunächst eine Header-Datei namens ‘bits/stdc++.h‘, die alle Standard-Vorlagenbibliotheken von C++ enthält.

• Wir definieren zwei Makros, ‘Alphabet‘ und ‘Max‘, die die Gesamtzahl der Zeichen im Alphabet und den Maximalwert der Zeichen definieren.

• Wir erstellen eine Struktur namens ‘tree_node‘ und definieren einen Zeiger auf ‘tree_node‘, um die Adresse des Briefes zu speichern. Definieren Sie die Variable „end_word“ mit dem Datentyp „bool“, die für das Endzeichen der Zeichenfolge verwendet wird.

• Wir verwenden einen Zeiger, um eine Verbindung zu einem neuen Knoten herzustellen, der den durch den Trie erstellten Baum darstellt, und definieren eine Funktion namens ‘buildNode‘.

• Um eine Zeichenfolge einzufügen, haben wir eine rekursive Funktion namens „ins_recursive_of_string“ erstellt, die drei Parameter akzeptiert: itm, str (die einzufügende Zeichenfolge) und i (das das aktuell verarbeitete Zeichen darstellt). Die

-Funktion
• ins()

  ist im Code als Wrapper-Funktion von ins_recursive_of_str() definiert. Es akzeptiert zwei Parameter: tree_trie* itm (ein tree_trie-Objekt) und string str (die einzufügende Zeichenfolge). Es ruft die rekursive Funktion unter Verwendung des aktuellen Knotens, der einzufügenden Zeichenfolge und des Startindex 0 auf.

Als nächstes erstellen wir eine Funktion namens
• LeafNode()

  , die ein tree_trie-Objekt als Parameter akzeptiert und prüft, ob es sich um einen Blattknoten handelt, d. h. ob er keine untergeordneten Knoten hat. Die

Funktion
• display_joint()

  ist im Code definiert und akzeptiert vier Parameter: tree_trie* root, tree_trie* itm (der Knoten, der gerade verarbeitet wird), char str[] (ein Zeichenarray str, für Stores die vom Wurzelknoten zum aktuellen Knoten gebildete Pfadzeichenfolge) und eine int-Ebene (eine ganzzahlige Ebene, die die Tiefe des aktuellen Knotens darstellt).

Dieser Code definiert die Funktion
• displayJ()

  , die eine Wrapper-Funktion für display_joint() ist. Es akzeptiert ein tree_trie-Objekt als Argument und ruft die Funktion display_joint() mit dem Wurzelknoten, einem leeren Zeichenarray und einer Startebene von 0 als Argumente auf.

Dieser Code definiert die Funktion main(), die ein neues
• tree_trie

  -Objekt als Trie-Wurzelknoten generiert. Es generiert einen Vektor s, der eine Liste von Zeichenfolgen enthält, die in den Trie eingefügt werden sollen. Anschließend wird die Funktion ins() aufgerufen, um jede Zeichenfolge in den Trie einzufügen.

Abschließend wird eine Meldung gedruckt, die den Beginn der Ausgabe anzeigt, und die Funktion
• displayJ()

  aufgerufen, um alle Trie-Join-Punkte anzuzeigen.

Beispiel

In diesem Programm drucken wir alle möglichen Verbindungspunkte eines Versuchs aus, der aus einer bestimmten Liste von Zeichenfolgen erstellt wurde.

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

Ausgabe

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

Fazit

Wir haben das Konzept der Trie-Datenstruktur untersucht, bei dem wir alle möglichen Trie-Join-Punkte aus einer gegebenen Liste von Zeichenfolgen erstellt haben. Wir sehen in der Ausgabe, dass die Zeichen u und t alle möglichen Verbindungspunkte des Tries verbinden, indem sie Zeichenfolgen wie tutor, true und tuo verwenden. Daher kann ein Baum durch die Angabe möglicher Verbindungspunkte seine Knoten reduzieren.

Das obige ist der detaillierte Inhalt vonGibt alle möglichen Knoten eines Trie aus, das aus der angegebenen Liste von Zeichenfolgen erstellt wurde. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!