资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

C++二叉树深度探索：DFS函数详解与应用实例

创作时间:

作者:

@小白创作中心

C++二叉树深度探索：DFS函数详解与应用实例

引用

CSDN

https://blog.csdn.net/m0_59246703/article/details/145765482

本文将详细介绍C++中二叉树的深度优先搜索（DFS）函数，探讨如何自动更新深度、求最大叶子节点深度，并通过实例展示其应用场景。

二叉树与DFS简介

二叉树是一种常见的数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。深度优先搜索（DFS）是一种遍历或搜索树或图的算法，它沿着树的深度遍历节点，尽可能深的搜索树的分支。

DFS函数实现

在C++中，我们可以通过递归或栈来实现DFS。以下是一个递归实现的DFS函数示例：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void dfs(TreeNode* node, int depth) {
    if (node == NULL) return;
    // 处理当前节点
    std::cout << "Node: " << node->val << ", Depth: " << depth << std::endl;
    // 递归遍历左子树
    dfs(node->left, depth + 1);
    // 递归遍历右子树
    dfs(node->right, depth + 1);
}

在这个函数中，depth参数表示当前节点的深度。每次递归调用时，深度自动增加1。

自动更新深度

在DFS函数中，深度的更新是通过递归调用时传递depth + 1来实现的。这种方式确保了每个节点的深度都能正确计算。在 DFS 的递归实现中，depth 的更新规则如下：

进入递归时：每次递归调用时，depth 的值会加 1，表示当前节点的深度比父节点深一层。
退出递归时：当递归返回到上一层时，depth 的值会自动恢复到调用前的状态，因为递归调用栈会保存每一层的 depth 值。这种机制是由递归的特性决定的：每次递归调用都会创建一个新的栈帧，保存当前的状态（包括 depth 的值）。当递归返回时，栈帧会被弹出，恢复到上一层调用时的状态。

求最大叶子节点深度

为了求二叉树的最大叶子节点深度，我们可以在DFS过程中记录最大深度：

int maxDepth = 0;
void dfs(TreeNode* node, int depth) {
    if (node == NULL) return;
    if (node->left == NULL && node->right == NULL) {
        // 叶子节点
        maxDepth = std::max(maxDepth, depth);
    }
    dfs(node->left, depth + 1);
    dfs(node->right, depth + 1);
}

DFS函数的应用

DFS函数在二叉树中有广泛的应用，包括但不限于：

路径搜索：查找从根节点到叶子节点的特定路径。
子树检查：检查一个树是否是另一个树的子树。
序列化与反序列化：将二叉树转换为字符串，或从字符串重建二叉树。

具体应用实例

假设我们有一个二叉树，表示一个家族的家谱。每个节点代表一个人，左子节点和右子节点分别代表其子女。我们可以使用DFS来查找家族中最长的直系血亲链（即最大叶子节点深度）。

#include <iostream>
#include <algorithm>
struct TreeNode {
    std::string name;
    TreeNode* left;
    TreeNode* right;
    TreeNode(std::string n) : name(n), left(NULL), right(NULL) {}
};
int maxDepth = 0;
void dfs(TreeNode* node, int depth) {
    if (node == NULL) return;
    if (node->left == NULL && node->right == NULL) {
        maxDepth = std::max(maxDepth, depth);
    }
    dfs(node->left, depth + 1);
    dfs(node->right, depth + 1);
}
int main() {
    TreeNode* root = new TreeNode("祖父");
    root->left = new TreeNode("父亲");
    root->right = new TreeNode("叔叔");
    root->left->left = new TreeNode("儿子");
    root->left->right = new TreeNode("女儿");
    dfs(root, 1);
    std::cout << "家族中最长的直系血亲链深度为: " << maxDepth << std::endl;
    return 0;
}

在这个例子中，DFS函数帮助我们找到了家族中最长的直系血亲链深度。

DFS经典例题解析

深度优先搜索（DFS）是一种常用的搜索算法，适用于解决排列、组合、棋盘问题等。下面通过两个经典例题来理解DFS的使用方法，并分析其搜索顺序和实现细节。

7.1 AcWing 824 排列数字

题目描述：给定一个整数 ( n )，将数字 ( 1 ~ n ) 排成一排，输出所有可能的排列，按字典序输出。

输入格式：一个整数 ( n )。

输出格式：每行一个排列，数字之间用空格分隔。

数据范围：( 1 ≤ n ≤ 7 )。

解题思路：

搜索顺序：从第一个位置开始，依次枚举每个数字，确保每个数字只使用一次。
使用一个数组path记录当前排列，一个布尔数组str记录数字是否被使用过。
递归终止条件：当排列长度等于 ( n ) 时，输出结果。
回溯时恢复现场，确保下一次搜索的正确性。

代码实现：

#include<iostream>
using namespace std;
const int N = 10;
int path[N]; // 存储当前搜索状态
int n;
bool str[N]; // 判断数字是否被使用过
void dfs(int u) {
    if (u == n) { // 搜索到最后一个位置
        for (int i = 0; i < n; i++) printf("%d ", path[i]); // 输出结果
        puts("");
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!str[i]) { // 如果数字未被使用
            path[u] = i; // 记录当前数字
            str[i] = true; // 标记为已使用
            dfs(u + 1); // 递归到下一个位置
            str[i] = false; // 回溯恢复
        }
    }
}
int main() {
    cin >> n; // 输入n
    dfs(0); // 从第0个位置开始搜索
    return 0;
}

7.2 AcWing 843 n-皇后问题

题目描述：在 ( n × n ) 的国际象棋棋盘上放置 ( n ) 个皇后，使得它们互不攻击（即不在同一行、同一列或同一对角线上）。输出所有可能的摆放方案。

输入格式：一个整数 ( n )。

输出格式：每个方案占 ( n ) 行，每行一个长度为 ( n ) 的字符串，.表示空，Q表示皇后。每个方案输出完成后输出一个空行。

数据范围：( 1 ≤ n ≤ 9 )。

解题思路：

搜索顺序：枚举每一行的皇后放置位置，确保不冲突。
使用三个布尔数组col、ug、aug分别记录列、主对角线、副对角线是否被占用。
递归终止条件：当所有行都放置了皇后时，输出结果。
回溯时恢复现场，确保下一次搜索的正确性。

代码实现：

#include<iostream>
using namespace std;
const int N = 20; // 对角线数量为 2n-1，开两倍空间
char g[N][N]; // 存储棋盘状态
int n;
bool col[N], ug[N], aug[N]; // 列、主对角线、副对角线是否被占用
void dfs(int u) {
    if (u == n) { // 搜索到最后一行
        for (int i = 0; i < n; i++) puts(g[i]); // 输出结果
        puts("");
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!col[i] && !ug[u + i] && !aug[n - u + i]) { // 当前位置合法
            g[u][i] = 'Q'; // 放置皇后
            col[i] = ug[u + i] = aug[n - u + i] = true; // 标记为已占用
            dfs(u + 1); // 递归到下一行
            g[u][i] = '.'; // 回溯恢复
            col[i] = ug[u + i] = aug[n - u + i] = false; // 回溯恢复
        }
    }
}
int main() {
    cin >> n; // 输入n
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            g[i][j] = '.'; // 初始化棋盘
    dfs(0); // 从第0行开始搜索
    return 0;
}