Python編程實(shí)現(xiàn)二叉樹及七種遍歷方法詳解
本文實(shí)例講述了Python實(shí)現(xiàn)二叉樹及遍歷方法。分享給大家供大家參考,具體如下:
介紹:
樹是數(shù)據(jù)結(jié)構(gòu)中非常重要的一種,主要的用途是用來提高查找效率,對(duì)于要重復(fù)查找的情況效果更佳,如二叉排序樹、FP-樹。另外可以用來提高編碼效率,如哈弗曼樹。
代碼:
用Python實(shí)現(xiàn)樹的構(gòu)造和幾種遍歷算法,雖然不難,不過還是把代碼作了一下整理總結(jié)。實(shí)現(xiàn)功能:
① 樹的構(gòu)造
② 遞歸實(shí)現(xiàn)先序遍歷、中序遍歷、后序遍歷
③ 堆棧實(shí)現(xiàn)先序遍歷、中序遍歷、后序遍歷
④ 隊(duì)列實(shí)現(xiàn)層次遍歷
#coding=utf-8 class Node(object): """節(jié)點(diǎn)類""" def __init__(self, elem=-1, lchild=None, rchild=None): self.elem = elem self.lchild = lchild self.rchild = rchild class Tree(object): """樹類""" def __init__(self): self.root = Node() self.myQueue = [] def add(self, elem): """為樹添加節(jié)點(diǎn)""" node = Node(elem) if self.root.elem == -1: # 如果樹是空的,則對(duì)根節(jié)點(diǎn)賦值 self.root = node self.myQueue.append(self.root) else: treeNode = self.myQueue[0] # 此結(jié)點(diǎn)的子樹還沒有齊。 if treeNode.lchild == None: treeNode.lchild = node self.myQueue.append(treeNode.lchild) else: treeNode.rchild = node self.myQueue.append(treeNode.rchild) self.myQueue.pop(0) # 如果該結(jié)點(diǎn)存在右子樹,將此結(jié)點(diǎn)丟棄。 def front_digui(self, root): """利用遞歸實(shí)現(xiàn)樹的先序遍歷""" if root == None: return print root.elem, self.front_digui(root.lchild) self.front_digui(root.rchild) def middle_digui(self, root): """利用遞歸實(shí)現(xiàn)樹的中序遍歷""" if root == None: return self.middle_digui(root.lchild) print root.elem, self.middle_digui(root.rchild) def later_digui(self, root): """利用遞歸實(shí)現(xiàn)樹的后序遍歷""" if root == None: return self.later_digui(root.lchild) self.later_digui(root.rchild) print root.elem, def front_stack(self, root): """利用堆棧實(shí)現(xiàn)樹的先序遍歷""" if root == None: return myStack = [] node = root while node or myStack: while node: #從根節(jié)點(diǎn)開始,一直找它的左子樹 print node.elem, myStack.append(node) node = node.lchild node = myStack.pop() #while結(jié)束表示當(dāng)前節(jié)點(diǎn)node為空,即前一個(gè)節(jié)點(diǎn)沒有左子樹了 node = node.rchild #開始查看它的右子樹 def middle_stack(self, root): """利用堆棧實(shí)現(xiàn)樹的中序遍歷""" if root == None: return myStack = [] node = root while node or myStack: while node: #從根節(jié)點(diǎn)開始,一直找它的左子樹 myStack.append(node) node = node.lchild node = myStack.pop() #while結(jié)束表示當(dāng)前節(jié)點(diǎn)node為空,即前一個(gè)節(jié)點(diǎn)沒有左子樹了 print node.elem, node = node.rchild #開始查看它的右子樹 def later_stack(self, root): """利用堆棧實(shí)現(xiàn)樹的后序遍歷""" if root == None: return myStack1 = [] myStack2 = [] node = root myStack1.append(node) while myStack1: #這個(gè)while循環(huán)的功能是找出后序遍歷的逆序,存在myStack2里面 node = myStack1.pop() if node.lchild: myStack1.append(node.lchild) if node.rchild: myStack1.append(node.rchild) myStack2.append(node) while myStack2: #將myStack2中的元素出棧,即為后序遍歷次序 print myStack2.pop().elem, def level_queue(self, root): """利用隊(duì)列實(shí)現(xiàn)樹的層次遍歷""" if root == None: return myQueue = [] node = root myQueue.append(node) while myQueue: node = myQueue.pop(0) print node.elem, if node.lchild != None: myQueue.append(node.lchild) if node.rchild != None: myQueue.append(node.rchild) if __name__ == '__main__': """主函數(shù)""" elems = range(10) #生成十個(gè)數(shù)據(jù)作為樹節(jié)點(diǎn) tree = Tree() #新建一個(gè)樹對(duì)象 for elem in elems: tree.add(elem) #逐個(gè)添加樹的節(jié)點(diǎn) print '隊(duì)列實(shí)現(xiàn)層次遍歷:' tree.level_queue(tree.root) print '\n\n遞歸實(shí)現(xiàn)先序遍歷:' tree.front_digui(tree.root) print '\n遞歸實(shí)現(xiàn)中序遍歷:' tree.middle_digui(tree.root) print '\n遞歸實(shí)現(xiàn)后序遍歷:' tree.later_digui(tree.root) print '\n\n堆棧實(shí)現(xiàn)先序遍歷:' tree.front_stack(tree.root) print '\n堆棧實(shí)現(xiàn)中序遍歷:' tree.middle_stack(tree.root) print '\n堆棧實(shí)現(xiàn)后序遍歷:' tree.later_stack(tree.root)
總結(jié):
樹的遍歷主要有兩種,一種是深度優(yōu)先遍歷,像前序、中序、后序;另一種是廣度優(yōu)先遍歷,像層次遍歷。在樹結(jié)構(gòu)中兩者的區(qū)別還不是非常明顯,但從樹擴(kuò)展到有向圖,到無向圖的時(shí)候,深度優(yōu)先搜索和廣度優(yōu)先搜索的效率和作用還是有很大不同的。
深度優(yōu)先一般用遞歸,廣度優(yōu)先一般用隊(duì)列。一般情況下能用遞歸實(shí)現(xiàn)的算法大部分也能用堆棧來實(shí)現(xiàn)。
我印象中是有遞歸構(gòu)造樹的方法,卻一直想不出該怎么構(gòu)造。后來仔細(xì)想了一下,遞歸思想有點(diǎn)類似深度優(yōu)先算法,而樹的構(gòu)造應(yīng)該是廣度優(yōu)先的。如果用遞歸的話一定要有個(gè)終止條件,例如規(guī)定樹深等。不然構(gòu)造出來的樹會(huì)偏向左單子樹或者右單子樹。所以一般樹的構(gòu)造還是應(yīng)該用隊(duì)列比較好。
以上說的不夠嚴(yán)謹(jǐn),有錯(cuò)誤之處,歡迎指正!
更多關(guān)于Python相關(guān)內(nèi)容可查看本站專題:《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python Socket編程技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》、《Python入門與進(jìn)階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
- python數(shù)據(jù)結(jié)構(gòu)之二叉樹的遍歷實(shí)例
- Python利用前序和中序遍歷結(jié)果重建二叉樹的方法
- python二叉樹遍歷的實(shí)現(xiàn)方法
- Python實(shí)現(xiàn)二叉樹結(jié)構(gòu)與進(jìn)行二叉樹遍歷的方法詳解
- python實(shí)現(xiàn)的二叉樹定義與遍歷算法實(shí)例
- Python實(shí)現(xiàn)輸入二叉樹的先序和中序遍歷,再輸出后序遍歷操作示例
- Python實(shí)現(xiàn)二叉樹的常見遍歷操作總結(jié)【7種方法】
- Python實(shí)現(xiàn)二叉樹前序、中序、后序及層次遍歷示例代碼
- python先序遍歷二叉樹問題
- python創(chuàng)建與遍歷二叉樹的方法實(shí)例
相關(guān)文章
Python實(shí)現(xiàn)telnet服務(wù)器的方法
這篇文章主要介紹了Python實(shí)現(xiàn)telnet服務(wù)器的方法,涉及Python通過Telnet連接服務(wù)器的相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-07-07python爬取盤搜的有效鏈接實(shí)現(xiàn)代碼
這篇文章主要介紹了python爬取盤搜的有效鏈接,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),具有一定的參考借鑒價(jià)值 ,需要的朋友可以參考下2019-07-07Python wxpython模塊響應(yīng)鼠標(biāo)拖動(dòng)事件操作示例
這篇文章主要介紹了Python wxpython模塊響應(yīng)鼠標(biāo)拖動(dòng)事件操作,結(jié)合實(shí)例形式分析了Python使用wxpython模塊創(chuàng)建窗口、綁定事件及相應(yīng)鼠標(biāo)事件相關(guān)操作技巧,需要的朋友可以參考下2018-08-08python 虛擬環(huán)境的創(chuàng)建與使用方法
本文先介紹虛擬環(huán)境的基礎(chǔ)知識(shí)以及使用方法,然后再深入介紹虛擬環(huán)境背后的工作原理,需要的朋友可以參考下2021-06-06PyTorch實(shí)現(xiàn)ResNet50、ResNet101和ResNet152示例
今天小編就為大家分享一篇PyTorch實(shí)現(xiàn)ResNet50、ResNet101和ResNet152示例,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-01-01怎么處理Python分割字符串時(shí)有多個(gè)分隔符
在使用Python處理字符串的時(shí)候,有時(shí)候會(huì)需要分割字符。本文就介紹了Python分割字符串時(shí)有多個(gè)分隔符,感興趣的可以了解一下2021-07-07