Loading... ## 前言 打印二叉树是分析堆排序的最佳方式 假设有这样的棵树 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| <div class="tip inlineBlock info"> 二叉树性质: 具具有n个节点的 完全二叉树 的深度为int(log_2n)+1 或者 math.ceil(log_2(n+1)) # log_2 对数的意思 </div> <div class="tip inlineBlock warning"> python中int是向下取整，math.ceil是向上取整 </div> 得出前导空格公式 深度：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("") Last modification：July 10th, 2020 at 06:00 pm © 允许规范转载 Support If you think my article is useful to you, please feel free to appreciate ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
