菜缤的世界 CairBin's Blog - DFS
type: channel
link: https://blog.cairbin.top/index.php/tag/DFS/
items: 二叉树及其遍历
items: DFS与N皇后问题

二叉树及其遍历
type: item
date: 2022-03-06T16:12:00+00:00
description: 二叉树及其遍历二叉树概念定义什么是二叉树二叉树特点是每个节点最多只能有两棵子树，且有左右之分的树。注：关于数据结构——树的一些基本概念可以参考《树的概念及基本术语》 - CairBin's Blog二叉树的基本性质关于二叉树的基本性质前面已经写的很详细了，可以回顾文章《二叉树》 - CairBin's Blog二叉树结构体定义结构体定义及其构造函数//链式二叉树结构体定义 typedef struct _BinTree { int data; //存放数据 struct _BinTree* lc; //左儿子 struct _BinTree* rc; //右儿子 //构造函数 _BinTree(int d, struct _BinTree* l = NULL, struct _BinTree* r = NULL) :data(d), lc(l), rc(r) {}; }Node;析构函数//析构函数 void destroyBinTree(Node* node) { //如果不存在该节点说明已经到该路径底部,则返回 if (node == NULL) return; //如果没到达该路径尽头则删除路上节点并继续向下走 //保存指向子节点的指针 Node* pl = node->lc; Node* pr = node->rc; delete node; //删除当前节点 node = NULL; //指针置为空，防止野指针 //递归,向下走 destroyBinTree(pl); destroyBinTree(pr); }创建二叉树并写入数据//创建二叉树结构并写入数据 //代码参考https://blog.csdn.net/u013575812/article/details/50129435 void buildBinTree(Node** node) { int data; cin >> data; if (data == -1) *node = NULL; else { *node = (Node*)malloc(sizeof(Node)); (*node)->data = data; buildBinTree(&(*node)->lc); buildBinTree(&(*node)->rc); } }二叉树的遍历宽度优先遍历（BFS）层序遍历图解分析二叉树宽度优先遍历就是要一层一层去遍历，故对于二叉树又叫层序遍历。以上图举例，BFS遍历顺序为EBCADFICH注：我们用队列实现搜索过程，关于队列的知识可以看文章《队列》 - CairBin's Blog此处为了方便，就不手动写队列(queue)了，直接使用C++ STL模板里的Queue代码下面给出代码：//BFS、层序遍历 void levelOrder(Node* node, queue<Node*>& que) { if (!node) return; Node* p = node; que.push(p); while (!que.empty()) { p = que.front(); //p设为队列头部元素 que.pop(); //队列尾部元素出队 cout << p->data << endl; if (p->lc) que.push(p->lc); if (p->rc) que.push(p->rc); } }深度优先遍历(DFS)按深度搜索的顺序访问二叉树，对根（父）节点、左儿子、右儿子进行组合，有三种访问顺序先序遍历中序遍历后序遍历这些遍历组合有如下性质中序+先序——可确定该树中序+后序——可确定该树先序+后续，且不知道中序——不可确定该树这些遍历又分别有两种方法：递归方法非递归方法对于非递归方法需要用到数据结构——栈（stack），关于栈的知识可以参考文章《栈的概念及性质》 - CairBin's Blog《顺序栈的操作》 - CairBin's Blog《链栈的操作》 - CairBin's Blog这里同样用STL模板里的Stack先序遍历图解分析我们依旧用该图先序遍历顺序：父节点、左儿子、右儿子本图访问顺序为：EBADCGFIH代码递归方法//先序遍历，递归 void preOrder_A(Node* node) { if (node == NULL) return; cout << node->data << endl; preOrder_A(node->lc); preOrder_A(node->rc); }非递归方法//先序遍历，非递归 void preOrder_B(Node* node, stack<Node*> &st) { if (!node) return; Node* p = node; while (p || !st.em…

