我必须使用 A* 解决学校的一个小问题(这不是我遇到的问题),我想使用树来存储探索过的节点,所以当找到解决方案时,很容易找到路径从叶子回到根。
在 python 中,可以使用 defaultdictionaries 创建一棵树:
def tree(): return defaultdict(tree)
例如:
a=tree() is an empty tree
a[1] tree with one root node
a[1][2] has a child of 2
a[1][2]['another']... and so on.
我试图做一些事情来添加一个新节点给定一个任意节点(k)给定树(a)和所需的新节点。我只能使用递归来解决。
def addNode(a,k,newNode):
for x in list(a.keys()):
if x!=k:
a[addNode(a[x],k,newNode)]
if x==k:
a[x][newNode]
break
但是我不太了解递归,不足以正确执行;这最终会添加具有正确父节点的新节点,但会添加 None 节点。所以这是另一个例子:
a=tree()
a
defaultdict(<function tree at 0x029CE930>, {})
a[1]
defaultdict(<function tree at 0x029CE930>, {})
a[1][2]
defaultdict(<function tree at 0x029CE930>, {})
a[1][3]
defaultdict(<function tree at 0x029CE930>, {})
a[1][2]['b']
defaultdict(<function tree at 0x029CE930>, {})
addNode(a,'b','new')
a
defaultdict(<function tree at 0x029CE930>, {1: defaultdict(<function tree at 0x029CE930>, {2: defaultdict(<function tree at 0x029CE930>, {'b': defaultdict(<function tree at 0x029CE930>, {'new': defaultdict(<function tree at 0x029CE930>, {})})}), 3: defaultdict(<function tree at 0x029CE930>, {}), None: defaultdict(<function tree at 0x029CE930>, {})}), None: defaultdict(<function tree at 0x029CE930>, {})})
如何正确实现这一点,为什么 addNode 过程会生成这些 None 节点?我有点看到我必须正确退出递归,那是怎么做的呢?
我也尝试恢复路径如下:
parentList=[]
found=False
def getPath(tree,final):
global found
for x in list(tree.keys()):
parentList.append(x)
if found:
parentList.pop()
if x==final:
found=True
else:
getPath(tree[x],final)
if not found:
parentList.pop()
我尝试将所有父节点添加到堆栈中,直到找到目标节点,然后弹出所有父节点,直到只有到达目标状态的路径保留在堆栈中。我怎么能以优雅的方式做到这一点?