注册 登录
编程论坛 Python论坛

【求助】python Trie 字典树 代码问题

Arsmart 发布于 2021-04-06 15:38, 994 次点击
lst = ['ab', 'ac']
Trie = {}
 
for i in lst:
    cur_node = Trie
    # print("Trie", Trie)
    print("i", i)
    for x in i[:-1]:  # 从小到大,从存在的负数一直到-1为止,也就是从最左到右侧,截止到-1,也就是不包含最右侧的一位
        # 而a只有一位,自己就是-1位,所以不会被这个for给循环到,而是在下面的$中被包含。
        print("x", x)
        if x not in cur_node:
            cur_node[x] = {}  # 改变前面的内容,后面变量的值也会变,这是赋值,相当于浅拷贝。如果不想被相互关联,要用深拷贝
            print("1",cur_node)
        print("pre", cur_node)
        cur_node = cur_node[x]
        print("2",cur_node)
    cur_node[i[-1]] = '$' # 此句话的意思就是一个字符串的最后一位(-1位),对应的是$
    print("last", cur_node)
print(Trie)
/////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////
i ab
x a
1 {'a': {}}
pre {'a': {}}
2 {}
last {'b': '$'}
 
 
i ac
x a
pre {'a': {'b': '$'}}
2 {'b': '$'}
last {'b': '$', 'c': '$'}
{'a': {'b': '$', 'c': '$'}}

///////////////////////////////////////////////////////////////////////////
这段代码的目的是实现TRIE字典树结构,是来自https://blog.的代码,先行感谢。但是我有一点不懂为什么从输出的第一个循环到第二个循环的时候,原来的cur_node是last {'b': '$'},而第二个循环的时候又变成了pre {'a': {'b': '$'}}。。。是不是有什么奇妙的python的性质?和赋值有关吗?多谢大佬指点!
2 回复
#2
zyb1593572021-04-06 22:13
在cur_node = cur_node[x],即xxx_node=xxx_node["a"]后, 在第一次大循环完成xxx_node值为{"b","$"},即同步更新字典Trie["a"]为:{"b","$"}, 那么第一循环结束Trie就为{"a": {'b': '$'}}。第二次循环,xxx_node=Trie,那么xxx_node==Trie=={"a": {"b": "$"}}。
SO,  ……
第一循环
node=Trie
node=node[x] or node["a"] or Trie["a"]
那么
node==Trie["a"]=={"b": "$"}
即Trie=={a: {b: $} }

第二循环:
node=Trie
那么: node==?





[此贴子已经被作者于2021-4-6 22:26编辑过]

#3
sssooosss2021-04-07 22:02
共同学习
1