一个 Trie数据结构作为一个动态数组的容器,在本文中,我们将研究如何在 **C/C++**中实现一个 Trie。
这是基于树的数据结构,但不一定存储密钥,在这里,每个节点只有一个值,该值是根据位置定义的。
因此,每个节点的值表示前缀,因为它是经过一系列匹配的根节点的点。
我们将这些匹配称为 前缀匹配,因此,我们可以使用Tries来存储字典中的单词!
例如,在上图中,根节点是空的,所以每个字符串都匹配了根节点。
在这里,钥匙只存储在叶节点位置上,因为前缀匹配停止在任何叶节点上,所以任何非叶节点不会 NOT存储整个字符串,而仅存储前缀匹配字符。
由于所有这些原因,试图被称为 前缀树,现在让我们来了解我们如何从程序员的角度来实现这个数据结构。
在 C/C++ 中实现 Trie 数据结构
让我们先写下 Trie 结构,一个 Trie Node主要有两个组成部分:
- 这是孩子
- 一个标记标志一个叶节
但是,由于我们也会打印 Trie,如果我们能够在 data部分中存储另一个属性,那么就更容易了。
因此,让我们定义 TrieNode结构. 在这里,因为我只会存储较低的字母,我会将此作为一个 26空树实现。
1// The number of children for each node
2// We will construct a N-ary tree and make it
3// a Trie
4// Since we have 26 english letters, we need
5// 26 children per node
6#define N 26
7
8typedef struct TrieNode TrieNode;
9
10struct TrieNode {
11 // The Trie Node Structure
12 // Each node has N children, starting from the root
13 // and a flag to check if it's a leaf node
14 char data; // Storing for printing purposes only
15 TrieNode* children[N];
16 int is_leaf;
17};
现在我们已经定义了我们的结构,让我们写函数以在内存中初始化一个 TrieNode,并释放它的指针。
1TrieNode* make_trienode(char data) {
2 // Allocate memory for a TrieNode
3 TrieNode* node = (TrieNode*) calloc (1, sizeof(TrieNode));
4 for (int i=0; i<N; i++)
5 node->children[i] = NULL;
6 node->is_leaf = 0;
7 node->data = data;
8 return node;
9}
10
11void free_trienode(TrieNode* node) {
12 // Free the trienode sequence
13 for(int i=0; i<N; i++) {
14 if (node->children[i] != NULL) {
15 free_trienode(node->children[i]);
16 }
17 else {
18 continue;
19 }
20 }
21 free(node);
22}
将一句话插入三
现在我们将写入insert_trie()函数,该函数将指针带到根节点(顶部节点)并将一个单词插入到 Trie。
插入程序很简单,它通过字符字符重复,并评估相对位置。
例如,一个b字符将有1的位置,所以它将是第二个孩子。
1for (int i=0; word[i] != '\0'; i++) {
2 // Get the relative position in the alphabet list
3 int idx = (int) word[i] - 'a';
4 if (temp->children[idx] == NULL) {
5 // If the corresponding child doesn't exist,
6 // simply create that child!
7 temp->children[idx] = make_trienode(word[i]);
8 }
9 else {
10 // Do nothing. The node already exists
11 }
我们将按字符匹配前缀字符,如果它不存在的话,就简单地初始化一个节点。
否则,我们只是继续在链子上移动,直到我们匹配了所有字符。
1temp = temp->children[idx];
最后,我们将插入所有未匹配的字符,我们将返回更新的Trie。
1TrieNode* insert_trie(TrieNode* root, char* word) {
2 // Inserts the word onto the Trie
3 // ASSUMPTION: The word only has lower case characters
4 TrieNode* temp = root;
5
6 for (int i=0; word[i] != '\0'; i++) {
7 // Get the relative position in the alphabet list
8 int idx = (int) word[i] - 'a';
9 if (temp->children[idx] == NULL) {
10 // If the corresponding child doesn't exist,
11 // simply create that child!
12 temp->children[idx] = make_trienode(word[i]);
13 }
14 else {
15 // Do nothing. The node already exists
16 }
17 // Go down a level, to the child referenced by idx
18 // since we have a prefix match
19 temp = temp->children[idx];
20 }
21 // At the end of the word, mark this node as the leaf node
22 temp->is_leaf = 1;
23 return root;
24}
搜索一个词在三
现在我们已经在 Trie 上实现了插入,让我们看看搜索给定的模式。
我们将尝试与字符符串符号匹配,使用上面的相同前缀匹配策略。
如果我们已经到达链条的尽头,还没有找到匹配,这意味着链条不存在,因为一个完整的前缀匹配还没有完成。
为了正确返回,我们的模式必须准确匹配,我们完成匹配后,我们必须达到叶节。
1int search_trie(TrieNode* root, char* word)
2{
3 // Searches for word in the Trie
4 TrieNode* temp = root;
5
6 for(int i=0; word[i]!='\0'; i++)
7 {
8 int position = word[i] - 'a';
9 if (temp->children[position] == NULL)
10 return 0;
11 temp = temp->children[position];
12 }
13 if (temp != NULL && temp->is_leaf == 1)
14 return 1;
15 return 0;
16}
好吧,所以我们已经完成了插入和搜索程序。
要测试它,我们首先会写一个print_tree()函数,它会打印每个节点的数据。
1void print_trie(TrieNode* root) {
2 // Prints the nodes of the trie
3 if (!root)
4 return;
5 TrieNode* temp = root;
6 printf("%c -> ", temp->data);
7 for (int i=0; i<N; i++) {
8 print_trie(temp->children[i]);
9 }
10}
现在我们已经完成了这一点,让我们到现在为止运行完整的程序,以检查它是否正常工作。
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5// The number of children for each node
6// We will construct a N-ary tree and make it
7// a Trie
8// Since we have 26 english letters, we need
9// 26 children per node
10#define N 26
11
12typedef struct TrieNode TrieNode;
13
14struct TrieNode {
15 // The Trie Node Structure
16 // Each node has N children, starting from the root
17 // and a flag to check if it's a leaf node
18 char data; // Storing for printing purposes only
19 TrieNode* children[N];
20 int is_leaf;
21};
22
23TrieNode* make_trienode(char data) {
24 // Allocate memory for a TrieNode
25 TrieNode* node = (TrieNode*) calloc (1, sizeof(TrieNode));
26 for (int i=0; i<N; i++)
27 node->children[i] = NULL;
28 node->is_leaf = 0;
29 node->data = data;
30 return node;
31}
32
33void free_trienode(TrieNode* node) {
34 // Free the trienode sequence
35 for(int i=0; i<N; i++) {
36 if (node->children[i] != NULL) {
37 free_trienode(node->children[i]);
38 }
39 else {
40 continue;
41 }
42 }
43 free(node);
44}
45
46TrieNode* insert_trie(TrieNode* root, char* word) {
47 // Inserts the word onto the Trie
48 // ASSUMPTION: The word only has lower case characters
49 TrieNode* temp = root;
50
51 for (int i=0; word[i] != '\0'; i++) {
52 // Get the relative position in the alphabet list
53 int idx = (int) word[i] - 'a';
54 if (temp->children[idx] == NULL) {
55 // If the corresponding child doesn't exist,
56 // simply create that child!
57 temp->children[idx] = make_trienode(word[i]);
58 }
59 else {
60 // Do nothing. The node already exists
61 }
62 // Go down a level, to the child referenced by idx
63 // since we have a prefix match
64 temp = temp->children[idx];
65 }
66 // At the end of the word, mark this node as the leaf node
67 temp->is_leaf = 1;
68 return root;
69}
70
71int search_trie(TrieNode* root, char* word)
72{
73 // Searches for word in the Trie
74 TrieNode* temp = root;
75
76 for(int i=0; word[i]!='\0'; i++)
77 {
78 int position = word[i] - 'a';
79 if (temp->children[position] == NULL)
80 return 0;
81 temp = temp->children[position];
82 }
83 if (temp != NULL && temp->is_leaf == 1)
84 return 1;
85 return 0;
86}
87
88void print_trie(TrieNode* root) {
89 // Prints the nodes of the trie
90 if (!root)
91 return;
92 TrieNode* temp = root;
93 printf("%c -> ", temp->data);
94 for (int i=0; i<N; i++) {
95 print_trie(temp->children[i]);
96 }
97}
98
99void print_search(TrieNode* root, char* word) {
100 printf("Searching for %s: ", word);
101 if (search_trie(root, word) == 0)
102 printf("Not Found\n");
103 else
104 printf("Found!\n");
105}
106
107int main() {
108 // Driver program for the Trie Data Structure Operations
109 TrieNode* root = make_trienode('\0');
110 root = insert_trie(root, "hello");
111 root = insert_trie(root, "hi");
112 root = insert_trie(root, "teabag");
113 root = insert_trie(root, "teacan");
114 print_search(root, "tea");
115 print_search(root, "teabag");
116 print_search(root, "teacan");
117 print_search(root, "hi");
118 print_search(root, "hey");
119 print_search(root, "hello");
120 print_trie(root);
121 free_trienode(root);
122 return 0;
123}
在使用您的gcc编译器编译后,您将获得以下输出。
1Searching for tea: Not Found
2Searching for teabag: Found!
3Searching for teacan: Found!
4Searching for hi: Found!
5Searching for hey: Not Found
6Searching for hello: Found!
7 -> h -> e -> l -> l -> o -> i -> t -> e -> a -> b -> a -> g -> c -> a -> n ->
虽然它可能是显而易见的,它是如何被打印的,但线索是看 print_tree() 方法. 因为它打印了当前节点,然后所有的孩子,顺序确实表明这一点。
那么,现在就来实施删除方法吧!
删除一个单词从三
实际上,这两种方法比其他两种方法更复杂。
没有任何类型的格式算法,因为我们没有明确的方式来存储密钥和值。
但是,对于本文的目的,我只会处理删除,如果要删除的单词是叶节,也就是说,它必须全程匹配前缀,直到叶节节。
让我们开始吧,我们对删除函数的签名将是:
1TrieNode* delete_trie(TrieNode* root, char* word);
正如前面提到的,这只会删除前缀匹配完成直到一个叶节点,所以让我们写另一个函数 `is_leaf_node()',这对我们来说是这样做的。
1int is_leaf_node(TrieNode* root, char* word) {
2 // Checks if the prefix match of word and root
3 // is a leaf node
4 TrieNode* temp = root;
5 for (int i=0; word[i]; i++) {
6 int position = (int) word[i] - 'a';
7 if (temp->children[position]) {
8 temp = temp->children[position];
9 }
10 }
11 return temp->is_leaf;
12}
好了,所以完成了,让我们看看我们的delete_trie()方法的草案。
1TrieNode* delete_trie(TrieNode* root, char* word) {
2 // Will try to delete the word sequence from the Trie only it
3 // ends up in a leaf node
4 if (!root)
5 return NULL;
6 if (!word || word[0] == '\0')
7 return root;
8 // If the node corresponding to the match is not a leaf node,
9 // we stop
10 if (!is_leaf_node(root, word)) {
11 return root;
12 }
13 // TODO
14}
完成此检查后,我们现在知道我们的词将以叶节结尾。
但是还有另一个情况要处理呢?如果有另一个字符串具有当前字符串的部分前缀匹配的话呢?
例如,在下面的 Trie 中,单词 茶和 ted在 te 之前有部分共同的匹配。
因此,如果发生这种情况,我们不能简单地将整个序列从 t 到 a 删除,因为这时,两条链将被删除,因为它们是链接的!
因此,我们需要找到最深的点,直到这样的比赛发生,只有在那之后,我们才能删除剩余的链条。
这涉及到找到最长的前缀字符串,所以让我们写另一个函数。
1char* longest_prefix(TrieNode* root, char* word);
这将返回 Trie 中最长的匹配,而不是当前的单词(‘word’)。
1char* find_longest_prefix(TrieNode* root, char* word) {
2 // Finds the longest common prefix substring of word
3 // in the Trie
4 if (!word || word[0] == '\0')
5 return NULL;
6 // Length of the longest prefix
7 int len = strlen(word);
8
9 // We initially set the longest prefix as the word itself,
10 // and try to back-track from the deepest position to
11 // a point of divergence, if it exists
12 char* longest_prefix = (char*) calloc (len + 1, sizeof(char));
13 for (int i=0; word[i] != '\0'; i++)
14 longest_prefix[i] = word[i];
15 longest_prefix[len] = '\0';
16
17 // If there is no branching from the root, this
18 // means that we're matching the original string!
19 // This is not what we want!
20 int branch_idx = check_divergence(root, longest_prefix) - 1;
21 if (branch_idx >= 0) {
22 // There is branching, We must update the position
23 // to the longest match and update the longest prefix
24 // by the branch index length
25 longest_prefix[branch_idx] = '\0';
26 longest_prefix = (char*) realloc (longest_prefix, (branch_idx + 1) * sizeof(char));
27 }
28
29 return longest_prefix;
30}
这里还有另一个扭曲! 由于我们试图找到最长的匹配,算法实际上会贪婪地匹配原始字符串本身! 这不是我们想要的。
我们想要最长的匹配是 NOT输入字符串,因此,我们必须用另一种方法进行检查,即check_divergence()。
这将检查从根到当前位置是否有任何分支,并返回最佳匹配的长度,这是 NOT的输入。
如果我们处于错误的链条中,这与原来的字符串相匹配,那么就不会有分支从点!所以这对我们来说是用check_divergence()来避免那个丑陋的点的好方法。
1int check_divergence(TrieNode* root, char* word) {
2 // Checks if there is branching at the last character of word
3 //and returns the largest position in the word where branching occurs
4 TrieNode* temp = root;
5 int len = strlen(word);
6 if (len == 0)
7 return 0;
8 // We will return the largest index where branching occurs
9 int last_index = 0;
10 for (int i=0; i < len; i++) {
11 int position = word[i] - 'a';
12 if (temp->children[position]) {
13 // If a child exists at that position
14 // we will check if there exists any other child
15 // so that branching occurs
16 for (int j=0; j<N; j++) {
17 if (j != position && temp->children[j]) {
18 // We've found another child! This is a branch.
19 // Update the branch position
20 last_index = i + 1;
21 break;
22 }
23 }
24 // Go to the next child in the sequence
25 temp = temp->children[position];
26 }
27 }
28 return last_index;
29}
最后,我们确保我们不只是盲目删除整个链条,所以现在让我们继续使用我们的删除方法。
1TrieNode* delete_trie(TrieNode* root, char* word) {
2 // Will try to delete the word sequence from the Trie only it
3 // ends up in a leaf node
4 if (!root)
5 return NULL;
6 if (!word || word[0] == '\0')
7 return root;
8 // If the node corresponding to the match is not a leaf node,
9 // we stop
10 if (!is_leaf_node(root, word)) {
11 return root;
12 }
13 TrieNode* temp = root;
14 // Find the longest prefix string that is not the current word
15 char* longest_prefix = find_longest_prefix(root, word);
16 //printf("Longest Prefix = %s\n", longest_prefix);
17 if (longest_prefix[0] == '\0') {
18 free(longest_prefix);
19 return root;
20 }
21 // Keep track of position in the Trie
22 int i;
23 for (i=0; longest_prefix[i] != '\0'; i++) {
24 int position = (int) longest_prefix[i] - 'a';
25 if (temp->children[position] != NULL) {
26 // Keep moving to the deepest node in the common prefix
27 temp = temp->children[position];
28 }
29 else {
30 // There is no such node. Simply return.
31 free(longest_prefix);
32 return root;
33 }
34 }
35 // Now, we have reached the deepest common node between
36 // the two strings. We need to delete the sequence
37 // corresponding to word
38 int len = strlen(word);
39 for (; i < len; i++) {
40 int position = (int) word[i] - 'a';
41 if (temp->children[position]) {
42 // Delete the remaining sequence
43 TrieNode* rm_node = temp->children[position];
44 temp->children[position] = NULL;
45 free_trienode(rm_node);
46 }
47 }
48 free(longest_prefix);
49 return root;
50}
上面的代码仅仅会找到前缀匹配的最深节点,并从 Trie 中删除剩余的序列匹配单词,因为这与任何其他匹配无关。
上述程序的时间复杂性
程序的时间复杂性在下面提到。
| Procedure | Time Complexity of Implementation |
search_trie() | O(n) -> n is the length of the input string |
insert_trie() | O(n) -> n is the length of the input string |
delete_trie() | O(C*n) -> C is the number of alphabets, |
| n is the length of the input word |
在几乎所有情况下,字母数是常数,所以 delete_trie() 的复杂性也减少到 O(n)。
用于 Trie 数据结构的完整 C/C++ 程序
最后,我们(希望)完成了我们的delete_trie()函数,让我们检查我们所写的内容是否正确,使用我们的驱动程序。
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5// The number of children for each node
6// We will construct a N-ary tree and make it
7// a Trie
8// Since we have 26 english letters, we need
9// 26 children per node
10#define N 26
11
12typedef struct TrieNode TrieNode;
13
14struct TrieNode {
15 // The Trie Node Structure
16 // Each node has N children, starting from the root
17 // and a flag to check if it's a leaf node
18 char data; // Storing for printing purposes only
19 TrieNode* children[N];
20 int is_leaf;
21};
22
23TrieNode* make_trienode(char data) {
24 // Allocate memory for a TrieNode
25 TrieNode* node = (TrieNode*) calloc (1, sizeof(TrieNode));
26 for (int i=0; i<N; i++)
27 node->children[i] = NULL;
28 node->is_leaf = 0;
29 node->data = data;
30 return node;
31}
32
33void free_trienode(TrieNode* node) {
34 // Free the trienode sequence
35 for(int i=0; i<N; i++) {
36 if (node->children[i] != NULL) {
37 free_trienode(node->children[i]);
38 }
39 else {
40 continue;
41 }
42 }
43 free(node);
44}
45
46TrieNode* insert_trie(TrieNode* root, char* word) {
47 // Inserts the word onto the Trie
48 // ASSUMPTION: The word only has lower case characters
49 TrieNode* temp = root;
50
51 for (int i=0; word[i] != '\0'; i++) {
52 // Get the relative position in the alphabet list
53 int idx = (int) word[i] - 'a';
54 if (temp->children[idx] == NULL) {
55 // If the corresponding child doesn't exist,
56 // simply create that child!
57 temp->children[idx] = make_trienode(word[i]);
58 }
59 else {
60 // Do nothing. The node already exists
61 }
62 // Go down a level, to the child referenced by idx
63 // since we have a prefix match
64 temp = temp->children[idx];
65 }
66 // At the end of the word, mark this node as the leaf node
67 temp->is_leaf = 1;
68 return root;
69}
70
71int search_trie(TrieNode* root, char* word)
72{
73 // Searches for word in the Trie
74 TrieNode* temp = root;
75
76 for(int i=0; word[i]!='\0'; i++)
77 {
78 int position = word[i] - 'a';
79 if (temp->children[position] == NULL)
80 return 0;
81 temp = temp->children[position];
82 }
83 if (temp != NULL && temp->is_leaf == 1)
84 return 1;
85 return 0;
86}
87
88int check_divergence(TrieNode* root, char* word) {
89 // Checks if there is branching at the last character of word
90 // and returns the largest position in the word where branching occurs
91 TrieNode* temp = root;
92 int len = strlen(word);
93 if (len == 0)
94 return 0;
95 // We will return the largest index where branching occurs
96 int last_index = 0;
97 for (int i=0; i < len; i++) {
98 int position = word[i] - 'a';
99 if (temp->children[position]) {
100 // If a child exists at that position
101 // we will check if there exists any other child
102 // so that branching occurs
103 for (int j=0; j<N; j++) {
104 if (j != position && temp->children[j]) {
105 // We've found another child! This is a branch.
106 // Update the branch position
107 last_index = i + 1;
108 break;
109 }
110 }
111 // Go to the next child in the sequence
112 temp = temp->children[position];
113 }
114 }
115 return last_index;
116}
117
118char* find_longest_prefix(TrieNode* root, char* word) {
119 // Finds the longest common prefix substring of word
120 // in the Trie
121 if (!word || word[0] == '\0')
122 return NULL;
123 // Length of the longest prefix
124 int len = strlen(word);
125
126 // We initially set the longest prefix as the word itself,
127 // and try to back-tracking from the deepst position to
128 // a point of divergence, if it exists
129 char* longest_prefix = (char*) calloc (len + 1, sizeof(char));
130 for (int i=0; word[i] != '\0'; i++)
131 longest_prefix[i] = word[i];
132 longest_prefix[len] = '\0';
133
134 // If there is no branching from the root, this
135 // means that we're matching the original string!
136 // This is not what we want!
137 int branch_idx = check_divergence(root, longest_prefix) - 1;
138 if (branch_idx >= 0) {
139 // There is branching, We must update the position
140 // to the longest match and update the longest prefix
141 // by the branch index length
142 longest_prefix[branch_idx] = '\0';
143 longest_prefix = (char*) realloc (longest_prefix, (branch_idx + 1) * sizeof(char));
144 }
145
146 return longest_prefix;
147}
148
149int is_leaf_node(TrieNode* root, char* word) {
150 // Checks if the prefix match of word and root
151 // is a leaf node
152 TrieNode* temp = root;
153 for (int i=0; word[i]; i++) {
154 int position = (int) word[i] - 'a';
155 if (temp->children[position]) {
156 temp = temp->children[position];
157 }
158 }
159 return temp->is_leaf;
160}
161
162TrieNode* delete_trie(TrieNode* root, char* word) {
163 // Will try to delete the word sequence from the Trie only it
164 // ends up in a leaf node
165 if (!root)
166 return NULL;
167 if (!word || word[0] == '\0')
168 return root;
169 // If the node corresponding to the match is not a leaf node,
170 // we stop
171 if (!is_leaf_node(root, word)) {
172 return root;
173 }
174 TrieNode* temp = root;
175 // Find the longest prefix string that is not the current word
176 char* longest_prefix = find_longest_prefix(root, word);
177 //printf("Longest Prefix = %s\n", longest_prefix);
178 if (longest_prefix[0] == '\0') {
179 free(longest_prefix);
180 return root;
181 }
182 // Keep track of position in the Trie
183 int i;
184 for (i=0; longest_prefix[i] != '\0'; i++) {
185 int position = (int) longest_prefix[i] - 'a';
186 if (temp->children[position] != NULL) {
187 // Keep moving to the deepest node in the common prefix
188 temp = temp->children[position];
189 }
190 else {
191 // There is no such node. Simply return.
192 free(longest_prefix);
193 return root;
194 }
195 }
196 // Now, we have reached the deepest common node between
197 // the two strings. We need to delete the sequence
198 // corresponding to word
199 int len = strlen(word);
200 for (; i < len; i++) {
201 int position = (int) word[i] - 'a';
202 if (temp->children[position]) {
203 // Delete the remaining sequence
204 TrieNode* rm_node = temp->children[position];
205 temp->children[position] = NULL;
206 free_trienode(rm_node);
207 }
208 }
209 free(longest_prefix);
210 return root;
211}
212
213void print_trie(TrieNode* root) {
214 // Prints the nodes of the trie
215 if (!root)
216 return;
217 TrieNode* temp = root;
218 printf("%c -> ", temp->data);
219 for (int i=0; i<N; i++) {
220 print_trie(temp->children[i]);
221 }
222}
223
224void print_search(TrieNode* root, char* word) {
225 printf("Searching for %s: ", word);
226 if (search_trie(root, word) == 0)
227 printf("Not Found\n");
228 else
229 printf("Found!\n");
230}
231
232int main() {
233 // Driver program for the Trie Data Structure Operations
234 TrieNode* root = make_trienode('\0');
235 root = insert_trie(root, "hello");
236 root = insert_trie(root, "hi");
237 root = insert_trie(root, "teabag");
238 root = insert_trie(root, "teacan");
239 print_search(root, "tea");
240 print_search(root, "teabag");
241 print_search(root, "teacan");
242 print_search(root, "hi");
243 print_search(root, "hey");
244 print_search(root, "hello");
245 print_trie(root);
246 printf("\n");
247 root = delete_trie(root, "hello");
248 printf("After deleting 'hello'...\n");
249 print_trie(root);
250 printf("\n");
251 root = delete_trie(root, "teacan");
252 printf("After deleting 'teacan'...\n");
253 print_trie(root);
254 printf("\n");
255 free_trienode(root);
256 return 0;
257}
出发点( )
1Searching for tea: Not Found
2Searching for teabag: Found!
3Searching for teacan: Found!
4Searching for hi: Found!
5Searching for hey: Not Found
6Searching for hello: Found!
7 -> h -> e -> l -> l -> o -> i -> t -> e -> a -> b -> a -> g -> c -> a -> n ->
8After deleting 'hello'...
9 -> h -> i -> t -> e -> a -> b -> a -> g -> c -> a -> n ->
10After deleting 'teacan'...
11 -> h -> i -> t -> e -> a -> b -> a -> g ->
因此,我们已经到达了我们在 C/C++ 中的 Trie Data Structure 实现的尽头,我知道这是一个漫长的阅读,但希望你已经明白了如何正确地应用这些方法!
下载代码
你可以在我上传的 Github Gist中找到完整的代码,这可能不是最有效的代码,但我已经尽力确保它正常工作。
如果您有任何疑问或建议,请在下面的评论部分提出它们!
参考
- [ 维基百科 文章 】(https://en.wikipedia.org/wiki/Trie)
推荐阅读:
如果您对类似主题感兴趣,您可以参阅数据结构和算法( / 社区 / 教程 / 数据结构 - 算法)部分,其中包括哈希表和图表理论等主题。