python實(shí)現(xiàn)樹的深度優(yōu)先遍歷與廣度優(yōu)先遍歷詳解
本文實(shí)例講述了python實(shí)現(xiàn)樹的深度優(yōu)先遍歷與廣度優(yōu)先遍歷。分享給大家供大家參考，具體如下：
廣度優(yōu)先(層次遍歷)
從樹的root開始，從上到下從左到右遍歷整個(gè)樹的節(jié)點(diǎn)
數(shù)和二叉樹的區(qū)別就是，二叉樹只有左右兩個(gè)節(jié)點(diǎn)
廣度優(yōu)先 順序：A - B - C - D - E - F - G - H - I
代碼實(shí)現(xiàn)
def breadth_travel(self, root):
"""利用隊(duì)列實(shí)現(xiàn)樹的層次遍歷"""
if root == None:
return
queue = []
queue.append(root)
while queue:
node = queue.pop(0)
print node.elem,
if node.lchild != None:
queue.append(node.lchild)
if node.rchild != None:
queue.append(node.rchild)
深度優(yōu)先
深度優(yōu)先有三種算法：前序遍歷，中序遍歷，后序遍歷
先序遍歷 在先序遍歷中，我們先訪問根節(jié)點(diǎn)，然后遞歸使用先序遍歷訪問左子樹，再遞歸使用先序遍歷訪問右子樹
根節(jié)點(diǎn)->左子樹->右子樹
#實(shí)現(xiàn) 1
def preorder(self, root):
"""遞歸實(shí)現(xiàn)先序遍歷"""
if root == None:
return
print root.elem
self.preorder(root.lchild)
self.preorder(root.rchild)
#實(shí)現(xiàn) 2
def depth_tree(tree_node):
if tree_node is not None:
print (tree_node._data)
if tree_node._left is noe None:
return depth_tree(tree_node._left)
if tree_node._right is not None:
return depth_tree(tree_node._right)
中序遍歷 在中序遍歷中，我們遞歸使用中序遍歷訪問左子樹，然后訪問根節(jié)點(diǎn)，最后再遞歸使用中序遍歷訪問右子樹
左子樹->根節(jié)點(diǎn)->右子樹
def inorder(self, root):
"""遞歸實(shí)現(xiàn)中序遍歷"""
if root == None:
return
self.inorder(root.lchild)
print root.elem
self.inorder(root.rchild)
后序遍歷 在后序遍歷中，我們先遞歸使用后序遍歷訪問左子樹和右子樹，最后訪問根節(jié)點(diǎn)
左子樹->右子樹->根節(jié)點(diǎn)
def postorder(self, root):
"""遞歸實(shí)現(xiàn)后續(xù)遍歷"""
if root == None:
return
self.postorder(root.lchild)
self.postorder(root.rchild)
print root.elem
更多關(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ì)有所幫助。
PyCharm取消波浪線、下劃線和中劃線的實(shí)現(xiàn)
python opencv鼠標(biāo)畫矩形框之cv2.rectangle()函數(shù)
Python爬蟲動(dòng)態(tài)IP代理使用及防止被封的方法
Python采集大學(xué)教務(wù)系統(tǒng)成績(jī)單實(shí)戰(zhàn)示例
pycharm遠(yuǎn)程linux開發(fā)和調(diào)試代碼的方法