<pre><code>def recurse(tree):
"""Walks a tree depth-first and yields the path at every step."""
# We convert the tree to a list of paths through it,
# with the most recently visited path last. This is the stack.
def explore(stack):
try:
# Popping from the stack means reading the most recently
# discovered but yet unexplored path in the tree. We yield it
# so you can call your method on it.
path = stack.pop()
except IndexError:
# The stack is empty. We're done.
return
yield path
# Then we expand this path further, adding all extended paths to the
# stack. In reversed order so the first child element will end up at
# the end, and thus will be yielded first.
stack.extend(path + (elm,) for elm in reversed(path[-1]))
yield from explore([(tree,)])
# The linear structure yields tuples (root, child, ...)
linear = recurse(root)
# Then call checkChild(rootDict, child, ...)
next(linear) # skip checkChild(rootDict)
for path in linear:
checkChild(rootDict, *path[1:])
</code></pre>
<p>为了便于理解,假设根看起来像这样:</p>
<pre><code>root
child1
sub1
sub2
child2
sub3
subsub1
sub4
child3
</code></pre>
<p>那就像一棵树。我们可以通过这棵树找到一些路径,例如<code>(root, child1)</code>。当您将这些路径提供给<code>checkChild</code>时,这将导致调用<code>checkChild(rootNode, child1)</code>。最终<code>checkChild</code>将为树中的每个路径准确调用一次。因此,我们可以将树写为路径列表,如下所示:</p>
<pre><code>[(root,),
(root, child1),
(root, child1, sub1),
(root, child1, sub2),
(root, child2),
(root, child2, sub3),
(root, child2, sub3, subsub1),
(root, child2, sub4),
(root, child3)]
</code></pre>
<p>此列表中路径的顺序恰好与循环结构匹配。它被称为深度优先。(另一种排序顺序,<em>宽度优先</em>,将首先列出所有子节点,然后列出所有子节点,最后列出所有子节点。)</p>
<p>上面的列表与代码中的<code>stack</code>变量相同,只是<code>stack</code>只存储它需要记住的最少数量的路径。你知道吗</p>
<p>总之,<code>recurse</code>一个接一个地生成这些路径,最后一位代码调用<code>checkChild</code>方法,就像您在问题中所做的那样。你知道吗</p>