使用嵌套值搜索樹結構？

輸入：樹結構是按照父/子帳戶的分層順序分隔出來的財務帳戶列表。任何給定的帳戶都可以有任意數量的父母/子女。在Python結構中，每個孩子都是一個列表，可以包含任意數量的詞典和/或文本值。字典代表指向額外帳戶的孩子，而文本值代表沒有其他後代的孩子。這裏是JSON（測試它，請把它轉換回在Python）格式的一些示例輸入：使用嵌套值搜索樹結構？

[ 
    { 
     "Assets":[ 
     { 
      "Bank":[ 
       "Car", 
       "House" 
      ] 
     }, 
     { 
      "Savings":[ 
       "Emergency", 
       { 
        "Goals":[ 
        "Roof" 
        ] 
       } 
      ] 
     }, 
     "Reserved" 
     ] 
    } 
]

在幕後有一個包含看起來像這樣的帳戶定義的輸入文件：

Assets:Bank:House 
Assets:Savings:Emergency 
Assets:Savigs:Goals:Roof

我有解析和創建上面看到的樹結構的現有代碼。

目標：最終目標是通過搜索樹來提供使用給定字符串輸入的自動完成。使用樣品輸入的上方，以下輸入將產生它們各自的輸出：

"Assets" => ["Bank, "Savings", "Reserved"] 
"Assets:Bank" => ["Car", "House"] 
"Assets:Savings:Goals" => ["Roof"]

部分解決：遞歸是我在哪裏得到絆倒。我能夠創建可處理「根」帳戶的結果的代碼，但我不確定如何使其遞歸爲子帳戶提供結果。下面的代碼：

def search_tree(account, tree): 
    # Check to see if we're looking for a root level account 
    if isinstance(account, str) and ":" not in account: 
     # Collect all keys in the child dictionaries 
     keys = {} 
     for item in tree: 
      if isinstance(item, dict): 
       keys[item.keys()[0]] = item 

     # Check to see if the input matches any children 
     if account in keys: 
      # Collect all children of this account 
      children = [] 

      for child in keys[account][account]: 
       if isinstance(child, str): 
        children.append(child) 
       else: 
        children.append(child.keys()[0]) 

      return children 

# tree = ..... 
account = "Assets" 
print search_tree(account, tree) # Would produce ["Bank", "Savings", "Reserved"] 
# In the future I would provide "Assets:Bank" as the account string and get back the following: ["Car", "House"]

我怎麼會做出這種遞歸向下搜索到ň兒？

來源

2016-08-02 Joshua Gilman

傳遞你的搜索字符串作爲列表或分裂「：」在函數內部。在函數內部，再次運行該函數，其餘搜索元素作爲參數。 – handle

這就是我要去的地方，但是我一直陷在如何知道我什麼時候處於搜索的「結尾」。換句話說，我如何知道我已經到達最終的孩子，我需要返回最終孩子的任何子女帳戶（以及如何在遞歸如此之後返回這些值）。 –

堅持下去，爲你嘗試一下... – handle

I不會去真正回答你的問題（與問候您的具體標準輸出的輸出要求），但我會幫助你展示如何搜索樹結構

首先描述你的樹結構

樹=節點列表
nodeType1 =字典由節點名稱=>兒童
nodeType2 =簡單即basestring（nodeName的），沒有兒童（葉節點）

現在我們就可以開始寫一個遞歸解決方案

def search(key,tree): 
    if isinstance(tree,(list,tuple)): # this is a tree 
     for subItem in tree: # search each "node" for our item 
      result = search(key,subItem) 
      if result: 
       return result 
    elif isinstance(tree,dict): # this is really a node (nodeType1) 
     nodeName,subTree = next(tree.iteritems()) 
     if nodeName == key: # match ... in your case the key has many parts .. .you just need the "first part" 
      print "Found:",key 
      return subTree 
     else: # did not find our key so search our subtree 
      return search(key,subTree) 

    elif isinstance(tree,basestring): #leaf node 
     if tree == key: # found our key leaf node 
      print "Found",key 
      return tree

這真的只是一個很普通的解決方案，它可以被用來搜索一個條目（即「豪斯醫生」或「賬戶」 ......它不記錄被用來在解決時）的路徑

現在讓我們回到檢查您的問題聲明

的關鍵是多關鍵Part1:part2:part3 所以，讓我們開始在這個問題上的工作

def search_multipartkey(key,T,separator=":"): 
    result = T 
    for part in key.split(separator): 
     result = search(part,result) 
     if not result: 
      print "Unable to find part:",part 
      return False 
     else: 
      print "Found part %s => %s"%(part,result) 
    return result

可以幾乎肯定提高在這個但這給出了一個很好的起點（雖然它不是也許有人希望的方式遞歸）

來源

2016-08-02 16:32:31

不完整（沒有時間了，但我相信你一定會設法整合你的測試）：

tree = [ 
     {"Assets": [ 
        {"Bank": [ 
           "Car", 
           "House" 
           ] 
        }, 
        {"Savings": [ 
           "Emergency", 
           {"Goals": 
             ["Roof"] 
           } 
           ] 
        }, 
        "Reserved" 
        ] 
     } 
    ] 



def search_tree(account, tree, level): 
    """ """ 
    print("account", account) 
    print("tree", tree) 
    print("level", level) 
    print("-------------") 

    if account == []: 
     return 

    r = None 
    for d in tree: 
     print("a:",account[0]) 
     print("d:",d) 
     try: 
      newtree = d[account[0]] 
      newaccount = account[1:] 
      print("new:", newtree, newtree) 
      r = search_tree(newaccount, newtree, level+1) 
     except Exception as e: 
      print("failed because:", e) 
    return r 

account = "Assets:Bank" 
search_tree(account.split(":"), tree, 0)

輸出：

> py -3 t.py 
account ['Assets', 'Bank'] 
tree [{'Assets': [{'Bank': ['Car', 'House']}, {'Savings': ['Emergency', {'Goals': ['Roof']}]}, 'Reserved']}] 
level 0 
------------- 
a: Assets 
d: {'Assets': [{'Bank': ['Car', 'House']}, {'Savings': ['Emergency', {'Goals': ['Roof']}]}, 'Reserved']} 
new: [{'Bank': ['Car', 'House']}, {'Savings': ['Emergency', {'Goals': ['Roof']}]}, 'Reserved'] [{'Bank': ['Car', 'House']}, {'Savings': ['Emergency', {'Goals': ['Roof']}]}, 'Reserved'] 
account ['Bank'] 
tree [{'Bank': ['Car', 'House']}, {'Savings': ['Emergency', {'Goals': ['Roof']}]}, 'Reserved'] 
level 1 
------------- 
a: Bank 
d: {'Bank': ['Car', 'House']} 
new: ['Car', 'House'] ['Car', 'House'] 
account [] 
tree ['Car', 'House'] 
level 2 
------------- 
a: Bank 
d: {'Savings': ['Emergency', {'Goals': ['Roof']}]} 
failed because: 'Bank' 
a: Bank 
d: Reserved 
failed because: string indices must be integers

仍然沒有測試，但返回你想要（對於這種情況）：

def search_tree(account, tree, level): 
    """ """ 
    #print() 
    #print() 
    #print("account", account) 
    #print("tree", tree) 
    #print("level", level) 
    #print("-------------") 

    if account == []: 
     #print("reached end") 
     #print("tree", tree) 
     return tree 

    r = None 
    for d in tree: 
     #print("a:",account[0]) 
     #print("d:",d) 
     try: 
      newtree = d[account[0]] 
      newaccount = account[1:] 
      #print("new:", newtree, newtree) 
      r = search_tree(newaccount, newtree, level+1) 
     except Exception as e: 
      #print("failed because:", e) 
      pass 
    return r 

account = "Assets:Bank" 
print(search_tree(account.split(":"), tree, 0)) # --> ['Car', 'House']

來源

2016-08-02 16:26:41 handle

注意：這是在迭代中覆蓋'r'因此它對於列表中具有相同密鑰的多個字典不起作用。 – handle

使用嵌套值搜索樹結構？

回答

相關問題