数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究打印从给定字符串列表构建的 Trie 的所有可能的连接节点
在 C++ 中，Trie 是一种高级数据结构，用于存储树的集合。Trie 这个词来源于检索（retrieval），它也被称为数字树或前缀树。
让我们以一个给定字符串列表的所有可能的连接节点为例。
我们将字符串输入定义为 {“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’ 的指针来存储字母的地址。使用布尔数据类型定义变量 ‘end_word’，它将用于字符串的结束字符。
我们定义了一个名为‘buildNode’ 的函数，使用指针连接一个新的节点，该节点表示构建的 Trie 树。
为了插入字符串，我们创建了一个名为‘ins_recursive_of_string’ 的递归函数，它接受三个参数 - itm、str（要插入的字符串）和 i（指示当前正在处理的字符）。
函数ins() 在代码中定义为ins_recursive_of_str() 的包装函数。它接受两个参数：tree_trie* itm（一个 tree_trie 对象）和string str（要插入的字符串）。它使用当前节点、要插入的字符串和起始索引 0 来调用递归函数。
接下来，我们创建一个名为is LeafNode() 的函数，它将 tree_trie 对象作为参数，并检查它是否为叶子节点，即它是否没有子节点。
函数display_joint() 在代码中定义，并接受四个参数：tree_trie* root, tree_trie*itm（正在处理的当前节点），char str[]（一个字符数组 str，存储从根节点到当前节点的路径形成的字符串）和一个整数 level（表示当前节点深度的整数 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 的所有可能的连接节点。因此，通过提供可能的连接节点，树可以减少其节点数量。
205 次查看
