ネストされた値でツリー構造を検索していますか？

Question

入力：ツリー構造は、親/子アカウントの階層順に分離された金融口座のリストです。任意のアカウントは、任意の数の親子を持つことができます。 Python構造体では、各子は任意の数の辞書および/またはテキスト値を含むことができるリストです。辞書は追加のアカウントを指す子を表しますが、テキストの値はそれ以上の子孫を持たない子を表します。舞台裏

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

次のようになり、アカウントの定義が含まれている入力ファイルが存在している：ここではJSON（バックPythonでそれを変換してください、それをテストするため）でフォーマットされたいくつかの例の入力がある

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"] 

がどのようになるだろうN子供まで検索するには、この再帰：ここでは、コードですか？

Answer 1

I = mは、実際に（特定の標準出力の出力要件に関して）あなたの質問に答えるつもりはないが、私はどのように最初にあなたのツリー構造

1. ツリーを記述するツリー構造に

   を検索する方法を紹介するのに役立ちますノードのリスト

2. nodeType1は今
3. 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 

（それはおそらく誰かがために期待していた方法で再帰的ではありませんが）

Answer 2

（時間のうち、私は、あなたのテストを統合するための管理と確信しています）不完全：

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']