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

yipeiwu_com6年前Python基础

本文实例讲述了Python实现基于二叉树存储结构的堆排序算法。分享给大家供大家参考,具体如下:

既然用Python实现了二叉树,当然要写点东西练练手。

网络上堆排序的教程很多,但是却几乎都是以数组存储的数,直接以下标访问元素,当然这样是完全没有问题的,实现简单,访问速度快,也容易理解。

但是以练手的角度来看,我还是写了一个二叉树存储结构的堆排序

其中最难的问题就是交换二叉树中两个节点。

因为一个节点最多与三个节点相连,那么两个节点互换,就需要考虑到5个节点之间的关系,也需要判断是左右孩子,这将是十分繁琐的,也很容易出错。

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("【听图阁-专注于Python设计】测试结果")
  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()

运行结果:

PS:这里再为大家推荐一款关于排序的演示工具供大家参考:

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:
http://tools.jb51.net/aideddesign/paixu_ys

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程

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

相关文章

Python编程产生非均匀随机数的几种方法代码分享

Python编程产生非均匀随机数的几种方法代码分享

1.反变换法 设需产生分布函数为F(x)的连续随机数X。若已有[0,1]区间均匀分布随机数R,则产生X的反变换公式为: F(x)=r, 即x=F-1(r) 反函数存在条件:如果函数y=f...

python+selenium select下拉选择框定位处理方法

一、前言 总结一下python+selenium select下拉选择框定位处理的两种方式,以备后续使用时查询; 二、直接定位(XPath) 使用Firebug找到需要定位到的元素,直接...

基于Python的身份证号码自动生成程序

基于Python的身份证号码自动生成程序

需求细化: 1.身份证必须能够通过身份证校验程序。 2.通过查询,发现身份证号码是有国家标准的,标准号为 GB 11643-1999 可以从百度下载到这个文档 下载:GB11643-19...

python实现获取序列中最小的几个元素

本文实例讲述了python实现获取序列中最小的几个元素。分享给大家供大家参考。 具体方法如下: import heapq import random def issorted(d...

使用Python编写一个模仿CPU工作的程序

今天早上早些时候,在我的Planet Python源中,我读到了一篇有趣的文章"开发CARDIAC:纸板计算机(Developing upwards: CARDIAC: The Card...