建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
創(chuàng)新互聯(lián)Python教程：面向對象之深度優(yōu)先和廣度優(yōu)先
面向對象深度優(yōu)先和廣度優(yōu)先是什么？
成都創(chuàng)新互聯(lián)一直秉承“誠信做人，踏實做事”的原則，不欺瞞客戶，是我們最起碼的底線！ 以服務為基礎，以質量求生存，以技術求發(fā)展，成交一個客戶多一個朋友！為您提供網(wǎng)站設計、成都網(wǎng)站制作、成都網(wǎng)頁設計、成都微信小程序、成都網(wǎng)站開發(fā)、成都網(wǎng)站制作、成都軟件開發(fā)、成都app開發(fā)是成都本地專業(yè)的網(wǎng)站建設和網(wǎng)站設計公司，等你一起來見證！
相關推薦：《Python視頻教程》
二叉樹的兩種遍歷是數(shù)據(jù)結構的經(jīng)典考察題目, 廣度遍歷考察隊列結構, 深度遍歷考察遞歸
深度優(yōu)先
先序遍歷(父, 左子, 右子) 0, 1, 3, 7, 8, 4, 9, 2, 5, 6 中序遍歷(左子, 父, 右子) 7, 3, 8, 1, 9, 4, 0, 5, 2, 6 后序遍歷(左子, 右子, 父) 7, 8, 3, 9, 4, 1, 5, 6, 2, 0
"深度優(yōu)先遍歷"考察遞歸, 將子節(jié)點為空作為終止遞歸的條件
相關推薦：《Python視頻教程》
廣度優(yōu)先
"廣度優(yōu)先遍歷"考察隊列的結構, 消除父節(jié)點(出隊列,順便打印), 添加子節(jié)點(進隊列),當隊列內元素個數(shù)為零, 完成遍歷
添加元素
廣度優(yōu)先遍歷
深度優(yōu)先
Python3 實現(xiàn)
class Node(object):
"""初始化一個節(jié)點,需要為節(jié)點設置值"""
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinaryTree(object):
"""
創(chuàng)建二叉樹,完成
- 添加元素
- 廣度遍歷
- 深度遍歷(先序遍歷, 中序遍歷, 后序遍歷)
"""
def __init__(self):
self.root = None
pass
# 添加元素
def addNode(self, val):
# 創(chuàng)建隊列結構存儲結點
nodeStack = [self.root,]
# 如果根結點為空
if self.root == None:
self.root = Node(val)
print("添加根節(jié)點{0}成功!".format(self.root.val))
return
while len(nodeStack) > 0:
# 隊列元素出列
p_node = nodeStack.pop()
# 如果左子結點為空
if p_node.left == None:
p_node.left = Node(val)
print("添加左:{0} ".format(p_node.left.val))
return
# 如果右子節(jié)點為空
if p_node.right == None:
p_node.right = Node(val)
print("添加右:{0} ".format(p_node.right.val))
return
nodeStack.insert(0, p_node.left)
nodeStack.insert(0, p_node.right)
# 廣度遍歷(中序: 先讀父節(jié)點,再讀左子節(jié)點, 右子節(jié)點)
def breadthFirst(self):
nodeStack = [self.root, ];
while len(nodeStack) > 0:
my_node = nodeStack.pop()
print("-->",my_node.val)
if my_node.left is not None:
nodeStack.insert(0, my_node.left)
if my_node.right is not None:
nodeStack.insert(0, my_node.right)
# 深度優(yōu)先(先序遍歷)
def preorder(self, start_node):
if start_node == None:
return
print(start_node.val)
self.preorder(start_node.left)
self.preorder(start_node.right)
# 深度優(yōu)先(中序遍歷)
def inorder(self, start_node):
if start_node == None:
return
self.inorder(start_node.left)
print(start_node.val)
self.inorder(start_node.right)
# 深度優(yōu)先(后序遍歷)
def outorder(self, start_node):
if start_node == None:
return
self.outorder(start_node.left)
self.outorder(start_node.right)
print(start_node.val)
def main():
bt = BinaryTree()
bt.addNode(0)
bt.addNode(1)
bt.addNode(2)
bt.addNode(3)
bt.addNode(4)
bt.addNode(5)
bt.addNode(6)
bt.addNode(7)
bt.addNode(8)
bt.addNode(9)
print("廣度遍歷-->")
bt.breadthFirst()
print("先序遍歷-->")
bt.preorder(bt.root)
print("中序遍歷-->")
bt.inorder(bt.root)
print("后序遍歷-->")
bt.outorder(bt.root)
if __name__ == '__main__':
main() 網(wǎng)頁名稱：創(chuàng)新互聯(lián)Python教程：面向對象之深度優(yōu)先和廣度優(yōu)先
轉載來于：http://m.5511xx.com/article/ccocdgs.html
