23.4-二叉树的遍历-堆排序及算法实现
无论走到哪里，都应该记住，过去都是假的，回忆是一条没有尽头的路，一切以往的春天都不复存在，就连那最坚韧而又狂乱的爱情归根结底也不过是一种转瞬即逝的现实。 - - - - - - - - - - - - 马尔克斯 《百年孤独》
自 树和二叉树的遍历原理：
总结：
- 凡是跟树相关的都是跟它的二叉树的对数相关；
- 树 可以大大提高我们的效率，堆排序的时间复杂度为O(n)；
第一种理解
遍历:顾名思义就是将所有的元素浏览一遍；
对于线性表来说遍历很简单，没有什么复杂的规则，沿着一条直线依次浏览即可。
但是对于二叉树来说，就不仅仅只有这一种方式了
1.层次遍历（广度优先遍历）
二叉树的人层次遍历很简单，层次这个词就说明了重点，也就是每层遍历完，再进行下一层，即从左往右，从上往下。
2.深度优先遍历
深度优先遍历分为： 先序、中序、后序；
由于每一个二叉树结点结构体包含三部分，第一数据，还有两个指向孩子结点的指针，可以为空，也就是说每个结点都有两个指针，这里将整个完整的二叉树图画出来，便于更好地理解。
这是一个完整的遍历示意图，每一个结点具有三个进出方向对，当所有的进出对都走完后，遍历结束，还有注意的是所有的遍历都是在这张图的基础上，只不过规则不同。
每一个结点三进三出，这也就是遍历的规则核心所在，还有就是将一个周角分为三个120度的小角，也就对应了三个规则。
对于叶子结点，仍然满足，因为可以将两个孩子结点的指针以空表示。
如果第二次来到某结点时访问，将会是以上的顺序，也就是三个120度角的第二个。
如果第三次来到某结点时访问，将会是以上的另一种顺序，也就是来到第三个120角时访问。
第二种理解
第二种理解，核心思想如上，两种理解方式结果相同，只是理解方向不同。
一般树的深度优先遍历，由于树的分支数不定，所以中序是一种不确定的状态，所以区别在于 研究树的先序和后序
如果第一次来到某结点就访问即为先序，最后一次来到即为后序；
堆排序 Heap Sort
堆 Heap
堆是具有以下性质的完全二叉树（尽左边放）：
- 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
- 或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
- 跟结点一定是大顶堆中的最大值，一定是小顶堆中的最小值；
大顶堆与小顶堆
用简单的公式来描述一下堆的定义就是：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
堆排序的基本思想
将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
# Heap Sort
import math
# 构建二叉树
def print_tree(array, unit_width=2):
'''
i 前空格 元素间
3 7
2 3
1 1
0 0
'''
length = len(array)
index = 1
depth = math.ceil(math.log2(length)) #4
sep = ' '*unit_width
for i in range(depth-1,-1,-1):
pre = 2**i - 1
print(sep*pre,end='')
offset = 2 ** (depth - i - 1)
line = array[index: index+offset]
intervalspace = sep * (2*pre + 1)
print(intervalspace.join(map(str,line)))
index += offset
def heap_adjust(n,i,array:list):
'''
调整当前结点(核心算法)
调整的结点的起点在n//2，保证所有调整的结点都有孩子结点
:param n: 待比较数个数
:param i: 当前结点的下标
:param array: 待排序数据
:return: None
'''
while 2 * i <= n:
# 孩子结点判断 2i为左孩子，2i+1为右孩子
lchile_index = 2 * i
# 先假定左孩子大，如果存在右孩子且大则最大孩子索引就是右孩子
max_child_index = lchile_index # n=2i
if n > lchile_index and array[lchile_index + 1] > array[lchile_index]: # n>2i说明还有右孩子
max_child_index = lchile_index + 1 # n=2i+1
# 和子树的根结点比较
if array[max_child_index] > array[i]:
array[i], array[max_child_index] = array[max_child_index], array[i]
i = max_child_index # 被交换后，需要判断是否还需要调整
else:
break
#print_tree(array)
# 2.构建大顶堆，大根堆
def max_heap(total,array:list):
for i in range(total//2,0,-1):
heap_adjust(total,i,array)
return array
# print_tree(max_heap(total,origin))
heap_adjust(total, total// 2, origin)
print('convert raw_list to tree:')
origin = [0,30,20,80,40,50,10,60,70,90]
total = len(origin) -1
print(origin)
print_tree(origin)
print('-'*30)
print(print_tree(max_heap(total,origin)))
# 排序
def sort(total, array:list):
while total > 1:
array[1], array[total] = array[total], array[1] # 堆顶和最后一个结点交换
total -= 1
if total == 2 and array[total] >= array[total-1]:
break
heap_adjust(total,1,array)
return array
print_tree(sort(total,origin))
print(origin)
#------------------------------------------------
convert raw_list to tree:
[0, 30, 20, 80, 40, 50, 10, 60, 70, 90]
30
20 80
40 50 10 60
70 90
------------------------------
90
70 80
40 50 10 60
20 30
None
10
20 30
40 50 60 70
80 90
[0, 10, 20, 30, 40, 50, 60, 70, 80, 90]
#构造二叉树；
# 思路1：倒叙打印间隔 前面补写一个0，
array = [0,30,20,80,40,50,10,60,70,90]
length = len(array)
index = 1
unit_width = 2
sep = ' '*unit_width
depth = math.ceil(math.log2(length)) # 4层
for i in range(depth-1,-1,-1):
pre = 2**i-1
print(sep*pre,end='') # 前置空格；
offset = 2**(depth-i-1)
line = array[index:index+offset] # 取数字；
#print(line)
intervalspace = sep * (2*pre +1)
print(intervalspace.join(map(str,line)))
index += offset
#------------------------------------------------------
30
20 80
40 50 10 60
70 90
# 思路2：格式化字符串写法；
import math
def print_trees(array,unit_width=2):
length = len(array)
depth = math.ceil(math.log2(length+1))
index = 0
width = 2**depth -1 # 行宽度，最深的行15个数
for i in range(depth): # 0123
for j in range(2**i): # 计数
# 居中打印，后面追加一个空格
print('{:^{}}'.format(array[index],width*unit_width),end = ' '*unit_width)
index += 1
if index >= length:
break
width = width//2 # 居中打印宽度减半
print() #控制换行；
print_trees([x+1 for x in range(29)])
