树的遍历和排序

python的树的遍历和堆排序:
二叉树的遍历：
遍历：迭代所有元素一遍
树的遍历：对树中所有元素不重复地访问一遍，也称作扫描

广度优先遍历：
层序遍历

深度优先遍历：
前序遍历
中序遍历
后序遍历

遍历序列：
将树中所有元素遍历一遍后，得到的元素的序列。将层次结构转换成了线性结构

层序遍历：
按照树的层次，从第一层开始，自左向右遍历元素

遍历序列：
ABCDEFGHI

二叉树的遍历：
深度优先遍历：
1、设树的根结点为D，左子树为L，右子树为R，且要求L一定在R之前，则有下面几种遍历方式

2、前序编列，也叫先序遍历，也叫先根遍历，DLR

3、中序遍历，也叫中根遍历，LDR

4、后序遍历，也叫后根遍历，LRD

前序遍历DLR：
1、从根结点开始，先左子树后右子树
2、每个子树内部依然是先根结点，再左子树后右子树，递归遍历
3、遍历序列：
A BDGH CEIF

中序遍历：LDR
1、从根结点的左子树开始遍历，然后是根结点，再右子树
2、每个子树内部，也是先左子树，后根结点，再右子树，递归遍历

遍历序列：
这个一定要分清楚是左子树还是右子树，因为中间遍历的时候会有差别

后序遍历LRD：
1、先左子树，后右子树，再根结点
2、每个子树内部依然是先左子树，后右子树，再根结点，递归遍历

遍历序列：GHDB IEFC

堆Heap:
1、堆是一个完全二叉树
2、每个非叶子结点都要大于或者等于其左右孩子结点的值称为大顶堆
3、每个非叶子结点都要小于或者等于其左右孩子结点的值称为小顶堆
4、根结点一定是大顶堆中的最大值，一定是小顶堆中的最小值

堆排序Heap Sort:
大顶堆：
1、完全二叉树的每个非叶子结点都要大于或者等于其左右孩子结点的值称为大顶堆
2、根结点一定是大顶堆中的最大值

小顶堆：
1、完全二叉树的每个非叶子结点都要小于或者等于其左右孩子结点的值称为小顶堆
2、根结点一定是小顶堆中的最小值

构建完全二叉树：
1、待排序数字为，30，20，80，40，50，10，60，70，90
2、构建一个完全二叉树存放数据，并根据性质5对元素编号，放入顺序的结构中
3、构建一个列表为[0,30,20,80,40,50,10,60,70,90]

构建大顶堆的核心算法：
1、度数为2的结点A，如果它的左右孩子结点的最大值比它大的，将这个最大值和该结点交换
2、度数为1的结点A，如果它的左孩子的值大于它，则交换
3、如果结点A被交换到新的位置，还需要和其孩子结点重复上面的过程

构建大顶堆–起点结点的选择：
1、完全二叉树的最后一个结点的双亲结点开始，即最后一层的最右边叶子结点的父结点开始

2、结点树为n,则起始结点的编号为n//2(性质5)

构建大顶堆–下一个结点的选择：
从起始结点开始向左找其同层结点，到头后再从上一层的最右边结点开始继续向左逐个查找，直至根结点

大顶堆的目标：
确保每个结点的都比左右(指的是孩子)结点的值大

排序：
1、将大顶堆根结点这个最大值和最后一个叶子结点交换，那么最后一个叶子结点就是最大值，将这个叶子结点排除在待排序结点之外
2、从根结点开始(新的根结点)，重新调整为大顶堆后，重复上一步

总结：
1、是利用堆性质的一种选择排序，在堆顶选出最大值或者最小值
2、时间复杂度
堆排序的时间复杂度为O(nlogn)
由于堆排序对原始记录的排序状态并不敏感，因此无论是最好、最坏和平均时间复杂度均为O(nlogn)
空间复杂度：
只是使用了一个交换用的空间，空间复杂度就是O(1)

稳定性：
不稳定的排序算法

#思路，第一行取一个，第二行取2个，第三行取3个，以此类推，投影来思考一个栅格系统
#代码实现

import math

#居中对齐方案
def print_tree(array,unit_width=2):
length = len(array) #9
depth = math.ceil(math.log2(length + 1)) #4

index = 0
width = 2**depth – 1 #行宽15
for i in range(depth): # 0 1 2 3
for j in range(2**i): #0:0 1:0,1 2:0,1,2,3 3:0~7
#居中打印，后面追加一个空格
print(‘{:^{}}’.format(array[index],width * unit_width),end=’ ‘*unit_width)
index += 1
if index >= length:
break
width = width // 2
print()
#测试
print_tree([x + 1 for x in range(29)])

import math

#投影格实现
def print_tree(array):
”’
前空格 元素间
1 7 0
2 3 7
3 1 3
4 0 1

”’
index = 1
depth = math.ceil(math.log2(len(array))) #因为补0了，不然应该是math.ceil(math.log2(len(array)+1))
sep = ‘ ‘
for i in range(depth):
offset = 2 ** i
print(sep * (2 ** (depth – i – 1) – 1),end=”)
line = array[index:index + offset]
for j, x in enumerate(line):
print(“{:>{}}”.format(x,len(sep),end=”))
interval = 0 if i == 0 else 2 ** (depth – i) – 1
if j < len(line) -1:
print(sep * interval,end=”)
index += offset
print()
print_tree([x +1 for x in range(100)])