因为一些原因博主已经好几天没更今天补上

将递归之前我们先来看这个中序遍历

如果该结点非空就继续调用程序Inordertraversal(BT->Left)

直到调用到D则调用Inordertraversal(BT->Left)结束

开始执行printf("%d",BT->Data);

输出D

接着执行Inordertraversal(BT->Right)

因为D没有右子树直接返回到B

调用下面两句printf("%d",BT->Data);

Inordertraversal(BT->BT->Right)

后面同理直到调用结束

再看看图的dfs调用

用上图讲解dfs（深度优先搜素）（递归）

首先传入A

将A标记为已访问

接着不断递归

递归到B

将B标记为已访问

因为visited[v]=true;

在dfs前面相当于标记操作在递归操作以前->前序遍历

接着递归

将E标记为已访问

由于E无邻接节点返回到B接着遍历B的邻接结点直到结束

好的铺垫作好我们接着讲八皇后问题中的dfs和回溯

void dfs(int row) {
    if (row > n) {
        ans++;
        if (ans <= 3) {
            for (int i = 1; i <= n; ++i) {
                cout << queen[i] << " ";
            }
            
            cout << endl;
        }
        return;
    }
    
    for (int col = 1; col <= n; ++col) {
        if (isSafe(row, col)) {
            queen[row] = col;
            dfs(row + 1);
            queen[row] = 0; 
        }
    }
}
 

主要代码如上

if（）{

}

段中相当于递归出口

if判断的一定是结束后的下一个状态

由树的递归可以知道要判断该节点是否存在子节点

queen[row] = col;
dfs(row + 1);
queen[row] = 0;

回溯的核心在于每次递归返回都有一次对原状态的恢复

下面讲解一下剪枝，结束一下递归

剪枝算法是一种在搜索算法中常用的优化策略，它的核心思想是在搜索过程中，通过一些判断条件提前排除那些不可能产生最优解或者符合要求解的分支，避免对这些分支进行无意义的搜索，从而减少搜索空间，提高算法的效率。

基本概念

在搜索算法（如深度优先搜索 DFS、广度优先搜索 BFS）中，搜索空间通常可以用一个搜索树来表示。树中的每个节点代表一个可能的状态，从根节点到某个节点的路径表示一个部分解。剪枝算法就像是在这棵搜索树上 “修剪” 掉那些不必要的树枝，让搜索过程更高效。

常见剪枝类型

1. 可行性剪枝

当搜索到某个节点时，如果根据当前状态可以判断出从该节点继续搜索下去无法得到符合要求的解，就可以直接放弃对该节点及其子节点的搜索。

例如，在一个路径规划问题中，要求找到从起点到终点的最短路径，并且路径长度不能超过某个阈值。如果在搜索过程中，当前路径的长度已经超过了这个阈值，那么从这个节点继续搜索下去肯定无法得到符合要求的解，就可以直接剪枝。

2. 最优性剪枝

在求最优解的问题中，如果当前搜索到的部分解已经不可能比已知的最优解更优，就可以停止对该部分解的继续搜索。

比如，在求解一个最小化问题时，已经找到了一个当前最优解为 x，在搜索过程中，某个部分解的代价已经大于 x，那么从这个部分解继续搜索下去得到的解肯定不会比 x 更优，就可以剪枝。

3. 重复性剪枝

在搜索过程中，可能会出现重复的状态。如果已经对某个状态进行过搜索，再次遇到相同的状态时，就不需要再次搜索，直接跳过即可。

例如，在一些组合问题中，可能会出现相同元素的不同排列组合得到相同的结果，这时就可以通过记录已经搜索过的状态来避免重复搜索。

经典例题同样宝宝们自己去洛谷搜题号哇（p1025)

P1025 [NOIP 2001 提高组] 数的划分

 题目描述

将整数 n 分成 k 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。

例如：$n=7$，$k=3$，下面三种分法被认为是相同的。

