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

相关推荐:Python视频教程

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

深度优先

先序遍历(父，左，右)0，1，3，7，8，4，9，5，6
中序遍历(左子，父，右子)7、3、8、1、9、4、0、5、2、6
后序遍历(左子，右子，父)7、8、3、9、4、1、5、6、2

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

相关推荐:Python视频教程

广度优先

"广度优先遍历"检查队列结构，消除父节点(排队，顺便打印)，添加子节点(进入队列)。当队列中的元素数量为零时，完成遍历

添加元素

广度优先遍历

深度优先

Python3 实现

classNode(object):
"""一个节点的初始化需要为节点设置值"""
def__init__(self,val):
self.val=val
self.left=None
self.right=None
classBinaryTree(object):
"""
创造二叉树，完成
-添加元素
-广度遍历
-深度遍历(先序遍历，中序遍历，后序遍历)
"""
def__init__(self):
self.root=None
pass
#添加元素
defaddNode(self,val):
#创建队列结构存储结构
nodeStack=[self.root,]
#若根结点为空
ifself.root==None:
self.root=Node(val)
print("成功添加根节点{0}！".format(self.root.val))
return
whilelen(nodeStack)>0:
#队列元素列出
p_node=nodeStack.pop()
#若左子节点为空
ifp_node.left==None:
p_node.left=Node(val)
print("添加左：{0}".format(p_node.left.val))
return
#若右节点为空
ifp_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)
#广度遍历(中序:先读父节点，再读左节点，右节点)
defbreadthFirst(self):
nodeStack=[self.root,];
whilelen(nodeStack)>0:
my_node=nodeStack.pop()
print("-->",my_node.val)
ifmy_node.leftisnotNone:
nodeStack.insert(0,my_node.left)
ifmy_node.rightisnotNone:
nodeStack.insert(0,my_node.right)
#深度优先(先序遍历)
defpreorder(self,start_node):
ifstart_node==None:
return
print(start_node.val)
self.preorder(start_node.left)
self.preorder(start_node.right)
#深度优先(中序遍历)
definorder(self,start_node):
ifstart_node==None:
return
self.inorder(start_node.left)
print(start_node.val)
self.inorder(start_node.right)
#深度优先(后序遍历)
defoutorder(self,start_node):
ifstart_node==None:
return
self.outorder(start_node.left)
self.outorder(start_node.right)
print(start_node.val)
defmain():
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()