广度优先和深度优先的特点,深度优先和广度优先的结果是唯一的吗
什么是面向对象的深度优先和广度优先？
相关：《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视频教程》
广度优先
‘广度优先遍历’检查队列的结构，消除父节点(出队列，顺便打印)，添加子节点(入队列)。当队列中的元素数为零时，添加元素的遍历就完成了。
广度优先遍历
深度优先
Python3 实现
classNode(对象):
初始化节点需要为节点设置值
def__init__(self，val):
self.val=val
self.left=无
self.right=无
classBinaryTree(对象):
创建一个二叉树，完成
-添加元素
-广度遍历
-深度遍历(一阶遍历、中阶遍历和二阶遍历)
def__init__(self):
self.root=None
及格
#添加元素
defaddNode(self，val):
#创建队列结构存储节点
nodeStack=[self.root，]
#如果根节点为空
ifself.root==None:
铌
sp;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()
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。