温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

Python中面向对象之深度优先和广度优先是什么

发布时间:2020-10-24 14:17:31 来源:亿速云 阅读:287 作者:小新 栏目:编程语言

小编给大家分享一下Python中面向对象之深度优先和广度优先是什么,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!

面向对象深度优先和广度优先是什么?

Python中面向对象之深度优先和广度优先是什么

Python中面向对象之深度优先和广度优先是什么

Python中面向对象之深度优先和广度优先是什么

Python中面向对象之深度优先和广度优先是什么

二叉树的两种遍历是数据结构的经典考察题目, 广度遍历考察队列结构, 深度遍历考察递归

Python中面向对象之深度优先和广度优先是什么

深度优先

先序遍历(父, 左子, 右子) 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中面向对象之深度优先和广度优先是什么

广度优先遍历

Python中面向对象之深度优先和广度优先是什么

深度优先

Python中面向对象之深度优先和广度优先是什么

Python中面向对象之深度优先和广度优先是什么

Python中面向对象之深度优先和广度优先是什么

Python3 实现

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中面向对象之深度优先和广度优先是什么的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI