Странного поведения в коде Python

Question

Я пытаюсь написать простой способ связать узлы дерева вместе таким образом:

• Каждого лист связан с предыдущим и следующим листом в дереве
• Каждый не-лист связан с предыдущим и следующим листом в дереве

Например, если у нас есть это дерево:

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

Это должно быть результатом метода:

• B.nextToken = Е
• C.prevToken = В
• E.nextToken = F
• E.prevToken = В
• Р .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

Интересно, почему это происходит? Последние строки в конце рекурсивной функции должны предоставить получателю, что у родителя будет тот же самый следующий, что и его последний ребенок!

Answer 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 внутренних узлов. Это необходимо, если вы хотите, чтобы они ссылались на фактический первый/последний лист.

Answer 2

В качестве альтернативы, использовать генераторы экземпляр проверки петли

Генератор дает узел в качестве базового варианта, если узел не имеет детей, то другой генератор ехать вниз по дереву. Предостережение здесь заключается в том, что node.children упорядочен слева направо.

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