用斜杠打印出二进制搜索树 [英] Printing out a binary search tree with slashes
问题描述
这是我的代码，用于打印出二进制搜索树的元素.目标是按级别顺序显示它，并用斜线将父级连接到每个子级.因此，例如，序列15 3 16 2 1 4 19 17 28 31 12 14 11 0在执行后将显示为:
That's my code to print out the elements of a binary search tree. The goal is to display it in level order, with slashes connecting the parent to each child. So for instance, the sequence 15 3 16 2 1 4 19 17 28 31 12 14 11 0 would display after execution as:
15
/ \
3 16
/ \ \
2 4 19
/ \ / \
1 12 17 28
/ / \ \
0 11 14 31
我已经研究了很长时间了，但是似乎无法正确设置间距/缩进量.我知道我编写了正确的算法来按正确的顺序显示节点，但是斜杠就不存在了.这是我的代码的结果: http://imgur.com/sz8l1
I've been working on it for a long time now, but I just can't seem to get the spacing/indentation right. I know I wrote the proper algorithm for displaying the nodes in the proper order, but the slashes are just off. This is the result of my code as is: http://imgur.com/sz8l1
我知道我已经很接近答案了，因为我的显示与我所需的显示相差不远，而且我感觉这是一个非常简单的解决方案，但是出于某种原因，我似乎只是把它弄对了.
I know I'm so close to the answer, since my display is not that far off from what I need, and I have a feeling it's a really simple solution, but for some reason I just seem to get it right.
推荐答案
我暂时没有时间了，但这是一个快速的版本. 我没有阅读您的代码(不了解C ++)，所以我不知道我们的解决方案有多接近.
I'm out of time for now, but here's a quick version. I did not read your code (don't know C++), so I don't know how close our solutions are.
我稍微改变了输出格式.我使用|代替了左侧节点的/，所以我根本不必担心左侧间距.
I changed the output format slightly. Instead of / for the left node, I used | so I didn't have to worry about left spacing at all.
15
| \
3 16
|\ \
2 4 19
| \ | \
1 | 17 28
| | \
0 12 31
| \
11 14
这是代码.我希望您能够从中获得所需的东西.我确实希望某些Python能够映射到您所使用的东西.主要思想是将每行数字视为到节点对象的位置图，并在每个级别上按键对地图进行排序，然后根据其分配的位置将其迭代打印到控制台.然后生成一个新地图，该地图的位置相对于其上一级的父母.如果发生冲突，请生成一个假节点以将真实节点撞到一条线上.
Here's the code. I hope you're able to take what you need from it. There are definitely some Pythonisms which I hope map to what you're using. The main idea is to treat each row of numbers as a map of position to node object, and at each level, sort the map by key and print them to the console iteratively based on their assigned position. Then generate a new map with positions relative to their parents in the previous level. If there's a collision, generate a fake node to bump the real node down a line.
from collections import namedtuple
# simple node representation. sorry for the mess, but it does represent the
# tree example you gave.
Node = namedtuple('Node', ('label', 'left', 'right'))
def makenode(n, left=None, right=None):
return Node(str(n), left, right)
root = makenode(
15,
makenode(
3,
makenode(2, makenode(1, makenode(0))),
makenode(4, None, makenode(12, makenode(11), makenode(14)))),
makenode(16, None, makenode(19, makenode(17),
makenode(28, None, makenode(31)))))
# takes a dict of {line position: node} and returns a list of lines to print
def print_levels(print_items, lines=None):
if lines is None:
lines = []
if not print_items:
return lines
# working position - where we are in the line
pos = 0
# line of text containing node labels
new_nodes_line = []
# line of text containing slashes
new_slashes_line = []
# args for recursive call
next_items = {}
# sort dictionary by key and put them in a list of pairs of (position,
# node)
sorted_pos_and_node = [
(k, print_items[k]) for k in sorted(print_items.keys())]
for position, node in sorted_pos_and_node:
# add leading whitespace
while len(new_nodes_line) < position:
new_nodes_line.append(' ')
while len(new_slashes_line) < position:
new_slashes_line.append(' ')
# update working position
pos = position
# add node label to string, as separate characters so list length
# matches string length
new_nodes_line.extend(list(node.label))
# add left child if any
if node.left is not None:
# if we're close to overlapping another node, push that node down
# by adding a parent with label '|' which will make it look like a
# line dropping down
for collision in [pos - i for i in range(3)]:
if collision in next_items:
next_items[collision] = makenode(
'|', next_items[collision])
# add the slash and the node to the appropriate places
new_slashes_line.append('|')
next_items[position] = node.left
else:
new_slashes_line.append(' ')
# update working position
len_num = len(node.label)
pos += len_num
# add some more whitespace
while len(new_slashes_line) < position + len_num:
new_slashes_line.append(' ')
# and take care of the right child
if node.right is not None:
new_slashes_line.append('\\')
next_items[position + len_num + 1] = node.right
else:
new_slashes_line.append(' ')
# concatenate each line's components and append them to the list
lines.append(''.join(new_nodes_line))
lines.append(''.join(new_slashes_line))
# do it again!
return print_levels(next_items, lines)
lines = print_levels({0: root})
print '\n'.join(lines)
这篇关于用斜杠打印出二进制搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
