本文實例講述了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 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()