横向打印二叉树
https://www.luogu.com.cn/problem/P8603
构造树的过程不难，比较烦人的是如何把这棵树横着打印出来
...|-12
10-|
...|-8-|
.......|...|-7
.......|-5-|
...........|-4
首先可以发现，打印的顺序是中序遍历，打印的过程可以在中序遍历的基础上修改
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class Tree:
def __init__(self, arr):
self.root = TreeNode(None)
for num in arr:
self.insert(num)
self.middle_order()
def insert(self, value):
cur_node = self.root
while cur_node.value is not None:
cur_node = cur_node.left if value < cur_node.value else cur_node.right
cur_node.value = value
cur_node.left = TreeNode(None)
cur_node.right = TreeNode(None)
def middle_order(self, node=None, per_print='', location=''):
"""
:param node:
:param per_print:
:param location: a string represent location of the node, '0' represent left and '1' represent right
:return:
"""
new_per_print = list(per_print)
indexes = [i for i, c in enumerate(new_per_print) if c == '|'] # all indexes of '|'
for i in range(len(location) - 1):
if location[i] == location[i + 1]:
new_per_print[indexes[i]] = '.'
new_per_print = ''.join(new_per_print)
if node is None:
node = self.root
to_print = str(node.value) + '-|'
elif node.left.value is None and node.right.value is None:
to_print = '-' + str(node.value)
print(new_per_print + to_print)
return
else:
to_print = '-' + str(node.value) + '-|'
s_len = len(to_print) - 1
if node.right.value is not None:
self.middle_order(node.right, per_print=per_print + '.' * s_len + '|', location=location + '1')
print(new_per_print + to_print)
if node.left.value is not None:
self.middle_order(node.left, per_print=per_print + '.' * s_len + '|', location=location + '0')
nums = [int(_) for _ in input().split()]
t = Tree(nums)