R6-1 邻接矩阵存储图的深度优先遍历

以下是邻接矩阵存储图的深度优先遍历的Python实现：

def DFS(MGraph, visited, v):
    visited[v] = True
    print(v, end=' ')
    for w in range(MGraph.Nv):
        if not visited[w] and MGraph.G[v][w] != 0:
            DFS(MGraph, visited, w)

def DFSTraverse(MGraph):
    visited = [False] * MGraph.Nv
    for v in range(MGraph.Nv):
        if not visited[v]:
            DFS(MGraph, visited, v)

其中，`MGraph`是邻接矩阵存储的图，`visited`是记录每个顶点是否被访问过的数组，`v`是当前访问的顶点。`DFS`函数是深度优先遍历的核心代码，它首先将当前顶点标记为已访问，并输出该顶点的编号。然后遍历该顶点的所有邻接点，如果邻接点未被访问过且与当前顶点有边相连，则递归访问该邻接点。`DFSTraverse`函数是深度优先遍历的入口，它遍历图中的所有连通块，对于每个连通块，从一个未被访问的顶点开始进行深度优先遍历。

相关问题

r6-2 二叉树的遍历

二叉树的遍历方式有三种：前序遍历、中序遍历和后序遍历。下面分别介绍这三种遍历方式。

1. 前序遍历

前序遍历是指从根节点开始，先输出根节点，然后按照左子树、右子树的顺序遍历每一个节点。具体实现方式如下：

def preorder_traversal(root):
    if not root:
        return
    print(root.val)
    preorder_traversal(root.left)
    preorder_traversal(root.right)

2. 中序遍历

中序遍历是指按照左子树、根节点、右子树的顺序遍历每一个节点。具体实现方式如下：

def inorder_traversal(root):
    if not root:
        return
    inorder_traversal(root.left)
    print(root.val)
    inorder_traversal(root.right)

3. 后序遍历

后序遍历是指按照左子树、右子树、根节点的顺序遍历每一个节点。具体实现方式如下：

def postorder_traversal(root):
    if not root:
        return
    postorder_traversal(root.left)
    postorder_traversal(root.right)
    print(root.val)

以上三种遍历方式都可以使用递归或非递归的方式实现。

R6-2 二叉树的遍历

二叉树的遍历是指按照某种顺序访问二叉树中的每个节点。二叉树的遍历方式主要有以下四种：

1. **前序遍历（Pre-order Traversal）**：
- 访问根节点。
- 前序遍历左子树。
- 前序遍历右子树。
- 顺序：根 -> 左 -> 右

2. **中序遍历（In-order Traversal）**：
- 中序遍历左子树。
- 访问根节点。
- 中序遍历右子树。
- 顺序：左 -> 根 -> 右

3. **后序遍历（Post-order Traversal）**：
- 后序遍历左子树。
- 后序遍历右子树。
- 访问根节点。
- 顺序：左 -> 右 -> 根

4. **层序遍历（Level-order Traversal）**：
- 从根节点开始，逐层从上到下、从左到右访问每个节点。

### 前序遍历示例
假设有以下二叉树：

    1
   / \
  2   3
 / \
4   5

前序遍历的结果为：1 -> 2 -> 4 -> 5 -> 3

### 中序遍历示例
中序遍历的结果为：4 -> 2 -> 5 -> 1 -> 3

### 后序遍历示例
后序遍历的结果为：4 -> 5 -> 2 -> 3 -> 1

### 层序遍历示例
层序遍历的结果为：1 -> 2 -> 3 -> 4 -> 5

二叉树的遍历在实际应用中非常广泛，例如表达式树求值、树的复制、树的比较等。