实现Trie树时第27行指针未递增问题求助

你的问题核心不是指针没递增，而是Trienode类的属性定义错误——next和isTerminal被定义成了类属性，所有Trienode实例会共享同一个next数组和isTerminal状态。这就导致不管创建多少个节点，它们的next都是同一个列表，插入操作的结果看起来像是所有字符都存在第一个节点里，实际是所有节点的next互相覆盖了。

修正步骤 #

1. 将类属性改为实例属性
   把next和isTerminal移到__init__方法中，让每个Trienode实例拥有独立的next数组和终端标记：

class Trienode:
    data: str

    def __init__(self, data):
        self.data = data
        self.next: list = [None] * 26  # 改为实例属性
        self.isTerminal: bool = False  # 改为实例属性

2. 优化display方法
   原来的display只打印根节点的直接子节点，无法遍历整个Trie树。改成递归遍历的方式，才能完整输出所有节点：

def display(self, node=None, prefix=""):
    if node is None:
        node = self.root
    current_prefix = prefix if node.data != '#' else ""
    if node.isTerminal:
        print(current_prefix + node.data)
    for i in range(26):
        child = node.next[i]
        if child is not None:
            self.display(child, current_prefix + node.data)

修正后的完整代码 #

class Trienode:
    data: str

    def __init__(self, data):
        self.data = data
        self.next: list = [None] * 26
        self.isTerminal: bool = False


class Trie:
    def __init__(self):
        self.root = Trienode('#')

    def insert(self, data):
        temp = self.root
        for ch in data:
            index = ord(ch) - ord('a')
            if temp.next[index] is None:
                temp.next[index] = Trienode(ch)
            temp = temp.next[index]
        temp.isTerminal = True

    def display(self, node=None, prefix=""):
        if node is None:
            node = self.root
        current_prefix = prefix if node.data != '#' else ""
        if node.isTerminal:
            print(current_prefix + node.data)
        for i in range(26):
            child = node.next[i]
            if child is not None:
                self.display(child, current_prefix + node.data)


if __name__ == '__main__':
    trie = Trie()
    trie.insert("apple")
    trie.insert("pineapple")
    trie.display()

运行后会输出：

apple
pineapple

这样就能正确完成Trie树的插入与展示操作了。

内容的提问来源于stack exchange，提问作者Mohammad Avesh Husain