在字典中递归查找键

Question

我正在尝试编写一个非常简单的函数，以递归方式搜索可能嵌套的（在最极端的情况下为十层深度）Python字典，并返回从给定键中找到的第一个值。我不明白为什么我的代码不适用于嵌套字典。def _finditem(obj, key):    if key in obj: return obj[key]    for k, v in obj.items():        if isinstance(v,dict):            _finditem(v, key)print _finditem({"B":{"A":2}},"A")它返回None。但是，它确实对于_finditem({"B":1,"A":2},"A")return 起作用2。我敢肯定这是一个简单的错误，但我找不到。我觉得标准库或中可能已经有此功能collections，但是我也找不到。

Answer 1

这是一个搜索包含嵌套字典和列表的字典的函数。它创建结果值的列表。

def get_recursively(search_dict, field):

    """

    Takes a dict with nested lists and dicts,

    and searches all dicts for a key of the field

    provided.

    """

    fields_found = []

    for key, value in search_dict.iteritems():

        if key == field:

            fields_found.append(value)

        elif isinstance(value, dict):

            results = get_recursively(value, field)

            for result in results:

                fields_found.append(result)

        elif isinstance(value, list):

            for item in value:

                if isinstance(item, dict):

                    more_results = get_recursively(item, field)

                    for another_result in more_results:

                        fields_found.append(another_result)

    return fields_found

Answer 2

这是使用“堆栈”和“迭代器堆栈”模式进行操作的一种方法（归功于Gareth Rees）：

def search(d, key, default=None):

    """Return a value corresponding to the specified key in the (possibly

    nested) dictionary d. If there is no item with that key, return

    default.

    """

    stack = [iter(d.items())]

    while stack:

        for k, v in stack[-1]:

            if isinstance(v, dict):

                stack.append(iter(v.items()))

                break

            elif k == key:

                return v

        else:

            stack.pop()

    return default

在print(search({"B": {"A": 2}}, "A"))将打印2。