Python递归实现Trie树插入功能出现节点位置错误求助

问题根源 #

原insert函数的核心错误在于：

• 匹配到当前字符时，直接取节点的最后一个子节点继续递归，而非在子节点中查找匹配下一个字符的节点，导致后续字符错误追加到之前插入单词的末尾节点下（比如"card"的'r'被加到了"cat"的't'节点下）。
• 插入逻辑未区分"当前节点子节点已有目标字符"和"需要新增节点"的场景，路径选择完全错误。

修复后的代码 #

调整递归逻辑，每次处理字符时优先遍历子节点查找匹配项，不存在则新建节点：

class trie :
    def __init__(self, char):
        self.char = char
        self.children = []
    def __repr__ (self):
        return "%s %s" %(self.char, self.children)
    def __str__ (self):
        return "[%s %s]" %(self.char, self.children)

def insert(root, word):
    # 单词为空时结束递归
    if not word:
        return "FIN"
    
    current_char = word[0]
    # 遍历子节点，查找匹配当前字符的节点
    for child in root.children:
        if child.char == current_char:
            # 找到匹配节点，递归处理剩余单词
            return insert(child, word[1:])
    
    # 无匹配节点，创建新节点并添加到子列表
    new_node = trie(current_char)
    root.children.append(new_node)
    # 递归处理剩余单词
    return insert(new_node, word[1:])

测试验证 #

运行原测试代码：

t = trie("#") # root
insert(t, "cat")
insert(t, "card")
insert(t, "dog")
print(t)

输出结果：
[# [[c [a [t []], r [d []]]], [d [o [g []]]]]]
根节点#的子结构完全符合预期，a的子节点包含t和r，解决了原问题。

额外说明 #

• 原代码中的rest函数可直接移除，修复后的逻辑不再依赖"取最后一个子节点"的操作。
• 插入"card"时，会在a的子节点中查找r，未找到则新建节点挂载到a下，确保路径正确。

内容的提问来源于stack exchange，提问作者Nielwig