本文实例讲述了Python实现基于二叉树存储结构的堆排序算法。分享给大家供大家参考，具体如下：
既然用Python实现了二叉树，当然要写点东西练练手。
网络上堆排序的教程很多，但是却几乎都是以数组存储的数，直接以下标访问元素，当然这样是完全没有问题的，实现简单，访问速度快，也容易理解。
但是以练手的角度来看，我还是写了一个二叉树存储结构的堆排序
其中最难的问题就是交换二叉树中两个节点。
因为一个节点最多与三个节点相连，那么两个节点互换，就需要考虑到5个节点之间的关系，也需要判断是左右孩子，这将是十分繁琐的，也很容易出错。
|
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#因为没有引用也没有指针，所以就把新的节点给返回回去 #前序遍历二叉树 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个节点 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):#新增节点为左孩子 self.ponit.left = node else: self.ponit.right = node while(temp != 0): if (node.val < node.father.val):#如果新增节点比其父亲节点值要大 p = node.father#先将其三个链子保存起来 LeftTemp = node.left RightTemp = node.right if (p.father != p):#判断其不是头结点 if (int(temp / 2) % 2 == 0):#新增节点的父亲为左孩子 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):#新增节点为左孩子 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#将二叉树最后一个叶子节点移到头结点 p.left = self.left p.right = self.right while(1):#优化是万恶之源 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):#之后就是一系列的交换节点的链的处理 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
