7

作为一个时间传递活动，我决定在 python中实现一个树（类似）结构。
我实现了一个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. 当只有一个孩子时，|放在孩子之上。(四)
  2. 否则，每个孩子都有一个+上面，（B，C，E，F）
  3. 甚至没有的时候。的孩子，^放在父母之下。（一种）
  4. 否则，（有奇数个孩子）+放在父母之下。（C）

我一直在考虑从下面开始。我意识到必须给每个孩子打电话，但一直无法实现任何（那种或其他的）任何接近它的东西。

4

2 回答 2

16

这是一个解决方案，涵盖了您正在寻找的大部分内容。

像任何树算法一样，向下递归树的子节点，并在每个节点处组合结果。诀窍是：display()返回一个矩形的文本，例如：

aaaaaa
aaaaaa
aaaaaa

大多数矩形将是空白。只返回文本的矩形可以很容易地组合结果。我们将使用以下两个辅助函数，一个用于测量块的宽度，另一个用于将块水平组合成更大的块：

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 回答
2

我想建议看一下 ETE 模块http://ete.cgenomics.org，它实现了您在此处描述的功能等等。

同时，我想在控制台窗口中以侧向树格式提供此条目 Pretty Print 输出，以前曾问过类似的问题。正如您在此类讨论中看到的那样，ETE 的 _asciiArt 函数提供了我认为您正在寻找的东西。

我希望这有帮助，

于 2013-07-26T11:33:01.667 回答