Python數(shù)據(jù)結(jié)構(gòu)與算法之二叉樹結(jié)構(gòu)定義與遍歷方法詳解
本文實(shí)例講述了Python數(shù)據(jù)結(jié)構(gòu)與算法之二叉樹結(jié)構(gòu)定義與遍歷方法。分享給大家供大家參考,具體如下:
先序遍歷,中序遍歷,后序遍歷 ,區(qū)別在于三條核心語句的位置
層序遍歷 采用隊(duì)列的遍歷操作第一次訪問根,在訪問根的左孩子,接著訪問根的有孩子,然后下一層 自左向右一一訪問同層的結(jié)點(diǎn)
# 先序遍歷 # 訪問結(jié)點(diǎn),遍歷左子樹,如果左子樹為空,則遍歷右子樹, # 如果右子樹為空,則向上走到一個(gè)可以向右走的結(jié)點(diǎn),繼續(xù)該過程 preorder(t): if t: print t.value preorder t.L preorder t.R # 中序遍歷 # 從根開始,一直走向左下方,直到無結(jié)點(diǎn)可以走則停下,訪問該節(jié)點(diǎn) # 然后走向右下方到結(jié)點(diǎn),繼續(xù)走向左下方:如果結(jié)點(diǎn)無右孩子,則向上走回父親結(jié)點(diǎn) inorder(t): inorder(t.L) print t.value inorder(t.R) # 后序遍歷 inorder(t): inorder(t.L) inorder(t.R) print t.value # 二叉樹結(jié)點(diǎn)類型 class BTNode: def __init__(self,value,lft=None,rgt=None): self.value = value self.lft = lft # 結(jié)點(diǎn)左分支 BTNode self.rgt = rgt # 結(jié)點(diǎn)右分支 BTNode
為了方便起見,定義一些打印操作
class BinTree(): def __init__(self): self.root = None # 創(chuàng)建一個(gè)空的二叉樹 def isEmpty(self): # 判斷二叉樹是否為空 if self.root is None: return True else: return False def makeBT(self,bt,L=None,R=None): # 從當(dāng)前結(jié)點(diǎn)創(chuàng)建二叉樹 bt.lft = L bt.rgt = R def returnBTdict(self): # 返回二叉樹的字典模式 if self.isEmpty(): return None def rec(bt=None,R=True): if R==True: bt = self.root return {'root':{'value':bt.value,"L":rec(bt.lft,False), "R":rec(bt.rgt,False)} } else: if bt==None: return None else: return {"value":bt.value, "L":rec(bt.lft,False) if bt.lft != None else None, "R":rec(bt.rgt,False) if bt.rgt != None else None} return None return rec() def __repr__(self): # 將二叉樹結(jié)構(gòu)打印為字典結(jié)構(gòu) return str(self.returnBTdict())
下面是各種遍歷方法,添加到樹的類中
def printT_VLR(self,bt=None,rec_count = 0): # 輸出二叉樹結(jié)構(gòu)(先序遍歷) # rec_count 用于計(jì)算遞歸深度 以便輸出最后的換行符 """ # 先序遍歷 # 訪問結(jié)點(diǎn),遍歷左子樹,如果左子樹為空,則遍歷右子樹, # 如果右子樹為空,則向上走到一個(gè)可以向右走的結(jié)點(diǎn),繼續(xù)該過程 preorder(t): if t: print t.value preorder t.L preorder t.R """ if bt==None: bt = self.root print bt.value, btL, btR = bt.lft, bt.rgt if btL != None: print btL.value,; rec_count += 1; self.printT_VLR(btL,rec_count); rec_count -= 1 if btR != None: print btR.value,; rec_count += 1; self.printT_VLR(btR,rec_count); rec_count -= 1 if rec_count == 0: print "\n" def printT_LVR(self,bt=None): """ # 中序遍歷 # 從根開始,一直走向左下方,直到無結(jié)點(diǎn)可以走則停下,訪問該節(jié)點(diǎn) # 然后走向右下方到結(jié)點(diǎn),繼續(xù)走向左下方:如果結(jié)點(diǎn)無右孩子,則向上走回父親結(jié)點(diǎn) inorder(t): inorder(t.L) print t.value inorder(t.R) """ if bt==None: bt = self.root btL, btR = bt.lft, bt.rgt if btL != None: self.printT_LVR(btL) print bt.value, if btR != None: self.printT_LVR(btR) def printT_LRV(self,bt=None): """ # 后序遍歷 inorder(t): inorder(t.L) inorder(t.R) print t.value """ if bt==None: bt = self.root btL, btR = bt.lft, bt.rgt if btL != None: self.printT_LRV(btL) if btR != None: self.printT_LRV(btR) print bt.value, def printT_levelorder(self): """ 層序遍歷 采用隊(duì)列的遍歷操作 第一次訪問根,在訪問根的左孩子,接著訪問根的有孩子,然后下一層 自左向右一一訪問同層的結(jié)點(diǎn) """ btdict = self.returnBTdict() q = [] q.append(btdict['root']) while q: tn = q.pop(0) # 從隊(duì)列中彈出一個(gè)結(jié)點(diǎn)(也是一個(gè)字典) print tn["value"], if tn["L"]!=None: q.append(tn["L"]) if tn["R"]!=None: q.append(tn["R"])
測試打印效果
def test(): bt = BinTree() # btns = [BTNode(v) for v in "+*E*D/CAB"] # 層序輸入 # bt.root = btns[0] # bt.makeBT(btns[0], L=btns[1], R=btns[2]) # bt.makeBT(btns[1], L=btns[3], R=btns[4]) # bt.makeBT(btns[3], L=btns[5], R=btns[6]) # bt.makeBT(btns[5], L=btns[7], R=btns[8]) btns = [BTNode(v) for v in [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]] bt.root = btns[0] bt.makeBT(btns[0], L=btns[1], R=btns[2]) bt.makeBT(btns[1], L=btns[3], R=btns[4]) bt.makeBT(btns[2], L=btns[5], R=btns[6]) bt.makeBT(btns[3], L=btns[7], R=btns[8]) bt.makeBT(btns[4], L=btns[9], R=btns[10]) bt.makeBT(btns[5], L=btns[11], R=btns[12]) bt.makeBT(btns[6], L=btns[13], R=btns[14])
輸出:
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
- Python數(shù)據(jù)結(jié)構(gòu)與算法之字典樹實(shí)現(xiàn)方法示例
- Python數(shù)據(jù)結(jié)構(gòu)與算法之完全樹與最小堆實(shí)例
- python數(shù)據(jù)結(jié)構(gòu)之二叉樹的統(tǒng)計(jì)與轉(zhuǎn)換實(shí)例
- python數(shù)據(jù)結(jié)構(gòu)之二叉樹的遍歷實(shí)例
- python數(shù)據(jù)結(jié)構(gòu)之二叉樹的建立實(shí)例
- python數(shù)據(jù)結(jié)構(gòu)樹和二叉樹簡介
- Python數(shù)據(jù)結(jié)構(gòu)樹與算法分析
相關(guān)文章
APPium+Python編寫真機(jī)移動(dòng)端自動(dòng)化腳本的項(xiàng)目實(shí)踐
本文主要介紹了APPium+Python編寫真機(jī)移動(dòng)端自動(dòng)化腳本的項(xiàng)目實(shí)踐,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-07-07使用Python的web.py框架實(shí)現(xiàn)類似Django的ORM查詢的教程
這篇文章主要介紹了使用Python的web.py框架實(shí)現(xiàn)類似Django的ORM查詢的教程,集成的ORM操作數(shù)據(jù)庫向來是Python最強(qiáng)大的功能之一,本文則探討如何在web.py框架上實(shí)現(xiàn),需要的朋友可以參考下2015-05-05Python的Flask框架與數(shù)據(jù)庫連接的教程
這篇文章主要介紹了Python的Flask框架與數(shù)據(jù)庫連接的教程,是Flask框架學(xué)習(xí)當(dāng)中的基本知識(shí),需要的朋友可以參考下2015-04-04Python3 實(shí)現(xiàn)串口兩進(jìn)程同時(shí)讀寫
今天小編就為大家分享一篇Python3 實(shí)現(xiàn)串口兩進(jìn)程同時(shí)讀寫,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-06-06pygame實(shí)現(xiàn)井字棋之第三步邏輯優(yōu)化
這篇文章主要介紹了pygame實(shí)現(xiàn)井字棋之第三步邏輯優(yōu)化,文中有非常詳細(xì)的代碼示例,對(duì)正在學(xué)習(xí)python的小伙伴們也有非常好的幫助,需要的朋友可以參考下2021-05-05Python實(shí)現(xiàn)接受任意個(gè)數(shù)參數(shù)的函數(shù)方法
下面小編就為大家分享一篇Python實(shí)現(xiàn)接受任意個(gè)數(shù)參數(shù)的函數(shù)方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-04-04