16

出力が次のようになるように、バイナリ ツリーを横に印刷するにはどうすればよいでしょうか。

   __/a
__/  \b
  \   _/c
   \_/ \d
     \e

(きれいなアスキー アートを歓迎)

うまく動かないコードを次に示します。

def print_tree(tree):
    def emit(node,prefix):
        if "sequence" in node:
            print "%s%s"%(prefix[:-1],node["name"])
        else:
            emit(node["left"],"%s_/ "%prefix.replace("/ "," /")[:-1].replace("_"," "))
            emit(node["right"],"%s \\ "%prefix.replace("\\ "," \\")[:-1])
    emit(tree,"")

これは次のように出力されます:

      _/hg19
    _/ \rheMac2
  _/ \mm9
  /\_/bosTau4
  /  \_/canFam2
_/     \pteVam1
 \_/loxAfr3
   \dasNov2

スコープ クリープ: 任意のノードの印刷する文字列を返す関数を渡すことができれば素晴らしいでしょう。このようにして、非リーブ ノードに関する情報も出力できることがあります。したがって、ノードに出力するものがあるかどうかは、パラメーターとして渡された関数によって制御されます。

JSON のテストデータは次のとおりです。

{
    "left": {
        "left": {
            "left": {
                "left": {
                    "name": "hg19", 
                    "sequence": 0
                }, 
                "right": {
                    "name": "rheMac2", 
                    "sequence": 1
                }
            }, 
            "right": {
                "name": "mm9", 
                "sequence": 2
            }
        }, 
        "right": {
            "left": {
                "name": "bosTau4", 
                "sequence": 3
            }, 
            "right": {
                "left": {
                    "name": "canFam2", 
                    "sequence": 4
                }, 
                "right": {
                    "name": "pteVam1", 
                    "sequence": 5
                }
            }
        }
    }, 
    "right": {
        "left": {
            "name": "loxAfr3", 
            "sequence": 6
        }, 
        "right": {
            "name": "dasNov2", 
            "sequence": 7
        }
    }
}
4

4 に答える 4

7

他の場所で説明されている一般的な再帰的アプローチを実装するコードを次に示します。ツリーの内部表現は、文字列 (リーフ) またはサブノードのタプル (ペア) です。ノードの中間「フラグメント」の内部表現は tuple です(above, below, lines)。ここで、aboveとはbelowルートの上下の行数であり、lines各部分行の反復子です (左側にスペースはありません)。

#!/usr/local/bin/python3.3

from itertools import chain
from random import randint


def leaf(t):
    return isinstance(t, str)

def random(n):
    def extend(t):
        if leaf(t):
            return (t+'l', t+'r')
        else:
            l, r = t
            if randint(0, 1): return (l, extend(r))
            else: return (extend(l), r)
    t = ''
    for _ in range(n-1): t = extend(t)
    return t

def format(t):
    def pad(prefix, spaces, previous):
        return prefix + (' ' * spaces) + previous
    def merge(l, r):
        l_above, l_below, l_lines = l
        r_above, r_below, r_lines = r
        gap = r_below + l_above
        gap_above = l_above
        gap_below = gap - gap_above
        def lines():
            for (i, line) in enumerate(chain(r_lines, l_lines)):
                if i < r_above:
                    yield ' ' + line
                elif i - r_above < gap_above:
                    dash = '_' if i - r_above == gap_above - 1 else ' '
                    if i < r_above + r_below:
                        yield pad(dash + '/', 2 * (i - r_above), line)
                    else:
                        yield pad(dash + '/', 2 * gap_below - 1, line)
                elif i - r_above - gap_above < gap_below:
                    if i < r_above + r_below:
                        yield pad(' \\', 2 * gap_above - 1, line)
                    else:
                        spaces = 2 * (r_above + gap_above + gap_below - i - 1)
                        yield pad(' \\', spaces, line)
                else:
                    yield ' ' + line
        return (r_above + gap_above, gap_below + l_below, lines())
    def descend(left, t):
        if leaf(t):
            if left:
                return (1, 0, [t])
            else:
                return (0, 1, [t])
        else:
            l, r = t
            return merge(descend(True, l), descend(False, r))
    def flatten(t):
        above, below, lines = t
        for (i, line) in enumerate(lines):
            if i < above: yield (' ' * (above - i - 1)) + line
            else: yield (' ' * (i - above)) + line
    return '\n'.join(flatten(descend(True, t)))


if __name__ == '__main__':
    for n in range(1,20,3):
        tree = random(n)
        print(format(tree))

出力例を次に示します。

          _/rrrr
        _/ \_/rrrlr
       / \   \rrrll
     _/   \_/rrlr
    / \     \rrll
   /   \   _/rlrr
  /     \_/ \rlrl
_/        \_/rllr
 \          \_/rlllr
  \           \rllll
   \        _/lrrr
    \     _/ \lrrl
     \   / \_/lrlr
      \_/    \lrll
        \   _/llrr
         \_/ \llrl
           \_/lllr
             \_/llllr
               \lllll

そして、おそらく、最後まで行の左側にスペースを埋め込まない理由を示す、もう少し非対称的なものです（ 経由flatten）。下半分が左側にパッドされていた場合、上腕の一部がパッドされた領域を横切ります.

               _/rrrrr
             _/ \rrrrl
           _/ \rrrl
         _/ \_/rrlr
        / \   \rrll
       /   \_/rlr
      /      \rll
     /        /lrrr
    /       _/  _/lrrlrr
   /       / \_/ \lrrlrl
  /       /    \lrrll
