樹的遍歷和排序

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)])