<p>虽然有一个简洁的解决方案可以计算每个节点的生成,但您也可以实现跟踪每个节点生成的树数据结构。你知道吗</p>
<pre><code>class Forest:
def __init__(self, forest_dict):
self.trees = [Tree(value, children) for value, children in forest_dict.items()]
def __iter__(self):
for tree in self.trees:
for node in iter(tree):
yield node
class Tree:
def __init__(self, value, children):
self.root = node = Node(value)
self.__recurse(node, children)
def __recurse(self, node, children):
for value, subchildren in children.items():
child = Node(value, node)
node.addChild(child)
self.__recurse(child, subchildren)
def __iter__(self):
for node in iter(self.root):
yield node
class Node:
def __init__(self, value, parent=None):
self.value = value
self.parent = parent
self.children = []
self.generation = 0
def addChild(self, child):
if not self.children:
node, generation = self, 1
while node is not None:
node.generation = max(node.generation, generation)
generation += 1
node = node.parent
self.children.append(child)
def __iter__(self):
yield self
for child in self.children:
for subchild in iter(child):
yield subchild
</code></pre>
<p>然后,如果将forest结构为嵌套字典,则很容易获得父节点代的列表。你知道吗</p>
<pre><code>forest_dict = {2:
{4:
{8:
{14: {},
15: {}
},
9: {16: {},
17: {}
}
},
5:
{1:
{6:
{18: {},
19: {}
},
10:
{20: {},
21: {}
}
},
7:
{12: {},
13: {}
}
}
},
3:
{0: {},
11: {}
}
}
forest = Forest(forest_dict)
print [node.generation for node in forest if node.generation]
# [4, 2, 1, 1, 3, 2, 1, 1, 1, 1]
</code></pre>
<p>很明显,这是一个更多的工作,但可能是值得的,这取决于你在做什么。注意,由于字典和不同的结构,顺序并不完全相同。你知道吗</p>