$1,1,5$;   
$1,5,1$;   
$5,1,1$.

问有多少种不同的分法。

## 输入格式

$n,k$ （$6<n \le 200$，$2  \le k  \le  6$）

## 输出格式

$1$ 个整数，即不同的分法。

## 输入输出样例 #1

### 输入 #1

```
7 3
```

### 输出 #1

```
4
```

## 说明/提示

四种分法为：  
$1,1,5$;  
$1,2,4$;  
$1,3,3$;  
$2,2,3$.

**【题目来源】**

NOIP 2001 提高组第二题

#include<bits/stdc++.h>
using namespace std;
// n 表示要划分的整数
int n;
// k 表示要划分的份数
int k;
// sum 用于记录不同分法的数量
int sum = 0;

// 深度优先搜索函数，i 表示当前划分的数的最小值，k 表示还需要划分的份数，n 表示还剩下多少数需要划分
void dfs(int i, int k, int n) {
    // 当只剩下一份待分，说明已经完成了一种划分方案
    if(k == 1) {
        // 分法数量加 1
        sum++;
        // 结束当前递归调用
        return;
    }

    // 剪枝：从 i 开始枚举当前划分的数，直到 n / k
    for(int j = i; j <= n / k; j++) {
        // 递归调用 dfs 函数，更新当前划分的最小值为 j，剩余要划分的份数为 k - 1，剩余要划分的数为 n - j
        dfs(j, k - 1, n - j);
    }
}

int main() {
    // 从标准输入读取 n 和 k 的值
    cin >> n >> k;
    // 从 1 开始进行深度优先搜索，初始时要划分的数为 n，剩余份数为 k
    dfs(1, k, n);
    // 输出不同分法的数量
    cout << sum;
    return 0;
}

 剪枝条件 j <= n / k 的原理

在递归函数 dfs 中，for 循环用于枚举当前划分的数 j。这里的 j 有两个限制条件： j >= i：这是为了保证划分方案不考虑顺序，因为我们规定划分的数是单调递增的，避免出现重复的划分情况。例如，对于 (1, 2, 4) 和 (2, 1, 4) 这种本质相同的划分，我们只考虑前面的数小于等于后面的数的情况。

j <= n / k：这是核心的剪枝条件。以下从两个方面解释其原理：

1，  避免产生无效划分：假设当前还剩下 n要划分成 k 份，如果 j大于 n / k，那么剩下的 n - j 就无法再划分成 k - 1份非零的数。因为即使剩下的每份都取最小的 1，也无法满足划分要求。例如，要把 7 分成 3 份，在某一步剩下 n = 7 要分成 k = 3 份。若 j 取 3，剩下 7 - 3 = 4 可以分成 2 份非零的数（如 1和 3、2 和 2）；但如果 j 取 4，剩下 7 - 4 = 3，要分成 3 - 1 = 2份非零的数，若一份取 1，另一份就是 2，这样只能算 2 份，无法满足分成 3 份的要求，这种情况就属于无效划分，应该避免。

2，  减少不必要的搜索：通过限制 j 的上限为 n / k，可以避免很多不必要的递归调用。因为超出这个范围的 j所产生的划分方案要么是无效的，要么会导致重复计算，所以提前排除这些情况可以大大减少搜索空间，提高算法效率。 通过这种剪枝操作，代码在处理较大的 n 和 k 时也能保持较好的性能。

常见的几种剪枝及例子

深度优先搜索（DFS）中的剪枝

可行性剪枝

可行性剪枝是指当搜索到某个状态时，如果可以判断从该状态继续搜索下去无法得到符合要求的解，就直接放弃对该状态及其子状态的搜索。

示例问题：在一个二维矩阵中寻找从起点到终点的路径，路径上的元素之和不能超过某个阈值。

#include <iostream>
#include <vector>

using namespace std;

