如何遍历这个树？

Question

我遇到了一个用Python创建树形结构的小技巧：

def Tree():
    return defaultdict(Tree)

t = Tree()
t["key1"]["key2"]["key3"] = value

我用这种方式来确保这个数据结构中的每个键都是唯一的，不管我处于哪个层级。不过，这也带来了一个小问题，因为我想根据特定的父节点插入新的键，比如我想给key3插入一个子节点，我该怎么遍历这个结构才能找到key3呢？我可以采取什么策略或方法来找到一个特定的“键”呢？

我觉得这个问题可以用递归来解决，但我对递归和编程还不太熟悉，这是我第一次尝试解决这种分组的问题。谢谢！

Answer 1

这里有一个函数，它会递归地搜索一个节点的“路径”——也就是说，它会找到一系列的父节点，这些父节点可以帮助我们找到我们想要的那个节点：

def findNode(tree, findKey, nodeType):
    if type(tree) != nodeType:  # Check if this is another node or a leaf
        # Reached the end of a branch, and the key was not found, so:
        # return None in order to trigger a `TypeError` and reject this branch
        return None   
    for key in tree:
        if key == findKey:
            # Key was found - return the final part of the path
            return [key]
        else:
            try:
                # Search the next level in this branch
                return [key] + findNode(tree[key], findKey, nodeType)
            except TypeError:
                pass

示例用法：

from collections import defaultdict
def Tree():
    return defaultdict(Tree)
t = Tree()

t[1][2][3][4] = 99
t[1][2][7][9] = 101
t[1][10][19][22] = 44
t[1][10][19][77] = 2822

findNode(t, 22, type(t))
# Result:
# [1, 10, 19, 22]

findNode(t, 7, type(t))
# Result:
# [1, 2, 7]

Answer 2

我在这里选择用一个简单的递归函数来找到相关的节点：

def find(t, search):
    #
    # Find the *first* dictionary object having
    # the key "search"
    for k in t:
        if k == search:
            return t
        if isinstance(t[k],dict):
            result = find(t[k],search)
            if result:
                return result

    return None

一旦你找到了这个节点，你可以根据自己的需要进行修改：

>>> from pprint import pprint
>>> pprint(t)
defaultdict(<function Tree at 0x1c17488>, {
  'key1': defaultdict(<function Tree at 0x1c17488>, {
            'key2': defaultdict(<function Tree at 0x1c17488>, {
                      'key3': 99})})})


>>> node = find(t, "key3")
>>> pprint(node)
defaultdict(<function Tree at 0x1c17488>, {
  'key3': 99})

现在你有了一个对新找到的字典的引用，通过这个引用进行修改会改变“原始”树，因为它们都指向同一个对象。我不是很清楚，所以看看这个例子：

>>> node["key3b"]=0
>>> pprint(t)
defaultdict(<function Tree at 0x1c17488>, {
  'key1': defaultdict(<function Tree at 0x1c17488>, {
            'key2': defaultdict(<function Tree at 0x1c17488>, {
                      'key3': 99, 
                      'key3b': 0})})})