以ASCII显示树
问题内容：
作为一个时间传递活动，我决定在python中实现一个Tree（类似）结构。
我实现了一个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） - 当甚至没有。的孩子，
^放在父母的下面。（一种） - 否则，（有奇数个孩子）
+放在父母的下面。（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
（诸如“将^置于父母以下的要求”留给读者练习）
