数据结构——深度优先遍历

树的深度优先遍历

树的深度优先遍历（Depth-First Traversal）是一种用于访问树的所有节点的算法，它有三种主要的形式：

前序遍历（Preorder Traversal）：先访问根节点，然后递归地访问左子树和右子树。

中序遍历（Inorder Traversal）：先递归地访问左子树，然后访问根节点，最后递归地访问右子树。对于二叉搜索树（BST），中序遍历会按照升序访问节点。

后序遍历（Postorder Traversal）：先递归地访问左子树，然后递归地访问右子树，最后访问根节点。

#include <iostream>
using namespace std;

// 树节点的结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 前序遍历
void preorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << " "; // 先访问根节点
    preorderTraversal(root->left); // 递归遍历左子树
    preorderTraversal(root->right); // 递归遍历右子树
}

// 中序遍历
void inorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    inorderTraversal(root->left); // 递归遍历左子树
    cout << root->val << " "; // 访问根节点
    inorderTraversal(root->right); // 递归遍历右子树
}

// 后序遍历
void postorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    postorderTraversal(root->left); // 递归遍历左子树
    postorderTraversal(root->right); // 递归遍历右子树
    cout << root->val << " "; // 最后访问根节点
}

int main() {
    // 创建一个简单的二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    cout << "Preorder Traversal: ";
    preorderTraversal(root);
    cout << endl;

    cout << "Inorder Traversal: ";
    inorderTraversal(root);
    cout << endl;

    cout << "Postorder Traversal: ";
    postorderTraversal(root);
    cout << endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

练习：二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

输入：root = [3,9,20,null,null,15,7]
输出：3

计算二叉树的最大深度是一个常见的树操作问题。最大深度是从根节点到最远叶子节点的最长路径的长度。

#include <iostream>
using namespace std;

// 树节点的结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int maxDepth(TreeNode* root) {
    if (root == nullptr) {
        return 0; // 空树的深度为0
    }

    // 递归计算左子树和右子树的深度，并取最大值加1
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return max(leftDepth, rightDepth) + 1;
}

int main() {
    // 创建一个简单的二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    int depth = maxDepth(root);
    cout << "Maximum Depth of the Binary Tree: " << depth << endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

练习：二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

输入：root = [3,9,20,null,null,15,7]
输出：2

计算二叉树的最小深度是另一个常见的树操作问题。最小深度是从根节点到最近叶子节点的最短路径的长度。与计算最大深度不同，计算最小深度需要特别处理某些情况，因为只有一个子树为空的节点深度不为零。

#include <iostream>
#include <algorithm>
using namespace std;

// 树节点的结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int minDepth(TreeNode* root) {
    if (root == nullptr) {
        return 0; // 空树的深度为0
    }

    // 如果只有左子树或只有右子树，返回不为空的子树的深度
    if (root->left == nullptr) {
        return minDepth(root->right) + 1;
    }
    if (root->right == nullptr) {
        return minDepth(root->left) + 1;
    }

    // 如果有左右子树，返回左右子树深度的较小值加1
    return min(minDepth(root->left), minDepth(root->right)) + 1;
}

