0

私と私の友人は、単純な Python プロジェクトに取り組んでいます。実際には、独自の方法で前置並列合計アルゴリズムを実装しています。

非常に奇妙な形式のバイナリ ツリーを作成して処理しています。この形式を、ete2 などの Tree 印刷ライブラリ/ソフトウェアで受け入れられる形式に変換したいと考えています。

したがって、ツリーのすべてのレベルがそのようにリストにプッシュされます

[ [level0], [level1], ... [level i-1], [root] ]

私たちの形式では、すべての内部リスト (ツリーのレベル) に偶数のノードまたはリーフがあります。

たとえば、次の入力があるとします[1, 2, 3, 4, 5]。これにより、次の出力リストが生成されます。[[1, 2, 3, 4], [3, 7], [10, 5], [15]]

上記の出力例の問題は、葉が最終レベルにない場合があることですが、それらは上位レベルのリストに含まれています。これにより、リストのリストを処理し、ノードとリーフを区別し、それらを正しい位置に配置することが難しくなります。

これを次のように視覚化したいと思います。

http://i.imgur.com/BKrqNZi.png

ここで、括弧内の数字はノードで、それ以外は葉です。

この出力ツリーを生成するために、1 つの Tree 描画ライブラリを使用したいと考えています。それらのほとんどは、このタイプのフォーマットを期待しています:[root, [left], [right]]

したがって、この例では、フォーマットは次のようになります。

[15, [10, [3, [1], [2]], [7, [3], [4]] ], [5] ]

現時点では、コードのロジック全体を書き直す立場にないため、奇妙な形式をその形式に変換するスマートな方法を探しています。

どんなアイデアでも大歓迎です。事前にどうもありがとうございました。

4

1 に答える 1

5

rツリーの row 、 colcの要素について、それらの要素が存在する場合、左と右の子要素がそれぞれ位置c*2と次の行にあるという事実を利用できc*2+1ます (そうでない場合、そのノードはリーフです)。それをアルゴリズムに入れるだけです：

def normalize(tree, row=0, col=0):
    try:
        node = tree[row][col]
        left  = normalize(tree, row+1, col*2)
        right = normalize(tree, row+1, col*2+1)
        return [node, left, right] if left or right else [node]
    except:
        return None # child index does not exist

例：

>>> tree = [[1, 2, 3, 4], [3, 7], [10, 5], [15]]
>>> print normalize(tree[::-1]) # reverse the list!
[15, [10, [3, [1], [2]], [7, [3], [4]]], [5]]
于 2014-06-20T20:30:51.967 に答える