特别提示,转行的朋友,不学习数据结构和算法,不刷Leetcode 等面试题库,是找不到程序员工作或者说找不到好的工作。黄哥:黄哥Python:提醒要转行当程序员的朋友,学习要分先后主次
广度优先搜索算法(英语:Breadth-First-Search,缩写为BFS),又译作宽度优先搜索,或横向优先搜索,是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。广度优先搜索的实现一般采用open-closed表。
广度优先搜索算法实现有二种方法。
1、递归,按照层数递归。
2、利用队列来实现。
请大家看代码。
'''
黄哥Python培训 黄哥所写
Python 3 qq:1465376564
'''
class BinaryTree:
'''二叉树类 黄哥所写'''
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def height(root):
if root is None:
return 0
return 1 + max(height(root.left), height(root.right))
def revel_traversal(root, level):
'''按照层来递归'''
if root is None:
return
if level == 1:
print(root.data)
elif level > 1:
revel_traversal(root.left, level - 1)
revel_traversal(root.right, level - 1)
def print_level_order(root):
h = height(root)
for i in range(1, h +1):
revel_traversal(root, i)
def bfs(root):
'''利用队列来实现'''
if root is None:
return
q = [root]
while q:
node = q.pop(0)
print(node.data)
if node.left is not None:
q.append(node.left)
if node.right is not None:
q.append(node.right)
return
if __name__ == '__main__':
root = BinaryTree(8)
node1 = BinaryTree(6)
node2 = BinaryTree(9)
node3 = BinaryTree(5)
node4 = BinaryTree(3)
root.left = node1
root.right = node2
node1.left = node3
node1.right = node4
print_level_order(root)
print("---------------")
bfs(root)黄哥:黄哥Python培训是这样训练学员的