大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
创新互联www.cdcxhl.cn八线动态BGP香港云服务器提供商,新人活动买多久送多久,划算不套路!
创新互联不只是一家网站建设的网络公司;我们对营销、技术、服务都有自己独特见解,公司采取“创意+综合+营销”一体化的方式为您提供更专业的服务!我们经历的每一步也许不一定是最完美的,但每一步都有值得深思的意义。我们珍视每一份信任,关注我们的成都网站制作、网站设计质量和服务品质,在得到用户满意的同时,也能得到同行业的专业认可,能够为行业创新发展助力。未来将继续专注于技术创新,服务升级,满足企业一站式成都全网营销推广需求,让再小的成都品牌网站建设也能产生价值!小编给大家分享一下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
"深度优先遍历"考察递归, 将子节点为空作为终止递归的条件
广度优先
"广度优先遍历"考察队列的结构, 消除父节点(出队列,顺便打印), 添加子节点(进队列),当队列内元素个数为零, 完成遍历
添加元素
广度优先遍历
深度优先
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中面向对象之深度优先和广度优先是什么的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注创新互联-成都网站建设公司行业资讯频道!