7

タイムパスアクティビティとして、Python でTree (like) 構造を実装することにしました。
次のようにクラスを実装しましたNode（ここでは単独で目的を果たします）。

class Node:
    def __init__(self, name, parent, *data):
        self.name = name
        self.parent = parent
        self.data = data
        self.children = []
        self.is_root = False

    def __repr__(self):
        return 'Node '+repr(self.name)

    def dic(self):
        retval = {self:[]}
        for i in self.children:
            retval[self].append(i.dic())
        return retval

    def display(self): # Here
        pass

    def has_children(self):
        return bool(self.children)

    def get_parent(self):
        return self.parent

    def add_child(self, name, *data):
        child = Node(name, self,*data)
        self.children.append(child)
        return child

ご覧のとおり、display機能は実装されていません。
これがツリーの例です。

A = Node('A',Node)
A.is_root = True
B = A.add_child('B')
D = B.add_child('D')
C = A.add_child('C')
E = C.add_child('E')
F = C.add_child('F')
G = C.add_child('G')

の出力例を次に示しますdisplay。

>>> A.display()
    A
  +-^-+
  B   C
  | +-+-+
  D E F G
>>> C.display()
   C
 +-+-+
 E F G

最短の形式で
、Node クラスから (上記のような) ASCII ツリーを「構築」するにはどうすればよいですか??

より長い形式で
は、印刷の「ロジック」は次のとおりです。

  1. 子が 1 人だけの場合は|、子の上に置かれます。(ニ)
  2. それ以外の場合、すべての子にはその+上に (B、C、E、F) があります。
  3. さえないとき。親^の下に配置されます。(ア)
  4. そうでなければ、(子の数が奇数です)+は親の下に置かれます。(ハ)

下から考えてみました。私は、それぞれの子への呼び出しが必要であることに気付きましたが、それに近いものを提供するもの (そのようなものまたはその他のもの) を実装することができませんでした。

4

2 に答える 2

16

これは、探しているもののほとんどをカバーするソリューションです。

他のツリー アルゴリズムと同様に、ツリーの子を再帰し、各ノードで結果を結合します。トリックは次のとおりdisplay()です。テキストの四角形を返します。次に例を示します。

aaaaaa
aaaaaa
aaaaaa

長方形のほとんどは空白になります。テキストの四角形のみを返すと、結果を簡単に組み合わせることができます。次の 2 つのヘルパー関数を使用します。1 つはブロック幅を測定するため、もう 1 つはブロックを水平方向に結合してより大きなブロックにするためです。

def block_width(block):
    try:
        return block.index('\n')
    except ValueError:
        return len(block)

def stack_str_blocks(blocks):
    """Takes a list of multiline strings, and stacks them horizontally.

    For example, given 'aaa\naaa' and 'bbbb\nbbbb', it returns
    'aaa bbbb\naaa bbbb'.  As in:

    'aaa  +  'bbbb   =  'aaa bbbb
     aaa'     bbbb'      aaa bbbb'

    Each block must be rectangular (all lines are the same length), but blocks
    can be different sizes.
    """
    builder = []
    block_lens = [block_width(bl) for bl in blocks]
    split_blocks = [bl.split('\n') for bl in blocks]

    for line_list in itertools.izip_longest(*split_blocks, fillvalue=None):
        for i, line in enumerate(line_list):
            if line is None:
                builder.append(' ' * block_lens[i])
            else:
                builder.append(line)
            if i != len(line_list) - 1:
                builder.append(' ')  # Padding
        builder.append('\n')

    return ''.join(builder[:-1])

これがどこに向かっているのかわかりますか？子は自身とその子孫を表示する四角形を返し、各ノードはこれらの四角形を結合して、それ自体を含むより大きな四角形にします。コードの残りの部分は、ダッシュとプラスをレンダリングするだけです。

class Node:
    def display(self): # Here
        if not self.children:
            return self.name

        child_strs = [child.display() for child in self.children]
        child_widths = [block_width(s) for s in child_strs]

        # How wide is this block?
        display_width = max(len(self.name),
                    sum(child_widths) + len(child_widths) - 1)

        # Determines midpoints of child blocks
        child_midpoints = []
        child_end = 0
        for width in child_widths:
            child_midpoints.append(child_end + (width // 2))
            child_end += width + 1

        # Builds up the brace, using the child midpoints
        brace_builder = []
        for i in xrange(display_width):
            if i < child_midpoints[0] or i > child_midpoints[-1]:
                brace_builder.append(' ')
            elif i in child_midpoints:
                brace_builder.append('+')
            else:
                brace_builder.append('-')
        brace = ''.join(brace_builder)

        name_str = '{:^{}}'.format(self.name, display_width)
        below = stack_str_blocks(child_strs)

        return name_str + '\n' + brace + '\n' + below

    # SNIP (your other methods)

そして、私たちはレースに出かけます！

                             a                             
+-+-+---------------------------+                          
b e f                           g                          
+     +-+-------------------------+                        
c     h i                         k                        
+       + +-+-+-+-------------+-------------+-+------+     
d       j l m p r             s             O P      Q     
            + +   +-+-+-+---------+             +-----+    
            n q   t u w x         y             R     S    
            +       +     +-------+-------+       +---+---+
            o       v     z       A       M       T   U   Z
                            +-+-+-+-+-+-+ +           +   +
                            B D E H I K L N           V   a
                            +   +   +               +-+-+ +
                            C   F   J               W X Y b
                                +                          
                                G

(「親の下に ^ を配置する」などの要件は、読者の演習として残されています)

于 2013-07-04T05:32:47.460 に答える