Golang 程序实现 Trie 数据结构
Trie 是一种类似于树的数据结构，用于存储和搜索一组动态字符串。它在处理键共享公共前缀(如字典单词)的数据时很有用。Trie 与其他检索数据结构不同，因为它具有高效的字符串操作和检索属性。在本文中，我们将学习在 Go 编程语言中实现 Trie 数据结构。
解释
Trie，也称为检索树，是一种树数据结构，通常用于存储和管理字符串集合。它提供对存储的字符串的访问。支持插入和删除等各种操作。这使其对于涉及搜索和提供建议的任务特别有用。
让我们看看 trie 树
(root)
/ | \
a b b
/ \ \
p a a
/| \ \
p p t l
/ \ \
l le l
/
e
我们在顶部有一个根节点，没有字符。
边连接节点，每条边代表一个字符。
节点可以有许多子节点和字符。
路径 a->p->p->l->e 代表苹果。
路径 b->a->t 代表蝙蝠
语法
func NewTrie() *Trie
语法定义了一个名为 NewTrie() 的函数，该函数定义为使用包含子节点映射的根节点初始化 Trie 的新实例。
func (t *Trie) StartsWith(前缀字符串) (单词 []字符串)
该语法定义了一个 StartsWith 函数，对于给定的前缀，该函数通过从根到前缀递归遍历节点，浏览 Trie 以识别共享该前缀的单词。它收集在该前缀下找到的单词并将它们作为列表返回。
算法
首先创建一个 TrieNode 类型的结构，该结构具有一个用于存储子节点的映射。
然后定义一个 Insert 函数将单词添加到 Trie。
开发一个 Search 函数来检查 Trie 中是否存在单词。
构建一个 StartsWith 函数来查找具有给定前缀的所有单词。
最后，设计一个 Print 函数来可视化 Trie 结构。
示例
在此示例中，我们使用 TrieNode 结构定义了一个 Trie 数据结构，其中包括一个用于存储子节点的映射和一个用于标记单词结尾的布尔值。Insert 函数通过遍历字符并根据需要创建节点来帮助添加字符串。 Search 函数遍历 Trie 以确定单词是否存在。最后，printTrie 函数以可视化方式显示 Trie 的结构。
package main
import "fmt"
type TrieNode struct{ children map[rune]*TrieNode; isEnd bool }
type Trie struct{ root *TrieNode }
func NewTrie() *Trie { return &Trie{root: &TrieNode{children: make(map[rune]*TrieNode)}}}
func (t *Trie) Insert(word string) {
node := t.root
for _, c := range word {
if node.children[c] == nil { node.children[c] = &TrieNode{children: make(map[rune]*TrieNode)}}
node = node.children[c]
}
node.isEnd = true
}
func (t *Trie) Search(word string) bool {
node := t.root
for _, c := range word {
if node.children[c] == nil { return false }
node = node.children[c]
}
return node.isEnd
}
func printTrie(node *TrieNode, level int, prefix string) {
if node == nil { return }
fmt.Printf("%s%d\n", prefix, level)
for c, childNode := range node.children {
printTrie(childNode, level+1, fmt.Sprintf("%s──", prefix))
fmt.Printf("%s%s\n", prefix, string(c))
}
}
func main() {
trie := NewTrie()
words := []string{"apple", "app", "banana", "bat"}
for _, w := range words { trie.Insert(w); }
fmt.Println("\nTrie Structure:"); printTrie(trie.root, 0, "")
fmt.Println("\nSearch 'app':", trie.Search("app"))
fmt.Println("Search 'banana':", trie.Search("banana"))
fmt.Println("Search 'batman':", trie.Search("batman"))
}
输出
Trie Structure: 0 ──1 ────2 ──────3 ────────4 ──────────5 ────────e ──────l ────p ──p a ──1 ────2 ──────3 ────────4 ──────────5 ────────────6 ──────────a ────────n ──────a ────n ──────3 ────t ──a b Search 'app': true Search 'banana': true Search 'batman': false
实际实施
联系人或电话簿应用程序:管理联系人信息的尝试可用于开发联系人或电话簿应用程序。Trie 数据结构允许通过其节点对联系人姓名中的特定字符进行编码，从而可以通过输入部分姓名来搜索联系人。
IDE 中的自动完成:作为集成开发环境 (IDE) 中的一项流行功能，代码自动完成需要简化实施。Trie 有助于快速识别与输入前缀匹配的有效代码片段，从而获得简化的体验。
结论
Trie 数据结构是字符串操作的基本工具，可高效存储和检索单词。在本文中，我们探讨了 Trie 的概念，并使用两种不同的方法在 Go 中实现了 Trie 数据结构。第一种方法强调插入和搜索，以突出 Trie 在字典或拼写检查器中查找单词的适用性。第二种方法通过实现前缀匹配来介绍 Trie 的多功能性，这对于自动完成或建议等任务很有用。
