python - 搜索具有嵌套值的树结构？

Question

输入:树形结构是按父/子帐户的分层顺序分隔的财务帐户列表。任何给定帐户可以有任意数量的 parent / child 。在 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"]

我如何进行递归搜索以搜索到n个 child ？

Answer 1

我不会真正回答你的问题(关于你的特定标准输出输出要求)，但我会帮助你展示如何搜索树结构

首先描述你的树结构

1. 树 = 节点列表
2. nodeType1 = 由nodeName=>children组成的字典
3. nodeType2 = 没有子节点(叶节点)的简单基字符串(节点名称)

现在我们可以开始编写递归解决方案

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

这实际上只是一个非常通用的解决方案，它可用于搜索单个条目(即“房屋”或“帐户”......它不记录用于到达解决方案的路径)

现在让我们回到检查你的问题陈述

key 是多部分 key 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

你几乎肯定可以对此进行改进，但这提供了一个很好的起点(尽管它不是像某人希望的那样递归)