Trie树：插入、查找、删除和遍历详解

Trie树，也称为前缀树或字典树，是一种非常有用的数据结构，尤其在处理字符串时。它允许我们高效地插入、查找、删除和遍历字符串集合。下面我们将详细讨论这些操作。

一、Trie树的原理

Trie树的每个节点代表一个字符，从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。例如，在单词 ‘apple’ 的 Trie 树中，我们可以从根节点依次经过 ‘a’、’p’、’p’、’l’、’e’ 这些节点，从而找到这个单词。

二、Trie树的插入

插入一个字符串到 Trie 树中，我们需要从根节点开始，根据字符串的每个字符找到相应的子节点。如果子节点不存在，就创建新的节点。例如，插入 ‘apple’ 的过程如下：

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False
def insert(root, word):
    node = root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
    node.is_end_of_word = True

三、Trie树的查找

查找一个字符串是否在 Trie 树中，同样从根节点开始，根据字符串的每个字符找到相应的子节点。如果在某个节点处找不到对应的子节点，说明字符串不存在于 Trie 树中。如果在遍历过程中遇到了一个标记为单词结尾的节点，说明找到了匹配的字符串。例如：

def search(root, word):
    node = root
    for char in word:
        if char not in node.children:
            return False
        node = node.children[char]
    return node.is_end_of_word

四、Trie树的删除

删除一个字符串从 Trie 树中需要一些额外的步骤。首先需要找到要删除的字符串的所有前缀路径，然后删除这些路径上的所有节点。最后还需要检查其他以该前缀开头的单词是否仍然存在于 Trie 树中，如果存在则恢复删除的节点。例如：

def delete(root, word):
    node = root
    for char in word:
        if char not in node.children:
            return False
        node = node.children[char]
    node.is_end_of_word = False  # Remove the end of word mark.
    return true  # If no other words have this prefix, the node will be deleted later.

五、Trie树的遍历

遍历 Trie 树有多种方式，比如深度优先搜索 (DFS) 和广度优先搜索 (BFS)。这里我们使用深度优先搜索来遍历整个 Trie 树：

def dfs(node):
    if node is None: return []
    if node.is_end_of_word: yield node.word  # Node is a word, return the word.
    for char, child in node.children.items():  # Traverse all the children nodes.
        yield from dfs(child)  # Use yield from to traverse the subtree of a child node.