面向对象之深度优先和广度优先

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

相关推荐：《Python视频教程》

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

深度优先

<pre class="brush:php;toolbar:false">先序遍历(父, 左子, 右子) 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</pre>

"深度优先遍历"考察递归, 将子节点为空作为终止递归的条件

相关推荐：《Python视频教程》

广度优先

<pre class="brush:php;toolbar:false">"广度优先遍历"考察队列的结构, 消除父节点(出队列,顺便打印), 添加子节点(进队列),当队列内元素个数为零, 完成遍历</pre>

添加元素

广度优先遍历

深度优先

Python3 实现

<pre class="brush:php;toolbar:false">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()</pre>

您可能感兴趣的文章：
面向对象之深度优先和广度优先
一文了解Python中的递归
前端优化-Javascript篇(3.标识符查找优化)
google搜索引擎优化之链接策略
Python多重继承中的菱形继承
站长必看:整站优化和单页面优化方法
搜索引擎google排名优化之链接广泛度全攻略
网站策划推广浅谈
0基础如何学php
什么是SEO？SEO怎么做？SEO新人必看