Python鳕鱼的奇怪行为

Question

我正在尝试编写一个简单的方法，以这种方式将树的节点链接在一起：

• 每片叶子都链接到树的上一片叶子和下一片叶子
• 每个非叶子都链接到树的上一个和下一个叶子

例如，如果我们有一棵树：

    A
  / |  \
 B  C    D
   / \  / \
  E  F  G  H
        |
        I

这应该是方法的结果：

• B.nextToken=E公司
• C.prevToken=B
• E.nextToken=F
• E.prevToken=B
• F.nextToken=1
• C.nextToken=I
• H.prevToken=我

方法代码如下：

prevToken = None
def depthFirstTraverseTokenLinking(tree):
    global prevToken
    if len(tree.children) == 0:
        tree.prevToken = prevToken
        if prevToken != None :
            prevToken.nextToken = tree # Is something wrong with this line?
        prevToken = tree
        return

    for c in tree.children:
        depthFirstTraverseTokenLinking(c)

    tree.prevToken = tree.children[0].prevToken
    tree.nextToken = tree.children[-1].nextToken

出于某种奇怪的原因，非叶子没有链接到下一个叶子，例如：

• C.nextToken=无

尽管

• F.nextToken=1

我想知道为什么会这样？递归函数末尾的最后几行应该表示父函数的下一行与其上一个子函数的下一行相同！你知道吗

Answer 1

或者，使用实例检查循环

如果节点没有子节点，则生成器生成节点作为基本情况，否则生成另一个生成器沿树向下移动。这是警告吗节点.子节点从左到右排列。你知道吗

def leafs(node):
    if len(node.children) == 0:
        yield node
    else:
        for child in node.children:
            yield leafs(child)

…还有一堆发电机的回路。。。当我写的时候，它变得更难看了-我想你可以把它清理干净一点，当它是真的。。。你知道吗

current_node = leafs(a)
stack = []
last_node = None
while True:
    if isinstance(current_node, types.GeneratorType):
        stack.append(current_node)
        current_node = current_node.next()
    else:
        if last_node and last_node != current_node:
            last_node.nextToken = current_node
            current_node.prevToken = last_node
            last_node = current_node
        try:
            current_node = stack[-1].next()
        except StopIteration:
            stack.pop()
        except IndexError:
            break

Answer 2

问题是，当您访问C时，只遍历它的子对象E&F

“I”还没有被访问，所以C.children[-1].nextToken == None因为只有访问“I”才会设置F.nextToken

解决方案：您必须首先在所有叶上运行，然后在内部节点上运行第二次。你知道吗

例如：

prevToken = None
def depthFirstTraverseTokenLinking(tree):
    depthFirstTraverseTokenLinkingPhase1(tree)
    depthFirstTraverseTokenLinkingPhase2(tree)

def depthFirstTraverseTokenLinkingPhase1(tree):
    global prevToken
    if len(tree.children) == 0:
        tree.prevToken = prevToken
        if prevToken != None :
            prevToken.nextToken = tree # Is something wrong with this line?
        prevToken = tree
        return

    for c in tree.children:
        depthFirstTraverseTokenLinkingPhase1(c)

def depthFirstTraverseTokenLinkingPhase2(tree):
    if len(tree.children) == 0:
        return

    for c in tree.children:
        depthFirstTraverseTokenLinkingPhase2(c)

    if tree.children[0].prevToken is not None:
        tree.prevToken = tree.children[0].prevToken
    else:
        tree.prevToken = tree.children[0]

    if tree.children[-1].nextToken is not None:
        tree.nextToken = tree.children[-1].nextToken
    else:
        tree.nextToken = tree.children[-1]

还要注意内部节点的prevToken/nextToken的变化。如果您希望它们链接到实际的第一个/最后一个叶，则需要这样做。你知道吗