本文實例講述了Python實現(xiàn)基于二叉樹存儲結構的堆排序算法。分享給大家供大家參考，具體如下：
既然用Python實現(xiàn)了二叉樹，當然要寫點東西練練手。
網絡上堆排序的教程很多，但是卻幾乎都是以數組存儲的數，直接以下標訪問元素，當然這樣是完全沒有問題的，實現(xiàn)簡單，訪問速度快，也容易理解。
但是以練手的角度來看，我還是寫了一個二叉樹存儲結構的堆排序
其中最難的問題就是交換二叉樹中兩個節(jié)點。
因為一個節(jié)點最多與三個節(jié)點相連，那么兩個節(jié)點互換，就需要考慮到5個節(jié)點之間的關系，也需要判斷是左右孩子，這將是十分繁瑣的，也很容易出錯。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
|
class Tree: def __init__(self, val = '#', left = None, right = None): self.val = val self.left = left self.right = right self.ponit = None self.father = None self.counter = 0 #前序構建二叉樹 def FrontBuildTree(self): temp = input('Please Input: ') node = Tree(temp) if(temp != '#'): node.left = self.FrontBuildTree() node.right = self.FrontBuildTree() return node#因為沒有引用也沒有指針，所以就把新的節(jié)點給返回回去 #前序遍歷二叉樹 def VisitNode(self): print(self.val) if(self.left != None): self.left.VisitNode() if(self.right != None): self.right.VisitNode() #中序遍歷二叉樹 def MVisitTree(self): if(self.left != None): self.left.MVisitTree() print(self.val) if(self.right != None): self.right.MVisitTree() #獲取二叉樹的第dec個節(jié)點 def GetPoint(self, dec): road = str(bin(dec))[3:] p = self for r in road: if (r == '0'): p = p.left else: p = p.right #print('p.val = ', p.val) return p #構建第一個堆 def BuildHeadTree(self, List): for val in List: #print('val = ', val, 'self.counter = ', self.counter) self.ponit = self.GetPoint(int((self.counter + 1) / 2)) #print('self.ponit.val = ', self.ponit.val) if (self.counter == 0): self.val = val self.father = self else: temp = self.counter + 1 node = Tree(val) node.father = self.ponit if(temp % 2 == 0):#新增節(jié)點為左孩子 self.ponit.left = node else: self.ponit.right = node while(temp != 0): if (node.val < node.father.val):#如果新增節(jié)點比其父親節(jié)點值要大 p = node.father#先將其三個鏈子保存起來 LeftTemp = node.left RightTemp = node.right if (p.father != p):#判斷其不是頭結點 if (int(temp / 2) % 2 == 0):#新增節(jié)點的父親為左孩子 p.father.left = node else: p.father.right = node node.father = p.father else: node.father = node#是頭結點則將其father連向自身 node.counter = self.counter self = node if(temp % 2 == 0):#新增節(jié)點為左孩子 node.left = p node.right = p.right if (p.right != None): p.right.father = node else: node.left = p.left node.right = p if (p.left != None): p.left.father = node p.left = LeftTemp p.right = RightTemp p.father = node temp = int(temp / 2) #print('node.val = ', node.val, 'node.father.val = ', node.father.val) #print('Tree = ') #self.VisitNode() else: break; self.counter += 1 return self #將頭結點取出后重新調整堆 def Adjust(self): #print('FrontSelfTree = ') #self.VisitNode() #print('MSelfTree = ') #self.MVisitTree() print('Get ', self.val) p = self.GetPoint(self.counter) #print('p.val = ', p.val) #print('p.father.val = ', p.father.val) root = p if (self.counter % 2 == 0): p.father.left = None else: p.father.right = None #print('self.left = ', self.left.val) #print('self.right = ', self.right.val) p.father = p#將二叉樹最后一個葉子節(jié)點移到頭結點 p.left = self.left p.right = self.right while(1):#優(yōu)化是萬惡之源 LeftTemp = p.left RightTemp = p.right FatherTemp = p.father if (p.left != None and p.right !=None):#判斷此時正在處理的結點的左后孩子情況 if (p.left.val < p.right.val): next = p.left else: next = p.right if (p.val < next.val): break; elif (p.left == None and p.right != None and p.val > p.right.val): next = p.right elif (p.right == None and p.left != None and p.val > p.left.val): next = p.left else: break; p.left = next.left p.right = next.right p.father = next if (next.left != None):#之后就是一系列的交換節(jié)點的鏈的處理 next.left.father = p if (next.right != None): next.right.father = p if (FatherTemp == p): next.father = next root = next else: next.father == FatherTemp if (FatherTemp.left == p): FatherTemp.left = next else: FatherTemp.right = next if (next == LeftTemp): next.right = RightTemp next.left = p if (RightTemp != None): RightTemp.father = next else: next.left = LeftTemp next.right = p if (LeftTemp != None): LeftTemp.father = next #print('Tree = ') #root.VisitNode() root.counter = self.counter - 1 return rootif __name__ == '__main__': print("服務器之家測試結果") root = Tree() number = [-1, -1, 0, 0, 0, 12, 22, 3, 5, 4, 3, 1, 6, 9] root = root.BuildHeadTree(number) while(root.counter != 0): root = root.Adjust() |
運行結果：
希望本文所述對大家Python程序設計有所幫助。
原文鏈接：http://blog.csdn.net/yk_ee/article/details/64121486
