python - 以ASCII格式显示树

作为一个时间传递活动，我决定在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树（如上所述）？？
在一个较长的形式，
印刷的“逻辑”是：
当只有一个孩子时，|放在孩子的上方。（d）
否则，每个孩子都有一个+在上面，（b，c，e，f）
当有偶数个孩子时，^放在家长的下面。（a）
否则，（有奇数个孩子）+放在家长的下面。（c）
我一直在考虑从下面开始。
我意识到必须给每个孩子打个电话，但却无法实现任何（类似的或其他的）能给他们提供任何接近它的东西。

最佳答案

这里有一个解决方案，涵盖了你所寻找的大部分内容。
与任何树算法一样，递归到树的子级，并在每个节点上组合结果。技巧如下：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

（如“将^放在父项下”等要求留给读者作为练习）