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

解決策: 最初にすべてのリーフで実行し、次に内部ノードで 2 回目の実行を行う必要があります。

例えば：

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 に答える