二叉树打印

二叉树打印

BeiJiXS

2020 年 07 月 10 日

856 次浏览

暂无评论

2049字数

Python

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

假设有这样的棵树

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 对数的意思

</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("")

最后修改：2020 年 07 月 10 日