以 ASCII 显示一棵树 [英] Displaying a tree in ASCII

查看:57
本文介绍了以 ASCII 显示一棵树的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

作为时间传递活动,我决定实施一个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 树(如上所示)?

以更长的形式,
打印的逻辑"是:

  1. 当只有一个孩子时,| 放在孩子的上方.(D)
  2. 否则,每个孩子上面都有一个+,(B,C,E,F)
  3. 当甚至没有时.对于孩子,^ 放在父级之下.(一)
  4. 否则,(有奇数个孩子)+ 放在父级之下.(C)

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

解决方案

这里的解决方案涵盖了您正在寻找的大部分内容.

像任何树算法一样,向下递归树的子节点,并在每个节点合并结果.技巧如下: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 child

As 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 G

In 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:

  1. When there is only one child, | is put above the child. (D)
  2. Else, Every child has a + above it, (B,C,E,F)
  3. When there are even no. of children, ^ is put below the parent. (A)
  4. Else, (there are odd no. of children) + is put below the parent. (C)

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
aaaaaa

Most 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 显示一棵树的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