您好,登錄后才能下訂單哦!
這篇文章主要介紹python3怎么實(shí)現(xiàn)二叉樹的遍歷與遞歸算法,文中介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們一定要看完!
Python是一種跨平臺的、具有解釋性、編譯性、互動(dòng)性和面向?qū)ο蟮哪_本語言,其最初的設(shè)計(jì)是用于編寫自動(dòng)化腳本,隨著版本的不斷更新和新功能的添加,常用于用于開發(fā)獨(dú)立的項(xiàng)目和大型項(xiàng)目。
1、二叉樹的三種遍歷方式
二叉樹有三種遍歷方式:先序遍歷,中序遍歷,后續(xù)遍歷 即:先中后指的是訪問根節(jié)點(diǎn)的順序 eg:先序 根左右 中序 左根右 后序 左右根
遍歷總體思路:將樹分成最小的子樹,然后按照順序輸出
1.1 先序遍歷
a 先訪問根節(jié)點(diǎn)
b 訪問左節(jié)點(diǎn)
c 訪問右節(jié)點(diǎn)
a(b ( d ( h ) )( e ( i ) ))( c ( f )( g )) -- abdheicfg
1.2 中序遍歷
a 先訪問左節(jié)點(diǎn)
b 訪問根節(jié)點(diǎn)
c 訪問右節(jié)點(diǎn)
( ( ( h ) d ) b ( ( i ) e ) ) a ( ( f ) c ( g ) ) -- hdbieafcg
1.3后序遍歷
a 先訪問左節(jié)點(diǎn)
b 訪問右節(jié)點(diǎn)
c 訪問根節(jié)點(diǎn)
((hd)(ie)b)(fgc)a -- hdiebfgca
2、python3實(shí)現(xiàn)樹結(jié)構(gòu)
#實(shí)現(xiàn)樹結(jié)構(gòu)的類,樹的節(jié)點(diǎn)有三個(gè)私有屬性 左指針 右指針 自身的值 class Node(): def __init__(self,data=None): self._data = data self._left = None self._right = None def set_data(self,data): self._data = data def get_data(self): return self._data def set_left(self,node): self._left = node def get_left(self): return self._left def set_right(self,node): self._right = node def get_right(self): return self._right if __name__ == '__main__': #實(shí)例化根節(jié)點(diǎn) root_node = Node('a') # root_node.set_data('a') #實(shí)例化左子節(jié)點(diǎn) left_node = Node('b') #實(shí)例化右子節(jié)點(diǎn) right_node = Node('c') #給根節(jié)點(diǎn)的左指針賦值,使其指向左子節(jié)點(diǎn) root_node.set_left(left_node) #給根節(jié)點(diǎn)的右指針賦值,使其指向右子節(jié)點(diǎn) root_node.set_right(right_node) print(root_node.get_data(),root_node.get_left().get_data(),root_node.get_right().get_data())
3、實(shí)現(xiàn)樹的遞歸遍歷(前 中 后 層次遍歷)
下例是樹的遍歷算法,其中對樹的類進(jìn)行了優(yōu)化,
#實(shí)現(xiàn)樹結(jié)構(gòu)的類,樹的節(jié)點(diǎn)有三個(gè)私有屬性 左指針 右指針 自己的值 class Node(): def __init__(self,data =None,left=None,right = None): self._data = data self._left = left self._right = right #先序遍歷 遍歷過程 根左右 def pro_order(tree): if tree == None: return False print(tree._data) pro_order(tree._left) pro_order(tree._right) #后序遍歷 def pos_order(tree): if tree == None: return False # print(tree.get_data()) pos_order(tree._left) pos_order(tree._right) print(tree._data) #中序遍歷 def mid_order(tree): if tree == None: return False # print(tree.get_data()) mid_order(tree._left) print(tree._data) mid_order(tree._right) #層次遍歷 def row_order(tree): # print(tree._data) queue = [] queue.append(tree) while True: if queue==[]: break print(queue[0]._data) first_tree = queue[0] if first_tree._left != None: queue.append(first_tree._left) if first_tree._right != None: queue.append(first_tree._right) queue.remove(first_tree) if __name__ == '__main__': tree = Node('A',Node('B',Node('D'),Node('E')),Node('C',Node('F'),Node('G'))) pro_order(tree) mid_order(tree) pos_order(tree)
4、遞歸算法
上面兩張圖片是從知乎貼過來的;圖1中返回后會(huì)直接返回到上一級的返回,這種想法是不全面的,較合理的返回應(yīng)該是如圖2 在子函數(shù)返回時(shí)應(yīng)返回到調(diào)用子函數(shù)的節(jié)點(diǎn),這樣在執(zhí)行完剩余代碼再返回到上一級
如果是按照圖1返回的話二叉樹的遍歷就不能按照上例來實(shí)現(xiàn)。
以上是“python3怎么實(shí)現(xiàn)二叉樹的遍歷與遞歸算法”這篇文章的所有內(nèi)容,感謝各位的閱讀!希望分享的內(nèi)容對大家有幫助,更多相關(guān)知識,歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。