摘要：
#遍历二叉树#不要重复访问二叉树中的所有元素#广度优先遍历#顺序遍历#从第一层开始，每个层从左到右遍历元素#深度优先遍历#假设树的根节点是D，左子树是L，右子树是R，并且L必须在R之前，然后有以下遍历方法：#优先遍历：也称为优先遍历，也称为根优先遍历，DLR#中间顺序遍历：也称中间根遍历，LDR#后续遍历：也称后续根遍历，LRD#遍历序列：遍历树中所有元素一次后获得的元素序列，将层次结构转换为直线
# 二叉树的遍历
# 对二叉树中的所有元素不重复的访问一遍
# 广度优先遍历
# 层序遍历
# 从第一层开始，没一层从左至右遍历元素
# 深度优先遍历
# 假设树的根节点为D，左子树为L，右子树为R，且要求L一定在R之前，则有以下遍历方式：
# 前序遍历：也叫先序遍历，也叫先根遍历，DLR
# 中序遍历：也叫中根遍历，LDR
# 后序遍历：也叫后根遍历，LRD
# 遍历序列：将树中所有元素遍历一遍后，得到的元素的序列，将层次结构转换成了线性结构
# 堆排序
# 堆是一个完全二叉树
# 每个非叶子结点的值都要大于或者等于其左右孩子结点的值，称为大顶堆
# 每个非叶子结点的值都要小于或者等于其左右孩子结点的值，称为小顶堆
# 根结点一定是大顶堆中的最大值，一定是小顶堆中的最小值
# 例子：构建一个完全二叉树（序列 -> 完全二叉树 -> 大顶堆 -> 排序 - > 大顶堆 -> 排序 ...）
# 待排序数字为：30 20 80 40 50 10 60 70 90
# 构建一个完全二叉树存放数据，并根据性质5对元素编号，放入顺序的数据结构中
# 性质5：按层依次编号
# 构建一个列表为[0, 30, 20, 80, 40, 50, 10, 60, 70, 90]***
# 0为补位，因为列表下表从0开始，想从1开始进行使用
# 构建大顶堆的核心算法
# 度数为2的结点A，如果它的左右孩子结点的最大值比它大，将这个最大值和该结点交换
# 度数为1的结点A，如果它的左孩子的值比它大，则交换
# 如果结点A被交换到新的位置，还需要和其孩子结点重复上面的过程
# 构建大顶堆 - 起点结点的选择
# 从完全二叉树的最后一个结点的双亲结点开始，即最后一层的最右边叶子结点的父节点开始***
# 结点数为n，则起始结点的编号n//2(性质5)
# 构建大顶堆 - 下一个结点的选择
# 从起始结点开始向左找其同层结点，到头后再从上一层的最右边结点开始继续向左逐个查找，直到根节点
# 下一结点：n -> n-1 -> n-2 ... 1
# 跟结点计算完毕后，如果有交换，则还需要向下对左右子树进行再次排序
# 大顶堆的目标
# 确保每个结点的值都比左右结点的值大
# 排序
# 将大顶堆根结点这个最大值和最后一个叶子结点交换，那么最后一个叶子结点就是最大值，将这个叶子结点排除在待排序结点外
# 从根结点开始（新的根结点），重新调整为大顶堆后，重复上一步
# 将列表打印成树（堆排序辅助函数）
import math
def printTree(lst):
treeLen = len(lst)
treeLay = math.ceil(math.log2(treeLen + 1)) # 树层数
index = 0
treeWidth = 2 ** treeLay - 1 # 树宽度
for i in range(treeLay):
for j in range(2**i):
print('{:^{}}'.format(lst[index], treeWidth), end=' ')
index += 1
if index >= treeLen:
break
treeWidth = treeWidth//2
print()
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9]
printTree(lst)
# 调整当前节点
def heap_adjust(n, i, array:list): # array:list 表示array变量的类型是list
'''
调整当前节点核心算放
:param n: 待比较数字的个数
:param i: 当前节点的下标
:param array: 待排序数据
:return:None
'''
while 2 * i <= n: # 性质5，=n只有左子树
# 孩子结点判断2i为左孩子，2i+1为右孩子
lChild_index = 2 * i
maxChild_index = lChild_index # n=2i
if n > lChild_index and array[lChild_index + 1] > array[lChild_index]: # n>2i说明还有右孩子
maxChild_index = lChild_index + 1 # n=2i+1
# 和子树的根节点比较
if array[maxChild_index] > array[i]:
array[i], array[maxChild_index] = array[maxChild_index], array[i] # 交换
i = maxChild_index # 被交换后，需要判断是否还需要调整
else:
break
printTree(array)
print('--------------------------')
# 构建大顶堆
def maxHeap(total, array:list):
for i in range(total//2, 0, -1):
heap_adjust(total, i, array) # 调整当前结点
return array
total = 9
origin = [0,30, 20, 80, 40, 50, 10, 60, 70, 90]
print('maxHeap is ')
printTree(maxHeap(total, origin))
# 结论：第一层是最大值，第二层一定有个次大值