13161216443

您所在位置: 首頁> 學習課程> python培訓班 | Python如何實現深度優先與廣度優先?

python培訓班 | Python如何實現深度優先與廣度優先?

發布百知教育 來源:學習課程 2019-12-06

問:Python如何實現深度優先與廣度優先?

答:上次說過Python新式類和舊式類的區別有一點是說:新式類的MRO算法采用C3算法廣度優先搜索,而舊式類的MRO算法是采用深度優先搜索。今天主要來說兩者的區別是什么,以及用Python代碼來實現這兩種方式的搜索 。


二叉樹深度優先與廣度優先遍歷的區別?


1) 二叉樹的深度優先遍歷的非遞歸的通用做法是采用棧,廣度優先遍歷的非遞歸的通用做法是采用隊列。


2) 深度優先遍歷:對每一個可能的分支路徑深入到不能再深入為止,而且每個結點只能訪問一次。要特別注意的是,二叉樹的深度優先遍歷比較特殊,可以細分為先序遍歷、中序遍歷、后序遍歷。具體說明如下:

先序遍歷:對任一子樹,先訪問根,然后遍歷其左子樹,最后遍歷其右子樹。

中序遍歷:對任一子樹,先遍歷其左子樹,然后訪問根,最后遍歷其右子樹。

后序遍歷:對任一子樹,先遍歷其左子樹,然后遍歷其右子樹,最后訪問根。


廣度優先遍歷:又叫層次遍歷,從上往下對每一層依次訪問,在每一層中,從左往右(也可以從右往左)訪問結點,訪問完一層就進入下一層,直到沒有結點可以訪問為止?!  ?/p>


 3)深度優先搜素算法:不全部保留結點,占用空間少;有回溯操作(即入棧、出棧操作),運行速度慢。而廣度優先搜索算法:保留全部結點,占用空間大;無回溯操作(即無入棧、出棧操作),運行速度快。


用Python來完成二叉樹深度優先與廣度優先遍歷:


python培訓




廣度優先:0, 1, 2, 3, 4, 5, 6, 7, 8, 9


深度優先

先序遍歷(父, 左子, 右子) 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


Python代碼實現如下:


class Node(object):
    """初始化一個節點,需要為節點設置值"""

    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BinaryTree(object):
    """
    創建二叉樹,完成
    - 添加元素
    - 廣度遍歷
    - 深度遍歷(先序遍歷, 中序遍歷, 后序遍歷)
    """


    def __init__(self):
        self.root = None
        pass

    # 添加元素
    def addNode(self, val):
        # 創建隊列結構存儲結點
        nodeStack = [self.root, ]

        # 如果根結點為空
        if self.root == None:
            self.root = Node(val)
            print("添加根節點{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

            # 如果右子節點為空
            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)

    # 廣度遍歷(中序: 先讀父節點,再讀左子節點, 右子節點)
    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)

    # 深度優先(先序遍歷)

    def preorder(self, start_node):

        if start_node == None:
            return

        print(start_node.val)
        self.preorder(start_node.left)
        self.preorder(start_node.right)

    # 深度優先(中序遍歷)
    def inorder(self, start_node):
        if start_node == None:
            return

        self.inorder(start_node.left)
        print(start_node.val)
        self.inorder(start_node.right)

    # 深度優先(后序遍歷)
    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()


如果對于參考答案有不認同的,大家指出和補充,歡迎留言!


python培訓班:http://www.onhairsalon.com/python2019



上一篇:鄭州java培訓班:上個Java培訓學校能找到高薪工作嗎?

下一篇:應屆生去公司找個Java程序員的職位需要什么技能?

相關推薦

www.onhairsalon.com

有位老師想和您聊一聊

關閉

立即申請