0

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

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

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

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

这应该是该方法的结果：

  • B.nextToken = E
  • C.prevToken = B
  • E.nextToken = F
  • E.prevToken = B
  • F.nextToken = I
  • C.nextToken = I
  • H.prevToken = I

下面是方法代码：

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 = I

我想知道为什么会这样？递归函数末尾的最后几行应该允许父级的 next 与其最后一个子级相同！

4

2 回答 2

1

问题是，当你访问 C 时，你只遍历了它的子 E & F。

“我”还没有被访问过，所以C.children[-1].nextToken == None因为只有访问“我”才会设置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如果您希望它们链接到实际的第一片/最后一片叶子，则需要这样做。

于 2013-02-14T07:29:30.570 回答
1

或者，使用生成器作为实例检查循环

如果该节点没有子节点，则生成器将该节点作为基本情况生成，否则另一个生成器将沿着树向下移动。这里需要注意的是 node.children 是从左到右排序的。

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

...和一个带有一堆生成器的循环...当我写它时，这变得更丑了-我认为您可以稍微清理一下并摆脱 while True...

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
于 2013-02-14T08:51:53.737 回答