前缀插入方法

Question

因此，我正在构建一个前缀树，如果我插入一个值“cat”，则指向“cat”的内部节点看起来像：[]->；['c']->；['c'，'a']->；['c'，'a'，'t']->；'cat'，其中最后一个值是叶子。但是我的方法是用[]->；['c']->；['a']->；['t']->；'cat'代替我想要的。你知道吗

class SimplePrefixTree:
    def __init__(self, weight_type: str) -> None:
        self.value = []
        self.weight = 0
        self.subtrees = []
        self.weight_type = weight_type

    def insert(self, value: Any, weight: float, prefix: List) -> None:
        new_node = self.c_node(value, weight, prefix)
            self.subtrees.append(new_node)

    def c_node(self, value: Any, weight: float, prefix: List) -> Any:
        new_node = SimplePrefixTree(self.weight_type)
        new_node.value = new_node.value + [prefix[0]]
        new_node.weight = weight
        new_node.insert(value, weight, prefix[1:])
        return new_node

我发现问题是如果我递归地这样做，我永远不能使用前一级节点值并添加到它，新节点总是以[]开头。我怎样才能改变这个？你知道吗

Answer 1

更改前缀树value的位置如下：

new_node = SimplePrefixTree(self.weight_type)
new_node.value = new_node.value + [prefix[0]]

不是你在做什么。您正在用value = []初始化一个新的SimplePrefixTree()。然后，你在它后面加上[prefix[0]]。难怪只有内容的东西永远只有一个元素；你永远只告诉它添加一个元素！你知道吗

这里您似乎想要的是将所有前面的元素添加到value，然后再添加prefix[0]。那么，您可以做的是在添加[prefix[0]]之前将self.value添加到new_node.value。你知道吗

new_node.value = new_node.value + self.value + [prefix[0]]

self引用的对象是您正在创建的新节点的父节点。因此，self.value已经具有前缀树的前几个元素。所以我们复制它们，然后添加prefix[0]。所以它是这样的（比如prefix = 'cat'：

root.value    = []
child_1.value = [] + root.value    + [prefix[0]] = [] + []         + ['c'] = ['c']
child_2.value = [] + child_1.value + [prefix[1]] = [] + ['c']      + ['a'] = ['c', 'a']
child_3.value = [] + child_2.value + [prefix[2]] = [] + ['c', 'a'] + ['t'] = ['c', 'a', 't']
...