int main() {
    // 创建一个简单的二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    int depth = minDepth(root);
    cout << "Minimum Depth of the Binary Tree: " << depth << endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

图的深度优先遍历

邻接矩阵

#include <iostream>
#include <vector>
using namespace std;

class Graph {
private:
    int numVertices; // 图中节点的数量
    vector<vector<int>> adjacencyMatrix; // 邻接矩阵

    // 深度优先遍历递归函数
    void DFSRecursive(int vertex, vector<bool>& visited) {
        visited[vertex] = true;
        cout << vertex << " ";

        // 遍历与当前节点相邻的节点
        for (int i = 0; i < numVertices; ++i) {
            if (adjacencyMatrix[vertex][i] == 1 && !visited[i]) {
                DFSRecursive(i, visited);
            }
        }
    }

public:
    // 构造函数，初始化图的大小
    Graph(int vertices) : numVertices(vertices) {
        adjacencyMatrix.resize(vertices, vector<int>(vertices, 0));
    }

    // 添加边
    void addEdge(int start, int end) {
        adjacencyMatrix[start][end] = 1;
        adjacencyMatrix[end][start] = 1;
    }

    // 深度优先遍历
    void DFS() {
        vector<bool> visited(numVertices, false);

        cout << "Depth-First Search (DFS): ";
        for (int i = 0; i < numVertices; ++i) {
            if (!visited[i]) {
                DFSRecursive(i, visited);
            }
        }
        cout << endl;
    }
};

int main() {
    Graph graph(5); // 创建一个有5个节点的图

    // 添加边
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(2, 4);

    // 进行深度优先遍历
    graph.DFS();

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

邻接表

#include <iostream>
#include <vector>
#include <list>
using namespace std;

class Graph {
private:
    int numVertices; // 图中节点的数量
    vector<list<int>> adjacencyList; // 邻接表

    // 深度优先遍历递归函数
    void DFSRecursive(int vertex, vector<bool>& visited) {
        visited[vertex] = true;
        cout << vertex << " ";

        // 遍历与当前节点相邻的节点
        for (int neighbor : adjacencyList[vertex]) {
            if (!visited[neighbor]) {
                DFSRecursive(neighbor, visited);
            }
        }
    }

public:
    // 构造函数，初始化图的大小
    Graph(int vertices) : numVertices(vertices) {
        adjacencyList.resize(vertices);
    }

    // 添加边
    void addEdge(int start, int end) {
        adjacencyList[start].push_back(end);
        adjacencyList[end].push_back(start); // 无向图需要添加双向引用
    }

    // 深度优先遍历
    void DFS() {
        vector<bool> visited(numVertices, false);

        cout << "Depth-First Search (DFS): ";
        for (int i = 0; i < numVertices; ++i) {
            if (!visited[i]) {
                DFSRecursive(i, visited);
            }
        }
        cout << endl;
    }
};

int main() {
    Graph graph(5); // 创建一个有5个节点的图

    // 添加边
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(2, 4);

    // 进行深度优先遍历
    graph.DFS();

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

在一个有向图中，如何使用深度优先搜索算法查找从一个节点到另一个节点的所有路径？

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

// 定义有向图的邻接表表示
unordered_map<int, vector<int>> graph;

// 存储所有路径的全局变量
vector<vector<int>> allPaths;

// 深度优先搜索函数
void dfs(int currentNode, int targetNode, vector<int>& currentPath, vector<bool>& visited) {
    // 将当前节点添加到路径中
    currentPath.push_back(currentNode);
    visited[currentNode] = true;

    // 如果当前节点等于目标节点，将当前路径添加到结果列表
    if (currentNode == targetNode) {
        allPaths.push_back(currentPath);
    } else {
        // 继续深度优先搜索邻居节点
        for (int neighbor : graph[currentNode]) {
            if (!visited[neighbor]) {
                dfs(neighbor, targetNode, currentPath, visited);
            }
        }
    }

    // 在递归结束后，将当前节点从路径中移除并标记为未访问
    currentPath.pop_back();
    visited[currentNode] = false;
}

// 查找从起始节点到目标节点的所有路径
vector<vector<int>> findAllPaths(int startNode, int targetNode) {
    vector<int> currentPath;
    vector<bool> visited(graph.size(), false);
    allPaths.clear(); // 清空之前的结果

    dfs(startNode, targetNode, currentPath, visited);

    return allPaths;
}

int main() {
    // 构建有向图的邻接表表示
    graph[0] = {1, 2};
    graph[1] = {3};
    graph[2] = {1};
    graph[3] = {4};
    graph[4] = {};

    int startNode = 0;
    int targetNode = 4;

    vector<vector<int>> paths = findAllPaths(startNode, targetNode);

    // 打印所有路径
    for (const vector<int>& path : paths) {
        for (int node : path) {
            cout << node << " ";
        }
        cout << endl;
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70