服务器之家

服务器之家 > 正文

Python实现基于二叉树存储结构的堆排序算法示例

时间:2020-12-23 00:21     来源/作者:yk_ee

本文实例讲述了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 root
if __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实现基于二叉树存储结构的堆排序算法示例

希望本文所述对大家Python程序设计有所帮助。

原文链接:http://blog.csdn.net/yk_ee/article/details/64121486

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址 2020-08-12
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
返回顶部