_/      _/     _/lrlrrr
 \     / \   _/ \lrlrrl
  \   /   \_/ \lrlrl
   \_/      \lrll
     \      _/llrrr
      \   _/ \llrrl
       \_/ \llrl
         \lll

これは「明らかな」再帰アルゴリズムです。悪魔は細部に宿ります。「_」なしで書くのが最も簡単で、ロジックが少し複雑になります。

おそらく唯一の「洞察」はgap_above = l_above、右の「アーム」が左のサブツリーの右側の長さを持っているということです (これを数回読む必要があります)。それは物事を比較的バランスの取れたものにします。上記の非対称の例を参照してください。

物事をより詳細に理解する良い方法は、padルーチンを変更して、代わりに文字を取得し、' '呼び出しごとに異なる文字を与えることです。次に、どのロジックがどのスペースを生成したかを正確に確認できます。これは、上記の上から下への埋め込みの呼び出しに A. B、C、および D を使用して得られるものです (明らかに、スペースの量がゼロの場合、文字はありません)。

             _/rrrr
            / \rrrl
          _/B _/rrlrr
         / \_/ \rrlrl
        /AA  \rrll
      _/BBB  _/rlrrr
     / \DD _/ \rlrrl
    /AA \_/ \_/rlrlr
   /AAAA  \C  \rlrll
  /AAAAAA  \_/rllr
_/AAAAAAAA   \rlll
 \DDDDDDDD   _/lrrrr
  \DDDDDD  _/ \lrrrl
   \DDDD  / \lrrl
    \DD _/B _/lrlrr
     \_/ \_/ \lrlrl
       \C  \lrll
        \_/llr
          \lll

ここに詳細な説明があります(ただし、ツリーはわずかに異なります)。

于 2013-05-21T21:45:26.720 に答える
2

文字列配列と「花びら」の行番号を含む表現構造を作成します。

rep(葉) は [0, repr(葉の値)]

top = nonleaf.leftとbottom = nonleaf.right: _

rep(top) の各行に、top の花びらの上にある場合はスペースを、下にある場合は適切な位置にスラッシュを埋め込みます。同様に、rep(bottom) の各行に、bottom のペタルの下にある場合はスペースを、上にある場合は適切な位置にバックスラッシュを埋め込みます。repr(nonleaf) は、[上部の高さ、上部のパディングされた行に続いて下部のパディングされた行] になります。

例：

rep(a): [0, ["a"]]
rep(b): [0, ["b"]]
rep(ab): [1, ["/"+"a", "\"+"b"]]
rep(c): [0, ["c"]]
rep(d): [0, ["d"]]
rep(cd): [1, ["/"+"c", "\"+"d"]]
rep(e): [0, ["e"]]
rep(cde): [2, [" "+"/c", "/" + "\d", "\" + "e"]]
rep(abcde): [2, [" "+"/a", "/"+"\b", "\ "+" /c", " \" + "/\d", "  " + "\e"]]

上のケースでは、パディングの幅は花びらの下の行数であることに注意してください。下のケースでは、パディングの幅は花びらに対応しています。したがって、(abcde) の場合、top には 2 行と花びら 1 があるため、パディングは (2 - 1 == 1) 1 文字です。下は花弁が 2 であるため、パディングは 2 文字です。

必要に応じて、(petal-1) 行目の各非葉に「_」を追加することもできます (および他のすべての行に余分なスペースを追加します)。

明らかに、これはコードではありません (「\」は発生するのを待っている構文エラーです) が、ここから実装するのはそれほど難しくありません。

于 2012-06-19T07:37:58.170 に答える
0

これに再帰的にアプローチし、個々のサブツリーのサイズを追跡する必要があります。特に、ルートがどこにあるか。不均衡なツリーは、次のように簡単に表示されます。

/
\/
 \/
  \/
   \

ここで、すでにこのツリーを構築していると考えてください。親レベルを追加するときに、これを次のように変換する必要があります。

  /
 /\/
/  \/
\   \/
 \   \
  \

重要なアイデアは、葉から始めることです。それらは些細なことです。次に、2つのサブツリーの行数とサブツリールートノードの位置が異なる場合に、それらを集約する方法を定義します。

于 2012-06-19T07:52:14.380 に答える
0

これは、プロジェクトのデバッグに役立った素敵な横向きのツリーです：http: //www.acooke.org/cute/ASCIIDispl0.html

結果は、VIMNERDtreeプラグインのディレクトリレイアウトに似ています。

__str__バイナリツリーのメソッドとしての私の再実装は次のとおりです。

def __str__(self):
    """Recursive __str__ method of an isomorphic node."""
    # Keep a list of lines
    lines = list()
    lines.append(self.name)
    # Get left and right sub-trees
    l = str(self.left).split('\n')
    r = str(self.right).split('\n')
    # Append first left, then right trees
    for branch in l, r:
        # Suppress Pipe on right branch
        alt = '| ' if branch is l else '  '
        for line in branch:
            # Special prefix for first line (child)
            prefix = '+-' if line is branch[0] else alt
            lines.append(prefix + line)
    # Collapse lines
    return '\n'.join(lines)
于 2012-08-06T20:49:45.180 に答える