Python實現(xiàn)基于二叉樹存儲結構的堆排序算法示例
更新時間：2017年12月08日 11:52:26 作者：yk_ee
這篇文章主要介紹了Python實現(xiàn)基于二叉樹存儲結構的堆排序算法,結合實例形式分析了Python二叉樹的定義、遍歷及堆排序算法相關實現(xiàn)技巧,需要的朋友可以參考下
本文實例講述了Python實現(xiàn)基于二叉樹存儲結構的堆排序算法。分享給大家供大家參考，具體如下：
既然用Python實現(xiàn)了二叉樹，當然要寫點東西練練手。
網絡上堆排序的教程很多，但是卻幾乎都是以數(shù)組存儲的數(shù)，直接以下標訪問元素，當然這樣是完全沒有問題的，實現(xiàn)簡單，訪問速度快，也容易理解。
但是以練手的角度來看，我還是寫了一個二叉樹存儲結構的堆排序
其中最難的問題就是交換二叉樹中兩個節(jié)點。
因為一個節(jié)點最多與三個節(jié)點相連，那么兩個節(jié)點互換，就需要考慮到5個節(jié)點之間的關系，也需要判斷是左右孩子，這將是十分繁瑣的，也很容易出錯。
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 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()
運行結果：
PS：這里再為大家推薦一款關于排序的演示工具供大家參考：
在線動畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：
http://tools.jb51.net/aideddesign/paixu_ys
更多關于Python相關內容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結構與算法教程》、《Python加密解密算法與技巧總結》、《Python編碼操作技巧總結》、《Python函數(shù)使用技巧總結》、《Python字符串操作技巧匯總》及《Python入門與進階經典教程》
希望本文所述對大家Python程序設計有所幫助。
您可能感興趣的文章:
相關文章
RANSAC是一種用于從包含異常數(shù)據(jù)的樣本數(shù)據(jù)集中計算數(shù)學模型參數(shù)的算法,本文主要介紹了python中ransac算法擬合圓的實現(xiàn),具有一定的參考價值,感興趣的可以了解一下2025-01-01
這篇文章主要介紹了使用OpenCV實現(xiàn)仿射變換—縮放功能，非常不錯，具有一定的參考借鑒價值,需要的朋友可以參考下2019-08-08
在python中利用numpy求解多項式以及多項式擬合的方法
今天小編就為大家分享一篇在python中利用numpy求解多項式以及多項式擬合的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-07-07
今天教各位小伙伴怎么用Python連接oracle,文中附帶非常詳細的圖文示例,對正在學習的小伙伴們很有幫助喲,需要的朋友可以參考下2021-05-05
python基于paramiko庫遠程執(zhí)行 SSH 命令,實現(xiàn) sftp 下載文件
這篇文章主要介紹了python基于paramiko庫遠程執(zhí)行 SSH 命令,實現(xiàn) sftp 下載文件的方法，幫助大家更好的理解和學習使用python，感興趣的朋友可以了解下2021-03-03
Python Paramiko創(chuàng)建文件目錄并上傳文件詳解
Paramiko是一個用于進行SSH2會話的Python庫,它支持加密、認證和文件傳輸?shù)裙δ?本文旨在詳細指導新手朋友如何使用Python的Paramiko庫來創(chuàng)建遠程文件目錄并上傳文件,希望對大家有所幫助2024-10-10
這篇文章主要介紹了在終端啟動Python時報錯的解決方案，幫助大家更好的理解和使用python，感興趣的朋友可以了解下2020-11-11
本篇文章主要介紹了python3讀取MySQL-Front的MYSQL密碼的相關知識，具有很好的參考價值。下面跟著小編一起來看下吧2017-05-05
這篇文章主要介紹了pygame可視化幸運大轉盤實現(xiàn),文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-04-04
這篇文章主要為大家詳細匯總了一些常用的Python爬蟲技巧,具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-09-09