二叉树的遍历和堆排序

## 二叉树的遍历

### 广度优先遍历

层序遍历 上到下 左到右 ABCDEFG

### 深度优先遍历

一探到底 根D 左子树L 右子树R
前序遍历 先根遍历 根 左 右 DLR
中序遍历 中根遍历 左 根 右 LDR
后序遍历 后根遍历 左 右 根 LRD

### 遍历序列

## 堆排序Heap Sort

大顶堆
小顶堆

构建完全二叉树

性质5：编号即索引

构建大顶堆
结点的度：叶子度为0，树的度是结点最大的度。

从最后一个叶子的父结点开始 n//2

import math

#居中对齐方案

def print_tree(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):
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_tree([x+1 for x in range(9) ])

#投影栅格实现
def print_tree(array):
index = 1
depth = math.ceil(math.log2(len(array)))
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([0, 1, 2, 4, 10, 20, 32, 40, 600])

origin = [0, 30, 20, 80, 40, 50, 10, 60, 70, 90]

total = len(origin) – 1
# print(origin)
# print_tree(origin)
print(“=”*50)

def heap_adjust(n, i, array: list):
”’
调整当前节点（核心算法）

调整的结点的起点在n // 2, 保证所有调整的结点都有孩子结点
:param n: 待比较数个数
:param i: 当前结点的下标
:param array: 待排序数据
:return: None
”’

while 2 * i <= n:
#孩子结点判断 2i为左孩子 2i + 1为右孩子
lchild_index = 2 * i
max_child_index = lchild_index
if n > lchild_index and array[lchild_index + 1] > array[lchild_index]:# n > 2i 说明还有右孩子
max_child_index = lchild_index + 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)

heap_adjust(total, total // 2, origin)
print(origin)
# print_tree(origin)

#构建大顶堆、大根堆
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))

#排序
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)