前言

打印二叉树是分析堆排序的最佳方式

假设有这样的棵树

                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|||||||||||
行号前导空格间隔
170
237
313
401

二叉树性质: 具具有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("")

            
最后修改:2020 年 07 月 10 日 06 : 00 PM
如果觉得我的文章对你有用,请随意赞赏