C++ Trie 数据结构

在本文中，我们将讨论 C++ 中的Trie 数据结构及其属性、操作和示例。

Trie 数据结构是一种多路树，用于存储不同的字符串。每个字符串由字符组成，这些字符存储在树状结构中，即Trie 数据结构。它也称为基数树或前缀树，或数字树。基本上，“trie”这个词来源于“retrieval”（检索）这个词，意为检索或找回某些东西。它用于各种任务，例如拼写检查、单词搜索、自动补全等。

Trie 数据结构的属性

Trie 数据结构有多种属性。Trie 数据结构的一些主要属性如下：

• Trie 数据结构是一种树状结构，其中每个节点代表字符串的一个单个字符，从根到节点的路径代表一个特定字符串。
• Trie 数据结构从根节点开始，该节点始终为空并表示空字符。从根节点，会分支出其他分支，这些分支包含字符串的其他字符。
• Trie 数据结构中字符串的末尾称为叶节点。每个叶节点可能包含额外信息。

它可以存储和共享字符串的共同初始部分，这指的是共享前缀。共享共同前缀使高效搜索一组字符串变得更容易。

Trie 数据结构中的操作

Trie 数据结构中可以完成三种操作：

1. 插入操作

此操作用于向 Trie 中添加一个新节点，即一个新字符串。

2. 搜索操作

此操作用于查找特定字符串并检查它是否存在于Trie 数据结构中。

3. 删除操作

此操作用于从Trie 数据结构中删除存在的字符串。

示例

让我们以一个例子来在 C++ 中实现 Trie 数据结构，以执行插入、搜索和删除操作。

编码

输出

上述 C++ 程序的解释

• 首先，程序中包含了 C++ 库。
• 我们假设了一个宏 "CHAR_SIZE"，它有 128 个字符。
• 创建了一个名为 "Trie" 的类，它有四个成员函数：insert、search、haveChildren 和 deletion。
• "insert" 函数用于向 Trie 中添加字符串。
• "search" 函数用于在 Trie 中搜索字符串，如果找到该字符串则返回 true。
• "haveChildren" 函数检查给定 Trie 节点中是否存在非零子节点。
• "delete" 函数是一个递归函数，用于从 Trie 中删除字符串。
• 使用 "insert" 函数插入了各种字符串，分别是 "java"、"javatpoint"、"javac" 和 "j"。
• 使用 "search" 函数检查了各种字符串是否存在。当搜索字符串 "java" 时，它返回 true。同样，当搜索字符串 "javatpoint" 时，它返回 true。当搜索字符串 "javaa" 时，它返回 false，因为此字符串不在 Trie 中。当搜索字符串 "javac" 时，它返回 true，当搜索字符串 "j" 时，它返回 true。
• 之后，使用 "deletion" 函数删除了字符串 "java"、"javatpoint"、"javac" 和 "j"。
• 在删除操作之后，再次调用 "search" 方法，以验证字符串是否已成功从 Trie 中删除。
• 如果搜索操作成功，当字符串找到时返回 1，当字符串未找到时返回 0。
• 最终输出将显示 Trie 为空。它打印 "Empty!!" 并返回 0。

结论

在本文中，我们理解了 Trie 数据结构，它是一种树状结构，用于存储字符串集合。它有各种应用，如单词搜索、拼写检查、自动补全等。我们理解了 Trie 数据结构的各种操作，包括插入、搜索和删除操作。