400-616-5551

您所在位置: 首页> 学习课程> python培训班 | Python如何实现深度优先与广度优先?

python培训班 | Python如何实现深度优先与广度优先?

发布百知教育 来源:学习课程 2019-12-06

问:Python如何实现深度优先与广度优先?

答:上次说过Python新式类和旧式类的区别有一点是说:新式类的MRO算法采用C3算法广度优先搜索,而旧式类的MRO算法是采用深度优先搜索。今天主要来说两者的区别是什么,以及用Python代码来实现这两种方式的搜索 。


二叉树深度优先与广度优先遍历的区别?


1) 二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列。


2) 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历、中序遍历、后序遍历。具体说明如下:

先序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树。

中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树。

后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。


广度优先遍历:又叫层次遍历,从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。   


 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.baizhiedu.com/python2019



上一篇:郑州java培训班:上个Java培训学校能找到高薪工作吗?

下一篇:python培训班 | 5个顶级异步Python框架

相关推荐