前言
打印二叉树是分析堆排序的最佳方式
假设有这样的棵树
30
20 80
40 50 10 60
70 90
我们把它看成这个样子
|||||||1
|||1|||||||2
|4|||5|||6|||7
8|9|||||||||||
############## 可知道一共需要多少占位符号
分析
|||||||1
|||1|||||||2
|4|||5|||6|||7
8|9|||||||||||
行号 | 前导空格 | 间隔 |
---|---|---|
1 | 7 | 0 |
2 | 3 | 7 |
3 | 1 | 3 |
4 | 0 | 1 |
二叉树性质: 具具有n个节点的 完全二叉树 的深度为int(log_2n)+1 或者 math.ceil(log_2(n+1)) # log_2 对数的意思
python中int是向下取整,math.ceil是向上取整
得出前导空格公式
深度:k
层序: n
前导空格: s
s = 2^(k-n) - 1
得出间隔:
间隔: i
第一行间隔一定为 0
第二行到第m行有:
i = 2^(k-n-1) - 1
实现流程
第一步
打印前导空格
第二步
打印单个数据
打印间隔
打印当个数据
...
实现代码
import math
origin = [0, 30, 20, 80, 40, 50, 10, 60, 70, 90]
def print_tree(array: list) -> None:
index = 1
# 因为补了0所以从1开始
sep = ' '
# 占位符
depth = math.ceil(math.log2(len(array)))
# 根据性质 math.ceil(log_2(n+1))
# 由于我们这人补了0 所以不要加了
for i in range(depth):
# 大循环按每层循环
offset = 2 ** i
# 第一层 [1:2] - > [index: index+offset] offset=1 -> index = 2
# 第二层 [2:4] - > [index: index+offset] offset=2 -> index = 4
# 第三层 [4:8]
# 偏移量每层的偏移量
line = array[index: index+offset]
print(sep * (2**(depth-i-1)-1), end='')
# s = 2^(k-n) - 1 打印前导空格
for k, v in enumerate(line):
print("{:^{}}".format(v, len(sep)), end='')
# 按sep的长度居中打印数据
if k == (len(line)-1) or i == 0:
break
# 如果已经是最后一个值或者层序为0就直接跳出
interval = 2 ** (depth-i) - 1
# i = 2^(k-n-1) - 1
print(sep*interval, end='')
# 打印间隔
index += offset
print("")