Python遞歸樹問題（添加元素或任意節點）

Question

我不得不解決學校使用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 

但我不明白遞歸太好，不足以做正確的;這最終會向父節點添加新節點，但會添加無節點。因此，這裏是另一個例子：

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程序使這些無節點？我看到我必須正確地退出遞歸，那麼怎麼做呢？

此外，我試圖恢復的路徑如下：

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() 

我嘗試，直到目標節點發現所有的家長加入到堆棧中，然後彈出了所有的父母，直到只拿到了路徑目標狀態保持在堆棧上。我怎麼能以優雅的方式做到這一點？

Answer 1

您看到None已被添加，因爲您的addNode函數不返回任何內容。這意味着當您使用a[addNode(a[x],k,newNode)]執行遞歸調用時，它相當於addNode(a[x],k,newNode); a[None]。我想你真正想要的東西像下面這樣：

def addNode(a,k,newNode): 
    if k in a: 
     a[k][newNode] 
    else: 
     for x in a: 
      addNode(a[x],k,newNode) 

例如：

>>> import json 
>>> a = tree() 
>>> a['1'] 
defaultdict(<function <lambda> at 0x7fee0285f848>, {}) 
>>> addNode(a, '1', 'new') 
>>> print json.dumps(a) 
{"1": {"new": {}}} 
>>> a['1']['2']['3'] 
defaultdict(<function <lambda> at 0x7fee0285f848>, {}) 
>>> addNode(a, '3', 'new2') 
>>> print json.dumps(a) 
{"1": {"new": {}, "2": {"3": {"new2": {}}}}}