DFS与N皇后问题
type: item
date: 2022-03-06T06:12:00+00:00
description: DFS与N皇后问题DFS什么是DFSDFS是指深度优先遍历也叫深度优先搜索。它是一种用来遍历或搜索树和图数据结构的算法注：关于树的一些知识可以去看《树的概念及基本术语》这篇文章它会不断地沿着节点的深度方向（该深度方向为其邻接点的方向）进行遍历DFS如何实现DFS主要步骤有以下几步访问并从某节点向邻接点出发，访问路径向深处走若走到最深处还有节点没访问，则再回到该层访问该节点（回溯）依次重复上述步骤，直至所有路径都被访问（递归）DFS时空复杂度空间复杂度DFS算法实际上是一个递归算法，需要借助一个递归工作栈故空间复杂度：O(n)时间复杂度时间复杂度：不确定为什么不确定？因为遍历图的过程实质上是对每个顶点找查其所有邻接点的过程，其耗费时间取决于所采用结构下面给出常用的几种数据结构DFS时的时间复杂度（注：n是图中结点的个数，e是图中边的个数。）邻接表 O(e+n)邻接矩阵 O(n^2)N皇后问题N皇后问题（HDU2553）HDU 2553 N皇后问题 在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。 你的任务是，对于给定的N，求出有多少种合法的放置方法。 输入：共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。 输出：共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。 输入样例： 1 8 5 0 输出样例： 1 92 10 经典DFS带来的问题而经典的DFS，基本是将所有子节点全部扩展开，再选取最新的节点进行扩展。但是对于N皇后来说，我们如果一一枚举，则有N的N次方种情况.即使N=10，则有10^10种情况，我们还要在这些情况中进行筛选，这无疑需要巨大的计算故：我们需要对DFS进行优化回溯与减枝我们可以让程序在某节点由某些条件就可以判断再进行继续展开并不符合要求，然后立即返回，达到回溯和减少树的枝干的生成（减枝）的目的，从而进行优化。下面给出N=4时减枝的树状图解问题分析关键问题关键问题：在扩展节点时如何去掉不符合条件的节点？设左上角是(0,0)，已经放好皇后是(i,j)，不同行、列、斜线的新皇后是(r,c)，则：横向不同行 i != r纵向不同列 j != c斜对角：从(i,j)向斜对角走a步，新坐标(r,c)有4种情况 (i-a,j-a) (i+a,j-a) (i-a,j+a) (i+a,j+a)，即|i-r| = |j-c|。也就是说不再斜线上满足 |i-r| != |j-c|其他问题由于给出N<=10，所以可以用打表的方式，将每种n取值对应的结果放到数组ans[n]中对于数组ans[]由于大小最方便设为11，n在0--10中取值一共11种情况。尽管我们可以忽略0定义成大小为10的数组（将n=1结果存放在ans[0]以此类推），但我们在取出数据时还要进行减法运算并不方便。对于在对特定的n取值分析时可用个tot变量来记录到达最深处情况的个数，由于循环是从0开始，我们只需要让r=n时tot自增1来记录并回溯数组col[r] = c，表示皇后放在第r行c列，我们可以用col[i] 来依次获得前几行皇后位置信息，故对于本题col[]数组定义最大为10就行题解代码#include <iostream> using namespace std; //tot记录每次n取特定值能放置n皇后情况的个数，每当n改变时tot重置为0 int n, tot = 0; //表示皇后存放位置 col[r] = c 表示第r行的皇后在第c列 int col[10]; //r为行,c为列 //check()用于检查新放置的皇后（r,c）是否和已经存放好的皇后冲突 //冲突返回false，不冲突返回true bool check(int r, int c) { for (int i = 0; i < r; i++) if (col[i] == c || (abs(col[i] - c) == abs(i - r))) //绝对值判断是否在同一斜线上 return false; //冲突返回false return true; //不冲突返回true } //r为检索的行 //对每行检索并放置皇后 void DFS(int r) { //若达到最底行（层）则新增1种情况，并返回（回溯） if (r == n) { tot++; return; } //对第r行（层）的每一列进行检索，若能放置则进入下一行（层）再从r+1行第0列向后检索放置依次类推 //若不能放置则本层次结束，递归然后回溯出去再改变上一层的列数，从该列再进行展开 for(int c=0;c<n;c++) if (check(r, c)) //检查若放在该层该列是否与之前…