树的遍历图的遍历 in Python

Python 实现二叉树的遍历，前序、中序、后序
Python 实现图的遍历，广度优先搜索、深度优先搜索

一些基本定义与思路，你可能需要知道

树的遍历

深度优先搜索

广度优先搜索

二叉树遍历

简单的二叉树结点类

class Node(object):
    def __init__(self, value, left, right):
        self.value = value
        self.left = left
        self.right = right

中序遍历

遍历左子树，访问当前节点，遍历右子树

def mid_travelsal(root):
    if root.left is not None:
        mid_travelsal(root.left)
    # 处理当前节点
    print(root.value)
    if root.right is not None:
        mid_travelsal(root.right)

前序遍历

访问当前节点，遍历左子树，遍历右子树

def pre_travelsal(root):
    # 处理当前节点
    print(root.value)
    if root.left is not None:
        mid_travelsal(root.left)
    if root.right is not None:
        mid_travelsal(root.right)

后序遍历

遍历左子树，遍历右子树，访问当前节点

def post_travelsal(root):
    if root.left is not None:
        mid_travelsal(root.left)
    if root.right is not None:
        mid_travelsal(root.right)
    # 处理当前节点
    print(root.value)

图的遍历

简单的图结点类

class Node(object):
    def __init__(self, value, adjacent):
        self.value = value
        self.visit = False # 是否被遍历的状态
        self.adjacent = adjacent # 临接节点

广度优先搜索 BFS

def bfs(root):
    node_queue = []
    root.visit = True
    print(root.value)
    node_queue.append(root)
    while node_queue:
        r = node_queue.pop(0)
    	for node in r.adjacent:
            if not node.visit:
            	print(node.value)
    			node.visit = True
                node_queue.append(node)

深度优先搜索 DFS

def dfs(root):
    if root is None:
        return
    print(root.value)
    root.visit = True
    for node in root.adjacent:
        if not node.visit:
        	dfs(node)