作为时间传递活动,我决定实施一个Tree(像)python中的结构.我实现了一个 Node 类(它单独在这里服务)像这样:
类节点:def __init__(self, name, parent, *data):self.name = 姓名self.parent = 父母self.data = 数据self.children = []self.is_root = 假def __repr__(self):返回'节点'+repr(self.name)def dic(自我):retval = {自我:[]}因为我在 self.children 中:retval[self].append(i.dic())返回值def display(self): # 这里经过def has_children(self):返回布尔值(self.children)def get_parent(self):返回 self.parentdef add_child(self, name, *data):child = Node(name, self,*data)self.children.append(child)返回孩子如您所见,display 功能未实现.这是一个示例树.
A = Node('A',Node)A.is_root = 真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.显示()一个+-^-+乙丙|+-+-+德福格>>>C.显示()C+-+-+EF G以最短的形式,如何从 Node 类构建"一个 ASCII 树(如上所示)?
以更长的形式,打印的逻辑"是:
我一直在考虑从下面开始.我意识到必须给每个孩子打电话,但一直无法实现任何接近它的东西(那种或其他).
解决方案这里的解决方案涵盖了您正在寻找的大部分内容.
像任何树算法一样,向下递归树的子节点,并在每个节点合并结果.技巧如下:display() 返回一个文本矩形,例如:
aaaaaa啊啊啊啊啊啊啊啊大部分矩形都是空白.仅返回文本矩形可以轻松组合结果.我们将使用以下两个辅助函数,一个用于测量块宽度,另一个用于将块水平组合成更大的块:
def block_width(block):尝试:return block.index(' ')除了值错误:返回 len(块)def stack_str_blocks(blocks):"""获取多行字符串列表,并将它们水平堆叠.例如,给定 'aaa aaa' 和 'bbbb bbbb',它返回'aaa bbbb aaa bbbb'.如:'aaa + 'bbbb = 'aaa bbbbaaa' bbbb' aaa bbbb'每个块必须是矩形的(所有线的长度相同),但块可以是不同的尺寸."""建造者 = []block_lens = [block_width(bl) for bl in blocks]split_blocks = [bl.split(' ') for bl in blocks]对于 itertools.izip_longest(*split_blocks, fillvalue=None) 中的 line_list:对于我,枚举中的行(line_list):如果行是无:builder.append(' ' * block_lens[i])别的:builder.append(行)如果我 != len(line_list) - 1:builder.append(' ') # 填充builder.append(' ')返回 ''.join(builder[:-1])看看这是怎么回事?孩子们返回一个显示他们自己和他们的后代的矩形,每个节点将把这些矩形组合成一个包含自己的更大的矩形.其余代码仅呈现破折号和加号:
类节点:def display(self): # 这里如果不是 self.children:返回 self.namechild_strs = [child.display() for child in self.children]child_widths = [block_width(s) for s in child_strs]# 这个块有多宽?display_width = max(len(self.name),总和(child_widths) + len(child_widths) - 1)# 确定子块的中点child_midpoints = []child_end = 0对于 child_widths 中的宽度:child_midpoints.append(child_end + (width//2))child_end += 宽度 + 1# 使用子中点建立支撑大括号生成器 = []对于 xrange(display_width) 中的 i:如果我<child_midpoints[0] 或 i >child_midpoints[-1]:大括号生成器.append(' ')elif i 在 child_midpoints 中:大括号builder.append('+')别的:大括号builder.append('-')大括号 = ''.join(brace_builder)name_str = '{:^{}}'.format(self.name, display_width)下面 = stack_str_blocks(child_strs)return name_str + ' ' + 大括号 + ' ' + 下面# SNIP(你的其他方法)我们要去比赛了!
一个++-+-+---------------------------+b f g+ +-+-------------------------+奇克+ + +-+-+-+-------------+-------------+-+------+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(诸如在父级下方放置 ^"之类的要求留给读者作为练习)
As a time-pass activity, I decided to implement a Tree(like) structure in python. I implemented a Node class (which alone serves the purpose here) like so:
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 childAs you can see the display function is not implemented. Here's an example tree.
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')Here's some sample output for display.
>>> A.display() A +-^-+ B C | +-+-+ D E F G >>> C.display() C +-+-+ E F GIn the shortest form, How can I "build" an ASCII tree (like above) from the Node class??
In a longer form, The "Logic" of printing is:
I have been thinking of starting from below. I realized that there has to be a call to the each of the children, but have been unable to implement anything (of that sorts or otherwise) that gave anything close to it.
解决方案Here's a solution that covers most of what you're looking for.
Like any tree algorithm, recurse down the children of the tree, and combine results at each node. Here's the trick: display() returns a rectangle of text, for example:
aaaaaa aaaaaa aaaaaaMost of the rectangle will be whitespace. Returning only rectangles of text makes it easy to combine results. We'll use the following two helper functions, one to measure block widths, and the other to combine blocks horizontally into larger blocks:
def block_width(block): try: return block.index(' ') except ValueError: return len(block) def stack_str_blocks(blocks): """Takes a list of multiline strings, and stacks them horizontally. For example, given 'aaa aaa' and 'bbbb bbbb', it returns 'aaa bbbb aaa 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(' ') 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(' ') return ''.join(builder[:-1])See where this is going? Children return a rectangle that displays themselves and their descendants, and each node will combine these rectangles into a larger rectangle that contains itself. The rest of the code just renders the dashes and pluses:
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 + ' ' + brace + ' ' + below # SNIP (your other methods)And we're off to the races!
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(Requirements like "placing a ^ below the parent" are left as an exercise for the reader)
更多推荐
以 ASCII 显示一棵树
发布评论