如何遍历这棵树？(how to traverse this tree?)

如何遍历这棵树？(how to traverse this tree?)

我遇到过这个创建树的python技巧：

def Tree(): return defaultdict(Tree) t = Tree() t["key1"]["key2"]["key3"] = value

所以我使用它的方式是这个数据结构中的每个键都是唯一的，无论我在哪个维度。 但是，这会带来一些问题，因为我希望能够根据特定父项插入新密钥，例如，我想将一个子项插入到key3 ，如何以找到key3的方式遍历它？ 例如，我可以采取哪些策略/方法来找到给定的“密钥”？

我有一种感觉，这可以递归地解决，但我对递归和编程相当缺乏经验，这是我第一次尝试解决一组群体类型问题。 谢谢！

I've come across this python trick of creating a tree:

def Tree(): return defaultdict(Tree) t = Tree() t["key1"]["key2"]["key3"] = value

So I'm using it in such a way that each key in this data structure is unique regardless of which dimension I am at. However, this poses a bit of a problem as I want to be able to insert new keys based on a specific parent, e.g I want to insert a child to key3, how do I traverse it in such a way that it finds key3? What strategies/approaches can I take to find a given "key" for example?

I have a feeling this can be solved recursively, but I'm fairly inexperienced with recursion and programming and this is my first attempt at solving a group of groups type problem. Thanks!

最满意答案

我选择在这里使用这个简单的递归函数find相关的节点：

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})})})

I choose here to find the relevant node using that simple recursive function:

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

Once you get the node, you might change it as you want:

>>> 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})

As you now have a reference to the newly found dictionary, changing it through that reference will alter the "original" tree -- as both contains references to the same object. I'm not quite clear, so look at this example:

>>> 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})})})