資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
