二叉樹的遍歷和堆排序

## 二叉樹的遍歷

### 廣度優先遍歷

層序遍歷 上到下 左到右 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)