// 矩阵
vector<vector<int>> matrix = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};
// 起点
pair<int, int> start = {0, 0};
// 终点
pair<int, int> endPoint = {2, 2};
// 阈值
int threshold = 15;
// 记录是否找到路径
bool found = false;

// 四个方向
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

void dfs(int x, int y, int currentSum) {
    // 可行性剪枝：如果当前路径和超过阈值，直接返回
    if (currentSum > threshold) {
        return;
    }
    // 如果到达终点，标记找到路径
    if (x == endPoint.first && y == endPoint.second) {
        found = true;
        return;
    }
    for (int i = 0; i < 4; ++i) {
        int newX = x + dx[i];
        int newY = y + dy[i];
        // 判断新位置是否合法
        if (newX >= 0 && newX < matrix.size() && newY >= 0 && newY < matrix[0].size()) {
            dfs(newX, newY, currentSum + matrix[newX][newY]);
        }
    }
}

int main() {
    dfs(start.first, start.second, matrix[start.first][start.second]);
    cout << (found ? "Found" : "Not found") << endl;
    return 0;
}

最优性剪枝

最优性剪枝是在求最优解的问题中，如果当前搜索到的部分解已经不可能比已知的最优解更优，就停止对该部分解的继续搜索。

示例问题：求解 0 - 1 背包问题，在一定的背包容量限制下，从若干个物品中选择一些物品放入背包，使得背包中物品的总价值最大。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 物品的重量列表
vector<int> weights = {2, 3, 4, 5};
// 物品的价值列表
vector<int> values = {3, 4, 5, 6};
// 背包的容量
int capacity = 8;
// 最大价值
int maxValue = 0;

void dfs(int index, int currentWeight, int currentValue) {
    // 最优性剪枝：如果当前价值加上剩余物品的最大价值都不能超过已知最大价值，直接返回
    int remainingValue = 0;
    for (int i = index; i < weights.size(); ++i) {
        remainingValue += values[i];
    }
    if (currentValue + remainingValue <= maxValue) {
        return;
    }
    // 更新最大价值
    maxValue = max(maxValue, currentValue);
    // 遍历每个物品
    for (int i = index; i < weights.size(); ++i) {
        if (currentWeight + weights[i] <= capacity) {
            dfs(i + 1, currentWeight + weights[i], currentValue + values[i]);
        }
    }
}

int main() {
    dfs(0, 0, 0);
    cout << "Max value: " << maxValue << endl;
    return 0;
}

3. 广度优先搜索（BFS）中的重复性剪枝

问题：在一个迷宫中寻找从起点到终点的最短路径。

#include <iostream>
#include <vector>
#include <queue>
#include <set>

using namespace std;

// 迷宫矩阵
vector<vector<int>> maze = {
    {0, 1, 0, 0},
    {0, 0, 0, 1},
    {0, 1, 0, 0},
    {0, 0, 1, 0}
};
// 起点
pair<int, int> startPoint = {0, 0};
// 终点
pair<int, int> endPos = {3, 3};
// 四个方向
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

int bfs() {
    queue<pair<pair<int, int>, int>> q;
    set<pair<int, int>> visited;
    q.push({startPoint, 0});
    visited.insert(startPoint);

    while (!q.empty()) {
        auto [pos, steps] = q.front();
        q.pop();
        int x = pos.first;
        int y = pos.second;
        if (x == endPos.first && y == endPos.second) {
            return steps;
        }
        for (int i = 0; i < 4; ++i) {
            int newX = x + dx[i];
            int newY = y + dy[i];
            // 判断新位置是否合法且未访问过
            if (newX >= 0 && newX < maze.size() && newY >= 0 && newY < maze[0].size() && maze[newX][newY] == 0 && visited.find({newX, newY}) == visited.end()) {
                q.push({{newX, newY}, steps + 1});
                visited.insert({newX, newY});
            }
        }
    }
    return -1;
}

int main() {
    int result = bfs();
    cout << "Shortest path steps: " << result << endl;
    return 0;
}

下篇更新递推